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

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

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

а) алгоритма Квайна;

б) алгоритма редукции;

в) метода резолюций.

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

конкретном случае.

1) x, y├ ((y → x) → z) v (z → y) → x).

2) x v y v u, y v u, x v z ├ x v y.

3) x, y, z ├ (x → y) v (y → z).

4) x v y ├ (x → z) v (y → z).

РЕШЕНИЕ.

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

1. x, y├ ((y → x) → z) v (z → y) → x.)

x Λ y → ((y → x) → z) v (z → y) → x.)

Данная формула доказуема.

Построим её доказательство по правилам вывода.

2. x v y v u, y v u, x v z ├ x v y

((x v y v u) Λ (y v u) Λ (x v z)) → x v y

Эта формула недоказуема.

Покажем её недоказуемость с помощью а) алгоритма Квайна;

б) алгоритма редукции;

в) метода резолюций.

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

((x v y v u) Λ (y v u) Λ (x v z)) → x v y

первая ветвь вторая ветвь

х = 0 x = 1

((0 v y v u) Λ (y v u) Λ (0 v z)) → 0 v y

((y v u) Λ (y v u) Λ z) → y

у = 0 у =1

((1 v u) Λ (0 v u) Λ z → 0

1 Λ u Λ z → 0

u Λ z → 0

z=0 z=1

0→ 0=1 u → 0

u=0 u=1

1→ 0=0 0 → 0=1

Получили набор переменных, при котором функция обращается в ноль.

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

 

 

б) Алгоритм редукции.

((x v y v u) Λ (y v u) Λ (x v z)) → x v y = Ф

Предположим, что Ф = 0, т.е. предположим, что формула недоказуема, тогда:

((x v y v u) Λ (y v u) Λ (x v z)) → x v y = 0

Значит (x v y v u) Λ (y v u) Λ (x v z) = 1, x v y=0

х = 0

у = 0

Следовательно,

y v u = 1 x v z = 1

u = 1 0 v z = 1

u = 1, u = 0 z = 1

Противоречий нет. Формула недоказуема.

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

x v y v u, y v u, x v z ├ x v y

S = { x v y v u; y v u; x v z; (x v y) }

Построим резолютивный вывод нуля из S:

D₁ = x v y v u res(D₁, D₂ ) = x D₆ = x

D₂ = y v u res(D₄, D₆ ) = 0

D₃ = x v z

D₄ = x

D₅ = y

Формула недоказуема.

Данное доказательство является оптимальным.

3. x, y, z ├ (x → y) v (y → z)

(x Λ y Λ z) → (x → y) v (y → z)

x y z
0 0 0	0	0	1	1	1	1
0 0 1	0	0	1	1	1	1
0 1 0	0	0	1	0	1	1
0 1 1	0	0	1	1	1	1
1 0 0	0	0	0	1	1	1
1 0 1	0	0	0	1	1	1
1 1 0	1	0	1	0	1	1
1 1 1	1	1	1	1	1	1

 

Эта формула доказуема.

Покажем её доказуемость по правилам вывода.

 

 

x ├ x; y ├ y; z ├ z

12

x, y, z ├ y; x, y, z ├ z;

7

x, y, z ├ (x → y); x, y, z ├ (y → z)

1

x, y, z ├ (x → y) v (y → z)

4. x v y ├ (x → z) v (y → z)

x v y → (x → z) v (y → z)

x y z
0 0 0	0	1	1	1	1
0 0 1	0	1	1	1	1
0 1 0	1	1	0	1	1
0 1 1	1	1	1	1	1
1 0 0	1	0	1	1	1
1 0 1	1	1	1	1	1
1 1 0	1	0	0	0	0
1 1 1	1	1	1	1	1

Эта формула недоказуема.

Покажем её недоказуемость с помощью а) алгоритма Квайна;

б) алгоритма редукции;

в) метода резолюций.

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

x v y → (x → z) v (y → z)

х = 0 х = 1

y → 1 v (y → z) 1 → (1 → z) v (y → z)

y → 1 = 1 1 → z v (y → z)

y = 0 y = 1

1 → z v 1 1 → z v z

1 → 1 = 1

z = 0 z = 1

1 → 0 = 0 1 → 1 = 1

 

Получили набор переменных, при котором функция обращается в ноль.

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

 

б) Алгоритм редукции

x v y → (x → z) v (y → z) = Ф

Предположим, что Ф = 0, т.е. предположим, что формула недоказуема, тогда:

(x → z) v (y → z) = 0, x v y = 1

x → z = 0 y → z = 0 x v y = 1

х = 1 y = 1 x = 1

z = 0 z = 0 y = 1

Противоречий нет. Формула недоказуема.

Данное доказательство является оптимальным.

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

x v y ├ (x → z) v (y → z)

S = { (x v y); (x → z); (y → z)}