Сколько решений имеет уравнение (x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4) ∧ (x4 → x5) = 1

Решение по шагам

1. 1

   Шаг 1. Разбираем структуру уравнения

   Слева стоит конъюнкция четырёх импликаций. Конъюнкция равна 1 только тогда, когда истинны все сомножители одновременно. Значит, набор подходит, если выполняются сразу четыре условия:

   $$x_1 \to x_2 = 1,\quad x_2 \to x_3 = 1,\quad x_3 \to x_4 = 1,\quad x_4 \to x_5 = 1$$

   Вспомним таблицу импликации: $X \to Y$ ложна единственный раз — при $X = 1$ и $Y = 0$. Во всех трёх остальных случаях она истинна. Значит, вместо перебора 32 строк удобнее описать, что именно нам запрещено.

2. 2

   Шаг 2. Переводим запрет на язык последовательности

   Каждая импликация $x_i \to x_{i+1}$ запрещает ровно один переход: «единица, а следом ноль». Переходы $0 \to 0$, $0 \to 1$ и $1 \to 1$ разрешены.

   Значит, во всей цепочке $x_1, x_2, x_3, x_4, x_5$ ноль не может стоять правее единицы: как только последовательность «поднялась» в 1, она обязана остаться в единицах до конца.

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