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


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

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

 

(x1 ∧ ¬x2) ∨ (¬x1 ∧ x2) ∨ (x2 ∧ x3) ∨ (¬x2 ∧ ¬x3) = 1

(x2 ∧ ¬x3) ∨ (¬x2 ∧ x3) ∨ (x3 ∧ x4) ∨ (¬x3 ∧ ¬x4) = 1

...

(x8 ∧ ¬x9) ∨ (¬x8 ∧ x9) ∨ (x9 ∧ x10) ∨ (¬x9 ∧ ¬x10) = 1

 

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

Решение.

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

Таким образом, первое уравнение имеет 6 решений.

 

Второе уравнение связано с первым только через переменные x2 и x3. На основании древа решений для первого уравнения выпишем пары значений переменных x2 и x3, которые удовлетворяют первому уравнению и укажем количество таких пар значений.

 

Количество

пар значений

x2x3
×211
×200
×110
×101

 

Поскольку уравнения идентичны с точностью до индексов переменных, древо решений второго уравнения аналогично первому. Следовательно, пара значений x2 = 1 и x3 = 1 порождает один набор переменных x2, ..., x4, удовлетворяющих второму уравнению. Поскольку среди наборов решений первого уравнения данных пар две, всего получаем 2 · 1 = 2 набора переменных x1, ..., x4, удовлетворяющих системе из двух уравнений. Рассуждая аналогично для пары значений x2 = 0 и x3 = 0, получаем 2 набора переменных x1, ..., x4. Пара x2 = 1 и x3 = 0 порождает четыре решения второго уравнения. Поскольку среди наборов решений первого уравнения данная пара одна, получаем 2 · 1 = 2 набора переменных x1, ..., x4, удовлетворяющих системе из двух уравнений. Аналогично для x2 = 0 и x3 = 1 — 2 набора решений. Всего система из двух уравнений имеет 2 + 2 + 2 + 2 = 8 решений.

 

Проведя аналогичные рассуждения для системы из трёх уравнений, получаем 10 наборов переменных x1, ..., x5, удовлетворяющих системе. Для системы из четырёх уравнений существует 12 наборов переменных x1, ..., x6, удовлетворяющих системе. Система из восьми уравнений имеет 20 решений.

 

Ответ: 20.

Источник: ЕГЭ по информатике 08.07.2013. Вторая волна. Ва­ри­ант 801.