Сколько существует различных наборов значений логических переменных x1, x2, … x7, y1, y2, … y7, которые удовлетворяют всем перечисленным ниже условиям?
(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1
(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1
…
(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1
(x7 ∨ y7) = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, ..., x7, y1, y2, ..., y7, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Из последнего уравнения находим, что возможны варианты значений x7 и y7: 11, 01, 10 . Построим древо вариантов для каждого из вариантов значений x7 и y7. Для пары значений 11:
Имеем один вариант набора решений.
Для пары значений 01:
Каждая ветка расщепляется на три из которых только две опять расщепляются на три, а одна — нет.
Вот как выглядело бы начало древа решений, если бы каждая ветка расщеплялась только на две (см. рис. слева). Тогда мы имели бы 2 · 2 · ... · 2 = 2N решений, где N — количество уравнений в системе.
В нашем случае (см. рис. справа) в каждой точке ветвления добавляется ещё по одному решению.
Тогда имеем 2N + 1 + 2 + 4 + ... + 2N − 1 решений. Преобразуем данное выражение:
Полученное выражение — сумма первых N членов геометрической прогрессии с знаменателем 2 и первым членом равным единице. Поскольку в системе семь уравнений, количество решений равно
Для пары значений 10 переменных x7y7 также имеем 127 решений.
Таким образом, система уравнений имеет 127 + 127 + 1 = 255 наборов решений.
Ответ: 255.