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

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. – коммутативность связки *, где символ * является общим обозначением для связок (операций) &, Ú, Å, ~, |, ¯.

2. – ассоциативность связки *, где *– общее обозначение для связок &,Ú,Å,~.

3. Дистрибутивность

а) – дистрибутивность конъюнкции относительно дизъюнкции;

б) – дистрибутивность дизъюнкции относительно конъюнкции;

в) – дистрибутивность конъюнкции относительно сложения по mod 2 (по модулю два).

4. а) ; б) суть правила де Моргана;

5. а) ; б) суть правила поглощения;

6. а) ; б) ;

7. а) ; б) ;

в) ; г) ; д) ;

8. а) ;

б) ; в) ;

9. а) ; б) .

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

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.

Принцип двойственности

Определение 1. Функции f*(x₁, ..., x_n) называется двойственной к функции f(x₁, ..., x_n), если f*(x₁, ..., x_n) = ( ₁, ..., _n).

Пример 1. Покажем с помощью таблицы истинности, что константа 0 двойственна к 1:

x	f	f*

Функции f(x) = x и g(x) = двойственны сами себе:

x	f	f*	g	g*

так как f*(0)= (1).

Определение 2. Если f*(x₁, ..., x_n) = f(x₁, ..., x_n), то f(x₁, ..., x_n) называется самодвойственной.

Пример 2.Покажем, что f(x₁,x₂,x₃)=x₁Åx₂Åx₃ – самодвойственна:

x1	x2	x3	f	f*

Если f*– самодвойственна, то ( ₁, ..., _n) = f(x₁, ..., x_n), т.е. на противоположных наборах функция принимает противоположные значения.

Пример 3. Покажем, что функция х₁Úх₂ двойственна к x₁&x₂, функция х₁ х₂ двойственна к функции x₁|x₂.

x1 x2	f=х1Úх2	f*	g=x1|x2	g*=x1 x2
0 0 0 1 1 0 1 1

Теорема о двойственных функциях

Если f* двойственна к f, то f двойственна к f*.