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

Представьте себе инженера, который проектирует микропроцессор для смартфона. В его распоряжении миллионы транзисторов, но каждый из них потребляет энергию, выделяет тепло и занимает физическое место на кремниевом кристалле. Если логическая схема, отвечающая за простое сложение чисел, будет состоять из 1000 элементов вместо 100, смартфон будет перегреваться и разряжаться за час. Именно здесь на помощь приходит математика, а точнее — процесс оптимизации логических выражений.

Общая постановка задачи минимизации

В основе работы любых цифровых устройств лежит булева алгебра. Сигналы в проводах интерпретируются как логический ноль (нет напряжения) и логическая единица (есть напряжение). Любое действие компьютера можно описать как булеву функцию — правило, по которому набору входных нулей и единиц сопоставляется выходной ноль или единица.

Зачастую первоначальное логическое выражение, описывающее нужную функцию, получается громоздким. Минимизация булевых функций — это процесс преобразования сложного логического выражения в эквивалентное, но более простое.

Совершенство достигается не тогда, когда нечего добавить, а тогда, когда нечего отнять.

Антуан де Сент-Экзюпери

Под «простотой» в дискретной математике обычно понимают критерий сложности (или цену схемы). Чаще всего это суммарное количество логических операций (И, ИЛИ, НЕ) и количество переменных (входов), участвующих в выражении. Чем меньше операций, тем меньше физических логических вентилей потребуется при сборке схемы.

Таблицы истинности: фундамент логики

Любую булеву функцию можно задать с помощью таблицы истинности. Это таблица, в которой перечислены все возможные комбинации входных переменных и соответствующее им значение функции.

Рассмотрим практический пример. Допустим, мы проектируем систему электронного голосования для трех директоров компании. Решение принимается большинством голосов. У нас есть три переменные: $x$, $y$ и $z$ (голоса директоров, где 1 — «за», 0 — «против»). Функция $f$ должна выдавать 1, если хотя бы две переменные равны 1.

Построим таблицу истинности для функции голосования:

x	y	z	f (Результат)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

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

Совершенные нормальные формы (СДНФ и СКНФ)

Существуют два универсальных способа записать функцию по её таблице истинности. Они называются совершенными, потому что каждая переменная участвует в каждом слагаемом или множителе ровно один раз (либо в прямом виде, либо с отрицанием).

Совершенная дизъюнктивная нормальная форма (СДНФ)

СДНФ строится по строкам таблицы, где функция равна единице (1).

Алгоритм построения СДНФ:

1. Найти все строки в таблице истинности, где результат равен 1.
2. Для каждой такой строки составить логическое произведение (конъюнкцию, оператор И, обозначается как $\land$). Если переменная в строке равна 1, берем ее как есть. Если равна 0, берем ее с отрицанием (оператор НЕ, обозначается как $\neg$). Такие произведения называются минтермами.
3. Соединить все полученные произведения знаком логического сложения (дизъюнкции, оператор ИЛИ, обозначается как $\lor$).

Применим алгоритм к нашей таблице голосования. Единицы стоят в четырех строках:

• Строка 4 ($x=0, y=1, z=1$): минтерм $\neg x \land y \land z$
• Строка 6 ($x=1, y=0, z=1$): минтерм $x \land \neg y \land z$
• Строка 7 ($x=1, y=1, z=0$): минтерм $x \land y \land \neg z$
• Строка 8 ($x=1, y=1, z=1$): минтерм $x \land y \land z$

Итоговая СДНФ:

$$f(x, y, z) = (\neg x \land y \land z) \lor (x \land \neg y \land z) \lor (x \land y \land \neg z) \lor (x \land y \land z)$$

Совершенная конъюнктивная нормальная форма (СКНФ)

СКНФ строится по строкам, где функция равна нулю (0). Подход зеркально противоположен.

Алгоритм построения СКНФ:

1. Найти все строки, где результат равен 0.
2. Для каждой строки составить логическую сумму (дизъюнкцию). Если переменная равна 0, берем ее без изменения. Если 1 — с отрицанием. Это макстермы.
3. Соединить все суммы знаком логического умножения (конъюнкции).

Для нашей таблицы нули находятся в первых четырех случаях (строки 1, 2, 3, 5). Итоговая СКНФ будет выглядеть так:

$$f(x, y, z) = (x \lor y \lor z) \land (x \lor y \lor \neg z) \land (x \lor \neg y \lor z) \land (\neg x \lor y \lor z)$$

Зачем нужна минимизация?

Посмотрим на полученную СДНФ. Чтобы собрать такую схему на заводе, нам понадобится:

• 3 инвертора (для создания $\neg x, \neg y, \neg z$)
• 4 элемента «3-И» (для умножения трех переменных)
• 1 элемент «4-ИЛИ» (для сложения четырех результатов)

Итого 8 логических вентилей и множество соединений. Это дорого и неэффективно.

Суть минимизации заключается в поиске закономерностей. В булевой алгебре есть закон склеивания: $(A \land B) \lor (A \land \neg B) = A$. Он означает, что если два выражения отличаются только одной переменной (в одном месте она с отрицанием, в другом без), эту переменную можно исключить, так как она не влияет на результат.

Если применить методы минимизации к нашей СДНФ, мы получим сокращенную форму:

$$f(x, y, z) = (x \land y) \lor (x \land z) \lor (y \land z)$$

Сравним результаты. Новая схема требует:

