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

Новосибирский государственный технический университет

Курсовая работа

по дисциплине «Мат. логика»

Вариант: 21

Группа: АМ-210

Выполнил: Устинов Е.Б

Новосибирск 2003

Задание №1

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

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

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

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

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

а) φ = x Ù z |- Øx ®z

Значит формула доказуема.

Аксиома

xÚz | - xÚz____

x Ú z | - ØØx Ú z

x Ú z |- Ø x ® z

б) y, z, Øu |- y Ú z Ú u

аксиомааксиома

y |- y z |- z

y |- y Ú z; z |- y Ú z

_ y, z |- y Ú z_

y, z, Øu |- y Ú z__

y, z, Øu |- y Ú z Ú u

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

в) y Ù Øx, y Ù x |- y ® (x ® y)

y |- y______

y Ù Øx, y Ù x, y |- y

y Ù Øx, y Ù x, y, x |- y

y Ù Øx, y Ù x, y |- x ® y

y Ù Øx, y Ù x |- y ®(x ® y)

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

г) (x Ù z) Ú y |- (x Ú y) Ù x

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

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

(x Ù z) Ú y ® (x Ú y) Ù x = f (x, y, z)

f(x) =1

(z Ú y) ® 1

f(y) = 1 f(y) = 0

1 ® 1 z ® 1

f(z) = 1 f(z) = 0

1 1

f(x) = 0

y ® 0

f(y) =0 f(y) = 1

Gt; противоречие

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

Предположим, что данная секвенция недоказуема:

Введем противоречие:

f((x Ù z) Ú y) = 1

f((x Ú y) Ù x) = 0

f(x Ú y) = 1

f(x) = 0

f(y) = 1

f(x, y) =0, только при (x, y) = (0, 1)

f((x Ù z) Ú y) = f((0 Ù z) Ú 1) = 1 = 1 тождество

(x, y) = (0, 1)

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