Page 50 - ЭВМ

– законы поглощения:

x ∨ 1 x ∧ 1 x = 2 х ;
1
x ∧ ( x ∨ 1 x 2 ) = x .
1
1

– закон идемпотентности дизъюнкции и конъюнкции:

x ∨∨∨∨ ... x = ;
∨
x
x
x
x
x ∧ ∧∧ x ...x = .
x
x
x

На основании правила де-Моргана, пользуясь методом матема-
тической индукции, отрицание любого выражения алгебры логики,
построенного с использованием операций дизъюнкции, конъюнкции
и отрицания, можно получить заменой в исходном выражении аргу-
ментов их отрицаниями и обменом местами символов дизъюнкции
и конъюнкции.
Используя второй закон дистрибутивности и выполняя тождест-

венные преобразования, можно получить

x ∨ 1 1 x ∧ x = 2 x ∨ 1 x .
2

Формы представления булевых функций. В алгебре логики
[1; 3] доказывается, что любую функцию алгебры логики, кроме
0
функции f = , можно представить в виде формулы через конъюнк-
цию, дизъюнкцию и отрицание в виде

σ
σ
z = f ( 1 2 , ,..., x R ,..., x n ) , x x = ∨ x x 2 σ 2 ...x σ R R ...x , (2.1)
x
n
1
3
n
1

σ
где x R R – общее обозначение для аргумента x R и его отрицания x ,
R
⎧ x при σ= 1
σ
причем x R R = ⎨ R R .
⎩ x R при σ= 0
R
Логическое суммирование в формуле (2.1) ведется для тех набо-
ров σ 1, σ 2, K, σ R, σ n, для которых f (x 1, x 2, K, x R, x n) = 1. Представление
функции алгебры логики в форме (2.1) называется совершенной
дизъюнктивной нормальной формой (СДНФ). Члены, входящие
в СДНФ, называются дизъюнктивными членами или конституентами
единицы.
Для таблично заданной булевой функции СДНФ строится сле-
дующим образом: выписываются из таблицы те наборы, для которых
функция равна единице, для каждого выписанного набора составляет-
σ
σ
σ
ся конъюнкция x , x , K, x . Соединяя полученные конъюнкции
2
1
n
1
2
n
знаком дизъюнкции, получается СДНФ искомой функции.
50