• 0 инверторов
• 3 элемента «2-И»
• 1 элемент «3-ИЛИ»

Количество вентилей сократилось вдвое (с 8 до 4), а сами вентили стали проще (у них меньше входов). В масштабах процессора, где таких функций миллиарды, подобная оптимизация экономит колоссальные ресурсы.

Основные методы минимизации

В рамках данного курса мы подробно изучим три основных подхода к минимизации булевых функций. Каждый из них имеет свои преимущества и область применения:

• Метод непосредственных преобразований (алгебраический). Основан на ручном применении законов и аксиом булевой алгебры (законы де Моргана, дистрибутивность, склеивание). Отлично подходит для простых функций от 2-3 переменных, но требует интуиции и не гарантирует нахождение абсолютно минимальной формы, если человек упустит неочевидное преобразование.
• Метод карт Карно (графический). Визуальный способ минимизации. Таблица истинности перерисовывается в виде специальной матрицы, где соседние ячейки отличаются только одной переменной. Это позволяет находить склеивания визуально, обводя единицы в прямоугольники. Идеально работает для функций от 3 до 5 переменных.
• Метод Куайна-Мак-Класки (таблично-алгоритмический). Строгий математический алгоритм, который последовательно сравнивает все минтермы друг с другом. Он лишен наглядности карт Карно, зато легко программируется и может применяться для функций с любым количеством переменных (6, 10, 100 и более). Именно этот алгоритм (и его эвристические модификации) лежит в основе современных систем автоматизированного проектирования электроники (САПР).

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

Итоги

• Минимизация булевых функций необходима для снижения аппаратной сложности цифровых схем, что экономит ресурсы, энергию и физическое пространство.
• Любую логическую задачу можно описать с помощью таблицы истинности, которая показывает зависимость выхода от всех комбинаций входов.
• На основе таблицы истинности строятся универсальные формулы: СДНФ (по единицам) и СКНФ (по нулям), которые обычно избыточны и требуют оптимизации.
• Основные инструменты оптимизации, которые будут изучены далее: алгебраические преобразования, карты Карно и алгоритм Куайна-Мак-Класки.

Постановка задачи минимизации

Представьте инженера, который проектирует систему управления для автономного дрона. Вес и энергопотребление здесь критичны: каждый лишний грамм батареи и каждая доля миллиампера сокращают время полета. Логическая схема, принимающая решения на основе данных с датчиков, состоит из тысяч микроскопических транзисторов. Если эту схему не оптимизировать, дрон получится тяжелым, дорогим и неэффективным. Именно поэтому после составления таблицы истинности инженеры не сразу идут на завод, а решают строгую математическую задачу — задачу минимизации.

Всё следует упрощать до тех пор, пока это возможно, но не более того.

Альберт Эйнштейн

Что такое «простота» логической схемы?

Прежде чем что-то минимизировать, необходимо определить, как измерять сложность. В дискретной математике и цифровой схемотехнике используются два основных критерия:

1. Цена по Квайну (число вхождений переменных). Это суммарное количество всех переменных (как с отрицанием, так и без него), участвующих в формуле. Каждая переменная в выражении называется литералом.
2. Аппаратная сложность (количество вентилей). Это число логических операций (И, ИЛИ, НЕ), которые необходимо выполнить.

Рассмотрим пример. Допустим, у нас есть функция, описывающая включение аварийного сигнала:

$$F = (x \\land y) \\lor (x \\land z)$$

Посчитаем её сложность:

• Цена по Квайну равна 4 (переменные $x, y, x, z$).
• Аппаратная сложность: 3 операции (два умножения и одно сложение).

Если применить закон дистрибутивности и вынести общий множитель, получим эквивалентную функцию:

$$F = x \\land (y \\lor z)$$

Теперь цена по Квайну равна 3, а аппаратная сложность снизилась до 2 операций. Схема стала проще, дешевле и быстрее, хотя выполняет абсолютно ту же задачу.

Анатомия логики: от минтермов к импликантам

Чтобы понять, как алгоритмически прийти к минимальной форме, необходимо ввести несколько фундаментальных понятий.

Импликанта — это логическое произведение (конъюнкция) переменных, при равенстве которого единице сама булева функция также гарантированно равна единице. Иными словами, это часть формулы, которая «покрывает» определенные единицы в таблице истинности.

Любой минтерм из Совершенной дизъюнктивной нормальной формы (СДНФ) является импликантой. Однако минтермы слишком громоздки, так как содержат все переменные функции. Наша цель — сократить их.

Простая импликанта — это такая импликанта, из которой нельзя удалить ни одну переменную так, чтобы оставшееся выражение продолжало быть импликантой. Это максимально «сжатый» блок логики, который уже нельзя упростить законом склеивания.

Три стадии эволюции булевой функции

Процесс минимизации можно представить как последовательный переход функции через несколько форм представления:

1. Совершенная ДНФ (СДНФ). Исходная, самая громоздкая форма. Состоит из полных минтермов. Описывает функцию «в лоб» по таблице истинности.
2. Сокращенная ДНФ. Сумма всех возможных простых импликант функции. В этой форме уже нет лишних переменных внутри слагаемых, но самих слагаемых может быть слишком много (они могут дублировать друг друга, покрывая одни и те же единицы).
3. Тупиковая ДНФ. Сокращенная форма, из которой удалены все лишние простые импликанты. Если из тупиковой формы убрать хотя бы одно слагаемое, функция изменит свое значение (перестанет покрывать некоторые единицы). У одной функции может быть несколько разных тупиковых форм.
4. Минимальная ДНФ. Это тупиковая форма, которая имеет наименьшую цену по Квайну среди всех возможных тупиковых форм.

