Задание 2 ЕГЭ по информатике: решайте с автопроверкой

Задание 2 проверяет, умеете ли вы работать с логическими выражениями. Дана функция от четырёх переменных и несколько строк её таблицы истинности, часть клеток пуста. Нужно понять, какой переменной соответствует каждый столбец.

Решать задачи номера

Как решать программой

Руками такие задачи решают рассуждением о том, при каких значениях выражение ложно. Программа решает их перебором: переменных всего четыре, поэтому вариантов расстановки столбцов 24, а вариантов заполнить пустые клетки немного.

Запишите выражение как функцию Python: «и» — это and, «или» — это or, «не» — это not, импликация a → b — это (not a) or b, равносильность a ≡ b — это a == b. Затем переберите все перестановки букв из itertools.permutations и все заполнения пустых клеток из itertools.product. Расстановка подходит, если строки фрагмента получаются разными и в каждой функция даёт значение из последнего столбца.

Частая ошибка: забыть, что строки фрагмента различны. Без этой проверки программа может найти лишние расстановки.

Разбор примера

Функция ((x ∨ ¬y) ∧ (z → w)) ∨ (x ∧ z), фрагмент из трёх строк. Пустые клетки в задаче обозначены -1, в программе для наглядности None. Программа перебирает расстановки и заполнения и печатает подошедшую расстановку.

from itertools import permutations, product

def F(x, y, z, w):
    return ((x or not y) and (not z or w)) or (x and z)

rows = [[None, 0, None, 1, 0], [0, 0, 0, 1, 1], [None, 1, 1, 0, 0]]
blanks = sum(r[:4].count(None) for r in rows)
answers = set()
for order in permutations('xyzw'):
    for fill in product((0, 1), repeat=blanks):
        it = iter(fill)
        full = [[next(it) if c is None else c for c in r[:4]] for r in rows]
        if len(set(map(tuple, full))) == len(full) and all(
                int(F(**dict(zip(order, f)))) == r[4] for f, r in zip(full, rows)):
            answers.add(''.join(order))
print(*answers)

Программа печатает

xzyw

Подходит одна расстановка: x, z, y, w. Проверить её легко и руками: подставьте значения второй строки, где пустых клеток нет, и убедитесь, что функция равна единице. Остальные 23 расстановки отпадают уже на одной из трёх строк.

Решить эту задачу

Задачи к заданию 2

  • Столбцы для ((x ∨ ¬y) ∧ (z → w)) ∨ (x ∧ z)ЛёгкаяРешать
  • Три переменные: ((x ≡ y) → z) ∧ (x ∨ z)ЛёгкаяРешать
  • Строки, где ¬(x → z) ∨ (y ≡ (w ∨ z)) истиннаЛёгкаяРешать
  • Строки, где ((x ∨ y) → (z ≡ w)) ∧ (w → x) ложнаЛёгкаяРешать
  • Сколько расстановок столбцов подходитЛёгкаяРешать
  • Три переменные, строки с F = 1: сколько вариантовЛёгкаяРешать
  • Две функции в одной таблицеЛёгкаяРешать
  • Все подходящие порядки столбцовЛёгкаяРешать

Бесплатно и без регистрации: пишете код в браузере и проверяете его тестами (без аккаунта — несколько задач в день).

Вопросы и ответы

Можно ли решить задание 2 без программы?
Да, рассуждением. Но программа на десять строк не ошибается в знаках и проверяет ответ, найденный руками.
Как записать импликацию в Python?
Как (not a) or b. Для 0 и 1 подходит и сравнение a <= b.
Что делать с пустыми клетками?
Перебрать все способы заполнить их нулями и единицами. Клеток мало, поэтому перебор быстрый.