Дизъюктивная нормальная форма

Дизъюктивная нормальная форма (ДНФ) - это нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов.

Любая булева формула может быть приведена к ДНФ. Для этого можно использовать закон двойного отрицания, закон де Моргана, закон дистрибутивности. Дизъюнктивная нормальная форма удобна для автоматического доказательства теорем.

Алгоритм приведения формулы к ДНФ:

1. Выражение импликации через дизъюнкцию и отрицание, используя эквивалентность.

2. Используя законы де Моргана, осуществить перенос всех отрицаний к переменным и сократить двойные отрицания, пользуясь законом двойного отрицания.

3. Используя закон дистрибутивности, преобразовать выражение так, чтобы все конъюнкции выполнялись раньше дизъюнкций.

Равносильные преобразования логических формул имеют то же назначение, что и преобразования формул в обычной алгебре. Они служат для упрощения формул или приведения их к определённому виду путем использования основных законов алгебры логики.

Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), тогда как другие преобразования основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.).

Задание 3 Приведите равносильными преобразованиями следующую формулу к ДНФ: (X ˄ Y) ˅ (Z → Y)

Решение задачи

(X ˄ Y) ˅ (Z → Y) = (X ˅ Y) ˅ (Z ˅ Y) = (X ˅ Y) ˅ (Z ˄ Y) = = X ˅ Y ˅ Z ˄ Y = X ˅ Y ˅ Z

КОНЪЮКТИВНАЯ НОРМАЛЬНАЯ ФОРМА

Конъюктивная нормальная форма (КНФ) – нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов.

Алгоритм приведения к КНФ аналогичен, только на шаге 3 делают так, чтобы все дизъюнкции встречались раньше конъюнкции.

Алгоритм приведения формулы к ДНФ:

1. Выражение импликации через дизъюнкцию и отрицание, используя эквивалентность.

2. Используя законы де Моргана, осуществить перенос всех отрицаний к переменным и сократить двойные отрицания, пользуясь законом двойного отрицания.

3. Используя закон дистрибутивности, преобразовать выражение так, чтобы все дизъюнкции выполнялись раньше конъюнкций.

Задание 4 Приведите равносильными преобразованиями следующую формулу к КНФ: (X ↔ Y) ˄ (X ˅ Z)

Решение задачи

(X ↔ Y) ˄ (X ˅ Z) = ((X ˅ Y) ˄ (X ˅ Y)) ˄ (X ˅ Z) = (X ˅ Y) ˄ (X ˅ Z) ˄ (X ˅ Y) ˄ (X ˅ Z) = (X ˅ Y) ˄ (X ˅ Y) ˄ (X ˅ Z)

МАШИНА ТЬЮРИНГА

Машина Тьюринга – это строгое математическое построение, математический аппарат, созданный для решения определенных задач.

Программа для машины Тьюринга представляет собой таблицу, в каждой клетке которой записана команда.

  дизъюктивная нормальная форма - student2.ru дизъюктивная нормальная форма - student2.ru дизъюктивная нормальная форма - student2.ru дизъюктивная нормальная форма - student2.ru
дизъюктивная нормальная форма - student2.ru дизъюктивная нормальная форма - student2.ru дизъюктивная нормальная форма - student2.ru дизъюктивная нормальная форма - student2.ru дизъюктивная нормальная форма - student2.ru
дизъюктивная нормальная форма - student2.ru дизъюктивная нормальная форма - student2.ru дизъюктивная нормальная форма - student2.ru дизъюктивная нормальная форма - student2.ru дизъюктивная нормальная форма - student2.ru

Клетка (qj, aj) определяется двумя параметрами – символом алфавита и состоянием машины. Команда представляет собой указание: куда передвинуть головку чтения/записи, какой символ записать в текущую ячейку, в какое состояние перейти машине. Для обозначения направления движения автомата используют одну из трех букв: «Л» (влево), «П» (вправо) или «Н» (неподвижен).

Машина Тьюринга характеризуется следующими данными:

а) внешним алфавитом дизъюктивная нормальная форма - student2.ru ;

б) внутренним алфавитом дизъюктивная нормальная форма - student2.ru ;

в) программой: совокупностью выражений дизъюктивная нормальная форма - student2.ru , дизъюктивная нормальная форма - student2.ru , дизъюктивная нормальная форма - student2.ru , каждое из которых имеет вид дизъюктивная нормальная форма - student2.ru , где дизъюктивная нормальная форма - student2.ru , дизъюктивная нормальная форма - student2.ru и дизъюктивная нормальная форма - student2.ru .

Здесь дизъюктивная нормальная форма - student2.ru – символ пустой ячейки; дизъюктивная нормальная форма - student2.ru – состояние остановки: попав в него, машина прекращает работу; дизъюктивная нормальная форма - student2.ru – начальное состояние: в этом состоянии машина начинает работу.

Несмотря на свое простое устройство, машина Тьюринга может выполнять все возможные преобразования слов, реализуя тем самым все возможные алгоритмы.

Задание 5 В соответствии с вариантом получить, если это возможно, результирующее слово на машине Тьюринга.

Решение задачи

Внешний алгоритм машины Тьюринга содержит четыре буквы: дизъюктивная нормальная форма - student2.ru , внутренний алфавит – три буквы - дизъюктивная нормальная форма - student2.ru . На ленте записано слово дизъюктивная нормальная форма - student2.ru .

Начальная конфигурация имеет вид:

дизъюктивная нормальная форма - student2.ru .

Программа машины задана таблицей 2:

  дизъюктивная нормальная форма - student2.ru дизъюктивная нормальная форма - student2.ru дизъюктивная нормальная форма - student2.ru дизъюктивная нормальная форма - student2.ru
дизъюктивная нормальная форма - student2.ru дизъюктивная нормальная форма - student2.ru дизъюктивная нормальная форма - student2.ru дизъюктивная нормальная форма - student2.ru дизъюктивная нормальная форма - student2.ru
дизъюктивная нормальная форма - student2.ru дизъюктивная нормальная форма - student2.ru дизъюктивная нормальная форма - student2.ru дизъюктивная нормальная форма - student2.ru дизъюктивная нормальная форма - student2.ru

Таблица 2

Требуется определить результирующее слово, которое будет записано на ленте после остановки машины.

1) а0 а1 а2 а3 а3 а2 а0

q1

2) a0 a1 a1 a3 a3 a2 a0

q1

3) a0 a3 a1 a3 a3 a2 a0

q1

4) a0 a2 a1 a3 a3 a2 a0

q1

5) a2 a2 a1 a3 a3 a2 a0

q2

Ответ: a2…a2 a1 a3 a3 a2

СПИСОК ЛИТЕРАТУРЫ

1. Алгебра логики - Большая советская энциклопедия : [в 30 т.] / гл. ред. А. М. Прохоров. — 3-е изд. — М. : Советская энциклопедия, 1969—1978.

2. Новиков П.С. Элементы математической логики. – М.: Наука, 1973.

3. Кондаков Н.И. Логический словарь. – 2-е изд.-М.: Наука, 1975. – 721 с.

4. Анкудинов Г.И., Анкудинов И.Г., Петухов О.А. Математическая логика и теория алгоритмов: Учеб.пособие. – 2-е изд. – СПб.: СЗТУ, 2003.

Наши рекомендации