§20. Преобразование логических выражений
Давайте разберёмся: зачем упрощать логические выражения, если можно просто строить таблицы истинности? Потому что при 10 переменных таблица содержит 1024 строки. Алгебра логики — это «читы» для работы с любой сложностью. Разберём всё по шагам.
Каждое решение — это логическая операция. Булева алгебра — язык, которым думают компьютеры.
20.1. Основные законы алгебры логики
Это как таблица умножения для логики — нужно понять один раз, а потом пользоваться везде. Каждый закон доказывается таблицей истинности, но мы запомним их по смыслу.
🤔 Зачем это нужно?
Представь: ты пишешь условие доступа в игре — «если игрок невидим ИЛИ у него есть пропуск, то пустить» — и хочешь оптимизировать проверку. Именно здесь и нужны законы алгебры логики: они позволяют упрощать логические выражения, не меняя их смысл.
Таблица основных законов
A & B = B & A
A ∨ B = B ∨ A(A & B) & C = A & (B & C)
(A ∨ B) ∨ C = A ∨ (B ∨ C)A & (B ∨ C) = (A & B) ∨ (A & C)
A ∨ (B & C) = (A ∨ B) & (A ∨ C)A & A = A
A ∨ A = A⚠️ В числах это не работает: 3 × 3 ≠ 3. А в логике — работает!
A & Ā = 0A ∨ Ā = 1Ā̄ = AA ∨ 1 = 1 A ∨ 0 = A
A & 1 = A A & 0 = 0¬(A & B) = Ā ∨ B̄
¬(A ∨ B) = Ā & B̄A & (A ∨ B) = A
A ∨ (A & B) = A🔥 Законы де Моргана — главное оружие программиста
Именно эти два закона помогают убирать отрицание со скобок. Мнемоника: «разбиваешь скобку — переворачиваешь операцию».
Пример из Python: условие
not (a and b)полностью эквивалентно
(not a) or (not b)Компилятор именно так и оптимизирует код!
Как применять законы: разбираем примеры
📌 Пример 1. Закон исключённого третьего
Упростим выражение:
A & B & C ∨ A & B & C̄Выносим за скобки A & B:
= A & B & (C ∨ C̄) ← закон: C ∨ C̄ = 1
= A & B & 1 ← закон: A & 1 = A
= A & B ✓📌 Пример 2. Поглощение и исключённое третье в комбо
Упростим выражение:
(A ∨ B) & (A ∨ B ∨ C) & (A ∨ B ∨ C̄)Замечаем, что в последних двух множителях есть C ∨ C̄:
= (A ∨ B) & (A ∨ B ∨ (C ∨ C̄))
= (A ∨ B) & (A ∨ B ∨ 1) ← C ∨ C̄ = 1
= (A ∨ B) & 1 ← A ∨ 1 = 1
= A ∨ B ✓
Де Морган — это «разбивалка» скобок. Самый используемый закон в реальном коде.
🎯 Ключевые выводы раздела 20.1
- Законы алгебры логики отражают фундаментальные свойства истины и лжи — они работают как обычная алгебра, но с нюансами (например,
A & A = A, а в числах это не так). - Законы де Моргана — самые полезные на практике: ими программисты оптимизируют условия
if/elseбуквально каждый день. - Вынесение общих множителей за скобки (дистрибутивный закон) сокращает количество вычислений — особенно в «горячих» местах кода или схемах процессора.
- Таблица истинности — инструмент проверки, а законы — инструмент преобразования. Вместе они дают полный контроль над логическими выражениями.
🤔 Проверь себя
1. Мини-кейс: В Python написано условие if not (user.is_admin and user.is_active). Перепиши его без отрицания скобок. Какой закон использовал?
Применяем первый закон де Моргана: not (A and B) = (not A) or (not B). Результат: if (not user.is_admin) or (not user.is_active).
2. Мысленный эксперимент: в каком из 10 законов нет аналога в алгебре чисел? Почему A & A = A не работает для чисел?
Закон идемпотентности. В числах: 3 × 3 = 9 ≠ 3. В логике переменная принимает лишь значения 0 или 1, и 1 & 1 = 1, 0 & 0 = 0 — результат совпадает с аргументом.
3. Упрости выражение: (A & B & C̄) ∨ (A & B & C) ∨ (A & B). Подсказка: попробуй сначала применить идемпотентность.
Первые два слагаемых дают A & B (пример 1). Третье слагаемое тоже A & B. По закону идемпотентности: A & B ∨ A & B = A & B.
4. Объясни закон поглощения A ∨ (A & B) = A своему другу через аналогию из реальной жизни.
Пример: «Я куплю мороженое ИЛИ (мороженое И рожок)». Если ты уже купишь мороженое — рожок можно брать или нет, итог тот же. Множество «мороженое» поглощает более узкое множество «мороженое с рожком».
20.2. Логические функции
Любое логическое выражение — это способ задать функцию. Подаём на вход набор 0 и 1, получаем на выходе 0 или 1. Именно так работают все цифровые схемы — от светофора до процессора.
🔢 Сколько существует логических функций?
Для n переменных количество различных булевых функций равно 2^(2^n):
n = 1: 2^2 = 4 функции
n = 2: 2^4 = 16 функций
n = 3: 2^8 = 256 функций
n = 10: 2^1024 ≈ больше, чем атомов во Вселенной!Но нам не нужны все — любую функцию можно выразить через отрицание, конъюнкцию и дизъюнкцию.
16 логических функций двух переменных
Для двух переменных всего 16 функций. Вот ключевые из них:
Константа «Ложь»
F1(A,B) = 0 (всегда 0)Конъюнкция (И)
F2(A,B) = A & BИсключающее ИЛИ (XOR)
F7(A,B) = A ⊕ BИстина, когда значения разные
Дизъюнкция (ИЛИ)
F8(A,B) = A ∨ BСтрелка Пирса (ИЛИ-НЕ)
F9(A,B) = A ↓ B = ¬(A ∨ B)Эквиваленция
F10(A,B) = A ↔ BИстина, когда значения одинаковы
Импликация
F14(A,B) = A → B = Ā ∨ BЛожна только когда A=1, B=0
Штрих Шеффера (И-НЕ)
F15(A,B) = A | B = ¬(A & B)Константа «Истина»
F16(A,B) = 1 (всегда 1)⚡ Функциональная полнота — самая мощная идея
Штрих Шеффера (И-НЕ) и стрелка Пирса (ИЛИ-НЕ) — это функционально полные системы по одной функции. Из одного типа логических вентилей можно собрать любую логическую схему. Именно на этом принципе построены все современные процессоры!
Ā = A | A (NOT через NAND)
A & B = (A | B) | (A | B) (AND через NAND)
A ∨ B = (A | A) | (B | B) (OR через NAND)
Из одного логического вентиля — всё многообразие вычислений. Принцип функциональной полноты в действии.
🎯 Ключевые выводы раздела 20.2
- Логическая функция — это «чёрный ящик»: принимает набор 0/1, выдаёт 0/1. Программа, схема, веб-форма — всё это логические функции.
- Количество функций растёт двойной экспонентой: для 10 переменных их столько, что никакой таблицей не покрыть — поэтому нам и нужны законы преобразования.
- Штрих Шеффера и стрелка Пирса — «атомы» логики. Это объясняет, почему производители чипов могут сделать миллиарды вентилей одного типа и получить любой компьютер.
🤔 Проверь себя
1. В игровом движке Unity: showDeath = (hp <= 0) AND (NOT isInvincible). Это какая из 16 функций по структуре?
F2 (конъюнкция), применённая к двум аргументам, один из которых получен через F13 (отрицание). Формально: F = A & B̄, что соответствует F3 — отрицание обратной импликации.
2. Сколько различных логических функций от четырёх переменных? Запиши вычисление.
n = 4
2^(2^4) = 2^16 = 65 536 функций3. Придумай аналогию для функциональной полноты: что в реальном мире тоже является «одним из всего»?
Например: из одного вида кирпича можно построить любое здание. Или: на языке Pascal из структур if/while можно написать любую программу — это тоже «функционально полная» система управляющих конструкций.
20.3. Составление выражения по таблице истинности (СДНФ)
Что делать, когда у тебя есть таблица истинности, но нет выражения? Существует чёткий алгоритм — он называется построением Совершенной Дизъюнктивной Нормальной Формы (СДНФ).
📋 Алгоритм построения СДНФ: 3 шага
Отмечаем в таблице истинности все наборы, где F = 1.
Для каждого такого набора записываем конъюнкцию: если переменная = 1 → берём её как есть; если = 0 → берём с отрицанием.
Все полученные конъюнкции соединяем операцией ∨. Готово — это СДНФ!
Пример: составляем СДНФ и упрощаем
Дана таблица истинности функции F(A, B, C):
| A | B | C | F |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Шаг 2: конъюнкции для строк с F = 1
Набор (0,1,0): A=0 → Ā, B=1 → B, C=0 → C̄ → Ā & B & C̄
Набор (0,1,1): A=0 → Ā, B=1 → B, C=1 → C → Ā & B & C
Набор (1,1,0): A=1 → A, B=1 → B, C=0 → C̄ → A & B & C̄Шаг 3: СДНФ
F = Ā&B&C̄ ∨ Ā&B&C ∨ A&B&C̄✂️ Упрощение через законы
F = Ā&B&C̄ ∨ Ā&B&C ∨ A&B&C̄
= B & (Ā&C̄ ∨ Ā&C ∨ A&C̄) ← вынесли B
= B & (Ā&(C̄∨C) ∨ A&C̄) ← вынесли Ā из первых двух
= B & (Ā&1 ∨ A&C̄) ← C̄ ∨ C = 1
= B & (Ā ∨ A&C̄) ← Ā&1 = Ā
= B & (Ā∨A) & (Ā∨C̄) ← дистрибутивность
= B & 1 & (Ā ∨ C̄) ← A ∨ Ā = 1
= B & (Ā ∨ C̄) ✓Итог: выражение сократилось с 9 переменных до 3. На уровне схемы — меньше вентилей, меньше энергии, быстрее работа.
Упростить — значит найти суть. Минимальная схема работает быстрее и экономит энергию.
🎯 Ключевые выводы раздела 20.3
- СДНФ — это универсальный алгоритм: для любой таблицы истинности можно построить логическое выражение. Таблица и формула — два равноправных способа задать одну функцию.
- Упрощение — это не просто «красиво». На уровне железа: меньшее выражение = меньше транзисторов = меньше тепла = быстрее процессор.
- Последовательное применение законов — как цепочка ходов в шахматах: каждый шаг законен, и в конце — победа над сложностью.
- СДНФ — не единственная нормальная форма: существует также СКНФ (конъюнктивная). Они дополняют друг друга, как координаты x и y.
🤔 Проверь себя
1. По таблице ниже составь СДНФ и упрости её.
| A | B | F |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
СДНФ: F = Ā&B̄ ∨ Ā&B
Упрощение: F = Ā & (B̄ ∨ B) = Ā & 1 = Ā2. Запиши импликацию A → B в виде СДНФ, а затем упрости. Совпало ли с формулой Ā ∨ B?
Таблица: A→B ложна только при A=1, B=0.
F=1 на наборах: (0,0), (0,1), (1,1)
СДНФ: Ā&B̄ ∨ Ā&B ∨ A&B
= Ā&(B̄∨B) ∨ A&B
= Ā ∨ A&B
= (Ā∨A) & (Ā∨B) ← дистрибутивность
= 1 & (Ā∨B)
= Ā ∨ B ✓ — совпало!3. Творческое задание: придумай логическую задачу из реальной жизни и составь для неё таблицу истинности и выражение.
Например: светофор пропускает пешехода (F=1), если горит зелёный (A=1) И нет машин (B=1). Тогда F = A & B. Или сложнее: турникет в метро открывается, если баланс > 0 ИЛИ есть безлимитная карта.
📌 Итоги параграфа §20
✅ Что ты теперь умеешь
- Применять 10 основных законов алгебры логики для упрощения выражений.
- Объяснять, почему де Морган — это «читкод» для любого программиста.
- Вычислять количество логических функций от n переменных по формуле
2^(2^n). - По таблице истинности строить СДНФ и затем минимизировать её с помощью законов.
- Видеть связь между логическими выражениями и работой реального «железа».
🏆 Задания повышенного уровня
Задание 9. Побитовая конъюнкция
Для какого наименьшего неотрицательного целого числа A формула тождественно истинна?
x & 25 ≠ 0 → (x & 17 = 0 → x & A ≠ 0)Здесь & — побитовая конъюнкция двух неотрицательных целых чисел.
25 = 011001₂ (биты 4, 3, 0)
17 = 010001₂ (биты 4, 0)
Множество истинности предиката (x & 25 ≠ 0):
числа с единицей хотя бы в одном из битов 4, 3, 0.
Множество истинности предиката (x & 17 = 0):
числа с нулями в битах 4 и 0.
Пересечение: числа у которых биты 4 и 0 — нули,
но бит 3 — единица.
Минимальное A должно иметь единицу именно в бите 3:
A = 001000₂ = 8₁₀Задание 11. Система логических уравнений
Сколько решений имеет система?
⎧ (x₁ → x₂) & (x₂ → x₃) & (x₃ → x₄) = 1
⎩ (ȳ₁ ∨ y₂) & (ȳ₂ ∨ y₃) & (ȳ₃ ∨ y₄) = 1Подсказка: второе уравнение — это тоже цепочка импликаций в маскировке, потому что Ā ∨ B = A → B. Каждое уравнение имеет 5 решений:
0 0 0 0
0 0 0 1
0 0 1 1
0 1 1 1
1 1 1 1Так как переменные двух уравнений независимы, по правилу произведения:
Всего решений: 5 × 5 = 25
