Ассоциативность
Коммутативность
x1 & x2 = x2 & x1.
x1 v x2 = x2 v x1.
x1 v (x2 v x3) = (x1 v x2) v x3.
x1 & (x2 & x3) = (x1 & x2) & x3.
x1 & (x2 v x3) = (x1 & x2) v (x1 & x3).
x1 v (x2 & x3) = (x1 v x2) & (x1 v x3 ).
Отметим также важные соотношения:
X v X = X, X & X = X, X v 1 = 1, X & 1 = X,
X v 0 = X, X & 0 = 0, X v ØX = 1, X & ØX = 0.
Положим x a = { X, если a = 1; ØX, если a = 0 }.
Утверждение. Любая функция алгебры логики кроме 0 может быть представлена в форме
f(x 1...xn) = Ú x1 a & x2 a... & xn a (1.1)
При этом дизъюнкция в правой части берется только по тем наборам аргументов, на которых функция, заданная таблично, обращается в 1.
Определение. Представление функции алгебры логики в виде (1.1) называется ДСНФ - дизъюнктивной совершенной нормальной формой.
Для построения ДСНФ необходимо выполнить следующие шаги:
· выбрать в таблице истинности заданной функции все наборы аргументов, на которых функция равна 1;
· выписать соответствующие этим наборам конъюнкции, при этом, если аргумент xi входит в данный набор как 1, то он записывается без изменений, если же, как 0, то берется ;
|
|
· все полученные конъюнкции объединяются под знаком дизъюнкции.