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

Введем обозначение

,

где – параметр, равный либо 0, либо 1. Очевидно, что

Легко видеть, что 1 тогда и только тогда, когда .

Теорема о разложении функций по переменным. Каждую функцию алгебры логики при любом () можно представить в следующей форме:

, (1)

где дизъюнкция берется по всевозможным наборам значений переменных .

Это представление называется разложением функции по переменным .

Доказательство. Рассмотрим произвольный набор значений переменных и покажем, что левая и правая части соотношения (1) принимают на нем одно и то же значение. Левая часть дает . Правая –

В качестве следствий из теоремы рассмотрим два специальных случая разложения.

1) Разложение по переменной:

.

Функции и называются компонентами разложения. Данное разложение полезно, когда какие-либо свойства устанавливаются по индукции.

2) Разложение по всем переменным:

.

При тождественно не равной 0 оно может быть преобразовано:

.

В результате окончательно получим

. (2)

Такое разложение называется совершенной дизъюнктивной нормальной формой (совершенной д. н. ф.).

Непосредственно к понятию совершенной д. н. ф. примыкает следующая теорема.

Теорема. Каждая функция алгебры логики может быть представлена формулой в базисе .

Доказательство.1) Пусть . Тогда, очевидно,

.

2) Пусть тождественно не равна 0. Тогда ее можно представить формулой (2).

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

Пример 3. Найти совершенную д. н. ф. для функции .

0 0
0 1
1 0
1 1

.

Совершенная д. н. ф. есть выражение типа П. Покажем, что при тождественно не равной 1 ее можно представить в виде . Запишем для двойственной функции (очевидно не равной тождественно 0) разложение в виде совершенной д. н. ф.:

.

Из принципа двойственности следует

.

Таким образом, получаем разложение, которое называется совершенной конъюнктивной нормальной формой (совершенной к. н. ф.):

. (3)

Пример 4. Построить совершенную к. н. ф. для функции .

Имеем .