Математическая постановка задачи

Общая задача минимизации булевых функций формулируется так: для заданной булевой функции найти её минимальную дизъюнктивную нормальную форму (МДНФ).

Согласно теореме американского математика Уилларда Квайна, процесс поиска МДНФ всегда разбивается на два крупных этапа:

1. Переход от СДНФ к сокращенной ДНФ (поиск всех простых импликант).
2. Переход от сокращенной ДНФ к минимальной (выбор наилучшего подмножества простых импликант, которое покрывает все единицы функции).

Таблица покрытий: мост к минимальной форме

Второй этап минимизации (выбор наилучшего подмножества) наглядно решается с помощью таблицы покрытий (или таблицы Квайна).

Разберем этот процесс на конкретном примере с числами. Пусть у нас есть функция $f(x, y, z)$, которая равна единице на наборах входных данных: 1 (001), 3 (011), 4 (100), 5 (101) и 7 (111).

Представим, что мы уже выполнили первый этап (например, алгебраическим склеиванием) и нашли все пять простых импликант:

• $P_1 = \\neg x \\land z$
• $P_2 = \\neg y \\land z$
• $P_3 = y \\land z$
• $P_4 = x \\land z$
• $P_5 = x \\land \\neg y$

Теперь построим таблицу. В столбцах запишем номера наборов, на которых функция равна 1 (наши цели). В строках — найденные простые импликанты (наши инструменты). Если импликанта покрывает набор, ставим плюс.

Простая импликанта	1 (001)	3 (011)	4 (100)	5 (101)	7 (111)
$P_1 (\\neg x \\land z)$	+	+
$P_2 (\\neg y \\land z)$	+			+
$P_3 (y \\land z)$		+			+
$P_4 (x \\land z)$				+	+
$P_5 (x \\land \\neg y)$			+	+

Поиск ядра функции

Анализ таблицы всегда начинается с поиска ядра. Ядро функции — это совокупность простых импликант, которые являются единственным покрытием хотя бы для одного набора.

Посмотрим на столбец «4 (100)». В нем стоит только один плюс — в строке $P_5$. Это означает, что если мы не возьмем $P_5$ в итоговую формулу, набор 4 останется непокрытым, и схема будет работать с ошибкой. Следовательно, $P_5$ — это ядро, мы обязаны включить его в ответ.

Взяв $P_5$, мы автоматически покрываем наборы 4 и 5. Осталось покрыть наборы 1, 3 и 7 минимальным числом оставшихся импликант.

• Наборы 1 и 3 можно одновременно покрыть импликантой $P_1$.
• Оставшийся набор 7 можно покрыть импликантой $P_3$ или $P_4$.

Таким образом, мы нашли два варианта минимальной ДНФ (обе имеют одинаковую цену по Квайну, равную 6):

1. $f(x, y, z) = (x \\land \\neg y) \\lor (\\neg x \\land z) \\lor (y \\land z)$
2. $f(x, y, z) = (x \\land \\neg y) \\lor (\\neg x \\land z) \\lor (x \\land z)$

Любая из этих формул является правильным решением задачи минимизации и может быть отправлена инженерам для сборки микросхемы.

Итоги

• Задача минимизации заключается в поиске эквивалентного логического выражения с наименьшей ценой по Квайну (минимальным числом переменных) или наименьшей аппаратной сложностью.
• Основа минимизации — поиск простых импликант, то есть максимально сокращенных логических произведений, которые нельзя упростить дальше.
• Процесс оптимизации проходит через стадии: СДНФ $\\rightarrow$ Сокращенная ДНФ $\\rightarrow$ Тупиковая ДНФ $\\rightarrow$ Минимальная ДНФ.
• Таблица покрытий позволяет визуализировать связь между простыми импликантами и исходными минтермами, помогая выделить обязательное ядро функции и собрать минимальную формулу.

Метод непосредственных преобразований

Представьте себе начинающего программиста, который пишет код для системы доступа. Он создает длинное и запутанное условие: доступ разрешен, если пользователь является администратором и система активна, ИЛИ если пользователь является администратором и система неактивна. Код работает, но выглядит громоздко. Опытный разработчик посмотрит на это и скажет: «Система активна или нет — неважно. Доступ просто зависит от того, администратор ли это».

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

Математика — это искусство называть разные вещи одним и тем же именем.

Анри Пуанкаре

Суть алгебраического метода

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

Этот метод называется «непосредственным», потому что мы работаем напрямую с формулой, шаг за шагом заменяя её фрагменты на эквивалентные, но более короткие. Здесь нет таблиц или графиков — только чистая алгебра логики.

Инструментарий: законы булевой алгебры

Чтобы успешно минимизировать функции, необходимо свободно владеть базовыми законами булевой алгебры. Рассмотрим те из них, которые чаще всего применяются на практике.

