Закони алгебри логіки

1. Закон комутативності (перестановки)

х₁ · х₂ = х₂ · х_1;

х₁ х₂ = х₂ х_1.

2. Закон асоціативності (сполучення)

х₁ ·(х₂ · х₃) = (х₁ ·х₂) · х_3;

х₁ (х₂ х₃) = (х₁ х₂) х_{3 =} х₁ х₂ х_3.

3. Закон дистрибутивності (розподілу)

х₁ · (х₂ х₃) = х₁ · х₂ х₁ · х_3;

х₁ х₂ · х_{3 =} (х₁ х₂) · (х₁ х₃) .

4. Закон склеювання

(х₁ х₂) · (х_{1 2}) = х_1;

х₁ · х₂ х₁ · ₂ = х_1.

5. Закон поглинання

х₁ ·(х₁ х₂) = х_1;

х₁ х₁ · х₂ = х_1.

6. Закон дуальності (правило де Моргана)

= ;

= ·

Доведення 5-го закону (поглинання для кон’юнкції):

х₁ ·(х₁ х₂) = х₁ · х₁ х₁ · х₂ = х₁ (1 х₂) = х_1.

х₁ 1

Доведення закону дистрибутивності для диз’юнкції (3-й закон):

Застосовуючи закон поглинання:

х₁ х₂ · х₃ = х₁· (х₁ х₂ х₃) х₂ · х₃ = х₁· х₁ х₁· х₂ х₁· х₃ х₂· х₃ =

= х₁ ·(х₁ х₃) х₂ ·(х₁ х₃) = (х₁ х₂) ·(х₁ х₃).

Доведення законусклеювання для кон’юнкції:

(х₁ х₂) · (х_{1 2}) = х₁ · х₁ х₁ · ₂ х₁ · х₂ х₂ · ₂ = х₁ х₁(х_{2 2}) = х₁ х₁=х_{1 .}

х₁ 0 1

Поговоримо про закони дуальності.

Правило Шеннона – для одержання алгебраїчного виразу інверсної функції

необхідно у згаданій функції всі змінні замінити на інверсні їм, всі знаки кон’юнкції – на знаки диз’юнкції, а всі знаки диз’юнкції – на знаки кон’юнкції.

Приклад: знайти інверсію логічної функції

Y = x₁ x₁ · x₁ x_3.

Розв’язок:

Правило де Моргана – інверсія кон’юнкції дорівнює диз’юнкції інверсій, а інверсія диз’юнкцій – кон’юнкції інверсій.

Приклад:

Y = = = .

Наслідки законів дуальності

x₁ x₂ =

х₁ · х₂ =

Вони справедливі для будь-якого числа змінних.