Некоторые свойства элементарных функций

 

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 Ú =1, x & 0=0, x & 1= x, x & =0, x Å 1= , x Å 0= x.

8. Самодистрибутивность импликации: x (y z)=(x y) (x z).

Равенство всех этих формул доказывается по определению, т.е. по равенству функций, которые они реализуют.

Проверим для примера самодистрибутивность импликации: x (y z)=(x y) (x z).

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.

Свойства элементарных функций и теорема о замене подформул на эквивалентные позволяют упрощать формулы.

Пример 3:

Упростим формулы:

1. x ₂ x ₃Ú x _{1 2} x ₃ = x ₃(x ₂Ú x _{1 2}) = x ₃((x ₂Ú x ₁)& (x ₂Ú ₂)) = (x ₁Ú x ₂) x _3.

2. x ₁Ú ₁ x ₂Ú _{1 2} x ₃Ú _{1 2} x ₃ x ₄ = x ₁Ú ₁(x ₂Ú _{2 3} x ₄) = x ₁Ú ₁(x ₂Ú x ₃Ú _{2 3} x ₄) = (x ₁Ú ₁)(x ₁Ú x ₂Ú x ₃Ú _{2 3} х ₄) = x ₁Ú (x ₂Ú x ₃)Ú () x ₄ = x ₁Ú (x ₂Ú х ₃Ú ())(x ₂Ú x ₃Ú x ₄) = x ₁Ú x ₂Ú x ₃Ú x _4.