СВ: Новая страница: «{{Определение |definition=Формула вида $x_{i_1}^{\sigma_{i_1}} x_{i_2}^{\sigma_{i_2}} \cdots x_{i_k}^{\sigma_{i_k}}$ , где $x_{...»

2026-10-24T19:56:12Z

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

Новая страница

{{Определение
|definition=Формула вида <math>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$, называется конъюнктом.
}}

{{Определение
|definition=Если $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$ представлена в совершенной дизъюнктивной нормальной форме (СДНФ).
}}

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

{{Утверждение
|statement=Пусть $f(x_1,...,x_n)\in P_2$.
Если $f\neq 0$, то она представима в виде СДНФ, причем единственным образом (с точностью до перестановки конъюнктов).
|proof=Во-первых, отметим, что разложение функции $f$ по всем переменным будет представлять собой СДНФ. Существование доказано.

Докажем единственность СДНФ.
Пусть
<math>
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>
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>
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>
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$.
Противоречие доказывает, что двух различных представлений функции в СДНФ
существовать не может.
}}

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

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

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

СВ: Новая страница: «{{Определение |definition=Формула вида x_{i_1}^{\sigma_{i_1}} x_{i_2}^{\sigma_{i_2}} \cdots x_{i_k}^{\sigma_{i_k}}, где $x_{...»

СВ: Новая страница: «{{Определение |definition=Формула вида $x_{i_1}^{\sigma_{i_1}} x_{i_2}^{\sigma_{i_2}} \cdots x_{i_k}^{\sigma_{i_k}}$ , где $x_{...»