Алгебра логики : правила построения и преобразования логических выражений

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

Обозначения
Я буду придерживаться обозначений, ясных большинству людей и привычных для программистов.
• «Истина» — 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)


Комментарии запрещены.





Статистика

Рейтинг@Mail.ru