Изменения
ДНФ
,Нет описания правки
==Канонические формы логических формул==
Любая логическая формула задает некоторую [[булева функция|булеву функцию]]. Но для всякой [[булева функция|булевой функции]] можно привести бесконечно много формул ее представляющих. Одной из задач алгебры логики является построение '''канонических форм'''(т.е формул построенных по определенному правилу).
{{Определение
{{Теорема
|statement=
Для любой булевой функции <tex>f(\vec{x})</tex>, не равной тождественному нулю, существует '''СДНФ''', ее задающая.
|proof =
Для любой булевой функции выполняется следующее соотношение, называемое '''разложением Шеннона'''.
<tex>f(\vec{x}) = \overline 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 x_1 \wedge \overline x_2 \wedge ...\wedge \overline x_{n-1} \wedge \overline x_n \wedge f(0,0,...,0,0)~\vee~</tex>
<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> возможных наборов значений n переменных. Если на некотором наборе <tex>f(\vec{x})=0</tex>, то весь соответствующий дизъюнктивный член также равен нулю и из представления данной функции его можно исключить. Если же <tex> f(\vec{x})=1</tex>, то в соответствующем дизъюннктивном члене само значение функции можно опустить. В результате для произвольной функции была построена '''СДНФ'''.
}}
==Алгоритм построения СДНФ по таблице истинности==
