Логические выражения и их преобразования

Результат вычисления логической функции можно использовать в качестве одного из аргументов другой функции, причём результат этой суперпозиции можно рассматривать как новую логическую функцию со своей таблицей истинности.

В выражении, записанном без использования скобок, первыми выполняются отрицания, затем – логические умножения и только после этого – логические сложения. Операции, записанные в скобках, выполняются вне очереди по отношению к операциям вне скобок.

Основные теоремы алгебры логики. Здесь x – это некоторая логическая переменная, принимающая значения 0 или 1.

• Логические операции с константами:

  x & 1 = x, x & 0 = 0;

• Теорема о тавтологии (повторении):

  x & x = x;

• Теорема о противоречии:
• Правило исключённого третьего:
• Теорема об инволюции (двойном отрицании):

Следующие четыре правила называются законами алгебры логики:

• Коммутативный закон:

  x1 & x2 = x2 & x1;

• Ассоциативный закон:

  x1 & (x2 & x3) = (x1 & x2) & x3;

• Дистрибутивный закон:
• Законы инверсии (законы де Моргана):

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