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

 

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(yz)=(xy) (xz).

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

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

x	y	z	yz	x(yz)	xy	xz

 

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

 

1. Законы склеивания:

xyÚx=x(yÚ)=x1=x (дистрибутивность & относительно Ú);

(xÚy)&(x)=xy =xÚ 0=x (дистрибутивность Ú относительно &).

2. Законы поглощения:

xÚxy=x(1Úy)=x1=x; x&(xÚy)=xÚxy=x.

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

Пример 3:

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

1. x₂x₃Úx₁₂x₃ = x₃(x₂Úx₁₂) = x₃((x₂Úx₁)&(x₂Ú₂)) = (x₁Úx₂)x_3.

2. x₁Ú₁x₂Ú₁₂x₃Ú₁₂x₃x₄ = x₁Ú₁(x₂Ú₂₃x₄) = x₁Ú₁(x₂Úx₃Ú₂₃x₄) = (x₁Ú₁)(x₁Úx₂Úx₃Ú₂₃х₄) = x₁Ú(x₂Úx₃)Ú()x₄ = x₁Ú(x₂Úх₃Ú())(x₂Úx₃Úx₄) = x₁Úx₂Úx₃Úx_4.