Загрузка...
скачать
Реферат на тему:

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



План:

    Введение
  • 1 Примеры и контрпримеры
  • 2 Построение ДНФ
    • 2.1 Алгоритм построения ДНФ
    • 2.2 Пример построения ДНФ
  • 3 k-дизъюнктивная нормальная форма
  • 4 Переход от ДНФ к СДНФ
  • 5 Формальная грамматика, описывающая ДНФ
  • Примечания
    Литература

Введение

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


1. Примеры и контрпримеры

Формулы в ДНФ:

A \or B
(A \and B) \or \neg A
(A \and B \and \neg C) \or (\neg D \and E \and F) \or (C \and D) \or B

Формулы не в ДНФ:

\neg(A \or B)
A \or (B \and (C \or D))

2. Построение ДНФ

2.1. Алгоритм построения ДНФ

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

A \rightarrow B = \neg A \vee B
A \leftrightarrow B = (A \wedge B) \vee (\neg A \wedge \neg B)

2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:

\neg (A \vee B) = \neg A \wedge \neg B
\neg (A \wedge B) = \neg A \vee \neg B

3) Избавиться от знаков двойного отрицания.

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


2.2. Пример построения ДНФ

Приведем к ДНФ формулу :F = ((X \rightarrow Y) \downarrow \neg (Y \rightarrow Z))

Выразим логические операции → и ↓ через :\vee \wedge \neg

F = ((\neg X \vee Y) \downarrow \neg(\neg Y \vee Z)) = \neg ((\neg X \vee Y) \vee \neg (\neg Y \vee Z))

В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:

F = \neg ((\neg X \vee Y) \vee \neg (\neg Y \vee Z)) = (\neg \neg X \wedge \neg Y) \wedge (\neg Y \vee Z) = (X \wedge \neg Y) \wedge (\neg Y \vee Z)

Используя закон дистрибутивности, приводим формулу к ДНФ:

F = (X \wedge \neg Y \wedge \neg Y) \vee (X \wedge \neg Y \wedge Z)

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

k-дизъюнктивная нормальной формой называют дизъюнктивную нормальную форму, в которой каждая конъюнкция содержит ровно k литералов.

Например, следующая формула записана в 2-ДНФ:

(A \and B) \or (\neg B \and C) \or (B \and \neg C)

4. Переход от ДНФ к СДНФ

Если в какой-то простой конъюнкции недостает переменной, например, Z, вставляем в нее выражение :Z \vee \neg Z = 1,после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем). Например:

X \vee \neg Y \neg Z = X(Y \vee \neg Y)(Z \vee \neg Z) \vee (X \vee \neg X)\neg Y \neg Z = XYZ \vee X \neg YZ \vee XY \neg Z \vee X \neg Y \neg Z \vee X \neg Y \neg Z \vee \neg X \neg Y \neg Z =
 = XYZ \vee X \neg YZ \vee XY \neg Z \vee X \neg Y \neg Z \vee \neg X \neg Y \neg Z

Таким образом, из ДНФ получили СДНФ.


5. Формальная грамматика, описывающая ДНФ

Следующая формальная грамматика описывает все формулы, приведенные к ДНФ:

<ДНФ> → <конъюнкт>
<ДНФ> → <ДНФ> ∨ <конъюнкт>
<конъюнкт> → <литерал>
<конъюнкт> → (<конъюнкт> ∧ <литерал>)
<литерал> → <терм>
<литерал> → ¬<терм>

где <терм> обозначает произвольную булеву переменную.

Примечания

  1. Поздняков С.Н., Рыбин С.В. Дискретная математика. — С. 303.

Литература

  • Ю.И. Галушкина, А.Н. Марьямов: Конспект лекций по дискретной математике - 2-е изд., испр. - М.: Айрис-пресс, 2008. - 176 с. - (Высшее образование)
скачать

Данный реферат составлен на основе статьи из русской Википедии. Синхронизация выполнена 20.07.11 01:43:23

Похожие рефераты: Нормальная форма, Нормальная форма Хомского, Нормальная форма БойсаКодда, K-конъюнктивная нормальная форма, Пятая нормальная форма, Нормальная форма (математика), Нормальная форма Чибрарио, Четвёртая нормальная форма, Конъюнктивная нормальная форма.

Категории: Булева алгебра.

Текст доступен по лицензии Creative Commons Attribution-ShareAlike.