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

Возможны два вида задач, решаемых с использованием исчисления предикатов:

1. Проверить заключение А, В С.

Схема: (А Ù В) ® С путем тождественных преобразований привести к «истине», т.е.

(А Ù В) ® С = … = (Р Ú ù Р) Ú (Р Ú «истина»).

2. Дана совокупность посылок, а надо вывести заключение, используя метод резолюции:

А, B, C, D, …,?

Пример: 1 посылка: «Всякая футбольная команда, которая может победить «Десну» Чернигов, является командой высшей лиги».

2 посылка: «Ни одна команда высшей лиги не может победить «Десну» Чернигов».

Проверить заключение: ««Десна» Чернигов - непобедима».

Вводим предметную переменную и кванторные выражения:

х – футбольная команда,

П (х) – команда, которая может победить «Десну» Чернигов.

В (х) – команда высшей лиги.

Записываем посылки и заключение через кванторные выражения:

" х (П (х) ® В (х)), " х (В (х) ® ù П (х)) $ х П (х).

Решение:

(" х (П (х) ® В (х)) Ù " х (В (х) ® ù П (х))) ® ù $ х П (х) =

= " х ((П (х) ® В (х)) Ù (В (х) ® ù П (х))) ® ù $ х П (х) =

= ù (" х ((ù П (х) Ú В (х)) Ù (ù В (х) Ú ù П (х)))) Ú ù $ х П (х) =

= ù (" х (ù П (х) Ù (В (х) Ú ù В (х)))) Ú ù $ х П (х) =

«истина»

= ù " х ù П (х) Ú ù $ х П (х) = ù (" х ù П (х) Ù $ х П (х)) =

= ù (ù $ х П (х) Ù $ х П (х)) = ù «ложь» = «истина».

«ложь»

Заключение верно: «Десна» Чернигов – непобедима.

Пример: Вывести заключение методом резолюции исчисления предикатов из следующих посылок:

1. Все выпускники Итона в этом колледже играют в крикет.

2. Никто, кроме преподавателей, не обедает за верхним столом.

3. Ни один из тех., кто играет в крикет, не умеет грести.

4. Все мои друзья в этом колледже – выпускники Итона.

5. Все преподаватели – прекрасные гребцы.

Решение:

Введем предметную переменную и кванторные выражения:

х – люди этого колледжа.

К (х) – играющие в крикет,

О (х) – обедающие за верхним столом,

И (х) – выпускники Итона,

Д (х) – мои друзья,

Г (х) – гребцы,

П (х) – преподаватели.

Тогда посылки с помощью кванторных выражений запишутся следующим образом:

1. Все выпускники Итона в этом колледже играют в крикет.

"(И (х) ® К (х)).

2. Никто, кроме преподавателей, не обедает за верхним столом.

"(ù П (х) ® ù О (х)).

3. Ни один из тех., кто играет в крикет, не умеет грести.

"(К (х) ® ù Г (х)).

4. Все мои друзья в этом колледже – выпускники Итона.

"(Д (х) ® И (х)).

5. Все преподаватели – прекрасные гребцы.

"(П (х) ® Г (х)).

Избавляемся от кванторов общности и переходим от импликации к дизъюнкции, применяем метод резолюции:

ù И (х)Ú К (х) ù И (х)Úù Г (х) ù И (х)Úù П (х) ù И (х)Ú ù О (х) ù Д (х)Ú ù О (х)

П (х) Ú ù О (х)

ù К (х) Ú ù Г (х)

ù П (х) Ú Г (х)

ù Д (х) Ú И (х)

Получили заключение ù Д (х) Ú ù О (х) = Д (х) ® ù О (х), т.е. мои друзья не обедают за верхним столом.

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