Основные законы алгебры логики

В алгебре логики существует четыре пары основных законов:

· два переместительных (коммутативных);

· два сочетательных (ассоциативных);

· два распределительных (дистрибутивных)

· два закона инверсии.

В алгебре логики доказано, что любую логическую функцию можно выразить только через комбинацию логических операций И, ИЛИ и НЕ.

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

Закон тождества. Согласно данному закону мысль, заключенная в некотором высказывании, остается неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует

A = A.

Закон противоречия утверждает, что никакое предложение не может быть истинно одновременно со своим отрицанием: «Это яблоко спелое» и «Это яблоко неспелое»

.

Закон исключенного третьего утверждает, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно, либо ложно; третьего не дано: «Сегодня я либо получу 10, либо не получу». Истинно либо суждение, либо его отрицание

A ∨ = 1.

Закон двойного отрицания заключается в том, что отрицать отрицание какого-нибудь высказывания то же, что утверждать это высказывание: «Неверно, что

2 ∙ 2< >4″

.

Законы идемпотентности утверждают, что в алгебре логики нет показателей степеней и коэффициентов. Конъюнкция одинаковых «сомножителей» равносильна одному из них; дизъюнкция одинаковых «слагаемых» равносильна одному из них:

A ∨ A = A;

A A = A.

Законы коммутативности и ассоциативности заключаются в том, что конъюнкция и дизъюнкция аналогичны одноименным знакам умножения и сложения чисел:

законы коммутативности:

A ∨ B = B ∨ A;

A B = B A;

законы ассоциативности:

(A ∨ B) ∨ C = A ∨ (B ∨ C);

(A B) C = A (B C).

Законы дистрибутивности утверждают, что логическое сложение и умножение равноправны по отношению к дистрибутивности: не только конъюнкция дистрибутивна относительно дизъюнкции, но и дизъюнкция дистрибутивна относительно конъюнкции:

(A ∨ B) C = (A C) ∨ (B C);

(A B) ∨ C = (A ∨ C) (B ∨ C).

Законы де Моргана показывают как отрицаются высказывания:

() = ;

() = ∨ .

Данные законы можно выразить в следующих кратких формулировках:

· отрицание логического произведения эквивалентно логической сумме отрицаний множителей;

· отрицание логической суммы эквивалентно логическому произведению отрицаний слагаемых.

Законы поглощения констант утверждают, что ложь не влияет на значение логического выражения при дизъюнкции, а истина – при конъюнкции:

A ∨ 1 = 1;

A ∨ 0 = A;

A 1 = A;

A 0 = 0.

Законы поглощения показывают, как упрощать логические выражения при повторе операнда: