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

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 ₃ – самодвойственна:

x 1	x 2	x 3	f	f *

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

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

 

x 1 x 2	f = х 1Ú х 2	f *	g = x 1| x 2	g *= x 1 x 2
0 0 0 1 1 0 1 1

 

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

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