Логика условий: и, или, не, если-то, для всех

Если ты уверенно отрицаешь условие цикла и знаешь, почему «все элементы пустого списка положительны» истинно, листай до «Теперь сам» в конце.

Как думаешь, когда кончится этот цикл

while i >= 0 and a[i] > klyuch:
    a[i + 1] = a[i]
    i = i - 1
a[i + 1] = klyuch

Это внутренний цикл сортировки вставками. Ответь себе до того, как читать дальше: что именно верно сразу после выхода из цикла? «i < 0 и a[i] <= klyuch»? Или что-то другое? От ответа зависит, куда программа положит ключ, а значит, верна ли сортировка. (and в Python ленивый: при i < 0 правая часть a[i] > klyuch не вычисляется вовсе.)

На что это похоже

Охранник на входе с правилом «пропускать, если есть пропуск И нет оружия». Он не пропускает, если нет пропуска ИЛИ есть оружие - хватит любой из двух причин. Перевернуть «и» в «или» при отрицании человек делает без раздумий, когда речь об охраннике, и ошибается, когда то же самое написано в условии цикла. Логика - это способ делать с условиями программы то, что ты и так умеешь делать с правилами из жизни.

Механизм: связки и их таблицы

Высказывание - утверждение, которое либо истинно, либо ложно: x > 5, список пуст, i < len(a). Связки собирают из них сложные. Таблица истинности перечисляет все случаи:

shapka = ["A", "B", "и", "или", "не A", "если", "ровно одно"]
print("  ".join(f"{h:5}" for h in shapka))
for A in [False, True]:
    for B in [False, True]:
        stroka = [A, B, A and B, A or B, not A, (not A) or B, A != B]
        print("  ".join(f"{str(x):5}" for x in stroka).rstrip())

A      B      и      или    не A   если   ровно одно
False  False  False  False  True   True   False
False  True   False  True   True   True   True
True   False  False  True   False  False  True
True   True   True   True   False  True   False

«И» истинно, только когда истинны оба. «Или» - когда истинно хотя бы одно (в том числе оба). Колонка «если» - импликация, о ней ниже. «Ровно одно» - отдельная связка, исключающее или, по-английски XOR; в Python для логических значений это !=.

Импликация «если A, то B», A → B, ложна в единственной строке: A истинно, B ложно. Когда A ложно, импликация истинна при любом B - обещание «если пойдёт дождь, возьму зонт» не нарушено в сухой день. Поэтому A → B записывается в программе как (not A) or B. Равносильность «A тогда и только тогда, когда B» - обе импликации сразу: A и B истинны одновременно или ложны одновременно.

Законы де Моргана: not (A and B) равносильно (not A) or (not B), а not (A or B) - (not A) and (not B). Отрицание проходит внутрь и меняет связку.

Правило

Отрицание переворачивает связку: «не (A и B)» = «не A или не B», «не (A или B)» = «не A и не B». Цикл while условие кончается, когда истинно отрицание условия. A → B ложно только при истинном A и ложном B. Отрицание «для всех x верно P» - «существует x, для которого P ложно»; отрицание «существует» - «для всех не».

Разбор: что верно после выхода из цикла

Вернёмся к циклу сортировки вставками. Он выходит, когда условие i >= 0 and a[i] > klyuch ложно, то есть по де Моргану, когда истинно i < 0 or a[i] <= klyuch. Не «и», а «или»: возможны два разных выхода.

В обоих случаях ключ кладётся в a[i + 1] - при i = -1 это и есть a[0]. Одна строка кода обслуживает обе ветви «или», и увидеть это можно только честно отрицав условие. Если ошибиться и решить, что после цикла верно «i < 0 И a[i] <= klyuch», то первый выход окажется невозможным, а он случается каждый раз, когда ключ меньше всех предыдущих.

Разбор: контрпример - отрицание «для всех»

Утверждения об алгоритмах почти всегда начинаются с квантора: «для всех входов алгоритм отвечает верно», «существует вход, на котором он ошибается». Отрицание «для всех x верно P» - «существует x, для которого P ложно». Найденный такой x называется контрпримером, и одного достаточно, чтобы опровергнуть утверждение «для всех», сколько бы верных примеров ни было собрано. В Python кванторы по списку - это all и any. Запись all(x % 2 == 0 for x in a) читается «для всех x из a верно x % 2 == 0», а [x for x in a if ...] строит список тех x из a, для которых условие истинно:

a = [4, 8, 15, 16]
print(all(x % 2 == 0 for x in a), any(x % 2 == 1 for x in a))
print([x for x in a if x % 2 == 1])
print(all(x > 0 for x in []), any(x > 0 for x in []))

False True
[15]
True False

«Все чётные» ложно, и это ровно то же, что «есть нечётное» - истинно; свидетель, 15, найден. Последняя строка выглядит странно, но она логична. «Все элементы пустого списка положительны» истинно: чтобы оно было ложным, нужен контрпример - элемент, который не положителен, а элементов нет. «Существует положительный» ложно по той же причине. Такую истинность называют пустой, и она постоянно встречается в доказательствах: утверждение «левее начала всё отсортировано» в начале цикла истинно именно так.

Где ошибаются

Отрицают условие, не меняя связку, и получают невозможное условие выхода, как в первом разборе. Путают «если A, то B» с «если B, то A»: «если число делится на 4, то оно чётное» верно, а «если число чётное, то оно делится на 4» - нет, контрпример 6. Обратное утверждение доказывают отдельно. Читают «или» как исключающее: x < 0 or x > 10 не значит «ровно одно», хотя тут оба сразу и невозможны. И проверяют утверждение «для всех» перебором примеров: десять подтверждений не доказывают ничего, а один контрпример опровергает.

Зачем это в работе

Упростить условие на ревью: if not (user.active and user.verified) читается хуже, чем if not user.active or not user.verified, а это одно и то же. Понять, при каком входе срабатывает ветка else, - это отрицание условия if. Опровергнуть «этот кеш всегда отдаёт свежие данные» - значит предъявить один запрос со старыми. И объяснить, почему тест «пустой список» проходит у функции «все ли элементы валидны»: ответ True - не ошибка, а пустая истинность, и об этом стоит договориться в спецификации.

Теперь сам

Цикл двоичного поиска: while levo < pravo and a[seredina] != x. Что верно после выхода? И чему равно all(x == 7 for x in [])?