Пример. Построить СКНФ и СДНФ булевой функции f(x₁, x₂, x₃)= 00101110.

Решение.

Строим таблицу значений функции (табл.):

Таблица

СКНФ (0): № 0, 1, 3, 7

$f(x_1,x_2,x_3)=(x_1 \vee x_2 \vee x_3) (x_1 \vee x_2 \vee\bar{x_3}) (x_1 \vee\bar{x_2} \vee\bar{x_3})(\bar{x_1} \vee\bar{x_2} \vee\bar{x_3})$

СДНФ (1): № 2, 4, 5, 6

$f(x_1,x_2,x_3)= \bar{x_1} x_2 \bar{x_3} \vee x_1 \bar{x_2} \bar{x_3} \vee x_1 \bar{x_2} x_3 \vee x_1 x_2 \bar{x_3}$

1. Теорема. Пусть f(x1, x2, …, xk) k-местная булева функция. Если f не равна тождественно нулю, то существует такая формула F, зависящая от списка переменных x1, x2, …, xn и находящаяся в СДНФ относительно этого списка, что F выражает собой функцию f. Формула F определена однозначно с точностью до перестановки дизъюнктивных членов.
2. Теорема . Пусть f(x1, x2, …, xk) k-местная булева функция. Если f не равна тождественно единице, то существует такая формула F, зависящая от списка переменных x1, x2, …, xk и находящаяся в СКНФ относительно этого списка, что F выражает собой функцию f. Формула F определена однозначно с точностью до перестановки конъюнктивных членов.