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

вания - дизъюнкции и для п- элементных областей интерпретации имеют место соотношения (2.7) и (2.8): VxP(x) равносильно P(aj)&P(a2)&...&P (arJ, ЗхР(х) равносильно P(ai) vP(a2) v... vP(arJ. Очевидно, высказывания равносильны тогда и только тогда, когда равно­ сильны отрицания этих высказываний, поэтому первое из этих соотношений эквивалентно следуюш,ему: —1 VxP(x) —\(P(ai)&P(a2)&...&P(an))—P(ai) v —P(a2) v.. v^P(an). Правая часть полученного соотношения есть не что иное, как запись вы­ сказывания Зс—Р(х). Таким образом, для п- элементных областей интерпрета­ ции имеем: —i\/xP(x)~3c—P(x). (2.9) Аналогично получим: -пЗхР(х) —\(P(ai)vP(a2)v... vP(a „)) —P(aij& —P(a2j&...&—P(a„j, следовательно, для и-элементных областей интерпретации имеет место: -пЗсР(х)~\/х—Р(х). (2.10) Соотношения (2.9) и (2.10) показывают, что при перенесении отрицания через кванторы последние меняются на двойственные. Покажем, что эти прави­ ла имеют место для указанных формул, но уже без ограничения конечности об­ ластей интерпретации. Рассмотрим формулу -nVxPfx). Возьмем произвольную (но фиксирован­ ную) интерпретацию. В каждой интерпретации эта формула означает некоторое высказывание (так как не имеет свободных переменных). Пусть высказывание —i \/хР(х)штшто. Тогда высказывание VxP(x)- лож­ но, следовательно, суш,ествует значение переменной х, для которого Р(х) лож­ но. Обозначим одно из таких значений через Ь. Итак, 5W и Рф) - ложно. В та­ ком случае —i Рф ) истинно, т.е. суш,ествует такое х (равное Ь), что —Р(х)штш1- но, поэтому Зх—Р(х)штшшо. Обратно, пусть теперь высказывание Зх—Р(х) истинно. Тогда по опреде­ лению квантора суш,ествования найдется такое значение переменной х, что —l P ^^ истинно. Обозначим одно из таких значений через Ь. Итак, be !М и —Рф) истинно. Следовательно, Р(Ь) ложно. По тогда по определению квантора обш,- ности получим, что VxP(x)=JI, а —i истинно. В результате доказали, что в каждой интерпретации —i VxP(x) истинно тогда и только тогда, когда истинно Зх—Р(хХ поэтому: —1 VxP(x) ~ Зх—Р(х). 41