Задача №6.

Методом резолюций проверить, противоречиво ли множество предложений {₁,₂}. Если множество непротиворечиво, то построить модель этого множества.

₁=xyzu (P₁(x)((P₂(x,y)P₃(y,z))(P₁(z)P₃(z,u)))),

₂=x (P₁(x)y (P₂(x,y)P₃(x,y))).

Решение:

₁= xyzu (P₁(x)((P₂(x,y)P₃(y,z))(P₁(z)P₃(z,u)))) 

xyzu (P₁(x)((P₂(x,y)P₃(y,z)) (P₁(z)P₃(z,u)))) 

xyzu (P₁(x)(P₁(z)P₂(x,y)P₃(y,z))(P₂(x,y)P₃(y,z)).

₂= x (P₁(x,y)y (P₂(x,y)P₃(x,y))) 

x(P₁(x)y (P₂(x,y)P₃(x,y))) 

xy((P₁(x)P₂(x,y)(P₁(x)P₃(x,y))).

(1)P₁(x) (2)P₁(z)P₂(x,y)P₃(y,z) (3)P₂(x,y)P₃(y,z) (4)P₁(x)P₂(x,y) (5)P₁(x)P₃(x,y)

Строим модель: =<P ,P ,P >

res((1),(4)) = P₂(x,z) - (6)

res((6),(3)) = P₃(y,z)

P₃(y,z) = 0  P₃(y,z) = 1

Задача №7.

Доказать примитивную рекурсивность функций, выражая их через простейшие с помощью операторов суперпозиции и примитивной рекурсии.

f(x) =

Задание №8.

Построить машины Тьюринга для вычисления функций:

f(x) =

…

0

1

1

1

0

…

q₁

q1

q2

q3

q4

q5

q6

q7

q8

q9

q10

q11

q12

q13

0

Lq0

Lq5

Lq5

Rq0

Rq7

Rq9

1Rq10

1q11

Lq12

Rq13

Rq0

1

Rq2

Rq3

Rq4

Rq6

Lq5

Lq6

0Rq8

Rq8

Lq11

Lq6

Задание №1

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

1. Алгоритма Квайна

2. Алгоритма редукции

3. Метода резолюций

Среди этих доказательств недоказуемости выбрать оптимальный в каждом конкретном случае.

1. Y(ZU) ⊦ (YZ)U

2. ⊦ YY

3. YXU , XYU , UX ⊦ UY

4. YZ ⊦ YZ

Решение:

1. Y(ZU) ⊦ (YZ)U

Данная секвенция недоказуема!

Метод Квайна: Y(ZU) ⊦ (YZ)U

Пусть Y=0 , тогда: Пусть Y=1 , тогда:

0(ZU) ⊦ (0Z)U 1(ZU) ⊦ (1Z)U

1 ⊦ 1U

Пусть U=0 , тогда: Пусть U=1 , тогда: Пусть Z=0 , тогда:

1 ⊦ 10 1 ⊦ 11 1(0U) ⊦ (10)U

1 ⊦ 0 1 ⊦ 1 1 ⊦ 0U

тождественно ложно. Пусть Z=1 , тогда:

1(1U) ⊦ (11)U

1(1U) ⊦ 1U

Пусть U=0 , тогда: Пусть U=1 , тогда:

1(10) ⊦ 10 1(11)  11

10  0 1  1

0  0

Метод редукции (оптимальный): Y(ZU)  (YZ)U

Докажем что при (YZ)U = 0, Y(ZU) =1

Чтобы выполнялось (YZ)U = 0 надо, чтобы выполнялось:

(YZ) = 1, U = 0

Чтобы выполнялось YZ = 1 достаточно Y = 0.

Тогда Y(ZU) =1 тождественно истинно.

Значит при Y = 0 и любых Z и U данная секвенция недоказуема!

Метод резолюций: Y(ZU)  (YZ)U

Приведем формулу (Y(ZU))  ((YZ)U) к КНФ.

(Y(ZU)),((YZ)U) = YZU,((YZ)U) =

= YZU,(YZ)U = YZU,YZ,U

 YZU

(2) YZ

(3) U

(4) res_Z(1,2) = YU

(5) res_U(3,4) = Y

Следовательно данная секвенция недоказуема.

2.  YY Данная секвенция доказуема!

Y  Y

₈ Y  Y

 YY

3. YXU , XYU , UX  UY

Данная секвенция недоказуема!

Метод Квайна: YXU , XYU , UX  UY

(YXU)(XYU)(UX)  UY

Пусть X = 0, тогда:

(Y0U)(0YU)(U0)  UY

(YU)1(U)  UY

Пусть Y = 0, тогда: Пусть Y = 1, тогда:

(0U)1(U)  U0 (1U)1(U)  U1

U1(U)  U 1(U)  1

Пусть U = 0, тогда: Пусть U = 1, тогда: Пусть U = 0, тогда: Пусть U = 1, тогда:

01(0)  0 11(1)  1 1(0)  1 1(1)  1

0  0 0  1 1  1 0  1

Пусть X = 1, тогда:

(Y1U)(1YU)(U1)  UY

1(YU)1  UY

Пусть Y = 0, тогда: Пусть Y = 1, тогда:

1(0U)1  U0 1(1U)1  U1

11  U 1U  1

Пусть U = 0, тогда: Пусть U = 1, тогда: Пусть U = 0, тогда: Пусть U = 1, тогда:

1  0 1  1 10  1 11  1

Тождественно ложно! 0  1 1  1

Метод редукции: YXU , XYU , UX  UY

Докажем, что при (UY) = 0, (YXU)(XYU)(UX) = 1

(UY) = 0 выполняется только при условии, что U = 0 и Y = 0

Тогда:

(0X0)(X00)(0X) = X(X1)(1X) = X11 = X

Значит при U = 0, Y = 0, X = 1 данная секвенция недоказуема!

Метод резолюций (оптимальный): YXU , XYU , UX  UY

Приведем формулу YXU , XYU , UX  UY к КНФ

YXU,XYU,UX,(UY) = YXU,XYU,UX,U,Y

1. YXU

2. XYU

3. UX

4. U

5. Y

6. res_X,Y(1,2) = U

7. res_U(4,6) = 0

Следовательно, данная секвенция недоказуема.

4. YZ  YZ Данная секвенция доказуема!

Тождественно истина доказуема доказуема

 Z ; _{12 12} Z  Z ; ₁₂ YZ  YZ

₆ YZ,Y,Y  Z ; YZ,Y,Z  Z ; YZ,Y  YZ

₈ YZ,Y  Z

YZ  YZ

Задание №2

Найти формулу исчисления предикатов истинностью на алгебраической системе  и ложностью на .

 = <;  > ,  = <; P(x,y)> , где P(x,y) означает что x и y взаимно просты.

Решение:

 : xy(xy), xy(xy)

 : xyP(x,y)

Задание №3

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

x (P(x)Q(x))x (P(x)Q(x))

Решение:

Безусловный вывод. Безусловный вывод.

₁P(x); Q(x)

₁₅P(x)Q(x)

₅x (P(x)Q(x))

x (P(x)Q(x))x (P(x)Q(x))

Задание №4

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

xP(x,x)x,y(P(x,y)P(y,x))xyzu(P(u,x)P(u,y)P(u,z))

Решение:

1. Удаляем импликацию:

xP(x,x)x,y(P(x,y)P(y,x))xyzu(P(u,x)P(u,y)P(u,z))

2. Вносим отрицание к атомарным формулам:

xP(x,x)x,y(P(x,y)P(y,x))xyzu(P(u,x)P(u,y)P(u,z))

3. Вынесем поочередно кванторы во внешнюю часть:

xv,yP(x,x)(P(v,y)P(y,v))xyzu(P(u,x)P(u,y)P(u,z))

xv,ynmzuP(x,x)(P(v,y)P(y,v))P(u,n)P(u,m)P(u,z)

4. Получили КлНФ. Методом резолюций проверим выполнимость данной формулы:

1. P(x,x)

2. P(v,y)P(y,v)

3. P(u,n)

4. P(u,m)

5. P(u,z)

6. res(1,3) = res(1,4) = res(1,5) = 0

Значит данное множество невыполнимо!