У Кота Матроскина проблема. У него есть следующее логическое выражение, зависящее от трёх переменных:
X₀(А, В, С) = (А И НЕ(В)) ИЛИ (А И НЕ(А) И НЕ(С)) ИЛИ (С И В И НЕ(А) И НЕ(С)) ИЛИ С
Над этим выражением ему нужно проделать следующий алгоритм. Первоначальное значение i = 1, и после каждого вычисления выражения значение i увеличивается на 1.
- Вычислить выражение Xᵢ, подставив Xᵢ₋₁ в данное выражение:
Xᵢ(А, В, С) = (С И Xᵢ₋₁(А, В, 1)) ИЛИ (НЕ(С) И Xᵢ₋₁(А, В, 0))
- Повторить первый пункт 10 раз.
- Вычислить выражение Xᵢ, подставив Xᵢ₋₁ в данное выражение:
Xᵢ(А, В, С) = (А И Xᵢ₋₁(1, В, С)) ИЛИ (НЕ(А) И Xᵢ₋₁(0, В, С))
- Повторить третий пункт 10 раз.
- Вычислить выражение Xᵢ, подставив Xᵢ₋₁ в данное выражение:
Xᵢ(А, В, С) = (В И Xᵢ₋₁(А, 1, С)) ИЛИ (НЕ(В) И Xᵢ₋₁(А, 0, С))
- Повторить пятый пункт 10 раз.
Под слагаемым подразумевается переменная / переменная с отрицанием / константа или последовательность из переменных / переменных с отрицаниями / констант, соединённых операцией И. Примерами слагаемых являются: А И В И С — 1 слагаемое, А И НЕ(В) — 1 слагаемое. Пример: в выражении А ИЛИ В ИЛИ С — 3 слагаемых, (А И НЕ(В) И 1) ИЛИ (0 И А) — 2 слагаемых.
Важное примечание! Изначальную формулу X₀ изменять нельзя. Для каждого из пунктов вычисление происходит по следующим правилам (X, Y, Z — любые переменные или функции):
- Раскрываем скобки по правилу: X И (Y ИЛИ Z) = (X И Y) ИЛИ (X И Z).
- Исключаем слагаемые, следуя правилам, описанным ниже:
- если внутри одного слагаемого есть 0, то это слагаемое исключаем;
- если есть повторяющиеся слагаемые — оставляем только одно, остальные исключаем;
- если в слагаемом одновременно встречаются X и НЕ(X) — слагаемое исключаем;
- НЕ(1) = 0, НЕ(0) = 1;
- 1 И X = X;
- слагаемые можно менять местами, так же, как и порядок переменных в слагаемом;
- делаем так, пока можно что-то исключить;
- правила, не описанные в этом списке, применять строго запрещено!
Сколько слагаемых получится в итоговом выражении?