Изменения
ДНФ
,→СДНФ
}}
Пример СДНФ:
<tex>f(x,y,z) = (x \land \overlineneg {y} \land z) \lor (x \land y \land \overlineneg {z})</tex>
{{Теорема
|statement=
Для любой булевой функции <tex>f(\overlineneg {x})</tex>, не равной тождественному нулю, существует СДНФ, ее задающая.
|proof =
Для любой булевой функции выполняется следующее соотношение, называемое '''разложением Шеннона'''.
<tex>f(\vec{x}) = \overline neg x_i \wedge f(x_1,..,x_{i-1},0,x_{i+1},..,x_n) \vee
x_i \wedge f(x_1,..,x_{i-1},1,x_{i+1},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}) = \overline neg x_1 \wedge \overline neg x_2 \wedge ...\wedge \overline neg x_{n-1} \wedge \overline neg x_n \wedge f(0,0,...,0,0)~\vee~</tex>
<tex>\overline neg x_1 \wedge \overline neg x_2 \wedge ... \wedge \overline neg x_{n-1} \wedge x_n \wedge f(0,0,...,0,1) ~\vee~</tex>
<tex>... </tex>
<tex>~\vee~ x_1 \wedge x_2 \wedge ... \wedge x_{n-1} \wedge \overline neg x_n \wedge f(1,1,...,1,0) ~\vee~</tex>
<tex>x_1 \wedge x_2 \wedge ... \wedge x_{n-1} \wedge x_n \wedge f(1,1,...,1) </tex>
