Алгебра логики
Алгебра логики — это правила, по которым логические выражения записывают, преобразуют и упрощают.
В прошлой главе мы научились читать простые логические выражения и находить их значения. Теперь посмотрим, как работать с более компактной записью: что вычисляется раньше, как устроено двойное отрицание и как правильно отрицать составные условия.
Порядок операций
Если в одном выражении несколько логических операций, их выполняют в фиксированном порядке.
Сначала вычисляют выражения в скобках, затем !, потом &&, и только потом ||.
Операции одного уровня обычно выполняют слева направо.
Например:
- !A && B означает (!A) && B.
- A || B && C означает A || (B && C).
- !(A || B) && C означает: сначала вычислить A || B, затем применить !, и только потом && C.
Если порядок вызывает сомнение, лучше сразу поставить скобки.
Двойное отрицание
Одно отрицание меняет логическое значение на противоположное. Два отрицания подряд возвращают исходное значение.
!!A = A
Это можно увидеть по таблице:
| A | !A | !!A |
|---|---|---|
| true | false | true |
| false | true | false |
Например:
- !!A совпадает с A.
- !(!(x > 5)) совпадает с x > 5.
- !!(A || B) совпадает с A || B.
Законы де Моргана
Когда отрицание стоит перед составным выражением, его удобно переносить внутрь. При этом логическая операция меняется.
!(A && B) = !A || !B
!(A || B) = !A && !B
Эти равенства называют законами де Моргана.
Коротко их смысл такой:
- отрицание И превращается в ИЛИ;
- отрицание ИЛИ превращается в И;
- каждая часть выражения тоже отрицается.
Например:
- !(x > 0 && x % 2 == 0) можно переписать как x <= 0 || x % 2 != 0.
- !(x < 3 || x == 8) можно переписать как x >= 3 && x != 8.
Отрицание сравнений
Перед тем как отрицать сложное условие, полезно уметь отрицать одно сравнение.
| Было | После отрицания |
|---|---|
| x > a | x <= a |
| x >= a | x < a |
| x < a | x >= a |
| x <= a | x > a |
| x == a | x != a |
| x != a | x == a |
Здесь ! обычно не оставляют снаружи, а сразу заменяют сравнение на противоположное. Так запись получается короче и понятнее.
На числовой оси это особенно хорошо видно:
Верхняя пара строк показывает, что отрицание условия x > 3 даёт x <= 3.
Нижняя пара строк показывает отрицание интервала: если условие 2 < x < 6 ложно, значит число находится слева от интервала или справа от него.
В программной записи это выглядит так:
!(x > 2 && x < 6) = x <= 2 || x >= 6
Здесь как раз и работает закон де Моргана:
- отрицание проходит внутрь;
- && меняется на ||;
- каждое сравнение заменяется на противоположное.
Задачи для тренировки
1. Расставьте скобки так, чтобы порядок действий стал явным.
a) !A || B && C
b) !(A || B) && C
c) !A && !B || C
Ответ
a) (!A) || (B && C)
b) (!(A || B)) && C
c) ((!A) && (!B)) || C
2. Упростите выражения с двойным отрицанием.
a) !!A
b) !(!(x < 4))
c) !!(A || B)
Ответ
a) A
b) x < 4
c) A || B
3. Перепишите выражения по законам де Моргана.
a) !(A && B)
b) !(A || B)
c) !(x >= 0 && x != 5)
d) !(x < 3 || x == 8)
Ответ
a) !A || !B
b) !A && !B
c) x < 0 || x == 5
d) x >= 3 && x != 8
4. Запишите отрицание каждого сравнения.
a) x <= 10
b) y > 4
c) n == 0
d) k != 9
Ответ
a) x > 10
b) y <= 4
c) n != 0
d) k == 9
5. Запишите отрицание условия: число x больше 1 и меньше 9.
Ответ
x <= 1 || x >= 9