РЕШУ ЕГЭ — информатика

Задания

Сколько существует различных наборов значений логических переменных x₁, x₂, ... x₁₂, которые удовлетворяют всем перечисленным ниже условиям?

((x₁ ≡ x₂) ∧ (x₃ ≡ x₄)) ∨ (¬(x₁ ≡ x₂) ∧ ¬(x₃ ≡ x₄)) = 0

((x₃ ≡ x₄) ∧ (x₅ ≡ x₆)) ∨ (¬(x₃ ≡ x₄) ∧ ¬(x₅ ≡ x₆)) = 0

...

((x₉ ≡ x₁₀) ∧ (x₁₁ ≡ x₁₂)) ∨ (¬(x₉ ≡ x₁₀) ∧ ¬(x₁₁ ≡ x₁₂)) = 0

В ответе не нужно перечислять все различные наборы значений переменных x₁, x₂, … x₁₂ при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение. Построим древо решений первого уравнения:

Заметим, что выражение (x₃ ≡ x₄) в двух случаях равно 1 и в двух случаях равно 0. Таким образом, одно уравнение имеет восемь решений.

Второе уравнение связано с первым только через выражение (x₃ ≡ x₄). Построим древо решений второго уравнения:

Для каждого из значений 0 и 1 выражения (x₃ ≡ x₄) существует четыре набора переменных x₁, x₂,...,x₄, удовлетворяющих первому уравнению (см. первый рисунок). Таким образом, система из двух уравнений имеет 4 · 4  =  16 решений.

Третье уравнение связано со вторым только через выражение (x₅ ≡ x₆). Построим древо решений третьего уравнения:

Для каждого из значений 0 и 1 выражения (x₅ ≡ x₆) существует 2 · 4  =  8 наборов переменных x₁, x₂,...,x₆, удовлетворяющих первому уравнению (см. первый и второй рисунок). Таким образом, система из трёх уравнений имеет 8 · 4  =  32 решения.

Аналогично система из четырёх уравнений будет иметь 64 решения, система из пяти уравнений  — 128.

Ответ: 128.

№ п/п	№ задания	Ответ
1	5627	128

Ключ