Удаление квантора общности

Система аксиом в исчислении предикатов

Вынесение констант

Пронесение кванторов

Отрицание формул с кванторами

Переименование связанных переменных

" х Р (х) = " y Р (y), $ х Р (х) = $ y Р (y).

" х Р (х) = ù $ х ù Р (х), $ х Р (х) = ù " х ù Р (х).

Так, в частности, первое обозначает, что «для всех х существует Р (х) истина это то же, что не существует ни одного х, для которого Р (х) ложь».

Примечание: данные преобразования говорят о том, что один из кванторов избыточен, т.е. один из них всегда можно выразить через другой.

Пронесение квантора общности через конъюнкцию

" х А (х) Ù " х В (х) = " х (А (х) Ù В (х)).

Это следствие того, что квантор общности является обобщенным выражением конъюнкции:

" х А (х) = А (х₁) Ù А (х₂) Ù … Ù А (х_n).

Пронесение квантора существования через дизъюнкцию

$ х А (х) Ú $ х В (х) = $ х (А (х) Ú В (х)).

Это следствие того, что квантор существования является обобщенным выражением дизъюнкции:

$ х А (х) = А (х₁) Ú А (х₂) Ú … Ú А (х_n).

Перестановка одноименных кванторов

" х " y P (х, y) = " y " х P (х, y) = " y, х P (х, y).

" х (Е Ù А (х)) = Е Ù" х А (х),

$ х (Е Ú А (х)) = Е Ú $ х А (х). Ä

Пример: докажем тождество Ä.

1. Пусть Е = «истина».

Тогда Е Ú $ х А (х) = «истина».

Е Ú А (х) = «истина» при любом х Þ $ х (Е Ú А (х)) = «истина».

2. Пусть Е = «ложь».

Тогда истинность левой части будет полностью зависеть от А (х), т.е

Е можно убрать.

$ х (Е Ú А (х)) = «истина» Þ $ х А (х) = «истина» Þ Е Ú $ х А (х)

= «истина».

Исчисление предикатов включает в себя все аксиомы исчисления высказываний и дополняется двумя аксиомами для кванторов.

" х А (х) ® А (y),

х, y Î M.

Т.е., если предикат А (х) истинен для всех х, то он истинен и для конкретного y.

Доказательство: Нужно доказать, что выражение вида

" х А (х) ® А (y) (1) является тавтологией.

Допустим, что " х А (х) ® А (y) = «ложь». Это возможно только, если:

" х А (х) = «истина», (2)

А y = «ложь». (3)

Но, если истинно (2), то для всех y из М должно выполняться А (y) =

= «истина», а мы получили (3), чего не может быть. Т.е. А (y) ¹ «ложь». А значит ложно и (1).

Следствие: В ® А (х) Þ В ® " х А (х).

Дата добавления: 2014-01-06