Название закона	Математическая запись	Практический смысл
Идемпотентность	$A \\lor A = A$ <br> $A \\land A = A$	Повторение одного и того же условия не меняет результат. В логике нет понятия «дважды истинно».
Поглощение	$A \\lor (A \\land B) = A$	Более общее условие делает частное избыточным. Если идет дождь, нам неважно, идет ли дождь и дует ветер.
Склеивание	$(A \\land B) \\lor (A \\land \\neg B) = A$	Если результат не зависит от состояния переменной $B$ (она встречается и в прямом, и в инверсном виде), её можно исключить.
Де Моргана	$\\neg(A \\lor B) = \\neg A \\land \\neg B$	Отрицание суммы равно произведению отрицаний. Позволяет раскрывать инверсии над скобками.
Дистрибутивность	$A \\land (B \\lor C) = (A \\land B) \\lor (A \\land C)$	Вынесение общего множителя за скобки (или раскрытие скобок), аналогично обычной школьной алгебре.

Особое внимание стоит уделить закону склеивания. Это главный двигатель всей минимизации. Именно он позволяет избавляться от лишних переменных, объединяя (склеивая) соседние минтермы.

Алгоритм алгебраической минимизации

Процесс минимизации не всегда линеен, так как требует математической интуиции, но в большинстве случаев он сводится к следующему пошаговому алгоритму:

1. Подготовка выражения. Если функция задана в произвольном виде, раскройте скобки и приведите её к дизъюнктивной нормальной форме (ДНФ) — сумме логических произведений.
2. Поиск пар для склеивания. Найдите слагаемые, которые отличаются только одной переменной (в одном слагаемом она с отрицанием, в другом — без).
3. Применение идемпотентности (дублирование). Если одно слагаемое может склеиться с несколькими другими, продублируйте его по закону $A \\lor A = A$. Это искусственно расширит формулу, но позволит провести больше сокращений.
4. Склеивание и вынесение за скобки. Примените закон склеивания ко всем найденным парам.
5. Поглощение. Проверьте полученный результат. Если в формуле остались элементы вида $X \\lor (X \\land Y)$, удалите избыточную часть $(X \\land Y)$.

Практический пример №1: Базовое склеивание

Рассмотрим функцию от двух переменных, заданную в СДНФ:

$$F(x, y) = (\\neg x \\land y) \\lor (x \\land \\neg y) \\lor (x \\land y)$$

Давайте оптимизируем её, следуя нашему алгоритму.

Шаг 1. Внимательно посмотрим на слагаемые. Третье слагаемое $(x \\land y)$ очень удобно: оно отличается от первого только переменной $x$, а от второго — переменной $y$.

Шаг 2. Применим хитрость — закон идемпотентности. Продублируем третье слагаемое, чтобы его хватило для склеивания с обоими соседями:

$$F(x, y) = (\\neg x \\land y) \\lor (x \\land y) \\lor (x \\land \\neg y) \\lor (x \\land y)$$

Шаг 3. Сгруппируем пары:

$$F(x, y) = [(\\neg x \\land y) \\lor (x \\land y)] \\lor [(x \\land \\neg y) \\lor (x \\land y)]$$

Шаг 4. В первой квадратной скобке вынесем за скобки $y$, во второй вынесем $x$:

$$F(x, y) = y \\land (\\neg x \\lor x) \\lor x \\land (\\neg y \\lor y)$$

Поскольку переменная ИЛИ её отрицание всегда дают истину ($A \\lor \\neg A = 1$), скобки превращаются в единицы:

$$F(x, y) = (y \\land 1) \\lor (x \\land 1) = y \\lor x$$

Мы сократили исходную формулу из трех сложных слагаемых до простейшей операции логического сложения (ИЛИ). Аппаратная сложность снизилась с 6 логических вентилей до всего 1 вентиля.

Практический пример №2: Работа с тремя переменными

Усложним задачу. Дана функция, управляющая запуском конвейера:

$$F(x, y, z) = (x \\land y \\land z) \\lor (x \\land \\neg y \\land z) \\lor (\\neg x \\land \\neg y \\land z)$$

Попробуем минимизировать её без дублирования, просто последовательно применяя законы.

Сначала сгруппируем первое и второе слагаемые. У них общая часть $(x \\land z)$:

$$F(x, y, z) = [x \\land z \\land (y \\lor \\neg y)] \\lor (\\neg x \\land \\neg y \\land z)$$

Скобка $(y \\lor \\neg y)$ равна 1, поэтому она исчезает (закон склеивания):

$$F(x, y, z) = (x \\land z) \\lor (\\neg x \\land \\neg y \\land z)$$

Теперь вынесем за скобки общую переменную $z$:

$$F(x, y, z) = z \\land (x \\lor (\\neg x \\land \\neg y))$$

Здесь мы сталкиваемся с интересным случаем. Внутри скобки можно применить распределительный закон: $A \\lor (B \\land C) = (A \\lor B) \\land (A \\lor C)$.

$$x \\lor (\\neg x \\land \\neg y) = (x \\lor \\neg x) \\land (x \\lor \\neg y)$$

Так как $(x \\lor \\neg x) = 1$, выражение упрощается до $(x \\lor \\neg y)$. Подставим это обратно к нашему $z$:

$$F(x, y, z) = z \\land (x \\lor \\neg y)$$

Итоговая формула стала значительно компактнее. Цена по Квайну (количество вхождений переменных) уменьшилась с 9 до 3.

Преимущества и недостатки метода

Алгебраический метод — это классика дискретной математики. У него есть свои сильные и слабые стороны.

Преимущества:

• Универсальность. Метод работает для функций с любым количеством переменных.
• Глубокое понимание. Ручное преобразование формул отлично развивает логическое мышление и понимание того, как работают цифровые схемы на фундаментальном уровне.

