Законы де Моргана в условиях

Урок о том, как правильно вносить отрицание внутрь скобок и почему «не в диапазоне» — это не то, что кажется.

Законы де Моргана — пара тождеств, превращающих отрицание конъюнкции в дизъюнкцию отрицаний и наоборот: $\neg(A\land B)=\neg A\lor\neg B$ и $\neg(A\lor B)=\neg A\land\neg B$.

Эти два правила вы встречали в разделе про упрощение формул. В коде они работают каждый день: их применяют, когда условие нужно инвертировать (написать «когда НЕ так») или упростить до читаемого вида. Ошибка здесь — это не косметика, а неверная логика: программа разрешает то, что должна запрещать.

Зачем это нужно

Часто проще описать «хороший» случай, а в коде нужен «плохой» (или наоборот). Например, форма валидна, когда заполнено имя и почта: name and email. А показать ошибку надо, когда форма невалидна, то есть not (name and email). По де Моргану это

$$ \neg(name \land email) = \neg name \lor \neg email $$

«нет имени ИЛИ нет почты». Звучит логично — и именно так и должно быть. А вот наивная «инверсия» not name and not email означала бы «нет имени И нет почты», то есть ошибку показывали бы, только когда пусто всё сразу. Это классический баг.

Два закона на формулах и в коде

Запишем оба тождества рядом:

$$ \neg(A\land B)=\neg A\lor\neg B, \qquad \neg(A\lor B)=\neg A\land\neg B $$

Словами: знак отрицания «проходит» внутрь скобки, переворачивая каждый операнд И меняя связку на противоположную ($\land \leftrightarrow \lor$). Проверим первое тождество перебором всех четырёх наборов — это и есть доказательство таблицей истинности.

print(" A      B   | ¬(A∧B) | ¬A∨¬B")
for A in (False, True):
    for B in (False, True):
        left = not (A and B)
        right = (not A) or (not B)
        print(f"{A!s:5} {B!s:5} | {left!s:6} | {right!s:5}  совпадают={left==right}")

Вывод:

 A      B   | ¬(A∧B) | ¬A∨¬B
False False | True   | True   совпадают=True
False True  | True   | True   совпадают=True
True  False | True   | True   совпадают=True
True  True  | False  | False  совпадают=True

Во всех четырёх строках столбцы равны — тождество выполнено.

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

Самая коварная ловушка — отрицание условия «попадает в диапазон». Пусть допустимы значения от 10 до 20 включительно:

$$ valid = (x \ge 10) \land (x \le 20) $$

Чему равно «НЕ valid»? Многие пишут x < 10 and x > 20 — и это всегда ложь, потому что число не может быть одновременно меньше 10 и больше 20. По де Моргану правильно так:

$$ \neg\big((x\ge 10)\land(x\le 20)\big)=(x\lt 10)\lor(x\gt 20) $$

Связку and при инверсии меняем на or. Сравним оба варианта на числах:

def вне_правильно(x):   # де Морган: меняем and на or
    return x < 10 or x > 20

def вне_ошибка(x):      # частый баг: оставили and
    return x < 10 and x > 20

for x in (5, 15, 25):
    print(x, "-> правильно:", вне_правильно(x), "| ошибка:", вне_ошибка(x))

Вывод:

5 -> правильно: True | ошибка: False
15 -> правильно: False | ошибка: False
25 -> правильно: True | ошибка: False

Ошибочная версия для x = 5 и x = 25 вернула False, хотя эти числа реально вне диапазона. То есть проверка «значение недопустимо» не сработала бы никогда — баг тихий и опасный.

Упрощение: до и после

Де Морган помогает не только инвертировать, но и убирать лишнее отрицание. Рассмотрим условие фильтра «оставить запись, если она НЕ (черновик ИЛИ удалена)»:

def оставить_до(is_draft, is_deleted):
    return not (is_draft or is_deleted)

def оставить_после(is_draft, is_deleted):   # де Морган: ¬(A∨B)=¬A∧¬B
    return (not is_draft) and (not is_deleted)

для = [(False, False), (True, False), (False, True), (True, True)]
for d, x in для:
    print(d, x, "->", оставить_до(d, x), оставить_после(d, x))

Вывод:

False False -> True True
True False -> False False
False True -> False False
True True -> False False

Обе функции дают одинаковый ответ на всех наборах. Вторая форма часто читается лучше: «не черновик И не удалена» — сразу видно оба требования по отдельности.

Как это работает

Почему отрицание «переворачивает» связку? Вспомните смысл операций. Конъюнкция $A\land B$ истинна, лишь когда оба истинны; значит ложна, как только хоть один ложен — а это в точности «$\neg A$ или $\neg B$». Дизъюнкция $A\lor B$ ложна, лишь когда оба ложны; значит её отрицание истинно, только когда оба отрицания истинны — «$\neg A$ и $\neg B$». Геометрически для диапазона это видно так: множество «$10 \le x \le 20$» — отрезок; его дополнение на прямой — два луча $x \lt 10$ и $x \gt 20$, соединённые союзом «или». Союз «и» дал бы пересечение лучей, а оно пусто.

Частые ошибки

Забыли поменять связку. При инверсии a and b становится not a or not b, а не not a and not b. Не сменив and на or (и обратно), вы получаете неверную логику.
«Не в диапазоне» через and. x < lo and x > hi — всегда ложь. Правильно x < lo or x > hi.
Двойное отрицание не упростили. not (not active) — это просто active ($\neg\neg A = A$); такие выражения стоит сворачивать.
Инверсия строгости. Отрицание x >= 10 — это x < 10 (граница меняет сторону вместе со строгостью), а не x > 10.

Итоги

$\neg(A\land B)=\neg A\lor\neg B$ и $\neg(A\lor B)=\neg A\land\neg B$ — отрицание входит внутрь и переворачивает связку.
Чтобы инвертировать условие в коде, отрицайте каждый операнд и меняйте and на or (и наоборот).
«Не в диапазоне» — это x < lo or x > hi; вариант с and всегда ложен.
Де Морган и закон двойного отрицания делают условия короче и читаемее без изменения смысла.