В) Алиса нравится всем, кроме жены Стивена. Алисе не нравится никто, кроме ее мужа. Никто не может быть женат сам на себе. Значит, Стивену нравится его жена

Рассмотрим теперь пример доказательства. Пусть нам нужно доказать теорему $x(P(x) & "yQ(x,y)) É Ø$y"x(Q(x,y) É ØP(x))

+ $x(P(x) & "yQ(x,y))

+ $y"x(Q(x,y) É ØP(x))

P(x) & "yQ(x,y)) (1, $и) х абс. огр.

"x(Q(x,y) É ØP(x)) (2, $и) y абс. огр.

Q(x,y) É ØP(x) (4, "и)

"yQ(x,y)) (3, &и)

Q(x,y) (6, "и)

P(x) (3, &и)

ØP(x) (5,7 Éи)

Ø$y"x(Q(x,y) É ØP(x))

$x(P(x) & "yQ(x,y)) É Ø$y"x(Q(x,y) É ØP(x)) (10, Éв)

В этом доказательстве ни одна переменная не была абсолютно ограничена дважды, ни одна переменная не ограничивает сама себя. Переменные х и у, абсолютно ограниченные в процессе вывода, не встречаются свободно ни в неисключенных посылках (которых нет), ни в заключении, значит доказательство можно считать завершенным. Теорема доказана.

Упражнение 5. При помощи исчисления предикатов докажите следующие теоремы:

а) "x(P(x) É Q(x)) É ("xP(x) É "xQ(x))

б) $x"y(Q(y,x) É ØP(y)) É "y(P(y) É $xØQ(y,x))

в) "х$y(P(x,y) É ØQ(x)) É $y($xQ(x) É ØP(x,y))

Все эвристики, которые были сформулированы для исчисления высказываний, сохраняют свою силу и для исчисления предикатов. Но к ним добавляются еще две, связанные с использованием кванторов:

Эвристика № 9. Если целью является формула с квантором – "αА или $αА, – то можно выбирать дополнительные посылки, не обращая внимания на кванторы, а исходя только из структуры подкванторного выражения А (кванторы потом всегда можно ввести).

Эвристика № 10. Если при осуществлении вывода на каком-то шаге необходимо применить несколько различных кванторных правил, то сначала по возможности следует использовать те правила, которые не требуют ограничения переменных (а именно, ("и) и ($в)).

Дата добавления: 2015-06-30; просмотров: 108; Нарушение авторских прав

Мы поможем в написании ваших работ!