Типовой расчет. Найти предваренную и клаузальную нормальные формы. Машина Тьюринга

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное

учреждение высшего образования

«Тульский государственный университет»

КАФЕДРА         ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ

МАТЕМАТИКА

Типовой расчет

Вариант 14

Выполнил: студент группы 220241

_________ Трасков М.Ю.

(подпись)

Проверил:         докторант кафедры ИБ

_________ Красоткина О.В.

      (подпись)

Тула 2015

Задание 3

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

 (Ɐx(A(x))) →(Ɐx(B(x)))  → Ǝy(C(y)&A(x) →C(y)&B(x));

(!Ɐx(A(x))) v !(Ɐx(B(x))) v Ǝy(C(y) & !A(x) v C(y)&B(x));

(!Ɐz(A(z))) v !(Ɐz(B(z))) v Ǝy(C(y) & !A(x) v C(y)&B(x));

(Ǝz(!A(z))) v (Ǝz(!B(z))) v Ǝy(C(y) & !A(x) v C(y)&B(x));

Ǝu Ǝz Ǝy((!A(u))) v (!B(z)) v (C(y) & !A(x) v C(y)&B(x)) - предваренная форма.

u=a, z=b, y=c

 [(C(c) & !A(x) v C(c)&B(x))] v !A(a) v !B(b) – сколемовская форма.

 [(C(c) v (C(c) & B(x))) & (!A(x) v (C(c) & B(x)))] v !A(a) v !B(b) =

[{С(с) v  C(c)) & (C(c) v B(x)} & {!A(x)vC(c) & !A(x) v (B(x)}] v !A(a) v !B(b)=

{С(с) v !A(a) v !B(b)} & { C(c) v B(x) v !A(a) v !B(b)} & {!A(x)vC(c) v !A(a) v !B(b)} & !A(x) v (B(x) v !A(a) v !B(b)} – клаузальная форма.

Задание 5

Составить программу машины Тьюринга в заданном алфавите и показать ее работоспособность на примере. A={0,1}. Считая непустое слово P записью числа в двоичной системе, получить двоичное число, равное учетверенному числу P.

q! – завершающее состояние.

Примеры