Математическая логика и теория алгоритмов

1 1 J cosxdx- J cosydy. 0 0 Точно также в сумме индекс суммирования можно переименовать: VI Т .хУп'-f^ х'/1Г. «=1 к=1 В последнем примере переименовывается п на к, но нельзя пе­ реименовывать т, ибо это свободная переменная. В формуле VxA(x) можно заменить переменную х Haj^. Ясно, что если X заменить другой переменной, то полученная формула будет равносильна исходной. Можно показать, что и в произвольной формуле переименование (замена) связанных переменных на другие приводит к формуле равносильной исходной. Имея в виду даль­ нейшие приложения, будем придерживаться следующего правила переименования связанных переменных. Пусть А - произвольная формула логики предикатов. Формулу Ло получим из А заменой связанных переменных другими переменны­ ми, отличными от всех переменных формулы А, причем заменяемая переменная в формуле ^4 должна меняться одинаковым образом всюду в области действия квантора, связывающего данную переменную и в самом кванторе. Тогда^^о равносильна^. При переименовании связанных переменных мы не обязаны пе­ реименовывать их всюду, где они входят в формулу А, а лишь только переменную выбранного нами квантора и в области действия этого квантора. Это значит, что одинаковые переменные, для которых свя­ зывающие их кванторы имеют различные области действия, могут переименовываться разным образом или одна из них может переименовываться, а другая нет, , Рассмотрим действие приведенного правила на примерах. Пусть имеем формулу \/л:Л(л:)=^Эх5(х)=>С(л). (2.21) Переименовав связанную переменную х ту, в первой посылке получим формулу, равносильную исходной; 69