Задание 23 из КИМ ЕГЭ
Бочарникова Г.М.,
учитель информатики
МОАУ «Гимназия № 8» г. Оренбург
Сколько различных
решений имеет система логических уравнений
(x1 ^ y1) = (¬x2 V ¬y2)
(x2 ^ y2) = (¬x3 V ¬y3)
...
(x5 ^ y5) = (¬x6 V ¬y6)
где x1,
…, x6, y1, …, y6, – логические
переменные? В ответе не нужно перечислять все различные наборы значений
переменных, при которых выполнено данное равенство. В качестве ответа нужно
указать количество таких наборов.
Решение:
1.
Из анализа системы логических уравнений мы видим, что присутствует 6
переменных Х и 6 переменных У. Так как любая из этих переменных
может принимать только два значения (0 и 1), то заменим эти переменные на 12
однотипных переменных, например Z.
2. Теперь перепишем
систему с новыми однотипными переменными. Сложность задачи будет заключаться во
внимательной записи при замене переменных.
(z1 ^ z2) = (¬z3 V ¬z4)
(z3 ^ z4) = (¬z5 V ¬z6)
...
(z9 ^ z10) = (¬z11 V ¬z12)
3.
Построим таблицу, в которой переберем все варианты z1, z2, z3, z4,
поскольку в первом логическом уравнении четыре переменных, то таблица будет
иметь 16 строк (16=24); уберем из таблицы такие значения z4,
при которых первое уравнение не имеет решения (зачеркнутые цифры в табл.).
|
Z. 1
|
Z. 2
|
Z. 3
|
Z. 4
|
|
0
|
0
|
0
|
0
|
|
1
|
|
1
|
0
|
|
1
|
|
1
|
0
|
0
|
|
1
|
|
1
|
0
|
|
1
|
|
1
|
0
|
0
|
0
|
|
1
|
|
1
|
0
|
|
1
|
|
1
|
0
|
0
|
|
1
|
|
1
|
0
|
|
1
|
4. Анализируя таблицу, строим правило
отображения пар переменных (например, паре Z1Z2=00
соответствует параZ3Z4 = 11).
4.
Заполняем таблицу, вычисляя количество пар переменных, при котором
система имеет решение.
6. Складываем все
результаты: 9 + 9 + 9 + 27 = 54
Ответ: 54.
Используемые источники
1. К.Ю. Поляков, М.А.
Ройтберг. Системы логических уравнений: решение с помощью битовых
цепочек. Журнал Информатика, № 12, 2014,
с. 4-12. Издательский дом "Первое сентября", г.
Москва.
2. Е.А. Мирончик, Метод
отображения. Журнал Информатика, № 10, 2013,
с. 18-26. Издательский дом "Первое сентября",
г. Москва.
3. К.Ю. Поляков. Материалы подготовки к ЕГЭ.
Режим доступа: http://kpolyakov.spb.ru/school/ege.htm
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.