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

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

Алгебра логики работает с высказываниями, которые принимают одно из двух значений: истина (1) или ложь (0). Над высказываниями выполняются логические операции — отрицание, конъюнкция, дизъюнкция, импликация и эквиваленция. Задача 2 ЕГЭ требует восстановить логическое выражение по таблице истинности, задача 15 — найти количество решений уравнения с логическими переменными. Ключ к обеим — твёрдое знание таблиц истинности и законов преобразования выражений.

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

Основные операции:

Операция	Название	Обозначение	Читается
$\lnot A$	отрицание (НЕ)	$\lnot A$, $\overline{A}$	"не A"
$A \land B$	конъюнкция (И)	$A \land B$, $A \cdot B$	"A и B"
$A \lor B$	дизъюнкция (ИЛИ)	$A \lor B$	"A или B"
$A \to B$	импликация	$A \to B$	"если A, то B"
$A \leftrightarrow B$	эквиваленция	$A \leftrightarrow B$, $A \equiv B$	"A тогда и только тогда, когда B"
$A \oplus B$	сложение по модулю 2 (XOR)	$A \oplus B$	"либо A, либо B"

Таблица истинности всех операций:

$A$	$B$	$\lnot A$	$A \land B$	$A \lor B$	$A \to B$	$A \leftrightarrow B$	$A \oplus B$
0	0	1	0	0	1	1	0
0	1	1	0	1	1	0	1
1	0	0	0	1	0	0	1
1	1	0	1	1	1	1	0

Важнейшее: импликация ложна только когда $A=1$, $B=0$ ("из истины следует ложь"). Во всех остальных случаях она истинна.

Основные законы:

• Законы де Моргана: $$\lnot(A \land B) = \lnot A \lor \lnot B, \qquad \lnot(A \lor B) = \lnot A \land \lnot B$$
• Дистрибутивность: $$A \land (B \lor C) = (A \land B) \lor (A \land C)$$ $$A \lor (B \land C) = (A \lor B) \land (A \lor C)$$
• Идемпотентность: $A \land A = A$, $A \lor A = A$
• Закон исключённого третьего: $A \lor \lnot A = 1$
• Закон противоречия: $A \land \lnot A = 0$
• Двойное отрицание: $\lnot \lnot A = A$
• Выражение импликации через ИЛИ и НЕ: $$A \to B = \lnot A \lor B$$
• Эквиваленция через импликации: $$A \leftrightarrow B = (A \to B) \land (B \to A)$$
• Приоритет операций (от старшего к младшему): $\lnot$, $\land$, $\lor$, $\to$, $\leftrightarrow$. Скобки меняют порядок вычислений.

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

Пример 1 (тип задания 2). Дан фрагмент таблицы истинности для выражения $F = (\lnot X \lor Y) \land Z$. При $X=0, Y=0$ определить, при каком $Z$ значение $F=1$. Подставляем: $\lnot X = 1$, значит $\lnot X \lor Y = 1$ при любом $Y$. Тогда $F = 1 \land Z = Z$. Значит $F=1$ только при $Z=1$.

Пример 2 (упрощение выражения). Упростить $\lnot(A \lor B) \lor (A \land B)$. По де Моргану: $\lnot A \land \lnot B \lor A \land B$. Это классическое выражение эквиваленции: результат равен $A \leftrightarrow B$ (истинно, когда $A$ и $B$ совпадают).

Пример 3 (тип задания 15). Сколько решений имеет уравнение $(X \to Y) \land (Y \to Z) = 1$? Уравнение истинно, когда обе импликации истинны одновременно. Переберём по логике: запрет только там, где предыдущая переменная 1, а следующая 0. Строим таблицу для трёх переменных (8 наборов) и вычёркиваем те, где $X=1,Y=0$ или $Y=1,Z=0$. Остаются: 000, 001, 011, 111 — то есть 4 решения (наборы, где значения "не убывают": $X \le Y \le Z$).

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

• Путают импликацию с дизъюнкцией: забывают, что $A \to B$ ложна только в одном случае из четырёх.
• Неверно применяют закон де Моргана: меняют операцию, но забывают поставить отрицание над каждой переменной ($\lnot(A \land B) \ne \lnot A \land \lnot B$).
• Ошибаются в приоритете операций — вычисляют дизъюнкцию раньше конъюнкции без скобок.
• В задании 15 забывают учитывать все переменные уравнения и теряют часть решений при переборе.
• Путают $\oplus$ (XOR) с обычным ИЛИ: при $A=B=1$ у XOR результат 0, а у ИЛИ — 1.
• Считают эквиваленцию симметричной операцией "или", хотя она истинна именно при совпадении значений, а не при их наличии.

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

Задание 2 проверяет умение восстановить недостающую часть логического выражения или таблицы истинности, используя знание операций и их таблиц. Задание 15 требует подсчитать количество наборов переменных, при которых сложное логическое уравнение истинно, — здесь важны законы преобразования и аккуратный перебор или построение дерева решений.