1. Идемпотентность & и Ú: х & x = x, x Ú x = x.
2. Коммутативность &, Ú, Å, |, ~, .
3. Ассоциативность &, Ú, Å, ~, поэтому в формулах вида xyz можно не ставить никаких скобок.
4. Дистрибутивность:
а) & по отношению к Ú: x &(y Ú z)= xy Ú xz,
б) Ú по отношению к &: x Ú(y & z)=(x Ú y)&(x Ú z),
в) & по отношению к Å: x (y Å z)= xy Å xz.
5. Инволюция: .
6. Правила де Моргана: = & и = Ú .
7. Законы действия с 0 и 1:
x Ú0= x, x Ú1=1, x &0=0, x &1= x, x Å1= , x Å0= x.
8. Самодистрибутивность импликации:
x (y z)=(x y) (x z) (табл. 12).
Равенство всех этих формул доказывается по определению, т.е. по равенству функций, которые они реализуют.
Проверим для примера самодистрибутивность импликации: x (y z)=(x y) (x z) (табл. 12).
Таблица 12
x | y | z | y z | x (y z) | x y | x z | |
Следствия из свойств элементарных функций
1. Законы склеивания:
xy Ú x = x (y Ú )= x 1= x (дистрибутивность & относительно Ú);
(x Ú y)&(x )= x • y = x Ú 0= x (дистрибутивность Ú относительно &).
2. Законы поглощения:
x Ú xy = x (1Ú y)= x 1= x; x &(x Ú y)= x Ú xy = x.
Свойства элементарных функций позволяют упрощать формулы.
Пример 7. Упростим формулы:
1. x 2 x 3Ú x 1 2 x 3 = x 3(x 2Ú x 1 2) = x 3((x 2Ú x 1)&(x 2Ú 2)) = (x 1Ú x 2) x 3.
2. x 1Ú 1 x 2Ú 1 2 x 3Ú 1 2 x 4 = x 1Ú 1 (x 2Ú 2 x 3Ú 2 3 x 4) =
= (x 1Ú 1)(x 1Ú x 2Ú 2 x 3Ú 2 3 x 4) = x 1Ú x 2Ú 2
= x 1Ú(x 2Ú )(x 2Ú x 3Ú x 4) = x 1Ú x 2Ú x 3Ú x 4.