259 подписчиков

ЕГЭ по информатике. Задание 23

13 мая 202013 мая 2020

563

4 мин

Одной из самой трудной задачей в ЕГЭ я считаю задачу 23, в которой надо найти количество различных наборов значений логических переменных, которые удовлетворяют указанному условию.

С ней, как правило, справляются не более 5% экзаменуемых. В чем причина? Скорее всего в том, что в данном блоке существует большое количество разнообразных задач и невозможно подобрать какое-то шаблонное решение.

В общем, задание 23 характеризуется высоким уровнем сложности, время выполнения – 10 минут, максимальный балл — 1.

Рассмотрим несколько примеров. Решать их методом замены переменных.

Пример 1. Сколько различных решений имеет система логических уравнений (СЛУ)

(x1 ^ y1) = (¬x2 V ¬y2)
(x2 ^ y2) = (¬x3 V ¬y3)
...
(x5 ^ y5) = (¬x6 V ¬y6)

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

Решение.

Проанализируем СЛУ. Видим, что присутствует 6 переменных Х и 6 переменных У. Каждая из этих переменных может принимать только два значения (0 и 1). Следовательно, заменим эти переменные на 12 однотипных переменных Z.

Перепишем систему с переменной Z.

(z1 ^ z2) = (¬z3 V ¬z4)
(z3 ^ z4) = (¬z5 V ¬z6)
...
(z9 ^ z10) = (¬z11 V ¬z12)

Оформим таблицу, в которой будем перебирать все варианты z1, z2, z3, z4.

Зачеркнем в таблице такие значения z4, при которых первое уравнение не имеет решения.

Проанализируем таблицу и построим отображение пар переменных.

Оформим еще одну таблицу, вычисляя количество пар переменных, при котором система имеет решение.

Осталось сложить значения в последнем столбце: 9 + 9 + 9 + 27 = 54.

Ответ: 54.

Пример 2. Сколько существует различных наборов значений логических переменных x1, х2, х3, х4, х5, х6, х7, х8, которые удовлетворяют всем перечисленным ниже условиям?

(x1 → х2) → (х3→ х4) = 1

(х3 → х4) → (х5 → х6) = 1

(х5 → х6) → (х7 → х8) = 1

В ответе не нужно перечислять все различные наборы значений переменных x1, х2, х3, х4, х5, х6, х7, х8, при которых выполнена данная система равенств. В качестве ответа нужно указать количество таких наборов.

Решение.

Проанализируем СЛУ. Видим, что присутствует 6 "одинаковых" импликаций. Каждая из них может принимать только два значения (0 и 1). Следовательно, заменим эти импликации на 6 однотипных переменных Y.

(x1 → х2) = y1;

(х3 → х4) = y2;

(х5 → х6) = y3;

(х7 → х8) = y4.

Кроме того правая часть во всех трех уравнениях равна 1.

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

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

Конъюнкция равна 1 (истинна), когда каждый множитель равен 1. Получается, что каждая импликация должна быть истинна, а это выполняется при всех значениях, кроме (1 → 0).

Оформим таблицу значений переменной Y:

Видим, что условия выполняются для всех пяти наборов y1, y2, y3, y4.

Возвращаемся к замене y1 = x1 → x2. Получаем, что значение y1 = 0 достигается на единственном наборе x1, x2: (1, 0). Следовательно, значение y1 = 1 – на трех наборах x1, x2: (0,0) , (0,1), (1,1).

Аналогично для y2, y3, y4.

Так как каждый набор (x1,x2) для переменной y1 сочетается с каждым набором (x3,x4) для переменной y2 и т.д., то количества наборов переменных x перемножаются:

Складываем количество наборов: 1 + 3 + 9 + 27 + 81 = 121.

Ответ: 121.

Приведу еще такой вариант решения 23 задания:

Пример 3. Сколько существует различных наборов значений логических переменных X1, X2,..., X9, Y1, Y2,..., Y9, которые удовлетворяют всем перечисленным ниже условиям?

В ответе не нужно перечислять все различные наборы значений переменных X1, X2,..., X9, Y1, Y2,..., Y9, при которых выполнена данная система равенств.

В качестве ответа нужно указать количество таких наборов.

Решение.

Сделаем одинаковую замену во всех уравнениях:

Для истинности конъюнкции должны быть истинными все её множители:

Из первого выражения следует, что в ряду X1, X2,..., X9 нули и единицы должны чередоваться. Получается два варианта: 010101010 и 101010101.

Из второго выражения следует, что для Х = 1, соответствующий Y = 1, а для Х = 0 - Y может быть и 0, и 1.

Получаем, что если среди значений Х есть n нулей, то соответствующие им Y можно выбрать 2^n способами.

В ряду 010101010 пять нулей, следовательно, Y для этого ряда можно выбрать 2*2*2*2*2 = 32 способами. В ряду 101010101 четыре нуля, для Y получается 2*2*2*2 = 16 способов.

Всего получаем 32 + 16 = 48 наборов.

Ответ: 48.

Если остались вопросы, пишите в комментариях. Обязательно отвечу. Если нужно разобрать конкретный пример, также - в комментарии.