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

Аналогичным образом можно установить: -пЗхР(х)~ Vx —J^(xJ. Далее рассмотрим формулу —i VxA (х,у) с одной двуместной предикатной буквой А . Возьмем для этой формулы произвольную (но фиксированную) ин­ терпретацию. В выбранной интерпретации возьмем произвольное значение свободной переменной}^, скажем, у=с (се 9А). Выражение —i VxA представ­ ляет собой отрицание результата навешивания квантора общности на одноме- 2 2 стный предикат^ (х,с) и по доказанному истинностные значения —i VxA (х,с)и Зс—^А совпадают, следовательно: -nVxA^(x,yJ ~ 3c —iA^(x,y). (2.11) Ясно, что аналогично соотношению (2.11) можно доказать следуюш,ие равносильности: I \75CiAi( (хj,X2, ••• ,Хц) -ЗС/ Ajc (хj,X2, •••,Хц), ^3XiAj^ (хj,X2, •••,Хц) 1>^2>•••>^nj• Можно доказать, что и для произвольной формулы А имеют место: ^V xA~ 3 c ^ , (2.12) ^ЗсА ~ V x ^ . (2.13) Если отрицание стоит перед несколькими кванторами, то, используя (2.12) и (2.13), отрицание можно переносить последовательно через каждый из кванторов, изменяя их на двойственные. В результате доказана следующая теорема. Теорема 2.4. Отрицание формулы, начинающейся с кванторов, равно­ сильно формуле, полученной заменой каждого квантора на двойственный и перенесением знака отрицания за кванторы. Высказывания (2.12) и (2.13) являются аналогами законов де Моргана. Используя их, легко выразить один из кванторов через другой. Для этого при­ меним операцию отрицания к левым и правым частям соотношений (2.12) и (2.13). Получим соответственно: VxA ~ ^Зс^, (2.14) 3 c A ~ ^ V x ^ . (2.15) Равносильности (2.14) и (2.15) показывают, что при определении формул логики предикатов можно было ввести только один из кванторов. Например, можно считать по определению, что для произвольной формулы А выражение ( VxA) есть формула, а выражение ЗсА уже является обозначением для формулы h(Vx(-vi))). 42