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

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

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

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

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

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

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

x₁ ∙(x₁x₂) = x₁.