Изменения

Формула <mathtex>f(\vec{x})</mathtex> от n переменных называется '''совершенно дизъюктивной нормальной формой(СДНФ)''', если она обладает следующими свойствами :

# <mathtex>f(\vec x)</mathtex> является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция n переменных <tex>x_1</tex>, x<subtex>2x_2</subtex>,...,x<subtex>nx_n</subtex>, причем на i-ом месте этой конъюнкции стоит i-ый терм.

'''Теорема''' : Для любой булевой функции <mathtex>f(\vec{x})</mathtex>, не равной тождественному нулю, существует СДНФ, ее задающая.

<mathtex>f(\vec{x}) = \overline x_i \wedge f(x_1,..,x_{i-1},0,x_{i+1},..,x_n) \veex_i \wedge f(x_1,..,x_{i-1},1,x_{i+1},x_n)</mathtex>

Данное соотношение легко проверить подстановкой всевозможных значений x<subtex>ix_i</subtex>(0 и 1). Эта формула позволяет выносить x<subtex>ix_i</subtex> за знак функции. Последовательно вынося x<subtex>1x_1</subtex>, x<subtex>2x_2</subtex>,.., x<subtex>nx_n</subtex> за знак <mathtex>f(\vec{x})</mathtex>, получаем следующую формулу : <mathtex> f(\vec{x}) = \overline x_1 \wedge \overline x_2 \wedge ...\wedge \overline x_{n-1} \wedge \overline x_n \wedge f(0,0,...,0,0)~\vee~</mathtex>

<mathtex>\overline x_1 \wedge \overline x_2 \wedge ... \wedge \overline x_{n-1} \wedge x_n \wedge f(0,0,...,0,1) ~\vee~</mathtex>

<mathtex>... </mathtex>

<mathtex>~\vee~ x_1 \wedge x_2 \wedge ... \wedge x_{n-1} \wedge \overline x_n \wedge f(1,1,...,1,0) ~\vee~</mathtex>

<mathtex>x_1 \wedge x_2 \wedge ... \wedge x_{n-1} \wedge x_n \wedge f(1,1,...,1) </mathtex>

Т.к применение данного соотношения к каждой из переменных увеличивает количество дизъюнктивных членов в два раза, то для функции от n переменных мы имеем 2ⁿ дизъюнктивных членов. Каждый из них соответствует значению функции на одном из 2ⁿ возможных наборов значений n переменных. Если на некотором наборе <mathtex>f(\vec{x})=0</mathtex>, то весь соответствующий дизъюнктивный член также равен 0 и из представления данной функции его можно исключить. Если же <mathtex> f(\vec{x})=1</mathtex>, то в соответствующем дизъюннктивном члене само значение функции можно опустить. В результате для произвольной функции была построена '''СДНФ'''.