Изменения
ДНФ
,→СДНФ
<tex>x_1 \wedge x_2 \wedge ... \wedge x_{n-1} \wedge x_n \wedge f(1,1,...,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>, то в соответствующей конъюнкции соответствующем конъюнкте само значение функции можно опустить. В результате для произвольной функции была построена СДНФ.
}}
