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

ЛЗхЛ~\/ХЛА. (2.13) Если отрицание стоит перед несколькими кванторами, то, ис­ пользуя (2.12) и (2.13), отрицание можно переносить последовательно через каждый из кванторов, изменяя его на двойственный. В результате доказана следующая теорема. Теорема 2.4. Отрицание формулы, начинающейся с кванто-1 ров, равносильно формуле, полученной заменой каждого квантора на] двойственный и перенесением знака отрицания за кванторы. Высказывания (2.12) и (2.13) являются аналогами законов де Моргана. Используя их, легко выразить один из кванторов через другой. Для этого применим операцию отрицания к левым и правым частям соотношений (2.12) и (2.13). Получим соответственно; УхЛ~1Эд:1д (2.14) 3x^~1Vx1/4. (2.15) Равносильности (2.14) и (2.15) показывают, что при опреде.11е- нии формул логики предикатов можно было ввести только один из кванторов. Например, можно считать по определению, что для произ­ вольной формулы А выражение (\/хЛ) есть формула, а выражение '^осА уже является обозначением для формулы (l(Vx(l Л))). Кто хочет обрести счастье ти мудрость, тот должен искать перемен. Конфуций § 8. Правила перестановки кванторов Пусть А - произвольная формула логики предикатов. Рассмот­ рим для А произвольную, но фиксированную интерпретацию. Сразу 66