Дистрибутивность

1 2 3 4 5 6 7

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

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

Отметим также важные соотношения:

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 ₁...x_n) = Ú x₁ ^a & x₂ ^a... & x_n ^a (1.1)

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

Определение. Представление функции алгебры логики в виде (1.1) называется ДСНФ - дизъюнктивной совершенной нормальной формой.

Для построения ДСНФ необходимо выполнить следующие шаги:

· выбрать в таблице истинности заданной функции все наборы аргументов, на которых функция равна 1;

· выписать соответствующие этим наборам конъюнкции, при этом, если аргумент x_i входит в данный набор как 1, то он записывается без изменений, если же, как 0, то берется ;