Алгебра логики — определенная часть математической логики, часто называемая исчислением высказываний.
Под высказыванием понимается всякое предложение, в котором содержится смысл утверждения (истинности) или отрицания (ложности). Одно и то же высказывание не может быть одновременно истинным и ложным или не истинным и не ложным. Отдельные высказывания можно обозначить заглавными буквами латинского алфавита А, В,С,... . Если высказывание (суждение) истинно, то, например, А=1. Если С =0, то высказывание С ложно. Рассматриваются только два значения высказывания: истинное или ложное (1 или 0). Такое условие алгебры логики приводит к соответствию между логическими высказываниями в математической логике и двоичными цифрами в двоичной системе счисления, что позволяет описывать работу схем и блоков машины и проводить их анализ и синтез с помощью алгебры логики.
В алгебре логики установлен целый ряд законов, с помощью которых возможно преобразование логических функций:
• коммутативный (переместительный):
• ассоциативный (сочетательный):
Эти законы полностью идентичны законам обычной алгебры;
• дистрибутивный (распределительный):
• закон поглощения.
В дизъюнктивной форме логических функций конъюнкция меньшего ранга, т.е. с меньшим числом переменных, поглощает все конъюнкции большего ранга, если ее изображение содержится в них. Это же справедливо и для конъюнктивных форм:
• законы склеивания:
где F - логическая функция общего вида, не зависящая от переменной х;
• закон свертки:
• правило де Моргана:
• избавление от импликации и эквиваленции:
• избавление от стрелки Пирса:
• избавление от штриха Шеффера:
• избавление от запрета:
• избавление от сложения по модулю 2:
Убедиться в тождественности приведенных зависимостей можно путем аналитических преобразований выражений или путем по строения таблицы истинности для логических функций, находящихся в левой и правой частях.
Используя данные зависимости, можно преобразовывать исходные выражения в более простые (минимизировать их). По упрощенным выражениям можно построить техническое устройство, имеющее минимальные аппаратные затраты.