Алгебра логики: операции, таблицы истинности, законы

Коротко о главном

Алгебра логики работает с высказываниями, которые могут быть либо истинными (1, True), либо ложными (0, False). Из простых высказываний с помощью логических операций строятся сложные. Задание 3 ОГЭ проверяет умение читать таблицы истинности и определять значения переменных по условию, задание 8 — вычислять количество путей/чисел с помощью логики или строить таблицы истинности по формуле.

Главное, что нужно знать наизусть: таблицы истинности НЕ, И, ИЛИ, приоритет операций и основные законы преобразования формул.

Определения и формулы/правила

Логические операции

Операция	Обозначение	Название	Смысл
Отрицание	$\lnot A$, $\overline{A}$	НЕ (NOT)	меняет значение на противоположное
Конъюнкция	$A \land B$, $A \cdot B$, $A \text{ И } B$	И (AND)	истинно, только если оба истинны
Дизъюнкция	$A \lor B$, $A + B$, $A \text{ ИЛИ } B$	ИЛИ (OR)	истинно, если хотя бы одно истинно
Импликация	$A \rightarrow B$	ЕСЛИ...ТО	ложно только когда $A=1, B=0$
Эквивалентность	$A \leftrightarrow B$, $A \sim B$	равносильно	истинно, когда $A$ и $B$ совпадают
Исключающее ИЛИ	$A \oplus B$	XOR	истинно, когда $A$ и $B$ различны

Таблицы истинности

$A$	$B$	$\lnot A$	$A \land B$	$A \lor B$	$A \rightarrow B$	$A \leftrightarrow B$
0	0	1	0	0	1	1
0	1	1	0	1	1	0
1	0	0	0	1	0	0
1	1	0	1	1	1	1

Приоритет операций (от высшего к низшему):

1. $\lnot$ (отрицание)
2. $\land$ (И)
3. $\lor$ (ИЛИ)
4. $\rightarrow$ (импликация)
5. $\leftrightarrow$ (эквивалентность)

Скобки всегда выполняются первыми, независимо от приоритета.

Основные законы алгебры логики

• Коммутативность: $A \land B = B \land A$; $A \lor B = B \lor A$
• Ассоциативность: $(A \land B) \land C = A \land (B \land C)$
• Дистрибутивность: $A \land (B \lor C) = (A \land B) \lor (A \land C)$
• Законы де Моргана: $\lnot(A \land B) = \lnot A \lor \lnot B$; $\lnot(A \lor B) = \lnot A \land \lnot B$
• Двойное отрицание: $\lnot \lnot A = A$
• Идемпотентность: $A \land A = A$; $A \lor A = A$
• Законы с константами: $A \land 1 = A$; $A \land 0 = 0$; $A \lor 1 = 1$; $A \lor 0 = A$
• Правило исключённого третьего: $A \lor \lnot A = 1$
• Правило противоречия: $A \land \lnot A = 0$
• Замена импликации: $A \rightarrow B = \lnot A \lor B$

Как применять

Пример 1. Чтение таблицы истинности (тип задания 3)

Дана формула $F = \lnot A \lor (B \land C)$. Нужно найти, при каких значениях $A, B, C$ формула ложна.

Формула $\lnot A \lor (B \land C)$ ложна только когда обе части ложны: $\lnot A = 0$ и $B \land C = 0$. Отсюда $A = 1$, и хотя бы одно из $B, C$ равно 0. Подходят наборы: $(1,0,0), (1,0,1), (1,1,0)$ — три набора из восьми возможных.

Пример 2. Определение истинного высказывания

Дано: только одно из четырёх утверждений верно.

• $P_1$: число делится на 2
• $P_2$: число делится на 3
• $P_3$: число делится на 5
• $P_4$: число делится на 7

Если известно, что верно ровно одно, ищем число, которое делится ровно на одно из указанных значений (например, 25 делится на 5, но не на 2, 3, 7 — подходит).

Пример 3. Применение закона де Моргана

Упростить: $\lnot(A \land \lnot B)$.

По закону де Моргана: $\lnot(A \land \lnot B) = \lnot A \lor \lnot \lnot B = \lnot A \lor B$.

Это равносильно импликации $A \rightarrow B$.

Типичные ошибки

• Путают приоритет: забывают, что $\land$ выполняется раньше $\lor$ (как умножение раньше сложения).
• Ошибка в импликации: считают её ложной во всех случаях, кроме $A=1,B=1$, забывая, что при $A=0$ импликация истинна всегда.
• Неверно применяют закон де Моргана: меняют операцию, но забывают поставить отрицание над каждой переменной отдельно.
• Путают эквивалентность и импликацию — эквивалентность симметрична, импликация нет: $A \rightarrow B \ne B \rightarrow A$.
• Забывают, что скобки меняют порядок вычисления независимо от стандартного приоритета операций.
• При построении таблицы истинности пропускают наборы значений переменных или дублируют их.

Где встречается на экзамене

Задание 3 обычно требует определить истинность составного высказывания или количество определённых наборов значений переменных по таблице истинности либо словесному описанию. Задание 8 часто связано с построением таблиц истинности для формул с 2–3 переменными, подсчётом количества единиц/нулей в результате или упрощением логического выражения перед вычислением ответа. Понимание законов де Моргана и приоритета операций критично для быстрого решения обоих заданий.