Введение в схемы, автоматы и алгоритмы


           

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


Имеется ряд специальных подклассов формул, позволяющих задавать все булевы функции. В этом разделе мы определим два таких подкласса функций, использующих только операции

и
.

Пусть

- это множество пропозициональных переменных. Введем для каждого
обозначения:
и
. Формула

(

), в которой
и все переменные разные, т.е.
при
, называется элементарной конъюнкцией (элементарной дизъюнкцией).

Определение 1.4.Формула

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

где каждая формула

- это элементарная конъюнкция.
называется совершенной ДНФ, если в каждую из ее конъюнкций
входят все
переменных из

Аналогично, формула

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

где каждая формула

- это элементарная дизъюнкция. Она является совершенной КНФ, если в каждую
входят все
переменных из

Рассмотрим произвольную булеву функцию

, зависящую от переменных из
. Oбозначим через

множество наборов значений переменных, на которых

принимает значение 1, а через

множество наборов, на которых

принимает значение 0, т.е.
и

Определим по этим множествам две формулы:

и

Теорема 1.1.

(1) Если функция

не равна тождественно 0, то формула
- это совершенная ДНФ, задающая функцию
.

(2) Если функция

не равна тождественно 1, то формула
- это совершенная КНФ, задающая функцию
.

Пример 1.2. Например, для функции

, представленной в таблице 1.1

совершенная ДНФ равна

, а ее совершенная КНФ:

Отметим, что совершенные ДНФ и КНФ часто являются чересчур сложными и длинными представлениями булевых функций. В нашем примере

может быть задана более простой ДНФ:
.



Содержание  Назад  Вперед