1632
правки
Изменения
ДНФ
,rollbackEdits.php mass rollback
{{Определение
|definition =
'''Совершенная дизъюнктивная нормальная форма, СДНФ''' (англ. ''perfect disjunctive normal form, PDNF'') — это ДНФ, удовлетворяющая условиям:
* в ней нет одинаковых простых конъюнкций,
* каждая простая конъюнкция полная.
Для любой булевой функции выполняется следующее соотношение, называемое '''разложением Шеннона''':
<tex>f(\vec{x}) = \neg x_i \wedge f(x_1, \dots ldots ,x_{i-1},0,x_{i+1}, \dots ldots ,x_n) \veex_i \wedge f(x_1, \dots ldots ,x_{i-1},1,x_{i+1}, \dots ldots ,x_n)</tex>.
Данное соотношение легко проверить подстановкой возможных значений <tex>x_i</tex> (<tex>0</tex> и <tex>1</tex>). Эта формула позволяет выносить <tex>x_i</tex> за знак функции. Последовательно вынося <tex>x_1</tex>, <tex>x_2</tex>,.., <tex>x_n</tex> за знак <tex>f(\vec{x})</tex>, получаем следующую формулу:
<tex> f(\vec{x}) = \neg x_1 \wedge \neg x_2 \wedge ...\ldots \wedge \neg x_{n-1} \wedge \neg x_n \wedge f(0,0,...\ldots,0,0)~\vee~</tex>
<tex>\neg x_1 \wedge \neg x_2 \wedge ... \ldots \wedge \neg x_{n-1} \wedge x_n \wedge f(0,0,...\ldots,0,1) ~\vee~ \\\dots ldots \\~\vee~ x_1 \wedge x_2 \wedge ... \ldots \wedge x_{n-1} \wedge \neg x_n \wedge f(1,1,...\ldots,1,0) ~\vee~\\ x_1 \wedge x_2 \wedge ... \ldots \wedge x_{n-1} \wedge x_n \wedge f(1,1,...\ldots,1) </tex>
Так как применение данного соотношения к каждой из переменных увеличивает количество конъюнктов в два раза, то для функции от <tex>n</tex> переменных мы имеем <tex>2^n</tex> конъюнктов. Каждый из них соответствует значению функции на одном из <tex>2^n</tex> возможных наборов значений <tex> n </tex> переменных. Если на некотором наборе <tex>f(\vec{x})=0</tex>, то весь соответствующий конъюнкт также равен нулю и из представления данной функции его можно исключить. Если же <tex> f(\vec{x})=1</tex>, то в соответствующем конъюнкте само значение функции можно опустить. В результате для произвольной функции была построена СДНФ.
== Пример построения СДНФ для медианы==
=== Построение СДНФ для медианы от трех аргументов ===
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex> 1 </tex>.
<tex> \langle x,y,z \rangle = (x \land y \land z) \lor (\neg {x} \land y \land z) \lor (x \land \neg {y} \land z) \lor (x \land y \land \neg {z})</tex>.
=== Построение СДНФ для медианы от пяти аргументов ===
{| class="wikitable" style="width:16cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
|<tex> x_1 </tex>||<tex> x_2 </tex>||<tex> x_3 </tex>||<tex>x_4</tex>||<tex> x_5 </tex>||<tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle </tex> ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 0 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 1 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 1 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 0 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 1 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 1 || 1 || 1 || 1 || <tex>(\neg {x_1} \land \neg {x_2} \land x_3 \land x_4 \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 0 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 1 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 0 || 1 || 1 || 1 || <tex>(\neg {x_1} \land x_2 \land \neg {x_3} \land x_4 \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 1 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 0 || 1 || 1 || <tex>(\neg {x_1} \land x_2 \land x_3 \land \neg {x_4} \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 1 || 0 || 1 || <tex>(\neg {x_1} \land x_2 \land x_3 \land x_4 \land \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 1 || 1 || 1 || <tex>(\neg {x_1} \land x_2 \land x_3 \land x_4 \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 0 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 1 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 0 || 1 || 1 || 1 || <tex>(x_1 \land \neg {x_2} \land \neg {x_3} \land x_4 \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 1 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 0 || 1 || 1 || <tex>(x_1 \land \neg {x_2} \land x_3 \land \neg {x_4} \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 1 || 0 || 1 || <tex>(x_1 \land \neg {x_2} \land x_3 \land x_4 \land \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 1 || 1 || 1 || <tex>(x_1 \land \neg {x_2} \land x_3 \land x_4 \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 0 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 0 || 1 || 1 || <tex>(x_1 \land x_2 \land \neg {x_3} \land \neg {x_4} \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 1 || 0 || 1 || <tex>(x_1 \land x_2 \land \neg {x_3} \land x_4 \land \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 1 || 1 || 1 || <tex>(x_1 \land x_2 \land \neg {x_3} \land x_4 \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 0 || 0 || 1 || <tex>(x_1 \land x_2 \land x_3 \land \neg {x_4} \land \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 0 || 1 || 1 || <tex>(x_1 \land x_2 \land x_3 \land \neg {x_4} \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 1 || 0 || 1 || <tex>(x_1 \land x_2 \land x_3 \land x_4 \land \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 1 || 1 || 1 || <tex>(x_1 \land x_2 \land x_3 \land x_4 \land x_5)</tex>
|}
<tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle = (\overline {x_1} \land \overline {x_2} \land x_3 \land x_4 \land x_5) \lor (\overline {x_1} \land x_2 \land \overline {x_3} \land x_4 \land x_5) \lor (\overline {x_1} \land x_2 \land x_3 \land \overline {x_4} \land x_5) \lor (\overline {x_1} \land x_2 \land x_3 \land x_4 \land \overline {x_5}) \lor (\overline {x_1} \land x_2 \land x_3 \land x_4 \land x_5) \lor (x_1 \land \overline {x_2} \land \overline {x_3} \land x_4 \land x_5) \lor (x_1 \land \overline {x_2} \land x_3 \land \overline {x_4} \land x_5) \lor (x_1 \land \overline {x_2} \land x_3 \land x_4 \land \overline {x_5}) \lor (x_1 \land \overline {x_2} \land x_3 \land x_4 \land x_5) \lor (x_1 \land x_2 \land \overline {x_3} \land \overline {x_4} \land x_5) \lor (x_1 \land x_2 \land \overline {x_3} \land x_4 \land \overline {x_5}) \lor (x_1 \land x_2 \land \overline {x_3} \land x_4 \land x_5) \lor (x_1 \land x_2 \land x_3 \land \overline {x_4} \land \overline {x_5}) \lor (x_1 \land x_2 \land x_3 \land \overline {x_4} \land x_5) \lor (x_1 \land x_2 \land x_3 \land x_4 \land \overline {x_5}) \lor (x_1 \land x_2 \land x_3 \land x_4 \land x_5)</tex>.
==Примеры СДНФ для некоторых функций==
Исключающее или: <tex> x \oplus y \oplus z = (\overline{x} \land \overline{y} \land z) \lor (\overline{x} \land y \land \overline{z}) \lor (x \land \overline{y} \land \overline{z}) \lor (x \land y \land z)</tex>.
== См. также ==
