Задача №1. Из данной совокупности секвенций выбрать доказуемые, построить их доказательства, для недоказуемых показать их недоказуемость с помощью: а) алгоритма Квайна

Из данной совокупности секвенций выбрать доказуемые, построить их доказательства, для недоказуемых показать их недоказуемость с помощью: а) алгоритма Квайна, б) алгоритма редукции, в)метода резолюций. Среди этих доказательств недоказуемости выбрать оптимально в каждом конкретном случае.

a) ├ x Ú (Ø x ® x)

b) x Ú Ø y├ Ø x ® Ø y

c) x Ù y Ù z├ (x Ú y) ® (y Ú z)

d) x Ù Ø x├ y ® Ø y.

Решение:

1. ├ x Ú (Ø x ® x) – доказуема (исходя из таблицы истинности)

Доказательство:

├ x – тождество истинно

├ x Ú (xÚ x)

├ x Ú (Ø x ® x)

1. x Ú Ø y├ Ø x ® Ø y – доказуема (исходя из таблицы истинности)

Доказательство:

x Ú Ø y├ x Ú Ø y – тождество истинно

x Ú Ø y├ Ø x ® Ø y

1. x Ù y Ù z├ (x Ú y) ® (y Ú z) – доказуема (исходя из таблицы истинности)

Доказательство:

y├ y 12 – тождество истинно

y, xÚ y├ y 12

y, z, xÚ y├ y 12

x, y, z, xÚ y├ y 4

x, y, z, xÚ y├ yÚ z 7

x Ù y Ù z├ (x Ú y) ® (y Ú z)

1. x Ù Ø x├ y ® Ø y– доказуема (исходя из таблицы истинности)

Доказательство:

├ Ø y – тождество истинно

├ Ø yÚ Ø y

├ y®Ø y

x Ù Ø x├ y ® Ø y

Задача №2.

Найти формулу исчисления предикатов истинную на алгебраической системе А=< R; ·> и ложную на системе B=< Q; ·>.

Решение:

Q – множество рациональных чисел.

R – множество действительных чисел.

" xÎ R($yÎ R(x=y*y*y*…*y))

Задача №3.

Построить доказательство формулы в исчислении предикатов.

($x P(x)Ú $x Q(x))«$x (P(x)Ú Q(x)).

Решение:

($x P(x)Ú $x Q(x))«$x (P(x)Ú Q(x))

$x P(x)Ú $x Q(x)®$x (P(x)Ú Q(x))Ù ($x (P(x)Ú Q(x))®$x P(x)Ú $x Q(x)

Доказываем с помощью дерева, используя формулы.

P(x)Ú Q(x)├ P(x)Ú Q(x)P(x)Ú Q(x)├ P(x)Ú Q(x)

$x P(x)Ú $x Q(x)├ $x (P(x)Ú Q(x)), $x (P(x)Ú Q(x))├ $x P(x)Ú $x Q(x)

$x P(x)Ú $x Q(x)®$x (P(x)Ú Q(x))Ù ($x (P(x)Ú Q(x))®$x P(x)Ú $x Q(x)

Задача №4.

Установить, выполнима ли следующая формула и если выполнима, то построить модель этой формулы.

" x P(x, x, x)Ù $x$y (Ø (x=y)Ù P(x, y, x))Ù Ø " x" y" z P(x, y, z).

Решение:

" x P(x, x, x)Ù $x$y (Ø (x=y)Ù P(x, y, x))Ù Ø " x" y" z P(x, y, z) ~

~ " x P(x, x, x)Ù $x$y (Ø (x=y)Ù P(x, y, x))Ù $x$y$z Ø P(x, y, z) ~ (x=a, x=b, y=c, z=d) ~

~ " x$a$y$b$c$d (P(x, x, x)Ù Ø (a=y)Ù P(a, y, a)Ù Ø P(b, c, d). – ПНФ.

a = f(x), b = g(x), y = e(x), c = s(x), d = h(x) Þ

P(x, x, x)Ù Ø (f(x) = e(x))Ù P(f(x), e(x), f(x))Ù Ø P(g(x), s(x), h(x)).

(1) P(x, x, x,)

(2)Ø (f(x) = e(x))

(3) P(f(x), e(x), f(x))

(4) Ø P(g(x), s(x), h(x))

Формула выполнима Þ строим модель: A={a, b}.

P(a, a, a) = P(b, b, b); f(a) = a, g(a) = a, e(a) = b, s(a) = b, h(a) = a;

f(b) =b, g(b) = b, e(b) = a, s(b) = a, h(b) = b;