Логика для ЕГЭ по информатике: операции, законы и задание №2

Если в выражении нет скобок, операции выполняются не слева направо.

Обычно используется порядок:

1. ¬       НЕ
2. ∧       И
3. ∨       ИЛИ
4. →       импликация
5. ≡       эквивалентность

Например:

¬x ∨ y ∧ z

сначала:

¬x

и:

y ∧ z

а уже потом выполняется ИЛИ.

Но на ЕГЭ я рекомендую простой принцип:

Если переводишь выражение в Python — ставь скобки.

Не пытайся каждый раз вспоминать приоритет всех операторов языка.

Например:

(not x) or (y and z)

читается гораздо надёжнее.

Не нужно учить десятки формул.

Вот несколько действительно полезных.

Двойное отрицание

¬¬A = A

Законы де Моргана

Очень важны:

¬(A ∧ B) = ¬A ∨ ¬B

и:

¬(A ∨ B) = ¬A ∧ ¬B

Простой способ запомнить:

отрицание заходит внутрь скобок и меняет И ↔ ИЛИ.

Например:

НЕ (идёт дождь И холодно)

равносильно:

НЕ идёт дождь ИЛИ НЕ холодно

Импликация

Обязательно нужно знать и использовать:

A → B = ¬A ∨ B

Эта формула особенно полезна в заданиях №2 и №15.

В современном задании №2 даётся:

1. логическая функция;
2. несколько строк таблицы истинности;
3. неизвестный порядок переменных в столбцах.

Нужно определить:

какая переменная соответствует каждому столбцу.

ФИПИ отдельно рекомендует для этого задания повторить логические операции и таблицы истинности; одна из характерных ошибок — забыть требование, что приведённые строки таблицы должны быть различными.

Рассмотрим пример современного типа задания.

Миша заполнял таблицу истинности логической функции $F=((x\equiv \mathrm{\neg }y)\to \mathrm{\neg }(w\to x))\vee \mathrm{\neg }z$, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных $w,x,y,z$.

Определите, какому столбцу таблицы соответствует каждая из переменных $w,x,y,z$.

Но есть ещё очень надёжный способ — перебрать все варианты.

Для четырёх переменных существует всего:

2⁴ = 16 наборов значений.

Поэтому Python может быстро построить нужные строки таблицы истинности.

Например:

Для задания №2 полезно уметь оба способа.

Аналитическое решение

Хорошо, когда выражение легко упрощается.

Например:

A ∧ B ∧ C = 1

сразу означает:

A = 1
B = 1
C = 1

Такое решение часто занимает меньше минуты.

Python

Универсальнее.

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

Лучший вариант на экзамене:

понимать логику аналитически, но уметь быстро проверить себя кодом.

Перепутать И и ИЛИ

И → нужны все единицы
ИЛИ → достаточно одной

Неверно записать импликацию

Правильно:

A <= B

Забыть про скобки

Лучше написать:

((not x) or y) and z

чем надеяться на приоритет операций.

Использовать одинаковые строки таблицы

Если в условии сказано, что строки различны, один и тот же набор нельзя использовать дважды. Это одна из типичных ошибок, отмечаемых в методических материалах ФИПИ.

Не стоит учить таблицы истинности как набор случайных нулей и единиц.

Намного полезнее понимать смысл операций:

НЕ — наоборот.
И — должны выполниться оба условия.
ИЛИ — достаточно одного.
Импликация — запрещён вариант 1 → 0.
Эквивалентность — одинаковые значения.
XOR — разные значения.

После этого и задание №2, и более сложная логика в других заданиях ЕГЭ становятся значительно понятнее.

Что нужно знать по логике для ЕГЭ по информатике?
Основные операции: отрицание, конъюнкцию, дизъюнкцию, импликацию, эквивалентность и их запись на Python.

Как запомнить импликацию?
Она ложна только в одном случае: 1 → 0.

Нужно ли решать задание №2 программой?
Нет. Многие задачи удобно решаются аналитически, но Python даёт универсальный способ проверки.