Законы и тождества булевой алгебры

1. Законы нуля: a 0 = a; a 0 = 0;0 a b c ….= 0.

2. Законы единицы: a 1 = a; a 1 = 1;1 a b c ….=1.

3. Законы повторения: a а = a; aа = a;

a а а а …= a; aааа…= a.

4. Закон двойного отрицания: = a.

5. Законы дополнительности: а = 0; a = 1.

6. Коммутативные законы: ab = ba; a b = b a.

7. Ассоциативные законы: a (bc) = (ab)c = abc;

a (b c) = (a b) c = a b c.

8. Дистрибутивные законы:

а) конъюнкции относительно дизъюнкции:

a (b c) = ab ac; ad(b c) = abd acd;

б) дизъюнкции относительно конъюнкции:

a bc = (a b)(a c); a bc d = (a b d)(a c d);

доказательство: рассмотрим правую частьпервой формулы

(a b)(a c)= aa ac ba bc,

так как aa = a, то a ac = a(1 c) = a и a ab = a(1 b) = a.

Следовательно, (a b)(a c) = aa ac ba bc = a bc.

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

a(a b) = a, доказательство: a(a b) = aa ab = a(1 b) = a1 = a.

a(a b)(a c)…= a;(a b)(a b c) = a b; ab abc = ab.

a( b) = ab;доказательство: a( b) = a ab = 0 ab = ab.

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

ab a = a,доказательство: ab a = a(b ) = a1 = a;

(a b)(a ) = a, доказательство:(a b)(a ) = a = a – см. доказательство дистрибутивного закона 8,б.

11. Законы обобщенного склеивания:(доказательства см. п.4.1.3)

12. Законы де Моргана: ; ;

; .

13. Разложение функций по переменным:

f(a,b,c,…,w) = af(1,b,c,…,w) f(0,b,c,…,w); (1)

f(a,b,c…w) = [a f(0,b,c,…,w)] [ f(1,b,c,…,w)]; (2)

af(a,b,c,…,w) = af(1,b,c,…,w);

a f(a,b,c,…,w) = a f(0,b,c,…,w);

f(a,b,c,…,w) = f(0,b,c,…,w);

f(a,b,c,…,w) = f(1,b,c,…,w).

Законы справедливы и если вместо переменных подставить правильные логические выражения (формулы).

Доказательство наиболее простых законов производится с помощью аксиом, а других с использованием уже доказанных законов.

Доказательство формул типа (1) и (2) производят с помощью подстановок а = 1, = 0, затем а = 0, = 1.

В общем случае для доказательства законов и тождеств в булевой алгебре применяют два подхода:

– первый – с помощью таблиц истинности, которые составляются для левой и правой частей предполагаемого тождества и сравниваются;

– второй – с применением преобразований логических выражений в левой и правой части предполагаемого тождества с помощью уже доказанных законов и тождеств и последующим сравнением результатов.

(Примеры преобразований см. Раздел 7.)

Вопросы для самоконтроля

1. Что такое «алгебра»? Что такое «булева алгебра»?

2. Каковы особенности логических переменных и функций?

3. Приведите аксиомы булевой алгебры.

4. Приведите логические функции одной переменной.

5. Приведите логические функции двух переменных.

6. Сколько может быть полностью определенных логических функций n переменных?

7. Что такое – вырожденная функция? Что такое – фиктивная переменная?

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

9. Приведите структуру таблицы истинности.

10. Как получается инверсная логическая функция?

11. Приведите пример использования приоритетов логических операций.

12. Приведите законы булевой алгебры: нуля и единицы, повторения, дополнительности, коммутативные, ассоциативные и дистрибутивные.

13. Приведите законы поглощения, склеивания и де Моргана.

14. Покажите на примерах разложение логических функций по переменным.

15. Как доказываются тождества в булевой алгебре?