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

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.