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

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

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

• всегда истинны высказывания: 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₃;

• для суммы по модулю два 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₁;