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

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

Формула вида [math]\displaystyle{ x_{i_1}^{\sigma_{i_1}} \vee x_{i_2}^{\sigma_{i_2}} \vee \cdots \vee 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)= (D_1) \wedge (D_2) \wedge ... \wedge (D_s)$, где $D_1$, $D_2$,..., $D_s$ — различные дизъюнкты, то говорят, что $f$ представлена в конъюнктивной нормальной форме (КНФ).

Если в каждый $D_i$ входят все переменные $x_1, ..., x_n$, то говорят, что

$f$ представлена в совершенной конъюнктивной нормальной форме (СКНФ).

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

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

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

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

Поскольку $f\neq 1$, то $\overline f\neq 0$. Тогда у функции $\overline f$ существует СДНФ, которая имеет вид: [math]\displaystyle{ \overline f(x_1, ..., x_n)= \bigvee_{i=1}^s K_i(x_1,...,x_n) =\bigvee_{\substack{(\sigma_1,...,\sigma_n)\\ \overline f(\sigma_1,...,\sigma_n)=1}} x_1^{\sigma_1}\cdots x_n^{\sigma_n}. }[/math]

Следовательно, [math]\displaystyle{ f(x_1, ..., x_n) = \neg \biggl( \bigvee_{\substack{(\sigma_1,...,\sigma_n)\\ f(\sigma_1,...,\sigma_n)=0}} x_1^{\sigma_1}\cdots x_n^{\sigma_n} \biggr)= }[/math]

Применим правила де Моргана. [math]\displaystyle{ = \bigwedge_{\substack{(\sigma_1,...,\sigma_n)\\ f(\sigma_1,...,\sigma_n)=0}} \neg \bigl( x_1^{\sigma_1}\cdots x_n^{\sigma_n} \bigr) =\bigwedge_{\substack{(\sigma_1,...,\sigma_n)\\ f(\sigma_1,...,\sigma_n)=0}} (\overline{x_1^{\sigma_1}}\vee \cdots \vee \overline{x_n^{\sigma_n}})= }[/math] [math]\displaystyle{ =\bigwedge_{\substack{(\sigma_1,...,\sigma_n)\\ f(\sigma_1,...,\sigma_n)=0}} (x_1^{\overline{\sigma_1}}\vee \cdots \vee x_n^{\overline{\sigma_n}}). }[/math]

Теперь покажем единственность СКНФ. Действительно, пусть у некоторой функции $f\neq 1$ существовало две различных СКНФ: [math]\displaystyle{ f(x_1,...,x_n) = \bigwedge_{i=1}^s (D_i(x_1,...,x_n))= \bigwedge_{i=1}^{s'} (D_i'(x_1,...,x_n)), }[/math] где $D_i$ и $D_i'$ — дизъюнкты. Возьмем отрицание от функции $f(x_1,...,x_n)$. [math]\displaystyle{ \overline f(x_1,...,x_n) = \overline{\bigwedge_{i=1}^s (D_i(x_1,...,x_n))}= \overline{\bigwedge_{i=1}^{s'} (D_i'(x_1,...,x_n))}. }[/math]

Произведем преобразования по правилам де Моргана и получим [math]\displaystyle{ \overline f(x_1,...,x_n) = \bigvee_{i=1}^s K_i(x_1,...,x_n)= \bigvee_{i=1}^{s'} K_i'(x_1,...,x_n), }[/math] где $K_i=\overline{D_i}$ и $K_i'=\overline{D_i'}$ — конъюнкты, полученные по правилам де Моргана из дизъюнктов СКНФ для функции $f$. Поскольку наборы дизъюнктов $\{D_1,...,D_s\}$ и $\{D_1',...,D_{s'}'\}$ различны, то и полученные наборы конъюнктов $\{K_1,...,K_s\}$ и $\{K_1',...,K_{s'}'\}$ не совпадают. Таким образом, мы получили две различных СДНФ для функции $\overline f$, что противоречит утверждению. Противоречие доказывает единственность СКНФ функции.

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

Из утверждений мы получили формулы, которые удобно использовать для построения СДНФ и СКНФ соответственно.

[math]\displaystyle{ f(x_1,...,x_n) = \bigvee_{\substack{(\sigma_1,...,\sigma_n)\\f(\sigma_1,...,\sigma_n)=1}} x_1^{\sigma_1}\cdots x_n^{\sigma_n}. }[/math] для функции $f\neq 0$.

Теперь для построения СДНФ необходимо выбрать каждый набор $(\sigma_1,...,\sigma_n)$, для которого $f(\sigma_1,...,\sigma_n)=1$, и сопоставить ему конъюнкт $x_1^{\sigma_1}\cdots x_n^{\sigma_n}$ совершенной дизъюнктивной нормальной формы.

Аналогично строится совершенная конъюнктивная нормальная форма по формуле:

[math]\displaystyle{ f(x_1, ..., x_n) = \bigwedge_{\substack{(\sigma_1,...,\sigma_n)\\ f(\sigma_1,...,\sigma_n)=0}} (x_1^{\overline{\sigma_1}}\vee \cdots \vee x_n^{\overline{\sigma_n}}). }[/math] для функции $f\neq 1$.

Пример

Рассмотрим функцию $f(x,y,z)$, заданную таблицей:

[math]\displaystyle{ \begin{array}{ccc|c} x & y & z & f\\ \hline 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 0\\ 0 & 1 & 1 & 0\\ 1 & 0 & 0 & 0\\ 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1\\ 1 & 1 & 1 & 0\\ \end{array} }[/math]

Тогда, СДНФ будет выглядеть следующим образом: [math]\displaystyle{ f(x,y,z) = x^0 y^0 z^0 \vee x^0 y^0 z^1 \vee x^1 y^0 z^1 \vee x^1 y^1 z^0 = }[/math] [math]\displaystyle{ = \overline x \overline y \overline z \vee \overline x \overline y z \vee x \overline y z \vee x y \overline z. }[/math]

СКНФ будет иметь вид: [math]\displaystyle{ f(x,y,z) = (x^{\overline 0} \vee y^{\overline 1} \vee z^{\overline 0}) \wedge (x^{\overline 0} \vee y^{\overline 1} \vee z^{\overline 1}) \wedge (x^{\overline 1} \vee y^{\overline 0} \vee z^{\overline 0}) \wedge (x^{\overline 1} \vee y^{\overline 1} \vee z^{\overline 1})= }[/math] [math]\displaystyle{ (x^{1} \vee y^{0} \vee z^{1}) \wedge (x^{1} \vee y^{0} \vee z^{0}) \wedge (x^{0} \vee y^{1} \vee z^{1}) \wedge (x^{0} \vee y^{0} \vee z^{0})= }[/math]

[math]\displaystyle{ = (x \vee \overline y \vee z) \wedge (x \vee \overline y \vee \overline z) \wedge (\overline x \vee y \vee z) \wedge (\overline x \vee \overline y \vee \overline z). }[/math]

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

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