Решение:

1. Удаляем отрицание:

x (y P(x,y)  y Q(x,y)  x (y P(x,y)y Q(x,y)));

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

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

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

x (y P(x,y)  y Q(x,y)  x (y P(x,y) y Q(x,y)));

4. Выносим кванторы во внешнюю часть:

xyzuvw (P(x,y)  Q(x,z)  P(u,v)  Q(u,w));

5. Вынеся кванторы во внешнюю часть, получаем соответственно ПНФ и КлНФ:

xyzuvw (P(x,y)  Q(x,z)  P(u,v)  Q(u,w)) – КлНФ и ПНФ.

Задание №6

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

₁= xyz P₁(x,y,z);

₂= xyz (P₂(x)  P₁(x,y,z)  (P₂(y)P₁(y,x,z)));

₃= xyzu (P₁(x,y,z)  P₁(x,y,u));Решение:

₁= xyz P₁(x,y,z);

₂= xyz (P₂(x)  P₁(x,y,z)  (P₂(y)P₁(y,x,z))) 

xyz (P₂(x)  P₁(x,y,z)  (P₂(y) P₁(y,x,z)))

₃= xyzu (P₁(x,y,z)  P₁(x,y,u));

{₁,₂,₃} = {P₁(x,y,z), P₂(x), P₁(x,y,z), P₂(y) P₁(y,x,z), P₁(x,y,z), P₁(x,y,u)};

Пусть в ₁ x=c₁; в ₂ z=c₂; в ₃ y=c₃, u=c_4, тогда:

{₁,₂,₃} = {P₁(c₁,y,z), P₂(x), P₁(x,y,c₂), P₂(y) P₁(y,x,c₂), P₁(x, c₃,z), P₁(x,c₃, c₄)};

(1) P₁(c₁,y,z);

(2) P₂(x);

(3) P₁(x,y,c₂);

(4) P₂(y) P₁(y,x,c₂);

(5) P₁(x,c₃,z);

(6) P₁(x,c₃,c₄);

(7) res((3)(6)) = 0;

Данное множество {₁,₂,₃} противоречиво! Модели не существует!

Задание №7

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

суперпозиции и примитивной рекурсии.

f(x) = 2x+1;

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

I₁¹(x)= 2*0+1= 1;

S (I₃³(x,y,z)) = f(x+1)= (x+1)+(x+1)+1= 2x+3;

Задание №8

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

f(x)= 2x+1;

Решение:

0

0

1

1

…

0

0

_q1

q₁01^x00…  q₀01^2x+10…

Построение машины Тьюринга для вычисления функции f(x)= 2x+1:

0q₁  Rq₂;

1q₂  Rq₂;

0q₂  Rq₃;

0q₃  1q₄;

1q₃  Rq₃;

1q₄  Lq₄;

0q₄  1q₅;

1q₅  Lq₆;

1q₆  0q₆;

0q₆  Lq₇;

1q₇  1q₂;

0q₇  Rq₈;

0q₈  1q₉;

1q₉  Lq₀;

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

а) ^¬(y ۸ ^¬z)⊦ ^¬y ۷ z

Промежуточная секвенция: ⊦ φ ۷ ^¬ φ

^¬ φ ⊦ ^¬ φ ^¬( φ ۷ ^¬ φ) ⊦ ^¬( φ ۷ ^¬ φ)

^¬

5,12

( φ ۷ ^¬ φ), ^¬ φ ⊦ φ ۷ ^¬ φ; ^¬( φ ۷ ^¬ φ) , ^¬ φ ⊦ ^¬( φ ۷ ^¬ φ)

^¬ ( φ ۷ ^¬ φ) , ^¬ φ ⊦

^¬ ( φ ۷ ^¬ φ) ⊦ φ ۷ ^¬ φ; ^¬( φ ۷ ^¬ φ) ⊦ ^¬( φ ۷ ^¬ φ)

^¬ ( φ ۷ ^¬ φ) ⊦

⊦ φ ۷ ^¬y

Доказательство правила вывода Γ, φ ۸ ψ ⊦ χ

Γ, φ, ψ ⊦ χ

ψ

7,12

12, 12, 3

⊦ ψ Γ, φ, χ ⊦ χ

Γ , φ ۸ ψ, φ ⊦ ψ; Γ, φ ۸ ψ, φ ⊦ ψ  x

φ

6

По доказанному

12

7

12, 2

8

12

10

12

12

12, 4

⊦ φ Γ, φ ۸ ψ, φ ⊦ χ

Γ

8

, φ ۸ ψ ⊦ φ Γ, φ ۸ ψ ⊦ φ  x

Γ , φ ۸ ψ ⊦ χ

y ۸ ^¬z ⊦ y ۸ ^¬z ^¬(y ۸ ^¬z) ⊦ ^¬(y ۸ ^¬z)

^¬ (y ۸ ^¬z), y ۸ ^¬z ⊦ y ۸ ^¬z; ^¬(y ۸ ^¬z), y ۸ ^¬z ⊦ ^¬(y ۸ ^¬z)

^¬

9, 12

(y ۸ ^¬z), y ۸ ^¬z ⊦

z

12, 12, 4

⊦ z ^¬(y ۸ ^¬z), y ۸ ^¬z ⊦ ^¬y ۷ z ⊦ z ۷ ^¬z

