Изменения

==Теорема об СДНФ==

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

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

==Алгоритм построения СДНФ по таблице истинности==

# В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 1.

# Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу : если значение некоторой переменной есть 1, то в конъюнкцию включаем саму переменную, иначе ее отрицание.

# Все полученные конъюнкции связываем операциями дизъюнкции.