Основные сведения из алгебры логики - часть 3

В общем случае операция конъюнкции может быть определена для любого числа аргументов: х1 & х2 & ... =

106

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

В алгебре логики действуют четыре основных закона: переместительный (коммутативный), сочетательный (ассоциативный), распределительный (дистрибутивный) и общей инверсии (правило или формула де Моргана). Приведем соотношения, отражающие эти законы.

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

• - для дизъюнкции х1 ? х2 = x2 ? х1;
• - для конъюнкции х1 & х2 = х2 & х1.

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

• - для дизъюнкции (х1 ? x2) ? x3 = х1 ? (x2 ? x3);
• - для конъюнкции (х1 & x2) & x3 = х1 & (x2 & x3).

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

• - для дизъюнкции (x1 ? x2) & x3 = х1 & х3 ? x2 & х3;
• - для конъюнкции (x1 & x2) ? x3 = (х1 ? х3) & (x2 ? х3).

4. Закон общей инверсии (формула де Моргана):

• - для дизъюнкции х1 ? х2 = х1 & х2;
• - для конъюнкции х1 & х2 = х1 ? х2.

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

Докажем, например, справедливость формул де Моргана для дизъюнкции и конъюнкции. С этой целью составим таблицу для четырех наборов переменных x1 и х2, а затем в столбцах этой таблицы вычислим по соответствующим правилам алгебры логики значения левых и правых частей доказываемых формул. Полученные результаты сведем в таблицу.

107