ЕГЭ по информатике 2016. Логическое уравнение, задание 23

Задание 23. Сколько существует различных наборов значений логических переменных x₁, x₂, … x₆, y₁, y₂, … y₆, которые удовлетворяют всем перечисленным ниже условиям?

(x₁ → x₂) /\ (x₂ → x₃) /\ (x₃ → x₄) /\ (x₄ → x₅) /\ (x₅ → x₆) = 1

(y₁ → y₂) /\ (y₂ → y₃) /\ (y₃ → y₄) /\ (y₄ → y₅) /\ (y₅ → y₆) = 1

(¬x₁ \/ y₁) /\ (¬x₂ \/ y₂) /\ (¬x₃ \/ y₃) /\ (¬ x₄ \/ y₄) /\ (¬x₅ \/ y₅) /\(¬x₆ \/y₆) = 1

В ответе не нужно перечислять все различные наборы значений переменных x₁, x₂, … x₆, y₁, y₂, … y₆, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение:

1. Перепишем систему уравнений в более понятном виде, раскрывая импликацию по формуле A → В = ¬А + В:

(¬x₁ + x₂)(¬x₂ + x₃)(¬x₃ + x₄)(¬x₄ + x₅)(¬x₅ + x₆) = 1

(¬у₁ + у₂)(¬у₂ + у₃)(¬у₃ + у₄)(¬у₄ + у₅)(¬у₅ + у₆) = 1

(¬x₁ + у₁)(¬x₂ + у₂)(¬x₃ + у₃)(¬x₄ + у₄)(¬x₅ + у₅)(¬x₆ + у₆) = 1

2. Рассмотрим первое уравнение

(¬x₁ + x₂)(¬x₂ + x₃)(¬x₃ + x₄)(¬x₄ + x₅)(¬x₅ + x₆) = 1

 Каждая скобка должна равняться 1:

(¬x₁ + x₂) = 1

(¬x₂ + x₃) = 1

…

(¬x₅ + x₆) = 1

 Строим дерево решений:

х1					0		1
х2				0		1	1
х3			0		1	1	1
х4		0		1	1	1	1
х5	0		1	1	1	1	1
х6	0	1	1	1	1	1	1

Имеем 7 наборов: 000000, 000001, 000011, 000111, 001111, 011111  и 111111.

3. Второе условие совпадает с первым, получаем семь наборов у₁у₂у₃у₄у₅у₆ : 000000, 000001, 000011, 000111, 001111, 011111 и 111111.

4. Поскольку первые два уравнения независимы друг от друга, система из первых двух уравнений имеет 7·7=49 решений: каждому решению первого соответствует 7 разных комбинаций переменных y₁, y₂, …, y₆, которые решают второе, и наоборот, каждому решению второго соответствует 7 разных комбинаций переменных x₁, x₂, …, x₆, которые решают первое:

х1х2х3х4х5х6	у1у2у3у4у5у6	у1у2у3у4у5у6	у1у2у3у4у5у6	у1у2у3у4у5у6	у1у2у3у4у5у6	у1у2у3у4у5у6	у1у2у3у4у5у6
000000	000000	000001	000011	000111	001111	011111	111111
000001	000000	000001	000011	000111	001111	011111	111111
000011	000000	000001	000011	000111	001111	011111	111111
000111	000000	000001	000011	000111	001111	011111	111111
001111	000000	000001	000011	000111	001111	011111	111111
011111	000000	000001	000011	000111	001111	011111	111111
111111	000000	000001	000011	000111	001111	011111	111111

5. Проверим, какие ограничения накладывает третье уравнение:

(¬x₁ + у₁)(¬x₂ + у₂)(¬x₃ + у₃)(¬x₄ + у₄)(¬x₅ + у₅)(¬x₆ + у₆) = 1

Первая скобка: ¬x₁ + у₁=1 _. При x₁ =0  у₁ может иметь значение 0 или 1, при x₁ =1 у₁ = 1. Проверяем на это условие комбинации переменных x₁, x₂, …, x₆ и y₁, y₂, …, y₆

х1х2х3х4х5х6	у1у2у3у4у5у6	у1у2у3у4у5у6	у1у2у3у4у5у6	у1у2у3у4у5у6	у1у2у3у4у5у6	у1у2у3у4у5у6	у1у2у3у4у5у6
000000	000000	000001	000011	000111	001111	011111	111111
000001	000000	000001	000011	000111	001111	011111	111111
000011	000000	000001	000011	000111	001111	011111	111111
000111	000000	000001	000011	000111	001111	011111	111111
001111	000000	000001	000011	000111	001111	011111	111111
011111	000000	000001	000011	000111	001111	011111	111111
111111	000000	000001	000011	000111	001111	011111	111111

Из набора комбинаций переменных вычеркнули шесть наборов.

6. Аналогично проверяем  ещё пять ограничений:

х1х2х3х4х5х6	у1у2у3у4у5у6	у1у2у3у4у5у6	у1у2у3у4у5у6	у1у2у3у4у5у6	у1у2у3у4у5у6	у1у2у3у4у5у6	у1у2у3у4у5у6
000000	000000	000001	000011	000111	001111	011111	111111
000001	000000	000001	000011	000111	001111	011111	111111
000011	000000	000001	000011	000111	001111	011111	111111
000111	000000	000001	000011	000111	001111	011111	111111
001111	000000	000001	000011	000111	001111	011111	111111
011111	000000	000001	000011	000111	001111	011111	111111
111111	000000	000001	000011	000111	001111	011111	111111

  

7. Общее количество решений системы 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28

Ответ: 28