Некоторые свойства элементарных функций
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 Ú 8. Самодистрибутивность импликации: x Равенство всех этих формул доказывается по определению, т.е. по равенству функций, которые они реализуют. Проверим для примера самодистрибутивность импликации: x
Следствия из свойств элементарных функций
1. Законы склеивания: xy Ú x (x Ú y)& (x 2. Законы поглощения: x Ú xy = x (1Ú y)= x Свойства элементарных функций и теорема о замене подформул на эквивалентные позволяют упрощать формулы. Пример 3: Упростим формулы: 1. x 2 x 3Ú x 1 2. x 1Ú
|
.
= х.
= 
& 
и 
= 
.
=1, x & 0=0, x & 1= x, x & 
=0, x Å 1= 
(y 
= x (y Ú 
)= x 
1= x (дистрибутивность & относительно Ú);
)= x 
y = x Ú 0= x (дистрибутивность Ú относительно &).
2) = x 3((x 2Ú x 1)& (x 2Ú 
1 x 2Ú 
1 
2 x 3Ú 
1 
2 x 3 x 4 = x 1Ú 
1(x 2Ú x 3Ú 
2 
2 
3 х 4) = x 1Ú (x 2Ú x 3)Ú (
) x 4 = x 1Ú (x 2Ú х 3Ú (
))(x 2Ú x 3Ú x 4) = x 1Ú x 2Ú x 3Ú x 4.
