Логические операции: И, ИЛИ, НЕ, импликация, эквивалентность

Зачем это в ЕГЭ. Задания на логические операции встречаются в №2 и №15 ЕГЭ по информатике. В №2 это обычно 1 первичный балл за простую проверку понимания операций, в №15 — до 2 баллов за сложные выражения с кванторами. Встречается в 90% вариантов.

Главная идея. Логические операции — это «кирпичики» для построения сложных условий. Ключ — чётко знать таблицы истинности и уметь упрощать выражения, особенно импликацию ($A \to B = \neg A \lor B$) и эквивалентность ($A \leftrightarrow B = (A \land B) \lor (\neg A \land \neg B)$).

Алгоритм (чеклист).
1. Выписать все переменные и их возможные значения.
2. Заменить все сложные операции (→, ↔) на базовые (¬, ∧, ∨) по формулам.
3. Построить таблицу истинности для упрощённого выражения.
4. Для №15: проверить выполнимость при разных кванторах («существует» — хотя бы одна 1, «для всех» — все 1).
5. Сравнить результат с условием задачи.

Опоры (кратко).
- Таблица истинности для базовых операций:
- $A \land B$: 1 только если оба 1
- $A \lor B$: 0 только если оба 0
- $\neg A$: инверсия
- Формулы замены:
- $A \to B \equiv \neg A \lor B$
- $A \leftrightarrow B \equiv (A \land B) \lor (\neg A \land \neg B)$
- Закон де Моргана: $\neg (A \land B) \equiv \neg A \lor \neg B$

Пример 1 (построение таблицы истинности).
Дано: $(A \lor \neg B) \land (B \to A)$.
Шаг 1. Заменяем импликацию: $(A \lor \neg B) \land (\neg B \lor A)$.
Шаг 2. Упрощаем: $(A \lor \neg B) \land (A \lor \neg B) = A \lor \neg B$.
Шаг 3. Строим таблицу для $A \lor \neg B$:
| A | B | ¬B | Результат |
|---|---|----|-----------|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |

Пример 2 (задача с кванторами, №15).
Дано: $\forall x \ (P(x) \to Q(x))$. При каких условиях ложно?
Шаг 1. Раскрываем импликацию: $\forall x \ (\neg P(x) \lor Q(x))$.
Шаг 2. Отрицание квантора: $\exists x \ \neg (\neg P(x) \lor Q(x))$.
Шаг 3. Упрощаем отрицание: $\exists x \ (P(x) \land \neg Q(x))$.
Ответ: выражение ложно, если существует $x$, для которого $P(x) = 1$ и $Q(x) = 0$.

Типичные ошибки.
1. Путаница в таблице истинности для импликации. Запоминаем: «ложь только когда из истины следует ложь» ($1 \to 0 = 0$).
2. Неправильное отрицание кванторов. $\neg \forall = \exists \neg$, а не наоборот.
3. Потеря скобок при замене операций. Всегда сохраняйте порядок действий.
4. Подмена переменных в №15. Проверяйте, что $x$ не «пропал» при преобразованиях.

Дальше. Разберите задачи на поиск количества решений логического уравнения — это частый подтип в №15.