Свойства конъюнкции, дизъюнкции и отрицания

Функции конъюнкции и дизъюнкции обладают рядом свойств, аналогичных свойствам обычных операций умножения и сложения. Легко убедится в том, что для этих функций выполняются сочетательный

x₁&(x₂&x₃)= (x₁&x₂)&x₃,

x₁ (x₂ x₃)= (x₁ x₂) x₃,

переместительный

x₁ x₂= x₁ x₂,

x₁& x₂= x₁&x₂,

и распределительный законы. Кроме того, выполняется распределительный закон дизъюнкции относительно конъюнкции.

x₁ (x₂&x₃)= (x₁ x₂)& (x₁ x₃).

Проверим справедливость этого закона путем сравнения таблиц для функций, стоящих в левой и правой частях рассматриваемого соотношения.

x 1	x 2	x 3	x2&x3	x1 (x2&x3)

x 1	x 2	x 3	x1 x2	x1 x3	(x1 x2)& (x1 x3)

Совпадение построенных таблиц доказывает наше утверждение.

Рассмотрим теперь ряд простых, но весьма важных соотношений

х х=х;

х&х=х.

х 1=1; х 0=х; х =1;

х&1=х. х&0=0. х& =0.

И как следствие получаем

х х … х=х,

х&х&…&х=х.

Как обобщение формул получаем следующие формулы, называемые формулами (законами) де Моргана

х₁ х₂ … х_n= ;

х₁&х₂&…&х_n= .