Основные законы алгебры логики
Основные законы алгебры логики позволяют проводить эквивалентные преобразования логических функций, записанных с помощью операций И, ИЛИ, НЕ, приводить их к удобному для дальнейшего использования виду и упрощать запись.
При выполнении преобразований функций алгебры логики могут быть полезны следующие соотношения:
§ всегда истинны высказывания: x + 1=1; x + x=1;
§ всегда ложны высказывания: x ∙ 0=0; x ∙ x=0;
§ правило двойного отрицания х=х;
§ правило повторения x + x + … + x=x;
x ∙ x ∙ … ∙ x =x.
Переместительный закон:
§ для дизъюнкции x1+x2 = x2+x1;
§ для конъюнкции x1∙x2 = x2∙x1;
§ для суммы по модулю два x1Åx2 = x2Åx1.
Сочетательный закон:
§ для дизъюнкции x1+(x2+x3)=(x1+x2)+x3;
§ для конъюнкции x1∙(x2∙x3)= (x1∙x2)∙x3;
§ для суммы по модулю два x1Å(x2Åx3) = (x1Åx2)Åx3,
то есть группирование переменных внутри дизъюнкции (конъюнкции) не изменяет значений функции.
Распределительный закон:
§ для дизъюнкции x1+x2∙∙x3=(x1+x2)(x1+x3),
то есть дизъюнкция переменной и конъюнкции эквивалентна конъюнкции дизъюнкций этой переменной с сомножителями;
§ для конъюнкции x1∙(x2+x3)= x1∙x2+x1∙x3,
то есть конъюнкция переменной и дизъюнкции равносильна дизъюнкции конъюнкций этой переменной со слагаемыми.
Закон инверсии (правило де Моргана):
§ для дизъюнкции x1+x2=x2 ∙ x1;
§ для конъюнкции x1∙x2=x2+x1,
то есть отрицание дизъюнкции (конъюнкции) переменных равно конъюнкции (дизъюнкции) отрицаний этих переменных.
Правило де Моргана справедливо для любого числа переменных:
x1+x2+…+xn= x1 ∙ x2 ∙ … ∙ xn,
x1∙x2∙…∙xn= x1 + x2 + … ∙ xn.
Переместительный и сочетательный законы для дизъюнкции и конъюнкции, а также распределительный закон для конъюнкции совпадают с законами обычной алгебры. Но в обычной алгебре нет законов, аналогичных распределительному для дизъюнкции и законам инверсии. Их справедливость доказывается посредством составления таблиц истинности для левой и правой частей формулы.
Правило склеивания x1∙x2+x1∙x2=x1.
Следующие соотношения могут быть выведены из рассмотренных выше:
x1+x1∙x2 = x1 ;
x1+x1∙x2 = x1∙1 +x1∙x2 = x1 ∙(1 + x2) = x1∙1 = x1;
x1 ∙(x1+x2) = x1.
Дата добавления: 2016-01-09; просмотров: 854;