Минимизация булевых функций и логические схемы

Учимся делать булевы формулы короче — а значит, схемы дешевле и быстрее — и видеть, как формула становится электронной схемой.

Минимизация булевой функции — поиск её кратчайшего эквивалентного представления (меньше операций и переменных) без изменения таблицы истинности.

Зачем минимизировать

СДНФ всегда работает, но почти всегда избыточна. В реальной схеме каждая логическая операция — это транзисторы: место на кристалле, энергия, задержка. Чем короче формула, тем меньше, дешевле и быстрее схема. Минимизация — это буквально экономия «железа». Те же идеи применяют компиляторы, упрощая логические выражения, и оптимизаторы запросов в базах данных. Минимизация — практическое искусство превращать «правильно» в «эффективно».

Главные законы упрощения

Булева алгебра подчиняется законам, многие из которых мы уже видели в логике и теории множеств. Для минимизации особенно важны два специфических.

Сердце минимизации — склеивание: если два терма различаются только одной переменной (в одном она с отрицанием, в другом без), эту переменную можно выкинуть. Например, (a ∧ b) ∨ (a ∧ ¬b): что бы ни было с b, важно только a — значит, всё выражение равно a. Логично: «a и b, или a и не-b» = «a при любом b» = «a».

Минимизация по шагам

Упростим f = (a ∧ b) ∨ (a ∧ ¬b) ∨ (¬a ∧ b):

• Склеиваем первые два терма по b: (a ∧ b) ∨ (a ∧ ¬b) = a. Осталось a ∨ (¬a ∧ b).
• Применяем тождество a ∨ (¬a ∧ b) = a ∨ b (полезное следствие законов): получаем a ∨ b.

Было три терма с шестью вхождениями переменных — стало a ∨ b, одно «ИЛИ». Проверим, что упрощённая функция совпадает с исходной по таблице истинности — это золотое правило: минимизация не должна менять поведение.

from itertools import product

def original(a, b):
    return (a and b) or (a and not b) or (not a and b)

def minimized(a, b):
    return a or b

# Сверяем таблицы истинности обеих функций
all_equal = all(int(original(a, b)) == int(minimized(a, b))
                for a, b in product([0, 1], repeat=2))

print("a b | исходная  минимизированная")
for a, b in product([0, 1], repeat=2):
    print(f"{a} {b} |    {int(original(a,b))}            {int(minimized(a,b))}")
print("Функции эквивалентны:", all_equal)

Вывод:

a b | исходная  минимизированная
0 0 |    0            0
0 1 |    1            1
1 0 |    1            1
1 1 |    1            1
Функции эквивалентны: True

Таблицы совпали во всех четырёх строках — значит, a ∨ b действительно эквивалентна громоздкой исходной формуле, но втрое короче. Машинная проверка «обе функции дают одну таблицу» — обязательный шаг любой минимизации: упростили, но обязаны убедиться, что ничего не сломали.

Карты Карно — идея

Делать склеивания вручную, выискивая подходящие термы, утомительно и легко ошибиться. Карта Карно — наглядный инструмент, который автоматизирует поиск склеиваний. Это таблица, где строки и столбцы помечены значениями переменных в специальном порядке (код Грея): соседние клетки различаются ровно в одной переменной. Тогда соседние единицы можно объединять в прямоугольники, и каждый прямоугольник — это уже склеенный, упрощённый терм.

Правила коротко: отмечаем единицы функции на карте, накрываем их прямоугольниками размером степени двойки (1, 2, 4, 8 клеток) — чем больше прямоугольник, тем короче терм. Карты Карно отлично работают для 2–4 переменных; для большего числа используют алгоритм Квайна-Мак-Класки (его умеют компьютеры). Идея одна: соседство в коде Грея = возможность склеить.

От формулы к логической схеме

Минимизированная формула напрямую превращается в логическую схему из вентилей (gate). Базовые вентили — это аппаратные «И», «ИЛИ», «НЕ», у каждого свой значок на схемах. Формула a ∨ b — это один вентиль ИЛИ с двумя входами. Формула (a ∧ b) ∨ ¬c — это вентиль И (для a ∧ b), вентиль НЕ (для ¬c) и вентиль ИЛИ, объединяющий их выходы. Так из булевой алгебры рождается реальная электроника: каждая операция в формуле — это физический элемент схемы. Минимизируя формулу, инженер минимизирует число вентилей — а значит, площадь чипа и его энергопотребление.

Двойственность: как СДНФ и СКНФ зеркалят друг друга

СДНФ и СКНФ связаны глубокой симметрией — принципом двойственности. Если в любом верном булевом тождестве поменять местами И ↔ ИЛИ, а также 0 ↔ 1, получится снова верное тождество. Например, из a ∧ 1 = a двойственностью получаем a ∨ 0 = a; из закона де Моргана для И — закон для ИЛИ. Это удваивает каждый закон, который мы выучили: достаточно помнить половину.

СДНФ и СКНФ — двойственная пара: СДНФ строится по единицам функции и использует И-термы, объединённые ИЛИ; СКНФ — по нулям, с ИЛИ-термами, соединёнными И. Есть и точная связь: СКНФ функции f получается, если построить СДНФ для отрицания ¬f, а потом применить де Моргана ко всей формуле. Понимание двойственности экономит силы и защищает от ошибок: разобравшись с одной нормальной формой, вы автоматически понимаете вторую — она устроена зеркально.

Типичные ошибки

• Менять таблицу истинности при «упрощении». Любое преобразование обязано сохранять функцию. Всегда проверяй эквивалентность (хоть таблицей, хоть кодом).
• Склеивать термы, различающиеся более чем одной переменной. Склеивание убирает ровно одну переменную; если различий больше, оно неприменимо.
• Думать, что СДНФ уже минимальна. СДНФ — отправная точка, почти всегда избыточная. Минимизация её существенно сокращает.

Итог

• Минимизация ищет кратчайшую эквивалентную формулу — это экономия вентилей в схеме.
• Ключевой приём — склеивание: термы, различающиеся одной переменной, сливаются, убирая её.
• Карты Карно автоматизируют склеивание через соседство клеток (код Грея).
• Формула напрямую отображается в схему из вентилей И, ИЛИ, НЕ.