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


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

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

 

(x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4) ∧ (x4 → x5) ∧ (x5 → x6) = 1

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) ∧ (y4 → y5) ∧ (y5 → y6) = 1

(¬x1 ∨ y1) ∧ (¬x2 ∨ y2) ∧ (¬x3 ∨ y3) ∧ (¬ x4 ∨ y4) ∧ (¬x5 ∨ y5) ∧ (¬x6 ∨ y6) = 1

 

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

Решение.

Заметим, что первое и второе уравнения не связаны между собой ни через какие переменные.

 

Рассмотрим первое уравнение. Для того, чтобы равенство выполнялось, необходимо, чтобы каждая скобка была истинной. Импликация ложна только тогда, когда посылка истинна, а следствие ложно. Представим решение этого уравнения в виде дерева.

 

 

Рассмотрим второе уравнение. Чтобы равенство выполнялось, необходимо, чтобы каждая скобка была истинной. Дерево для решения этого уравнения будет выглядеть так:

 

 

Теперь рассмотрим третье уравнение. Конъюнкция истинна только, если все операнды истинны. Каждое уравнения вида ¬xN ∨ yN = 1 имеет три решения: 01, 00, 11. То есть для каждой пары xN, yN запрещены решения вида 10.

Будем представлять решения уравнений в виде набора нулей и единиц, например, решение x1 = 0, x2 = x3 =x4, = x5= x6 = 1 имеет вид 011 111. Заметим, что для первых двух уравнений в наборах решений после единицы могут стоять только единицы. То есть разрешены решения вида 001 111.

Также заметим, что если yN = 0, то xN обязательно равно единице.

Таким образом, получаем, что набору yN 111 111, могут соответствовать наборы xN: 111 111, 011 111, 001 111, 000 111, 000 011, 000 001, 000 000. Всего семь наборов.

Аналогично, набору yN 011 111 соответствует шесть наборов и так далее. Всего получаем:

 

7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 наборов.

Ответ: 28.

Источник: ЕГЭ по информатике 23.03.2016. Досрочная волна