Essays.club - Получите бесплатные рефераты, курсовые работы и научные статьи
Поиск

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

Автор:   •  Март 15, 2019  •  Практическая работа  •  313 Слов (2 Страниц)  •  389 Просмотры

Страница 1 из 2

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

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

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

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

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

МАТЕМАТИКА

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

Вариант 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!

...

Скачать:   txt (2.6 Kb)   pdf (187.7 Kb)   docx (256.5 Kb)  
Продолжить читать еще 1 страницу »
Доступно только на Essays.club