Программное вычисление логических выражений

Для n независимых логических переменных общее число комбинаций их значений – $2^n$: каждая переменная независимо принимает одно из двух значений, а с добавлением ещё одной переменной количество комбинаций удваивается. Для двух переменных – 4, для трёх – 8, для четырёх – 16.

Если выписать все наборы по порядку – 000, 001, 010, 011, 100, 101, 110, 111 – это буквально счёт в двоичной системе от 0 до $2^n-1$: каждый разряд двоичного числа – это значение одной переменной (0 = False, 1 = True). Двоичное число и набор значений переменных – один и тот же объект, просто рассмотренный с двух разных сторон.

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

Логическое выражение F(A, B, C, …) – формула, построенная из переменных с помощью логических операций, которая для каждого конкретного набора значений переменных выдаёт одно значение: True или False.

Для одного набора значение считается в одну строку кода:

A, B, C = True, False, True

F = (A or B) and not (A and C)
print(F)   # False

Проверим вручную: A or B → True, A and C → True, not True → False, и True and False → False. Совпало.

Типовая задача, к которой мы идём: для скольких из всех возможных наборов значений выражение F истинно?

Когда условий, соединённых через and или через or, много, у Python есть более компактная запись.

all(набор_значений) – возвращает True, если все элементы набора истинны, иначе False.

any(набор_значений) – возвращает True, если истинен хотя бы один элемент набора.

По сути это ровно and-цепочка и or-цепочка, только записанные как вызов функции над значениями, перечисленными в квадратных скобках – [A, B, C] (полноценно спискам посвящён блок 9, здесь достаточно знать, что это просто перечисление значений через запятую).

A, B, C = True, False, True

print(A and B and C)      # False
print(all([A, B, C]))     # False – то же самое

print(A or B or C)        # True
print(any([A, B, C]))     # True – то же самое

all()/any() законны как замена цепочки and/or именно потому, что «И» и «ИЛИ» ассоциативны (закон из 3.4) – порядок группировки скобками роли не играет, и длинную цепочку можно свернуть в один список без потери смысла. Они особенно удобны, когда условий много: all([A, B, C, D, E]) читается компактнее, чем A and B and C and D and E.

Но это экономит только запись одного набора значений. Задачу «перечислить все $2^n$ наборов» all()/any() сами по себе не решают – список [A, B, C, D, E] для каждой строки таблицы всё равно приходится заполнять конкретными значениями вручную.

Чтобы посчитать, для скольких наборов выражение F истинно, нужно выписать все $2^n$ строк, для каждой вычислить F и в конце посчитать строки с результатом True. Порядок строк удобно брать двоичным счётом – от 000 до 111 – тогда точно не пропустишь и не повторишь ни одного набора.

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

Возьмём $F = \lnot A \lor (B \land C)$ и распишем все 8 наборов:

Столбец F содержит 1 в пяти строках из восьми – это и есть ответ на вопрос «для скольких наборов выражение истинно».

В выражении $\lnot A \lor (B \land C)$ можно узнать знакомую по 3.3 форму: это ровно импликация $A \to (B \land C)$, потому что $A \to X \equiv \lnot A \lor X$. А у импликации есть только один случай, когда она ложна: A истинно, а X ложно.

Значит, вместо вычисления всех 8 строк достаточно посмотреть на 4 набора с A=1 (100, 101, 110, 111) и найти среди них те, где $B \land C$ ложно – таких три (100, 101, 110). Именно в этих трёх наборах F ложно, а во всех остальных пяти – истинно. Результат совпал с таблицей, но получен быстрее – через закон, а не полным перебором.

Этот приём – сначала узнать знакомую форму и применить закон, и только потом, если нужно, считать по таблице – стоит держать в голове всегда, когда переменных много и перебирать все строки вручную невыгодно по времени.

Для 3 переменных – 8 строк, это ещё терпимо. Для 5 – уже 32. Для 10 – 1024. Даже с all()/any(), которые сокращают запись одной строки, все $2^n$ строк для большого n всё равно нужно перечислить и вычислить по отдельности – а переписывать почти одинаковый код тысячу раз вручную практически нереально.

Это не абстрактное неудобство: ситуация «много раз повторить почти одинаковое действие» – обычный сигнал, что нужен более систематичный инструмент, а не просто более короткая запись одной строки.