Алгебра логики
1. Что такое алгебра логики
Алгебра логики — это математическая система, в которой логические высказывания рассматриваются как переменные, принимающие значения 0 (ложь) и 1 (истина).
Все логические операции определены формально, как операции над этими значениями.
Эта алгебра лежит в основе логических схем, вычислительных машин и цифровой логики.
Множество значений:
\[
B = \{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. Пример преобразования
Пусть дана формула:
\[
\neg(p \to q)
\]
- Раскрываем импликацию:
\[
\neg(\neg p \vee q)
\]
- По закону де Моргана:
\[
p \wedge \neg q
\]
→ Отрицание импликации означает, что причина истинна, а следствие ложно.
10. Смысл алгебры логики
Алгебра логики формализует рассуждения — позволяет:
- проверять истинность сложных выражений;
- упрощать логические формулы;
- проектировать логические схемы (элементы И, ИЛИ, НЕ);
- формально доказывать тождества и следствия.
По сути, это арифметика для истинности,
где \(1\) — это истина, а \(0\) — ложь.
11. Минимизация логических выражений
Цель — упростить выражение, сохранив эквивалентность.
Для этого применяют законы:
- идемпотентности,
- дистрибутивности,
- поглощения,
- де Моргана.
Пример:
\[
p \vee (p \wedge q) = p
\]
(по закону поглощения)
12. Алгебра логики и схемы
| Операция | Символ | Логический элемент |
|---|---|---|
| \(\neg\) | NOT | Инвертор |
| \(\wedge\) | AND | Элемент “И” |
| \(\vee\) | OR | Элемент “ИЛИ” |
| \(\oplus\) | XOR | Исключающее ИЛИ |
| \(\to\) | — | Реализуется через OR и NOT |
Пример схемы:
\[
p \to q \equiv \neg p \vee q
\]
⇒ можно построить с помощью NOT и OR.
13. Булевая алгебра как формальная система
Булева алгебра — это система \((B, \vee, \wedge, \neg, 0, 1)\), где:
- \((B, \vee, \wedge)\) — коммутативные, ассоциативные операции
- Действуют законы дистрибутивности
- Существуют нейтральные элементы: \(0, 1\)
- Для каждого \(x \in B\) существует дополнение \(\neg x\)
такое, что \(x \vee \neg x = 1\) и \(x \wedge \neg x = 0\)
14. Пример: проверка эквивалентности
Докажем, что:
\[
p \to q \equiv \neg p \vee q
\]
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\}\).
- Любую формулу можно упростить, привести к нормальной форме или реализовать логически.