Постулаты и основные законы булевой алгебры

Алгебра Буля, как любая математическая наука, базируется на нескольких аксиомах, или постулатах.

1. Если x ≠ 1, то = 0; если x ≠ 0, то = 1 (аксиома взаимоисключения).

2. 0 Ù 0 = 0; 0 Ú 0 = 0.

3. 0 Ù 1 = 0; 0 Ú 1 = 1; (1 Ù 0 = 0; 1 Ú 0 = 1).

4. 1 Ù 1 = 1; 1 Ú 1 = 1.

5. ; (инверсии).

6. ; (двойной инверсии).

В качестве основных законов алгебры Буля чаще других используют следующие (законы и теоремы приведены без доказательств).

1. Нулевого множества: 0 Ù a = 0; 0 Ù a Ù b Ù … Ù x = 0;

0 Ú a = a

2. Универсального множества: 1 Ù a = a;

1 Ú a = 1; 1 Ú a Ú b Ú c Ú…Ú x = 1;

3. Идемпотентности (повторения): a Ù a Ù a Ù … Ù a = a;

a Ú a Ú a Ú …Ú a = a;

4. Дополнительности (противоречия): a Ù = 0; a Ú = 1;

5. Двойной инверсии: = a;

6. Коммутативности (переместительный): a Ú b = b Ú a;

a Ù b = b Ù a;

7. Ассоциативности (сочетательный): a Ù (b Ù c) = (a Ù b) Ù c;

a Ú (b Ú c) = (a Ú b) Ú c;

8. Д истрибутивности (распределительный): a Ù (b Ú c) = (a Ù b) Ú (a Ù c);

a Ú (b Ù c) = (a Ú b) Ù (a Ú c);

9. Поглощения: a Ú (a Ù b) = a;

a Ù (a Ú b) = a;

10. Склеивания: (a Ù b) Ú (a Ù ) = a;

(a Ú b) Ù (a Ù ) = a;

a Ù (Ú b) = a Ù b;

a Ú (Ù b) = a Ú b;

11. Инверсии (теорема де Моргáнa): ;

;

12. Теорема Шеннона: для того, чтобы получить инверсию некоторой ФАЛ, необходимо взять инверсии переменных и заменить операции дизъюнкции на конъюнкции и наоборот:

если существует Y = f (a,b,c,...,x, Ù, Ú), то =f(,,…, ,Ú, Ù)..

13. Разложения: f (a,b,c,...,x) = [a Ù f (1,b,c,...,x)] Ú [Ù f (0,b,c,...,x)];

f (a,b,c,...,x) = [a Ú f (0,b,c,...,x)] Ù [Ú f (1,b,c,...,x)].

Законы и теоремы булевой алгебры необходимы для преобразования и упрощения логических функций, для доказательства тождественности и равносильности функций, а также для представления булевых функций в различных формах.

Дата добавления: 2014-01-07