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

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

При выполнении преобразований функций алгебры логики могут быть полезны следующие соотношения:

§ всегда истинны высказывания: x + 1=1; x + x=1;

§ всегда ложны высказывания: x ∙ 0=0; x ∙ x=0;

§ правило двойного отрицания х=х.

Переместительный закон:

§ для дизъюнкции x₁+x₂ = x₂+x₁;

§ для конъюнкции x₁∙x₂ = x₂∙x₁;

§ для суммы по модулю два x₁Åx₂ = x₂Åx₁;

Сочетательный закон

§ для дизъюнкции x₁+(x₂+x₃)=(x₁+x₂)+x₃;

§ для конъюнкции x₁∙(x₂∙x₃)= (x₁∙x₂)∙x₃;

§ для суммы по модулю два x₁Å(x₂Åx₃) = (x₁Åx₂)Åx₃;

то есть группирование переменных внутри дизъюнкции (конъюнкции) не изменяет значений функции.

Распределительный закон:

§ для дизъюнкции x₁+x_2∙∙x₃=(x₁+x₂)(x₁+x₃);

то есть дизъюнкция переменной и конъюнкции эквивалентна конъюнкции дизъюнкций этой переменной с сомножителями;

§ для конъюнкции x₁∙(x₂+x₃)= x₁∙x₂+x₁∙x₃;

то есть конъюнкция переменной и дизъюнкции равносильна дизъюнкции конъюнкций этой переменной со слагаемыми.

Закон инверсии (правило де Моргана):

§ для дизъюнкции x₁+x₂=x₂ ∙ x₁;

§ для конъюнкции x₁∙x₂=x₂+x₁;

то есть отрицание дизъюнкции (конъюнкции) переменных равно конъюнкции (дизъюнкции) отрицаний этих переменных.

Правило де Моргана справедливо для любого числа переменных

x₁+x₂+…+x_n= x₁ ∙ x₂ ∙ … ∙ x_n,

x₁∙x₂∙…∙x_n= x₁ + x₂ + … ∙ x_n.

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

Правило склеивания x₁∙x₂+x₁∙x₂=x₁ ;

Следующие соотношения могут быть выведены из рассмотренных выше:

x₁+x₁∙x₂ = x₁ ;

x₁+x₁∙x₂ = x₁∙1 +x₁∙x₂ = x₁ ∙(1 + x₂) = x₁∙1 = x₁;

x₁ ∙(x₁+x₂) = x₁;