Нормальные формы

Нормальная форма – это синтаксически однозначный способ записи формулы, реализующей данную функцию.

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

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

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

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

Пример 3.2:

Отдельный элемент КНФ называется элементарной дизъюнкцией или конституентой нуля.

Очевидно, что каждая формула имеет бесконечно много ДНФ и КНФ.

Пример 3.3: Найдем несколько ДНФ для формулы .

1)

2)

3)

4)

5)