Одной из самой трудной задачей в ЕГЭ я считаю задачу 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.
Если остались вопросы, пишите в комментариях. Обязательно отвечу. Если нужно разобрать конкретный пример, также - в комментарии.
Читайте также: Задание 1, Задание 2, Задание 3, Задание 4, Задание 5, Задание 6, Задание 7, Задание 8, Задание 9, Задание 10, Задание 11, Задание 12, Задание 13, Задание 14, Задание 15, Задание 22, Задание 16, Задание 17, Задание 18, Задание 19, Задание 20, Задание 21, Задание 24, Задание 25, Задание 26, Задание 27.
Еще больше интересного материала в группе в ВК и на сайте. Кроме этого, можете воспользоваться услугами репетитора.
