16 Задача №1.

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

1. ├ x  ( x  x)

2. x  y├ x  y

3. x  y  z├ (x  y)  (y  z)

4. x  x├ y  y.

Решение:

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

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

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

├ x  (x x)

├ x  ( x  x)

2. x  y├ x  y – доказуема (исходя из таблицы истинности)

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

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

x  y├ x  y

3. 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)

4. 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;

Задача №5.

Привести к пренексной и клазуальной нормальной формам следующую формулу:

((xy P(x,y)xy Q(x,y))xy R(x,y)).

Решение:

((xy P(x,y)xy Q(x,y))xy R(x,y)) 

 (xy P(x,y)xy Q(x,y)) (xy R(x,y)) 

 xyP(x,y)xyQ(x,y)xyR(x,y) (- коньюктивная нормальная форма) 

 (x = a, y = b, x = c, y = d)  xyabcd (P(x,y)Q(a,b)R(c,d)) -

– клазуальная нормальная форма (она же является пренексной нормальной формой в данном случае).