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

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

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

 

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

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)

 

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

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

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

 

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

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

а) внешним алфавитом ;

б) внутренним алфавитом ;

в) программой: совокупностью выражений , , , каждое из которых имеет вид , где , и .

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

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

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

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

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

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

.

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

 

 

Таблица 2

 

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

 

1) а₀ а₁ а₂ а₃ а₃ а₂ а₀

q₁

2) a₀ a₁ a₁ a₃ a₃ a₂ a₀

q₁

3) a₀ a₃ a₁ a₃ a₃ a₂ a₀

q₁

4) a₀ a₂ a₁ a₃ a₃ a₂ a₀

q₁

5) a₂ a₂ a₁ a₃ a₃ a₂ a₀

q₂

 

Ответ: a_2…a₂ a₁ a₃ a₃ a₂

 

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

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

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

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

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