Логические (булевы) функции основные логические функции

Теорема. Если булева функция не равна тождественному нулю, то ее можно представить в виде СДНФ по ее таблице истинности следующим образом: берем только те наборы переменных(х₁,х_2, …,х_n), для которых f(х₁,х₂, …,х_n) =1, и составляем простую конъюнкцию для этого набора так: если х_i = 0, то берем в этой конъюнкции  , если х_i = 1, то берем х_i. Составляядизъюнкцию этих простых конъюнкций, придем к СДНФ.
Доказательство. Пусть f(x_1,x₂,…,x_n) не равна тождественному нулю, тогда в дизъюнкции можно не записывать слагаемые, равные нулю, а из формулы (* ) следует следующее представление для данной функции

Запись означает, что дизъюнкция берется по всем наборам ( ₁, __n) , для которых f ( ₁, __n) = 1. Так как   (если ₁=0), из формулы (**) следует утверждение теоремы.
Следствие. Любую логическую (булеву) функцию можно выразить через три логические функции: конъюнкцию, дизъюнкцию и отрицание.
Из предыдущей теоремы видно, что следствие верно для любой функции, не равной тождественному нулю. Однако если f(x₁, x₂,…, x_{n) =}0, то ее также можно выразить через конъюнкцию, дизъюнкцию и отрицание, например, так: f(x₁, x₂,…, x_{n) = x1} ,и, несмотря на то, что последнее выражение не является простой конъюнкцией (и, значит, не является СДНФ), тем не менее тождественный ноль также выражен через нужные три функции.
Набор функций, через которые можно выразить любые другие функции, называется полным набором (более точные формулировки даны в разд. 7). Таким образом, конъюнкция, дизъюнкция иотрицание являются полным набором.
По аналогии с представлением любой функции (не равной тождественному нулю) в виде СДНФ можно функцию (не равную тождественной 1) представить в виде СКНФ: простая дизъюнкциясоставляется для тех наборов переменных (х₁, х₂, …, х_п), для которых f(x₁, x₂,…, x_n) = 0, причем если х_i = 1, то в этой дизъюнкции берем  _, если же х_i = 0, то берем х_i.