2 задание ЕГЭ информатика
Таблицы истинности
1 балл ≈ 3 мин уровень Б
Задание 2 – дана логическая функция F от четырёх переменных и фрагмент таблицы истинности с пропусками; столбцы не подписаны. Нужно определить, какой переменной соответствует каждый столбец. 1 балл. Надёжнее всего решать перебором на Python.
Обозначения в Python
| Логика | Python |
|---|---|
| ¬x | not x |
| x ∧ y | x and y |
| x ∨ y | x or y |
| x → y | (not x) or y, или x <= y |
| x ≡ y | x == y |
| ¬(x ≡ y) (исключающее ИЛИ) | x != y |
Алгоритм
- Запиши функцию F на Python. Расставь скобки так же, как в условии.
- Перебери все заполнения пропусков (product) и все перестановки переменных по столбцам (permutations).
- Строки фрагмента должны быть различными – это условие тоже проверяй.
- Выведи перестановку, при которой все строки дают нужное значение F.
Разобранный пример. F = (x → y) ∧ ¬(z ≡ w) ∧ (x ∨ z), во всех трёх строках фрагмента F = 1. Строки (пропуск – None): (1, 1, 0, ?), (0, 0, 1, 1), (?, 1, ?, 1).
from itertools import product, permutations
def F(x, y, z, w):
return ((not x) or y) and (z != w) and (x or z)
for a, b, c in product([0, 1], repeat=3):
table = [(1, 1, 0, a), (0, 0, 1, 1), (b, 1, c, 1)]
if len(set(table)) != len(table):
continue
for p in permutations("xyzw"):
if all(F(**dict(zip(p, row))) for row in table):
print("".join(p))Программа выведет wxzy – это и есть ответ (если строка повторяется несколько раз, ответ всё равно один).
Ловушки: если в таблице F = 0, проверяй not F(...); забытые скобки при импликации – приоритет not выше and, and выше or; повторяющиеся строки фрагмента запрещены условием.
- Импликацию пиши как (not a) or b в скобках – так не ошибёшься с приоритетом.
- Количество пропусков = repeat в product: посчитай их заранее.
- Если программа ничего не вывела – проверь, правильно ли перенесены строки таблицы и значение F.
Разобранные задания 2 из открытого банка ФИПИ
Пример 1 · код ФИПИ 04F474
Логическая функция F задаётся выражением ¬x \/ y \/ (¬z /\ w).
На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F ложна.
Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных w, x, y, z.
| Переменная 1 | Переменная 2 | Переменная 3 | Переменная 4 | Функция |
| ??? | ??? | ??? | ??? | F |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.) Буквы в ответе пишите подряд, никаких разделителей между буквами ставить
не нужно.
Пример. Если бы функция была задана выражением ¬x \/ y, зависящим
от двух переменных: x и y, и был приведён фрагмент её таблицы истинности, содержащий все наборы аргументов, при которых функция истинна.
| Переменная 1 | Переменная 2 | Функция |
| ??? | ??? | F |
| 0 | 0 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Тогда первому столбцу соответствовала бы переменная y, а второму
столбцу переменная x. В ответе следовало бы написать: yx.
Показать ответ и решение
Ответ: wzyx
F=0 ⇔ x=1, y=0, не (z=0, w=1). Перебор перестановок – wzyx.
Пример 2 · код ФИПИ A5D159
Миша заполнял таблицу истинности логической функции F
((z → x) → (x ≡ y)) \/ ¬ w,
но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
| F | ||||
| 0 | 1 | 0 | 0 | |
| 0 | 0 | 0 | ||
| 1 | 1 | 0 |
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Функция задана выражением ¬x \/ y, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.
| F | ||
| 0 | 1 | 0 |
В этом случае первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе следует написать: yx.
Показать ответ и решение
Ответ: yxwz
F = 0 при и .
Перебор перестановок столбцов с заполнением пропусков даёт yxwz.
Пример 3 · код ФИПИ DC218E
Миша заполнял таблицу истинности функции (¬x \/ ¬y) /\ ¬(x≡z) /\ w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
| (¬x \/ ¬y) /\ ¬(x≡z) /\ w | ||||
| 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | |||
| 1 | 0 | 0 | 1 |
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы
в ответе пишите подряд, никаких разделителей между буквами ставить
не нужно.
Пример. Функция задана выражением ¬x \/ y, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.
| ¬x \/ y | ||
| 0 | 1 | 0 |
В этом случае первому столбцу соответствует переменная y, а второму столбцу переменная x. В ответе следует написать yx.
Показать ответ и решение
Ответ: xwzy
F=1 требует w=1, , .
Перебор расстановок с достройкой пустых клеток даёт единственный вариант xwzy.
Частые вопросы о задании 2
Сколько баллов даёт задание 2 ЕГЭ по информатике?
Максимум – 1 первичный балл. Норма времени на экзамене – около 3 мин. Уровень сложности – Б.
Что проверяет задание 2?
Задание 2 – дана логическая функция F от четырёх переменных и фрагмент таблицы истинности с пропусками; столбцы не подписаны. Нужно определить, какой переменной соответствует каждый столбец. 1 балл. Надёжнее всего решать перебором на Python.
Как подготовиться к заданию 2?
Прочитайте теорию выше: алгоритм, нужные факты и ловушки. Затем решите подход из 10 заданий с автопроверкой и разбором – первые без регистрации – и вернитесь к ошибкам. В пробниках Сотки номер встречается в полных вариантах ФИПИ с подсчётом баллов.