1. Что такое алгебра логики

Алгебра логики — это математическая система, в которой логические высказывания рассматриваются как переменные, принимающие значения 0 (ложь) и 1 (истина).
Все логические операции определены формально, как операции над этими значениями.

Эта алгебра лежит в основе логических схем, вычислительных машин и цифровой логики.

Множество значений:

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

• отрицание (НЕ): $\neg$
• конъюнкция (И): $\wedge$
• дизъюнкция (ИЛИ): $\vee$

2. Переменные и константы

Элемент	Обозначение	Значение	Пояснение
Логическая переменная	$p, q, r, …$	$0$ или $1$	принимает одно из двух значений
Константы	$0, 1$	$0$ — ложь, $1$ — истина	служат для выражения крайних значений

Пример:
Если $p$ означает «идёт дождь», то
$p = 1$ — дождь идёт,
$p = 0$ — дождя нет.

3. Основные логические операции

Операция	Символ	Формула	Таблица истинности	Смысл
Отрицание	$\neg p$	меняет 0↔1	$p=1 \Rightarrow \neg p=0$ $p=0 \Rightarrow \neg p=1$	инверсия
Конъюнкция (И)	$p \wedge q$	$\min(p,q)$	$(1,1)\to1$, остальное→0	истина только если оба истинны
Дизъюнкция (ИЛИ)	$p \vee q$	$\max(p,q)$	$(0,0)\to0$, остальное→1	истина если хотя бы одно истинно
XOR (исключающее ИЛИ)	$p \oplus q$	$p+q \pmod{2}$	$1+1=0$	истина, если ровно одно истинно
Импликация	$p \to q$	$\neg p \vee q$	ложна только при $p=1, q=0$	«если p, то q»
Эквиваленция	$p \leftrightarrow q$	$(p \to q) \wedge (q \to p)$	1, если одинаковы	«тогда и только тогда»

4. Таблица истинности для основных операций

$p$	$q$	$\neg p$	$p \wedge q$	$p \vee q$	$p \to q$	$p \leftrightarrow q$	$p \oplus q$
1	1	0	1	1	1	1	0
1	0	0	0	1	0	0	1
0	1	1	0	1	1	0	1
0	0	1	0	0	1	1	0

5. Основные законы булевой алгебры

Закон	Формула	Пояснение
Идемпотентность	$p \vee p = p$, $p \wedge p = p$	Повторение ничего не меняет
Коммутативность	$p \vee q = q \vee p$, $p \wedge q = q \wedge p$	Порядок не важен
Ассоциативность	$(p \vee q) \vee r = p \vee (q \vee r)$	Скобки можно менять местами
Дистрибутивность	$p \wedge (q \vee r) = (p \wedge q) \vee (p \wedge r)$	Распределение одной операции над другой
Нейтральные элементы	$p \vee 0 = p$, $p \wedge 1 = p$	0 и 1 ведут себя как в арифметике
Поглощение	$p \vee (p \wedge q) = p$, $p \wedge (p \vee q) = p$	“более сильное” условие поглощает слабое
Дополнение	$p \vee \neg p = 1$, $p \wedge \neg p = 0$	закон исключённого третьего
Двойное отрицание	$\neg(\neg p) = p$	инверсия дважды возвращает исходное
Де Моргана	$\neg(p \wedge q) = \neg p \vee \neg q$ $\neg(p \vee q) = \neg p \wedge \neg q$	связь между ∧ и ∨ через отрицание

6. Алгебраические преобразования (эквивалентности)

Преобразование	Эквивалент	Комментарий
$p \to q$	$\neg p \vee q$	Определение импликации
$p \leftrightarrow q$	$(p \wedge q) \vee (\neg p \wedge \neg q)$	Эквиваленция — оба одинаковы
$p \oplus q$	$(p \vee q) \wedge \neg(p \wedge q)$	XOR — строго одно истинно
$\neg(p \to q)$	$p \wedge \neg q$	Отрицание импликации

7. Тавтология, противоречие, выполнимость

Термин	Определение	Пример
Тавтология	Формула, истинная при любых значениях переменных	$p \vee \neg p$
Противоречие	Формула, ложная при любых значениях	$p \wedge \neg p$
Выполнимая формула	Истинна хотя бы при одном наборе значений	$p \wedge q$ (истинна если оба 1)

8. Совершенная нормальная форма

Любую логическую формулу можно привести к стандартному виду:

Вид	Обозначение	Форма	Пояснение
Дизъюнктивная нормальная форма (ДНФ)	Дизъюнкция (ИЛИ) конъюнктов (И)	$(p \wedge q) \vee (\neg p \wedge r)$	Истинна, если истинна хотя бы одна строка таблицы
Конъюнктивная нормальная форма (КНФ)	Конъюнкция (И) дизъюнктов (ИЛИ)	$(p \vee \neg q) \wedge (q \vee r)$	Ложна, если ложна хотя бы одна строка таблицы

Формулы в ДНФ и КНФ эквивалентны исходной формуле, просто переписаны системно.

9. Пример преобразования

Пусть дана формула:

1. Раскрываем импликацию:

1. По закону де Моргана:

→ Отрицание импликации означает, что причина истинна, а следствие ложно.

10. Смысл алгебры логики

Алгебра логики формализует рассуждения — позволяет:

• проверять истинность сложных выражений;
• упрощать логические формулы;
• проектировать логические схемы (элементы И, ИЛИ, НЕ);
• формально доказывать тождества и следствия.

По сути, это арифметика для истинности,
где $1$ — это истина, а $0$ — ложь.

11. Минимизация логических выражений

Цель — упростить выражение, сохранив эквивалентность.
Для этого применяют законы:

• идемпотентности,
• дистрибутивности,
• поглощения,
• де Моргана.

Пример:

(по закону поглощения)

12. Алгебра логики и схемы

Операция	Символ	Логический элемент
$\neg$	NOT	Инвертор
$\wedge$	AND	Элемент “И”
$\vee$	OR	Элемент “ИЛИ”
$\oplus$	XOR	Исключающее ИЛИ
$\to$	—	Реализуется через OR и NOT

Пример схемы:

⇒ можно построить с помощью NOT и OR.

13. Булевая алгебра как формальная система

Булева алгебра — это система $(B, \vee, \wedge, \neg, 0, 1)$, где:

1. $(B, \vee, \wedge)$ — коммутативные, ассоциативные операции
2. Действуют законы дистрибутивности
3. Существуют нейтральные элементы: $0, 1$
4. Для каждого $x \in B$ существует дополнение $\neg x$
   такое, что $x \vee \neg x = 1$ и $x \wedge \neg x = 0$

14. Пример: проверка эквивалентности

Докажем, что:

1. Таблица истинности:

p	q	$p \to q$	$\neg p \vee q$
1	1	1	1
1	0	0	0
0	1	1	1
0	0	1	1

Результаты совпадают → формулы эквивалентны.

Итого

• Алгебра логики — это математическая модель рассуждений.
• Основные операции: $\neg, \wedge, \vee$.
• Из них строятся сложные (импликация, эквиваленция, XOR).
• Всё сводится к булевой системе ${0,1}$.
• Любую формулу можно упростить, привести к нормальной форме или реализовать логически.