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

Определение:

Формула вида [math]\displaystyle{ x_{i_1}^{\sigma_{i_1}} x_{i_2}^{\sigma_{i_2}} \cdots x_{i_k}^{\sigma_{i_k}} }[/math], где $x_{i_j}$ — логическая переменная, $\sigma_{i_j}$ — логическая константа, $i_1 \lt i_2 \lt ... \lt i_k$, называется конъюнктом.

Определение:

Если $f(x_1, ..., x_n)$ представлена в виде

$f(x_1, ..., x_n)= K_1 \vee K_2 \vee ... \vee K_s$, где $K_1$, $K_2$,..., $K_s$ — различные конъюнкты, то говорят, что $f$ представлена в дизъюнктивной нормальной форме (ДНФ).

Если в каждый $K_i$ входят все переменные $x_1, ..., x_n$, то говорят, что $f$ представлена в совершенной дизъюнктивной нормальной форме (СДНФ).

Так же используют обозначения д.н.ф. и с.д.н.ф.

Утверждение:

Пусть $f(x_1,...,x_n)\in P_2$. Если $f\neq 0$, то она представима в виде СДНФ, причем единственным образом (с точностью до перестановки конъюнктов).

Доказательство:

Во-первых, отметим, что разложение функции $f$ по всем переменным будет представлять собой СДНФ. Существование доказано.

Докажем единственность СДНФ. Пусть [math]\displaystyle{ f(x_1,...,x_n) = \bigvee_{i=1}^s K_i(x_1,...,x_n)= \bigvee_{j=1}^{s'} K_j'(x_1,...,x_n), }[/math] где $K_i$ и $K_j'$ — конъюнкты, $i=\overline{1,s}$, $j'=\overline{1,s'}$. Причем, не умаляя общности, \mbox{$K_1\not\in\{K_1',...,K_{s'}'\}$}, поскольку представления в виде СДНФ должны быть различны.

Пусть $K_1(x_1,...,x_n)=x_1^{\sigma_1}\cdots x_n^{\sigma_n}$. [math]\displaystyle{ f(\sigma_1,...,\sigma_n)= \bigvee_{i=1}^s K_i(\sigma_1,...,\sigma_n)= \sigma_1^{\sigma_1}\cdots \sigma_n^{\sigma_n}\vee\bigvee_{i=2}^s K_i(\sigma_1,...,\sigma_n)= 1\vee\bigvee_{i=2}^s K_i(\sigma_1,...,\sigma_n)=1, }[/math] так как $\sigma^\sigma=1$, для любого $\sigma\in E_2 $.

С другой стороны, [math]\displaystyle{ f(\sigma_1,...,\sigma_n)= \bigvee_{j=1}^{s'} K_j'(\sigma_1,...,\sigma_n). }[/math] Нетрудно заметить, что для любого $K_j'=x_1^{\sigma_1'}\cdots x_n^{\sigma_n'}\in\{K_1',...,K_{s'}'\}$ выполняется [math]\displaystyle{ K_j'(\sigma_1,...,\sigma_n)=\sigma_1^{\sigma_1'}\cdots \sigma_n^{\sigma_n'}=0, }[/math] поскольку $\exists m=\overline{1,n}$, $\sigma_m\neq\sigma_m'$ Таким образом, $f(\sigma_1,...,\sigma_n)=\bigvee_{j=1}^{s'} 0=0$. Противоречие доказывает, что двух различных представлений функции в СДНФ существовать не может.

[math]\displaystyle{ \blacksquare }[/math]

Рис. 1. Строки с [math]\displaystyle{ f=1 }[/math] дают конъюнкты СДНФ, строки с [math]\displaystyle{ f=0 }[/math] — дизъюнкты СКНФ, причём в СКНФ литералы инвертируются. Для функции из примера получаются обе формы; зелёные строки — четыре единицы, оранжевые — четыре нуля.

Конспект: Дискретная математика