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

Пусть высказывание 1\/л:Р(х) истинно. Тогда высказывание VxPQc)- ложно, следовательно, существует значение переменной х, для которого Р ( х ) ложно. Обозначим одно из таких значений через Ь. Итак, b e М и Р ф ) - ложно. В таком случае 1 Р(Ь) истинно, т.е. сущест­ вует такое X (равное Ь), что 1 Р ( х ) истинно, поэтому Эх]Р ( х ) истинно. Обратно, пусть теперь высказывание 3x1 Р ( х ) истинно. Тогда по определению квантора существования найдется такое значение пере­ менной X, что 1 Р { х ) истинно. Обозначим одно из таких значений через Ь. Итак, b e М я 1 Р(Ь) истинно. Следовательно Р(Ь) ложно. Но тогда, по определению квантора общности, \ / х Р ( х ) = Л , а lVxP(x) истинно. В результате мы доказали, что в каждой интерпретации ' ] \ / х Р ( х ) истинно тогда и только тогда, когда истинно Зл'1 Р ( х ) , поэтому: У х Р ( х ) ~ З х ' ] Р ( х ) . Аналогичным образом можно установить: 1 ЗхР(х)~V x lР{х). Далее рассмотрим формулу ' ] \ / х А ^ ( х , у ) с одной двуместной пре­ дикатной буквой А^. Возьмем для этой формулы произвольную (но фиксированную) интерпретацию. В выбранной интерпретации используем произвольное значение свободной переменной у , скажем, у=с (се М). Выражение '\\/Х А \Х,С) представляет собой отрицание результата навешивания квантора общности на одноместный предикат А^{х,с) и по доказанному истинностные значения ']VxA^(x,c) и Зх1л^(х,с) совпадают, следовательно; '\\1хЛ\х,у) ~ Зx^Л\x,y). (2.11) Ясно, что аналогично соотношению (2,11) можно доказать сле­ дующие равносильности; lVx4i"(Xi,X2,...,JC „) ~ Зх'^Ак{Хх,Х2,...уХ„), ]3XiAk"(XlPC2,...,X „) ~VxPiAk"(Xi,X2,...^„). Можно доказать, что и для произвольной формулы/4 имеют место: 1Ух^'"ЭХ1Л (2.12) 65