Изменения
ДНФ
,Нет описания правки
'''Док-во :''' Для любой булевой функции выполняется следующее соотношение
<math>f(\vec{x}) = \overline x_i \bigwedge wedge f(x_1,..,x_{i-1},0,x_{i+1},..,x_n) \bigveeveex_i \bigwedge wedge f(x_1,..,x_{i-1},1,x_{i+1},x_n)</math>
Данное соотношение легко проверить подстановкой всевозможных значений x<sub>i</sub>(0 и 1). Эта формула позволяет выносить x<sub>i</sub> за знак функции. Последовательно вынося x<sub>1</sub>, x<sub>2</sub>,.., x<sub>n</sub> за знак <math>f(\vec{x})</math>, получаем следующую формулу :
<math> f(\vec{x}) = \overline x_1 \bigwedge wedge \overline x_2 \bigwedge wedge ...\bigwedge wedge \overline x_{n-1} \bigwedge wedge \overline x_n \bigwedge wedge f(0,0,...,0,0)~\bigveevee~</math>
<math>\overline x_1 \bigwedge wedge \overline x_2 \bigwedge wedge ... \bigwedge wedge \overline x_{n-1} \bigwedge wedge x_n \bigwedge wedge f(0,0,...,0,1) ~\bigveevee~</math>
<math>... </math>
<math>~\bigveevee~ x_1 \bigwedge wedge x_2 \bigwedge wedge ... \bigwedge wedge x_{n-1} \bigwedge wedge \overline x_n \bigwedge wedge f(1,1,...,1,0) ~\bigveevee~</math>
<math>x_1 \bigwedge wedge x_2 \bigwedge wedge ... \bigwedge wedge x_{n-1} \bigwedge wedge x_n \bigwedge wedge f(1,1,...,1) </math>
Т.к применение данного соотношения к каждой из переменных увеличивает количество дизъюнктивных членов в два раза, то для функции от n переменных мы имеем 2<sup>n</sup> дизъюнктивных членов. Каждый из них соответствует значению функции на одном из 2<sup>n</sup> возможных наборов значений n переменных. Если на некотором наборе <math>f(\vec{x})=0</math>, то весь соответствующий дизъюнктивный член также равен 0 и из представления данной функции его можно исключить. Если же <math> f(\vec{x})=1</math>, то в соответствующем дизъюннктивном члене само значение функции можно опустить. В результате для произвольной функции была построена '''СДНФ'''.
