2.2.6. Минимизация логических функций

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

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

Метод Квайна

Минимизируемая функция представляется в СДНФ, и к ней применяются все возможные операции неполного склеивания

, (2.10)

а затем поглощения

, (2.11)

и эта пара этапов применяется многократно. Таким образом, удаётся снизить ранг термов. Это процедура повторяется до тех пор, пока не останется ни одного терма, допускающего склеивание с каким-либо другим термом.

Заметим, что левую часть уравнения (2.10) сразу можно было минимизировать более простым и очевидным способом:

.

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

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

Метод карт Карно

Метод карт (таблиц) Карно является более наглядным, менее трудоёмким и надёжным способом минимизации логических функций, но его использование практически ограничено функциями 3-4 переменных, максимум – 5-6 переменных.

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

Таблицы истинности и карты Карно для функций И и ИЛИ двух переменных представлены на рис. 2.8. В каждую клетку карты записывается значение функции на соответствующем этой клетке наборе значений аргументов.

x	y	f			y			x	y	f			y
0	0	0		x	1	0		0	0	0		x	1	1
0	1	0			0	0		0	1	1			1	0
1	0	0						1	0	1
1	1	1						1	1	1

а) И б) ИЛИ

Рис. 2.8. Пример карт Карно для функций двух переменных

В карте Карно для функции И только одна 1, поэтому её ни с чем невозможно склеить. В выражении для минимальной функции будет только терм, соответствующий этой 1:

f = x y.

В карте Карно для функции ИЛИ уже три 1 и можно составить две склеивающиеся пары, при этом 1, соответствующая терму xy, используется дважды. В выражении для минимальной функции нужно записать термы для склеиваемых пар, оставляя в них все переменные, которые для этой пары не меняются, и убирая переменные, которые меняют своё значение. Для горизонтальной склейки получим x, а для вертикальной – y, в итоге получим выражение

f = x + y.

На рис. 2.9 приведены таблицы истинности двух функций трёх переменных (а) и их карты Карно (б и в). Функция f₂ отличается от первой тем, что на трёх наборах переменных она не определена (в таблице это обозначено прочерком).

При определении минимальной ДНФ функции используются следующие правила. Все клетки, содержащие 1, объединяются в замкнутые прямоугольные области, которые называются k-кубами, где k = log₂K, K – количество 1 в прямоугольной области. При этом каждая область должна представлять собой прямоугольник с числом клеток 2^k, где k = 0, 1, 2, 3, … . Для k = 1 прямоугольник называется один-куб и содержит 2¹ = 2 единицы; для k = 2 прямоугольник содержит 2² = 4 единицы и называется два-куб; при k = 3 область из 2³ = 8 единиц называется три-куб; и т. д. Единицы, которые невозможно объединить в прямоугольники, можно назвать ноль-кубами, которые содержат только одну единицу (2⁰ = 1). Как видно, при чётном k области могут иметь форму квадрата (но не обязательно), а при нечётном k – только прямоугольников.

x1	x2	x3	f1	f2		б в
0	0	0	0	–
0	0	1	1	1
0	1	0	0	1
0	1	1	1	1
1	0	0	0	0
1	0	1	0	–
1	1	0	1	1
1	1	1	1	–

а

Рис. 2.9. Пример карт Карно для функций трёх переменных

Эти области могут пересекаться, т. е. одни и те же клетки могут входить в разные области. Затем записывается минимальная ДНФ функции как дизъюнкция всех конъюнктивных термов, соответствующих k-кубам.

Каждая из указанных областей на карте Карно представляется в минимальной ДНФ конъюнкцией, число аргументов в которой на k меньше общего числа аргументов функции m, т. е. это число равно m – k. Каждая конъюнкция минимальной ДНФ составляется лишь из тех аргументов, которые для соответствующей области карты имеют значения либо без инверсий, либо только с инверсией, т. е. не меняют своего значения.

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

Для функции по карте Карно на рис. 2.9, б находим

,

поскольку для верхней замкнутой области переменные x₁ и x₂ имеют значения без инверсий, для нижней x₁ имеет значение с инверсией, а x₃ – без инверсии.

Неопредёленные значения в карте на рис. 2.9, в можно доопределить, заменив нулём или единицей. Для данной функции видно, что оба неопределённых значения выгоднее заменить 1. При этом образуются две области, являющиеся различными видами 2-кубов. Тогда выражение для минимальной ДНФ функции будет следующим:

.

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

Карты Карно можно рисовать разными способами (рис. 2.10).

			x2						x2x3	x2
x1						x1
		x3

а б

	00	01		11		10
0
1

в

Рис. 2.10. Разные способы изображения карт Карно для функции 3 переменных

Но самыми удобными вариантами карт Карно для функций 2-4 переменных являются показанные на рис. 2.11 таблицы, т. к. в них для каждой ячейки показаны все переменные в прямом или инверсном виде.

x3

x3

x2

x2

x2

x1

x1

x1

x2

x3

x3

x1

x4

x4

а б

Рис. 2.11. Наиболее удобное изображение карт Карно для функций 3 (а) и 4 (б) переменных

Для функций 5 и 6 переменных больше подходит способ, показанный на рис. 2.10, в.

	000	010	011	010		110	111		101	100
00
01
11
10

Рис. 2.12. Изображение карты Карно для функции 5 переменных

	000	010	011	010		110	111		101	100
000
001
011
010
110
111
101
100

Рис. 2.13. Изображение карты Карно для функции 6 переменных