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

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

и .

Пусть

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

(

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

и

Теорема 1.1.

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

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

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

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

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

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

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

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

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

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

Содержание раздела

---

---