Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Следовательно, формула (2.19) не истинна в приведенной интерпретации, т.е. не является логически общезначимой. Теорема доказана. Заметим, что в частном случае формула (2.19) может оказаться и логиче­ ски общезначимой, например, когда А является замкнутой формулой. В этом случае, как известно (см. § 4), формула/! равносильна формуле QiQ2...QrA, где Qi,Q2, -,Qn любая совокупность кванторов. Поэтому формула (2.19) будет логи­ чески общезначимой. Однако подчеркнем еще раз, что для произвольной формулы перестановка разноименных кванторов не всегда приводит к равносильным формулам. § 8. Правила переименования связанных неременных Рассмотрим формулы \/хА(х) и \/уА(у). Очевидно, что в каждой интерпре­ тации из истинности первой следует истинность второй, и наоборот, поэтому эти формулы равносильны: \/хА(х) ~ \/уА(у). Таким образом, переименование переменной хна у в кванторе и в области действия этого квантора привело к формуле, равносильной исходной. В математическом анализе имеется аналогичное правило. Например, за­ мена переменной в подинтегральном выражении определенного интеграла не меняет его величины: 1 1 j cos X dx= \ cos у dy. О О Точно так же в сумме индекс суммирования можно переименовать: т , да , , S S х^/к\ п=1 к=1 В последнем примере переименовывается п на к, но нельзя переименовывать т, ибо это свободная переменная. В формуле VxA(x) можно заменить переменную х на у. Ясно, что если х заменить любой другой переменной, то полученная формула будет равносильна исходной. Можно показать, что и в произвольной формуле А переименование связанных переменных на другие (отличные от всех переменных формулы А) приводит к формуле, равносильной исходной. Имея в виду дальнейшие прило­ жения, будем придерживаться следующего правила переименования связанных переменных. Пусть А - произвольная формула логики предикатов. Формулу Ао полу­ чим из А заменой связанных переменных другими переменными, отличными от всех переменных формулы А, причем заменяемая переменная в формуле А должна меняться одинаковым образом всюду в области действия квантора, свя­ зывающего данную переменную и в самом кванторе. Тогда равносильна/!. При переименовании связанных переменных мы не обязаны переимено­ вывать их всюду, где они входят в формулу А, а лишь только переменную вы- 44