Алгебра логики

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

Обозначения

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

• «Истина» — true
• «Ложь» — false
• Логическое «и» — and
• Логическое «или» — or
• Логическое отрицание — not

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

A and not B

следует понимать как

A and (not B)

Таблицы истинности

Коротко напомню правила выполнения операций

Операция отрицания:   Логическое <<и>>:         Логическое <<или>>:
------------------   -----------------------   ----------------------
not true  = false    false and false = false   false or false = false
not false = true     true  and false = false   true  or false = true
                     false and true  = false   false or true  = true
                     true  and true  = true    true  or true  = true

Свойства операций

Логические операции во многом аналогичны привычным математическим, но имеют и свою специфику.

Коммутативность — «от перестановки слагаемых сумма не изменяется»

A and B = B and A
A or  B = B or  A

Идемпотентность

X and X = X
X or  X = X

Ассоциативность — порядок выполнения операций не важен

(A and B) and C = A and (B and C)
(A or  B) or  C = A or  (B or  C)

Дистрибутивность — раскрытие скобок

C or  (A and B) = (C or  A) and (C or  B)
C and (A or  B) = (C and A) or  (C and B)

Законы де Моргана (ударение на «о»):

not (A and B) = (not A) or  (not B)
not (A or  B) = (not A) and (not B)

Законы поглощения:

A and (A or  B) = A
A or  (A and B) = A

Другие полезные закономерности, в которых фигурируют константы true и false:

A and true  = A
A or  true  = true
A and false = false
A or  false = A

A and (not A) = false
A or  (not A) = true

Пример

Например, вам надо выполнить некое действие с файлом, «если дата его создания T меньше времени L, а если время T больше L, то требуется выполнение дополнительного условия P». Дословно это можно записать так:

T < L or (T > L and P)

Используем дистрибутивность — раскрываем скобки:

(T < L or T > L) and (T < L or P)

Первая скобка всегда «истина», а «истина и что-то — равно что-то». Получаем выражение:

T < L or P

Даже в таком простом выражении нам удалось вдвое уменьшить количество операций.

Про что здесь не рассказано

Строго говоря, алгебра логики рассматривает не только операции «и», «или» и «не». Другие операции не обладают всем перечисленными свойствами и заслуживают отдельного рассказа. Но я не стал здесь их рассматривать, так как в прикладном программировании используются преимущественно только три операции, а любые другие можно выразить через эти три.

Например, «исключающее или» можно выразить так:

A xor B = (A or B) and (not A or not B)
или
A xor B = (A and not B) or (B and not A)