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



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

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

 

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

 

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, x6, x7, x8, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение.

Произведём замену: y1 = x1 → x2; y2 = x3 → x4; y3 = x5 → x6; y4 = x7 → x8. Получим уравнение:

 

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1.

 

Логическое И истинно, только тогда, когда истины все утверждения, поэтому данное уравнение эквивалентно системе уравнений:

Импликация ложна только в случае, если из истинного следует ложное. Данная система уравнений описывает ряд переменных {y1, y2, y3, y4}. Заметим, что если любую переменную из этого ряда приравнять 1, то все следующие должны также быть равны 1. То есть решения системы уравнений: 0000; 0001; 0011; 0111; 1111.

Уравнения вида xN → x{N+1} = 0 имеют одно решение, а уравнения вида xN → x{N+1} = 1 имеют три решения.

Найдём сколько наборов переменных x соответствуют каждому из решений y.

Решению y 0000 соответствует 1 · 1 · 1 · 1 = 1 решение.

Решению y 0001 соответствует 1 · 1 · 1 · 3 = 3 решения.

Решению y 0011 соответствует 1 · 1 · 3 · 3 = 9 решений.

Решению y 0111 соответствует 1 · 3 · 3 · 3 = 27 решений.

Решению y 1111 соответствует 3 · 3 · 3 · 3 = 81 решений.

Таким образом, суммарное число решений: 1 + 3 + 9 + 27 + 81 = 121.

 

Ответ: 121.