Недостатки:

• Отсутствие наглядности. В длинных формулах легко пропустить пару, которую можно склеить.
• Зависимость от интуиции. Алгоритм не дает четкого ответа на вопрос: «А точно ли я достиг минимальной формы, или можно сократить что-то еще?». Иногда для минимизации нужно искусственно усложнить формулу (добавить слагаемое), что неочевидно для новичков.

Именно из-за этих недостатков инженеры редко используют алгебраический метод для сложных схем. Для функций от 3 до 5 переменных гораздо удобнее применять графический подход, который исключает фактор человеческой невнимательности. Этот подход называется Методом карт Карно, и мы подробно разберем его в следующей статье.

Итоги

• Метод непосредственных преобразований основан на применении законов булевой алгебры для упрощения логических выражений.
• Главный инструмент минимизации — закон склеивания, который позволяет исключать переменные, не влияющие на результат.
• Закон идемпотентности ($A \\lor A = A$) часто используется как математическая хитрость для дублирования слагаемых, чтобы склеить их с разными соседями.
• Алгебраический метод отлично тренирует логику, но не гарантирует нахождения абсолютного минимума из-за зависимости от человеческой внимательности.

Основы графической минимизации и карты Карно

Представьте, что вы пытаетесь найти пару одинаковых носков в огромной куче белья в темной комнате. Вы берете один носок, сравниваете его с другим, откладываете, берете следующий... Это долгий, утомительный процесс, в котором легко ошибиться. Именно так ощущается метод алгебраических преобразований, который мы изучали в предыдущей статье. Выискивать пары для склеивания в длинной формуле — задача, требующая предельной концентрации.

А теперь представьте, что кто-то включил свет и разложил все носки по цветам и узорам в аккуратную сетку. Найти пару теперь можно за долю секунды, просто бросив взгляд на стол. В дискретной математике таким «включением света» стал графический метод минимизации, предложенный американским физиком Морисом Карно в 1953 году.

Геометрия есть искусство правильно рассуждать на неправильных чертежах.

Джордж Пойа

В этой статье мы разберем, как превратить скучные таблицы истинности в наглядные геометрические карты, и научимся оптимизировать логические схемы визуально.

От алгебры к геометрии: что такое карта Карно?

Карта Карно — это графическое представление таблицы истинности булевой функции. Она выглядит как двумерная матрица (сетка), в которой каждая ячейка соответствует одному возможному набору входных переменных (минтерму).

Главная магия карты Карно заключается в расположении этих ячеек. В обычной таблице истинности строки идут в порядке стандартного двоичного счета: 00, 01, 10, 11. Если мы попытаемся склеить соседние строки (например, 01 и 10), у нас ничего не выйдет, потому что они отличаются сразу в двух позициях. Закон склеивания ($A \\land B \\lor A \\land \\neg B = A$) работает только тогда, когда меняется ровно одна переменная.

Чтобы соседние ячейки в матрице всегда отличались только на одну переменную, Карно применил код Грея.

Код Грея: секрет идеального соседства

Код Грея (или рефлексивный двоичный код) устроен так, что любые два соседних значения имеют расстояние Хэмминга, равное 1. Это означает, что при переходе от одного числа к другому меняется состояние только одного бита.

Сравним обычный двоичный счет и код Грея для двух переменных:

Десятичное число	Обычный двоичный код	Код Грея	Изменилось битов (в коде Грея)
0	00	00	-
1	01	01	1 (правый)
2	10	11	1 (левый)
3	11	10	1 (правый)

Обратите внимание на переход от 1 к 2. В обычном коде меняются оба бита (01 $\\rightarrow$ 10). В коде Грея меняется только один (01 $\\rightarrow$ 11). Более того, если мы перейдем от последней строки (10) обратно к первой (00), изменится тоже только один бит!

Именно этот порядок (00, 01, 11, 10) используется для подписи столбцов и строк в картах Карно.

Топология карт: цилиндры и торы

Поскольку первая и последняя строки (или столбцы) в коде Грея отличаются только на один бит, они тоже являются «соседними» с точки зрения логики. Это придает картам Карно необычные пространственные свойства.

1. Для 3 переменных карта выглядит как прямоугольник $2 \\times 4$. Левый и правый края карты логически соприкасаются. Топологически такая карта представляет собой цилиндр.
2. Для 4 переменных карта имеет размер $4 \\times 4$. Здесь соприкасаются не только левый и правый края, но и верхний с нижним. Если свернуть такую карту по обеим осям, мы получим тор (фигуру, похожую на бублик). Четыре угловые ячейки такой карты являются соседями друг для друга и могут быть объединены в одну группу.

Золотые правила группировки

Процесс минимизации по карте Карно сводится к поиску и обведению групп единиц (если мы строим минимальную ДНФ). Каждая обведенная группа превращается в одно слагаемое (простую импликанту) в итоговой формуле.

Чтобы получить правильный и минимальный результат, необходимо строго соблюдать правила:

