СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости




Задания
Версия для печати и копирования в MS Word
Задание 23 № 7795

Сколько существует различных наборов значений логических переменных 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.


Аналоги к заданию № 7768: 7795 Все