Типовой расчет. Найти предваренную и клаузальную нормальные формы. Машина Тьюринга
Автор: traskovp • Март 15, 2019 • Практическая работа • 313 Слов (2 Страниц) • 485 Просмотры
МИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное образовательное
учреждение высшего образования
«Тульский государственный университет»
КАФЕДРА ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ
МАТЕМАТИКА
Типовой расчет
Вариант 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.
0 | 1 | ^ | |
q0 | q0,R,0 | q0,R,1 | q1,R,0 |
q1 | - | - | q!,N,0 |
q! – завершающее состояние.
Примеры
1. | ^^110^^ | ^^110^^ | ^^110^^ | ^^1100^^ | ^^11000^^ |
ꜛq0 | ꜛq0 | ꜛq0 | ꜛq1 | ꜛq! | |
2. | ^^10^^ | ^^10^^ | ^^100^^ | ^^1000^^ | |
ꜛq0 | ꜛq0 | ꜛq1 | ꜛq! | ||
3. | ^^101^^ | ^^101^^ | ^^101^^ | ^^1010^^ | ^^10100^^ |
ꜛq0 | ꜛq0 | ꜛq0 | ꜛq1 | ꜛq! |
...