Категории:

Астрономия
Биология
География
Другие языки
Интернет
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Механика
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Транспорт
Физика
Философия
Финансы
Химия
Экология
Экономика
Электроника

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

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

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

 

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

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) а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.