• Правило единиц: В группы можно объединять только ячейки, содержащие 1. Нули игнорируются.
• Правило формы: Группы могут быть только прямоугольными или квадратными. Никаких диагоналей, зигзагов или букв «Г».
• Правило степени двойки: Количество ячеек в группе должно быть равно степени двойки: 1, 2, 4, 8 или 16.
• Правило максимального размера: Группы должны быть настолько большими, насколько это возможно. Чем больше группа, тем больше переменных сократится. Группа из 2 ячеек удаляет 1 переменную, из 4 ячеек — 2 переменные, из 8 ячеек — 3 переменные.
• Правило перекрытия: Группы могут (и часто должны) пересекаться. Одна и та же единица может входить в несколько разных групп, если это помогает сделать эти группы больше.
• Правило достаточности: Каждая единица на карте должна быть покрыта хотя бы одной группой. При этом нельзя создавать «лишние» группы, которые покрывают только те единицы, которые уже вошли в другие группы.

Практический пример №1: Три переменные

Спроектируем логику включения охлаждающего вентилятора. У нас есть три датчика: $x$, $y$ и $z$. Функция $F(x, y, z)$ равна 1 на наборах входных данных: 1 (001), 3 (011), 4 (100) и 5 (101).

Построим карту Карно $2 \\times 4$. По вертикали отложим переменную $x$, по горизонтали — пару $yz$ в коде Грея.

$x \\setminus yz$	00	01	11	10
0	0	1	1	0
1	1	1	0	0

Начинаем группировку:

1. Видим две единицы рядом в верхней строке: ячейки (0,01) и (0,11). Обводим их. В этой группе $x=0$ и $z=1$ остаются неизменными, а $y$ меняется с 0 на 1. Переменная $y$ сокращается. Получаем импликанту: $\\neg x \\land z$.
2. Видим две единицы в нижней строке: ячейки (1,00) и (1,01). Обводим их. Здесь $x=1$ и $y=0$ стабильны, а $z$ меняется. Переменная $z$ сокращается. Получаем импликанту: $x \\land \\neg y$.

Все единицы покрыты. Итоговая минимальная функция:

$$F(x, y, z) = (\\neg x \\land z) \\lor (x \\land \\neg y)$$

Примечание: Мы могли бы объединить ячейки (0,01) и (1,01) по вертикали. Но это создало бы третью группу, которая покрывает единицы, уже учтенные в первых двух группах. Это нарушило бы правило минимальности (появилось бы лишнее слагаемое).

Практический пример №2: Четыре переменные и магия углов

Усложним задачу. Дана функция от четырех переменных $F(a, b, c, d)$, которая равна единице на наборах: 0, 2, 8, 10, 12, 14.

Переведем десятичные числа в двоичные, чтобы понять координаты: 0000, 0010, 1000, 1010, 1100, 1110. Заполним карту $4 \\times 4$:

$ab \\setminus cd$	00	01	11	10
00	1	0	0	1
01	0	0	0	0
11	1	0	0	1
10	1	0	0	1

Применяем правила:

1. Ищем самые большие блоки. В нижней половине карты есть четыре единицы, образующие квадрат: ячейки (11,00), (11,10), (10,00), (10,10). Вспомним, что левый и правый края склеиваются (цилиндр). Эта группа из 4 ячеек стабильна по переменной $a=1$ (обе строки начинаются на 1) и переменной $d=0$ (оба столбца заканчиваются на 0). Переменные $b$ и $c$ меняются и сокращаются. Результат: $a \\land \\neg d$.
2. У нас остались непокрытыми две единицы в верхней строке: (00,00) и (00,10). Мы можем объединить их в группу из двух. Но помним правило: группа должна быть максимально большой. Вспоминаем про форму тора! Четыре угла карты Карно являются соседями. Объединяем ячейки (00,00), (00,10), (10,00) и (10,10) в одну группу из 4 элементов. В этой угловой группе стабильны $b=0$ и $d=0$. Результат: $\\neg b \\land \\neg d$.

Итоговая минимальная функция:

$$F(a, b, c, d) = (a \\land \\neg d) \\lor (\\neg b \\land \\neg d)$$

Аппаратная сложность снизилась колоссально: вместо шести слагаемых по четыре переменные в каждом, мы получили всего два слагаемых по две переменные.

Джокеры в рукаве: неопределенные состояния

В реальной инженерной практике часто встречаются ситуации, когда некоторые комбинации входных сигналов физически невозможны. Например, если на вход схемы подается цифра от 0 до 9 в двоичном коде (BCD), то комбинации от 10 (1010) до 15 (1111) никогда не поступят на вход.

