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

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

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

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

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

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

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

(1) Ø 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