Логические уравнения и системы

Разбираемся, как сосчитать, сколько наборов переменных удовлетворяют логической системе, не перебирая руками тысячи строк.

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

На экзамене встречается задача: дана система из уравнений с переменными $x_1, x_2, \ldots, x_n$ (часто $n$ доходит до 8–10), и спрашивается, сколько различных наборов значений ей удовлетворяют. Полный перебор — это $2^{n}$ строк, при $n=10$ уже 1024, а в формате с парами переменных бывает и $2^{20}$. Перебирать руками нереально, поэтому нужен метод подсчёта. Самый мощный — «по цепочке».

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

Это задача 2-го уровня сложности, она стоит дороже и отсеивает тех, кто умеет только строить таблицы. Зато метод цепочки — это, по сути, динамическое программирование: вы наращиваете число решений по одной переменной за раз. Тот же приём (считать варианты пошагово, опираясь на предыдущий шаг) лежит в основе многих алгоритмов комбинаторики и в подсчёте путей в графе.

Импликация: ключ к чтению уравнений

Почти все такие уравнения собраны из импликаций. Запомните намертво:

$$a \Rightarrow b = \neg a \lor b, \qquad (a \Rightarrow b)=0 \iff a=1 \text{ и } b=0.$$

То есть импликация ложна в единственном случае — из истины следует ложь. Во всех трёх остальных случаях она истинна. Если уравнение требует $(a \Rightarrow b)=1$, это значит «запрещён только переход $a{=}1, b{=}0$». Часто в уравнении стоит цепочка

$$(x_1 \Rightarrow x_2) \land (x_2 \Rightarrow x_3) \land \ldots \land (x_{n-1} \Rightarrow x_n) = 1.$$

Такая цепочка истинна тогда и только тогда, когда последовательность $x_1, x_2, \ldots, x_n$ «не убывает»: после единицы не может стоять ноль. Значит решения — это последовательности вида $0,0,\ldots,0,1,1,\ldots,1$: сначала блок нулей, потом блок единиц. Сколько их? Граница между нулями и единицами стоит в одном из $n+1$ мест. Итог:

$$N = n + 1.$$

Как это работает: метод по цепочке (таблица переходов)

Когда уравнение одно и простое, формула $n+1$ закрывает вопрос. Но в ЕГЭ обычно даны ДВА условия на одни и те же переменные, и тогда считаем числа решений пошагово, ведя таблицу: сколько частичных решений заканчивается на $x_k{=}0$ и сколько на $x_k{=}1$.

Разберём систему

$$(x_1 \Rightarrow x_2) \land (x_2 \Rightarrow x_3) \land (x_3 \Rightarrow x_4) = 1.$$

Идём слева направо. Для $x_1$ возможны оба значения: одно решение оканчивается на 0, одно — на 1. Условие $x_k \Rightarrow x_{k+1}$ запрещает переход $1 \to 0$. Значит: если предыдущая переменная была 0, следующая может быть и 0, и 1; если предыдущая была 1, следующая обязана быть 1. Считаем, сколько цепочек оканчивается нулём ($c_0$) и единицей ($c_1$) на каждом шаге.

Правило перехода читается из таблицы так: новый $c_0 = $ (старый $c_0$) — ноль можно поставить только после нуля; новый $c_1 = $ (старый $c_0$ + старый $c_1$) — единицу можно поставить и после нуля, и после единицы. Итог для четырёх переменных: $1 + 4 = 5$ решений, что совпадает с формулой $n+1 = 4+1 = 5$. Метод таблицы важен, когда условия сложнее и простая формула не работает.

Когда добавляется второе условие

Пусть к цепочке добавлено $\neg x_1 = 1$, то есть $x_1 = 0$. Тогда стартовая строка таблицы меняется: оканчивается на 0 — одна цепочка, на 1 — ноль цепочек. Пересчитаем:

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

Проверка программой

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

from itertools import product

def impl(a, b):
    return (not a) or b

count = 0
for x in product((0, 1), repeat=4):
    x1, x2, x3, x4 = x
    cond = impl(x1, x2) and impl(x2, x3) and impl(x3, x4)
    if cond:
        count += 1
print("Решений цепочки из 4 переменных:", count)

count2 = 0
for x in product((0, 1), repeat=4):
    x1, x2, x3, x4 = x
    cond = impl(x1, x2) and impl(x2, x3) and impl(x3, x4) and (not x1)
    if cond:
        count2 += 1
print("С условием x1 = 0:", count2)

Вывод:

Решений цепочки из 4 переменных: 5
С условием x1 = 0: 4

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

• Путают направление импликации. $(a \Rightarrow b)$ запрещает $a{=}1, b{=}0$, а НЕ $a{=}0, b{=}1$. Перепутали — все числа поедут.
• В правиле перехода забывают, что ноль можно ставить только после нуля. Тогда $c_0$ начинает ошибочно расти.
• Для системы из нескольких уравнений с РАЗНЫМИ цепочками (например $x$-цепочка и $y$-цепочка, связанные общим условием) нужно вести таблицу по парам $(x_k, y_k)$ — четыре состояния, а не два. Сводить такую систему к простой формуле $n+1$ нельзя.
• Считают «всего» неправильно: общее число решений на шаге — это сумма $c_0 + c_1$, а финальный ответ — сумма на последнем шаге.

Итоги

• Импликация ложна только при переходе $1 \to 0$; цепочка импликаций истинна на неубывающих последовательностях.
• Простая цепочка из $n$ переменных даёт $n+1$ решение.
• Универсальный приём — таблица переходов: новый $c_0 = $ старый $c_0$; новый $c_1 = c_0 + c_1$; дополнительные условия меняют стартовые или промежуточные числа.
• Маленькие случаи проверяйте перебором — это страховка от арифметической ошибки.