Конъюнктивная нормальная форма - История изменений

СВ: Новая страница: «{{Определение |definition= Формула вида $x_{i_1}^{\sigma_{i_1}} \vee x_{i_2}^{\sigma_{i_2}} \vee \cdots \vee x_{i_k}^{\sigma_{i_k}}$
2026-10-24T19:59:54Z

Новая страница: «{{Определение |definition= Формула вида <math>x_{i_1}^{\sigma_{i_1}} \vee x_{i_2}^{\sigma_{i_2}} \vee \cdots \vee x_{i_k}^{\sigma_{i_k}}</ma...»

Новая страница
{{Определение
|definition=
Формула вида <math>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$, называется дизъюнктом.
}}
{{Определение
|definition=
Если $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$ представлена в совершенной конъюнктивной нормальной форме (СКНФ).
}}
Так же используют обозначения к.н.ф. и с.к.н.ф.
{{Утверждение
|statement=Пусть $f(x_1,...,x_n)\in P_2$.
Если $f\neq 1$, то она представима в виде СКНФ, причем единственным образом (с точностью до перестановки дизъюнктов).
|proof=
Поскольку $f\neq 1$, то $\overline f\neq 0$.
Тогда у функции $\overline f$ существует СДНФ, которая имеет вид:
<math>
\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>
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>
= \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>
=\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>
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>
\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>
\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>
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>
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$.

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

<math>
\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>
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>
=
\overline x \overline y \overline z \vee
\overline x \overline y z \vee
x \overline y z \vee
x y \overline z.
</math>

СКНФ будет иметь вид:
<math>
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>
(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>
=
(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>
}}

[[Файл:p37-01-table-to-sdnf-skpnf.svg|frame|none|900px|alt=Таблица истинности с подсветкой строк f = 1 и f = 0, правила построения конъюнктов и дизъюнктов, внизу СДНФ и СКНФ из четырёх членов|Рис. 1. Строки с <math>f=1</math> дают конъюнкты СДНФ, строки с <math>f=0</math> — дизъюнкты СКНФ, причём в СКНФ литералы инвертируются. Для функции из примера получаются обе формы; зелёные строки — четыре единицы, оранжевые — четыре нуля.]]

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