Значение функции на таких наборах нам не важно. В картах Карно такие ячейки помечаются крестиком ($X$) или прочерком ($-$) и называются неопределенными состояниями (don't cares).

При минимизации мы можем использовать эти ячейки как «джокеры». Если включение ячейки $X$ в группу единиц позволяет увеличить размер этой группы (например, с 2 до 4), мы считаем этот $X$ единицей. Если $X$ стоит в стороне и не помогает увеличить группы, мы просто игнорируем его, считая нулем. Это мощнейший инструмент, позволяющий дополнительно упростить схему.

Ограничения метода

Карты Карно — идеальный инструмент для человека. Они задействуют наше природное умение распознавать визуальные паттерны. Однако у метода есть жесткий предел применимости.

Карты отлично работают для 2, 3 и 4 переменных. Карту для 5 переменных можно представить как две 4-мерные карты, лежащие друг над другом (3D-матрица), где склеивание происходит еще и по вертикали между слоями. Это уже требует хорошего пространственного воображения. Для 6 переменных потребуется 4 слоя, что делает визуальный поиск ошибок почти неизбежным.

Для функций с большим числом переменных (что является нормой в современных процессорах) визуальные методы бессильны. Там на сцену выходят строгие алгоритмические подходы, главным из которых является метод Куайна-Мак-Класки. О нем мы поговорим в следующей статье курса.

Итоги

• Карта Карно — это графический метод минимизации, преобразующий алгебраический поиск общих множителей в визуальный поиск прямоугольных блоков.
• Координаты строк и столбцов в карте строятся по коду Грея, что гарантирует отличие соседних ячеек ровно на одну переменную.
• Топологически карты Карно замкнуты сами на себя: края карты являются соседними ячейками (образуя цилиндр или тор).
• Главная цель при работе с картой — покрыть все единицы минимальным количеством прямоугольных групп, делая каждую группу максимально большой (размером $2^k$).
• Неопределенные состояния (невозможные комбинации входов) можно использовать как «джокеры» для расширения групп и дальнейшего упрощения функции.

Табличный метод Квайна-Мак-Класки

Представьте инженера корпорации Intel или AMD, перед которым стоит задача спроектировать блок арифметико-логического устройства (АЛУ) для нового процессора. На вход этого блока поступают не три и не четыре сигнала, а сразу 64 или 128. Попытка нарисовать карту Карно для 64 переменных потребует создания матрицы, размер которой превышает количество атомов в обозримой Вселенной. Визуальные методы, идеально подходящие для человека, абсолютно бессильны перед масштабами современной микроэлектроники.

Здесь на помощь приходит строгая математика и алгоритмизация. Нам нужен метод, который не требует пространственного воображения, не зависит от внимательности инженера и, самое главное, может быть запрограммирован и передан на выполнение компьютеру. Именно таким инструментом является алгоритм, разработанный Уиллардом Квайном в 1952 году и усовершенствованный Эдвардом Мак-Класки в 1956 году.

Информатика не более связана с компьютерами, чем астрономия с телескопами.

Эдсгер Дейкстра

Суть таблично-алгоритмического подхода

Метод Квайна-Мак-Класки — это формализованный способ нахождения минимальной дизъюнктивной нормальной формы (МДНФ) булевой функции. По своей математической природе он делает абсолютно то же самое, что и карты Карно: ищет соседние минтермы и применяет к ним закон склеивания. Разница заключается лишь в форме представления данных.

Вместо того чтобы рисовать геометрические фигуры, алгоритм работает со списками двоичных чисел, последовательно сравнивая их друг с другом по строгим правилам. Процесс всегда делится на две крупные фазы:

1. Поиск всех простых импликант (максимально возможных склеиваний).
2. Построение таблицы покрытий для выбора минимально необходимого набора этих импликант.

Рассмотрим работу алгоритма на конкретном практическом примере. Допустим, мы проектируем дешифратор команд, логика которого описывается функцией от четырех переменных $w, x, y, z$. Функция равна единице на следующих наборах (в десятичной записи):

$$F(w, x, y, z) = \\Sigma(0, 2, 8, 10, 11, 14, 15)$$

где $F$ — логическая функция, $w, x, y, z$ — входные переменные, $\\Sigma$ — сумма минтермов (наборов, на которых функция принимает значение истина).

Двоичное представление и первичная группировка

Первое, что делает алгоритм — переводит десятичные номера наборов в двоичный код. Каждая позиция в коде соответствует переменной (1 — переменная без отрицания, 0 — с отрицанием).

Чтобы оптимизировать процесс сравнения, числа разбиваются на группы по количеству единиц в их двоичном представлении. Закон склеивания гласит, что объединить можно только те наборы, которые отличаются ровно в одном бите. Следовательно, склеивание возможно только между числами из соседних групп (например, число с одной единицей может склеиться только с числом, у которого ноль единиц или две единицы).

Составим стартовую таблицу:

Группа (число единиц)	Десятичный номер	Двоичный код ($w, x, y, z$)
0	0	0 0 0 0
1	2	0 0 1 0
1	8	1 0 0 0
2	10	1 0 1 0
3	11	1 0 1 1
3	14	1 1 1 0
4	15	1 1 1 1

Систематическое склеивание (первый проход)

Теперь алгоритм начинает последовательно сравнивать каждый элемент группы $N$ с каждым элементом группы $N+1$. Если два двоичных кода отличаются ровно в одной позиции, они склеиваются. Различающийся бит заменяется прочерком (-), что означает исключение этой переменной из формулы.

Сравниваем Группу 0 и Группу 1:

• 0 (0000) и 2 (0010) отличаются в третьем бите. Результат: 0 0 - 0.
• 0 (0000) и 8 (1000) отличаются в первом бите. Результат: - 0 0 0.

Сравниваем Группу 1 и Группу 2:

• 2 (0010) и 10 (1010) дают - 0 1 0.
• 8 (1000) и 10 (1010) дают 1 0 - 0.

Продолжая этот процесс для всех соседних групп, мы получаем новый список импликант. Важное правило: если исходный набор поучаствовал хотя бы в одном склеивании, мы ставим рядом с ним галочку. Наборы, оставшиеся без галочек, больше не могут быть упрощены — они автоматически становятся простыми импликантами.

Результат первого прохода:

Склеенные наборы	Новый код
(0, 2)	0 0 - 0
(0, 8)	- 0 0 0
(2, 10)	- 0 1 0
(8, 10)	1 0 - 0
(10, 11)	1 0 1 -
(10, 14)	1 - 1 0
(11, 15)	1 - 1 1
(14, 15)	1 1 1 -

В нашем случае все исходные наборы поучаствовали в склеивании, поэтому двигаемся дальше.

Глубокое склеивание (второй проход)

Алгоритм повторяется для новой таблицы. Теперь мы можем склеивать строки только в том случае, если прочерки (-) находятся в одинаковых позициях, а остальные биты отличаются ровно на одну позицию.

Ищем совпадения:

• Строка (0, 2) 0 0 - 0 и строка (8, 10) 1 0 - 0. Прочерк совпадает, первый бит отличается. Склеиваем! Получаем набор (0, 2, 8, 10) с кодом - 0 - 0.
• Строка (0, 8) - 0 0 0 и строка (2, 10) - 0 1 0. Дают тот же самый результат - 0 - 0. Дубликаты просто удаляются.
• Строка (10, 11) 1 0 1 - и строка (14, 15) 1 1 1 -. Дают набор (10, 11, 14, 15) с кодом 1 - 1 -.
• Строка (10, 14) 1 - 1 0 и строка (11, 15) 1 - 1 1. Снова дают 1 - 1 -.

Больше склеиваний произвести невозможно. Все элементы из таблицы первого прохода поучаствовали в создании новых групп. У нас остались две финальные конструкции, которые нельзя упростить дальше. Это и есть наши простые импликанты:

1. $P_1 = (0, 2, 8, 10)$ с кодом - 0 - 0. Переводим обратно в алгебру: переменные $w$ и $y$ исключены, $x=0$, $z=0$. Формула: $\\neg x \\land \\neg z$.
2. $P_2 = (10, 11, 14, 15)$ с кодом 1 - 1 -. Переменные $x$ и $z$ исключены, $w=1$, $y=1$. Формула: $w \\land y$.

Таблица покрытий (таблица Квайна)

Первая фаза завершена. Мы нашли все возможные простые импликанты. Теперь нужно выбрать из них минимальный набор, который покроет все исходные единицы функции. Для этого строится таблица покрытий.

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

Простые импликанты	0	2	8	10	11	14	15
$P_1$ (0, 2, 8, 10)	X	X	X	X
$P_2$ (10, 11, 14, 15)				X	X	X	X

Анализ таблицы начинается с поиска ядра — столбцов, в которых стоит только один крестик.

Посмотрим на столбец «0». Крестик стоит только в строке $P_1$. Это значит, что без $P_1$ мы физически не сможем реализовать логику для нулевого набора. Следовательно, $P_1$ — существенная импликанта, она обязана войти в итоговую формулу.

Посмотрим на столбец «15». Крестик стоит только в строке $P_2$. Значит, $P_2$ также является существенной импликантой.

Взяв $P_1$ и $P_2$, мы покрываем абсолютно все столбцы в таблице. Задача решена! Итоговая минимальная дизъюнктивная нормальная форма выглядит так:

$$F(w, x, y, z) = (\\neg x \\land \\neg z) \\lor (w \\land y)$$

где $F$ — минимизированная функция, $w, x, y, z$ — входные переменные, $\\neg$ — логическое отрицание (НЕ), $\\land$ — логическое умножение (И), $\\lor$ — логическое сложение (ИЛИ).

Исходная функция, состоявшая из семи громоздких слагаемых (по 4 переменные в каждом), сократилась до двух простых логических вентилей И и одного вентиля ИЛИ.

Вычислительная сложность и алгоритм Espresso

Метод Квайна-Мак-Класки идеален с математической точки зрения: он гарантированно находит абсолютно минимальную форму функции. Однако в реальном мире инженерии у него есть серьезный недостаток — экспоненциальный рост вычислительной сложности.

Задача минимизации булевых функций относится к классу NP-трудных задач. При увеличении количества входных переменных размер таблиц растет лавинообразно. Для функции от 4 переменных существует максимум 16 минтермов. Для функции от 32 переменных (стандартная шина данных старых процессоров) количество минтермов превышает 4 миллиарда. Ни один современный суперкомпьютер не способен построить и обработать полную таблицу покрытий для функции от 64 переменных за адекватное время.

Как же тогда проектируют современные процессоры?

В системах автоматизированного проектирования электроники (САПР) используются эвристические алгоритмы. Самым известным из них является алгоритм Espresso, разработанный в IBM в 1980-х годах.

В отличие от метода Квайна-Мак-Класки, Espresso не пытается найти абсолютно минимальную форму. Вместо этого он быстро находит достаточно хорошую (близкую к минимальной) форму. Алгоритм берет исходную функцию и начинает итеративно «раздувать» и «сжимать» импликанты в многомерном пространстве, отбрасывая избыточные части. Это позволяет оптимизировать логические схемы с сотнями переменных за считанные минуты, жертвуя лишь долями процента эффективности ради колоссальной скорости расчетов.

Итоги

• Метод Квайна-Мак-Класки — это универсальный таблично-алгоритмический способ минимизации булевых функций, не зависящий от количества переменных и пригодный для компьютерной автоматизации.
• Алгоритм состоит из двух этапов: последовательного склеивания двоичных кодов для поиска простых импликант и решения задачи о покрытии с помощью таблицы Квайна.
• Группировка минтермов по количеству единиц в двоичном коде значительно ускоряет процесс, так как склеивание возможно только между соседними группами.
• Из-за экспоненциальной вычислительной сложности (NP-трудность) чистый метод Квайна-Мак-Класки применяется редко для больших схем; в современной индустрии его заменяют эвристические программы-оптимизаторы, такие как алгоритм Espresso.