Алгебра логики — нормальные формы и схемы
Базовые связки ∧, ∨, ¬ разобраны в логике. Здесь — алгебра логики как инженерный инструмент: привести булеву функцию к каноническому виду, упростить её и связать с проверкой тождеств над множествами.
От формулы к функции
Формула ϕ(x₁,…,xₙ) задаёт булеву функцию f — {0,1}ⁿ → {0,1}. Таблица истинности из 2ⁿ строк определяет функцию однозначно. Две формулы эквивалентны (ϕ ∼ ψ), если совпадают на всех наборах — так проверяют рефакторинг сложных if и эквивалентность спецификаций.
Нормальные формы
| Форма | Структура | Когда удобна |
|---|---|---|
| ДНФ | ∨ конъюнкт литералов | "хотя бы один сценарий истинен" |
| КНФ | ∧ дизъюнкт литералов | "все ограничения выполнены" |
| СДНФ | по конъюнкте на каждую единицу таблицы | построение и склеивание |
| СКНФ | двойственно СДНФ | проверки "для всех комбинаций" |
Минимальная ДНФ — кратчайшее эквивалентное представление (меньше литералов → проще схема или условие). Путь: СДНФ → склеивание соседних минтермов → матрица Квайна (импликанты покрывают все единицы) → тупиковая форма с минимумом литералов.
Карта Карно
Для 2–4 переменных минтермы размещают в ячейках так, чтобы соседи отличались одной переменной (код Грея). Соседние 1 объединяют в прямоугольники размеров 1, 2, 4, … — из покрытия читают упрощённую ДНФ.
| Переменных | Размер карты | Типичное применение |
|---|---|---|
| 2 | 2×2 | два флага доступа |
| 3 | 2×4 | три условия в контроллере |
| 4 | 4×4 | ручная минимизация перед кодогенерацией |
При пяти и более переменных переходят к программным минимизаторам или SAT-решателям, а не к ручной карте.
Двойственность и полнота
Принцип двойственности: в формуле, построенной только из ∧, ∨, ¬, конъюнкции и дизъюнкции меняют местами — получают двойственную функцию f⁺. СДНФ ↔ СКНФ. Закон де Моргана — частный случай связи логики и операций над множествами (A ∪ B ↔ Ā ∩ B̄ в дополнении).
Полная система функций (теорема Поста) — такой набор связок, через который выражается любая булева функция. Классический базис — {∧, ∨, ¬}. В цифровой схемотехнике достаточно даже одной связки NAND или NOR.
Логические сети
Контактная схема — граф, где рёбра помечены переменными xᵢ (замыкающий контакт при xᵢ=1) или x̄ᵢ (при xᵢ=0). Проводимость между полюсами реализует булеву функцию. Исторически это модель реле и транзисторных вентилей; сегодня тот же смысл у комбинационных схем в FPGA и в синтезе из HDL.
Минимизация ДНФ — тот же смысл, что упрощение цепочки if с четырьмя булевыми флагами без изменения таблицы истинности. Проверка тождества A ∪ B = A ∪ (B \ A) можно свести к эквивалентности формул над характеристическими функциями множеств.
Предикатная логика и кванторы — в Логика. Формальные автоматы и regex — в Формальные языки и автоматы → Конечные автоматы и регулярные языки.