^¬ (y ۸ ^¬z), y, z ⊦ ^¬y ۷ z; ^¬(y ۸ ^¬z), y, ^¬z ⊦ ^¬y ۷ z; ^¬(y ۸ ^¬z) ⊦ z ۷ ^¬z

^¬ (y ۸ ^¬z), y ⊦ ^¬y ۷ z ^¬y ⊦ ^¬y ⊦ y ۷ ^¬ y

^¬ (y ۸ ^¬z), y ⊦ ^¬y ۷ z ^¬(y ۸ ^¬z), ^¬y ⊦ ^¬y ۷ z ^¬(y ۸ ^¬z) ⊦ y ۷ ^¬ y

^¬ (y ۸ ^¬z)⊦ ^¬y ۷ z

б) x ۷ y, x ۷ z, x ۷ ^¬z ۷ u ⊦ u ۷ y

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

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

(x ۷ y) ۸ (x ۷ z) ۸ (x ۷ ^¬z ۷ u) ⊦ (u ۷ y)

Пусть x = 1

(1 ۷ y) ۸ (1 ۷ z) ۸ (1 ۷ ^¬z ۷ u) ⊦ (u ۷ y)

1 ۸ 1 ۸ 1 ⊦ (u ۷ y)

1 ⊦ (u ۷ y)

Пусть u = 0

1 ⊦ y

Пусть y = 0

1 ⊦ 0  противоречие. Секвенция недоказуема.

• Алгоритм редукций.

(x ۷ y) ۸ (x ۷ z) ۸ (x ۷ ^¬z ۷ u) = 1

(u ۷ y) = 0  верно, при u = 0 и y = 0

(x ۷ 0) ۸ (x ۷ z) ۸ (x ۷ ^¬z ۷ 0) = 1

x ۸ (x ۷ z) ۸ (x ۷ ^¬z ) = 1

При x = 1:

1 ۸ (1 ۷ z) ۸ (1 ۷ ^¬z ) = 1 z – любое

z – любое  1 = 1

При x = 1, y = 0, u = 0 секвенция недоказуема.

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

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

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

^¬ φ ⊦ ^¬ φ ^¬( φ ۷ ^¬ φ) ⊦ ^¬( φ ۷ ^¬ φ)

^¬

5,12

( φ ۷ ^¬ φ), ^¬ φ ⊦ φ ۷ ^¬ φ; ^¬( φ ۷ ^¬ φ) , ^¬ φ ⊦ ^¬( φ ۷ ^¬ φ)

^¬ ( φ ۷ ^¬ φ) , ^¬ φ ⊦

^¬ ( φ ۷ ^¬ φ) ⊦ φ ۷ ^¬ φ; ^¬( φ ۷ ^¬ φ) ⊦ ^¬( φ ۷ ^¬ φ)

^¬ ( φ ۷ ^¬ φ) ⊦

⊦ φ ۷ ^¬y

P ⊦ P; ^¬P ⊦ ^¬P Q ⊦ Q; ^¬Q ⊦ ^¬Q

P

10

6

7, 9

12

12

10

, ^¬P ⊦ P; P, ^¬P ⊦ ^¬P Q, ^¬Q ⊦ Q; ^¬Q, Q ⊦ ^¬Q

P

12

12

, ^¬P ⊦ Q, ^¬Q ⊦

^¬ P ۷ Q, P, ^¬Q, ^¬P ⊦; ^¬P ۷ Q, P, ^¬Q, Q ⊦; ^¬P ۷ Q⊦^¬P ۷ Q

^¬ P ۷ Q, P, ^¬Q, ⊦

^¬

15

4

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

^¬

12

12

10

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

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

^¬

12, 4

12, 4

P ⊦ ^¬P; ^¬(^¬P ۷ Q) ⊦ ^¬(^¬P ۷ Q) Q ⊦ Q; ^¬(^¬P ۷ Q) ⊦ ^¬(^¬P ۷ Q)

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

^¬

10

9

9

(^¬P ۷ Q), ^¬P ⊦ ^¬(^¬P ۷ Q), Q ⊦

^¬

13

13

(^¬P ۷ Q) ⊦ P ^¬(^¬P ۷ Q) ⊦ ^¬Q

^¬

1

(^¬P(x) ۷ Q(x)) ⊦ x P(x) ^¬(^¬P(x) ۷ Q(x)) ⊦ x ^¬Q(x)

^¬

5

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

⊦(^¬P(x) ۷Q(x))۷ ^¬ (^¬P(x) ۷Q(x))

⊦

6

 x (P(x)  Q(x)) ۷ (x P(x) ۸ x ^¬Q(x))

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

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

М



P

одель:

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



R

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. r

   {c/x}

   es(2, 3) = ^¬P₁(c)

9. r

   

   

   es(2, 4) = P₂(c)

10. r

    {c/y}

    es(2, 5) = ^¬P₃(x)

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

12. r

    {c/x}

    es(1, 9) = P₁(x) ۷ ^¬P₃(x)

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



{(c, c)}

m = <{c}, P₁⁽¹⁾ , P₂⁽¹⁾ , P₃⁽¹⁾ , P₄⁽²⁾>







{c}

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

0 , если x = 0

f(x) = sg(x) =

1, если x > 0

Решение:

s g(0) = 0(x)

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

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

	q1	q2	q3	q4	q5	q6	q7	q8
0			L q4	R q5	L q6	1 q7	L q6
1	R q2	R q3	0 q4	L q0	R q5	0 q7	L q8	L q0