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

1. x ۷ y

2. x ۷ z

3. x ۷ z ۷ u

4. u

5. y

6. res_z(2, 3) = x ۷ u

7. res_u(6, 4) = x

8. res_y(2, 7) = x

 Секвенция недоказуема.

в) ⊦ (y ۸ z)  (y ۷ z)

y ۸ z ⊦ y ۸ z

y ۸ z ⊦ y

y ۸ z ⊦ y ۷ z

⊦ (y ۸ z)  (y ۷ z)

г) x ⊦ z  x

x ⊦ x

x, z ⊦ x

x ⊦ z  x

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

__ = < N, ≤ > __ = < N, P(x, y)>, где P(x, y) означает, что y делится на x.

Решение:

 x P(x, x): на ___: x ≤ x - верно всегда

на ___: P(x, x) – неверно при x = 0  (0, 0)  P

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

⊦  x (P(x)  Q(x)) ۷ ( x P(x) ۸  x Q(x))

Докажем: ⊦ φ ۷ φ

φ ⊦ φ (φ ۷ φ) ⊦ (φ ۷ φ)

(φ ۷ φ), φ ⊦

(φ ۷ φ) ⊦ φ ۷ φ; (φ ۷ φ) ⊦ (φ ۷ φ)

(φ ۷ φ) ⊦

⊦ φ ۷ y

P ⊦ P; P ⊦ P Q ⊦ Q; Q ⊦ Q

P ۷ Q, P, Q, P ⊦; P ۷ Q, P, Q, Q ⊦; P ۷ Q⊦ P ۷ Q

P ۷ Q, P, Q, ⊦

P(x) ۷ Q(x) ⊦  x (P(x)  Q(x)) ۷ ( x P(x) ۸  x Q(x))

(P ۷ Q), P⊦ P ۷ Q; (P۷ Q), P⊦ (P۷ Q) (P۷ Q), Q⊦ P۷ Q; (P۷ Q), Q⊦ (P۷ Q)

(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)⊦  x(P(x) Q(x))۷ ( xP(x)۸  xQ(x)); (P(x)۷ Q(x))⊦  x(P(x) Q(x))۷ ( xP(x)۸  xQ(x));

⊦ (P(x) ۷ Q(x))۷ (P(x) ۷ Q(x))

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

 x  y ((x = y) ۸ P(x, y) ۸  z R(x, y, z) ۸  u R(x, y, u))

m = < {a, b}{(a, b)}{(a, b, a)}>

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

  x ( y P(x, y)    y Q(x, y)) ۸  x (  y P(x, y)   y Q(y, y)) 

  x ( y P(x, y) ۷   y Q(x, y)) ۸  x (  y P(x, y) ۷  y Q(y, y)) 

  x ( y P(x, y) ۷   y Q(x, y)) ۸  x (  y P(x, y) ۷  y Q(y, y)) 

  x ( y P(x, y) ۷   y Q(x, y)) ۸  x (  y P(x, y) ۸  y Q(y, y)) 

  x  y  y₁ (P(x, y) ۷ Q(x, y₁)) ۸  x   y (P(x, y) ۸  y Q(y, y)) 

  x  y  y₁  x₁  y₂  y₃ ((P(x, y) ۷ Q(x, y₁)) ۸ P(x₁, y₂) ۸ Q(y₃, y₃)) 

КлНФ

  x  y  y₁  x₁  y₂  y₃((P(x, y) ۸ P(x₁, y₂) ۸ Q(y₃, y₃)) ۷ (Q(x, y₁) ۸ P(x₁, y₂) ۸ Q(y₃, y₃))) ПНФ

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

Ф₁ =   x (P₁(x) ۷ (P₂(x) ۸ P₃(x)))

Ф₂ =  y   x (P₄(x, y) ۸ (P₄(y, x)  (P₁(x) ۷ P₂(x))))

Ф₃ =   x (P₃(x)   y P₄(x, y))

Ф₁ =   x (P₁(x) ۷ P₂(x) ۷ P₃(x)))

Ф₂ =  y   x (P₄(x, y) ۸ (P₄(y, x) ۷ P₁(x)) ۸ (P₄(y, x) ۷ P₂(x)))

Ф₃ =   x   y (P₃(x) ۷ P₄(x, y))

1. P₁(x) ۷ P₂(x) ۷ P₃(x)

2. P₄(x, c)

3. P₄(c, x) ۷ P₁(x)

4. P₄(c, x) ۷ P₂(x)

5. P₃(x) ۷ P₄(x, y)

6. res(1, 3) = P₂(x) ۷ P₃(x) ۷ P₄(c, x)

7. res(1, 4) = P₁(x) ۷ P₃(x) ۷ P₄(c, x)

8.

9.

10.

11. res(1, 8) = res(2, 6) = P₂(c) ۷ P₃(c)

12.

 существует модель

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

0, если x = 0

f(x) = sg(x) =

1, если x > 0

Решение:

sg(0) = 0(x)

sg(x+1) = S(0(x))

8 Построить машину Тьюринга для вычисления функций из Вашей задачи №7.