Алгебра логики — нормальные формы и схемы

НЕ ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Архитектору Инженеру

Базовые связки ∧, ∨, ¬ разобраны в логике. Здесь — алгебра логики как инженерный инструмент: привести булеву функцию к каноническому виду, упростить её и связать с проверкой тождеств над множествами.

---

От формулы к функции

Формула ϕ(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) можно свести к эквивалентности формул над характеристическими функциями множеств.

Предикатная логика и кванторы — в 31. Формальные автоматы и regex — в 38 → 44.

---