Стремление к алгоритмизации поиска соседних элементарных произведений привело к разработке табличных методов минимизации логических функций. Одним из них является метод, основанный на использовании карт Карно.
Карты Карно – это графическое представление таблиц истинности логических функций. Они представляют собой таблицы, содержащие по 2nпрямоугольных ячеек, где n – число логических переменных.
На рис. 2.1, 2.2 и 2.3 приведены структуры карт Карно для функции двух, трех и четырех переменных, а в таблицах 2.4 и 2.5 представлены таблицы истинности для функции двух, трех переменныхсоответственно.
Таблица 2.4
| х1 | х2 | f(x1, x2) |
| 0 | 0 | f(0, 0) |
| 0 | 1 | f(0, 1) |
| 1 | 0 | f(1, 0) |
| 1 | 1 | f(1, 1) |
| х2 х1 | 0 | 1 |
| 0 | f(0,0) | f(0,1) |
| 1 | f(1,0) | f(1,1) |
Рис. 2.1. Структура карты Карно для функции двух переменных
Таблица 2.5
| х1 | х2 | х3 | f(x1, x2, х3) |
| 0 | 0 | 0 | f(0,0,0) |
| 0 | 0 | 1 | f(0,0,1) |
| 0 | 1 | 0 | f(0,1,0) |
| 0 | 1 | 1 | f(0,1,1) |
| 1 | 0 | 0 | f(1,0,0) |
| 1 | 0 | 1 | f(1,0,1) |
| 1 | 1 | 0 | f(1,1,0) |
| 1 | 1 | 1 | f(1,1,1) |
| х2х3 х1 | 00 | 01 | 11 | 10 |
| 0 | f(0,0,0) | f(0,0,1) | f(0,1,1) | f(0,1,0) |
| 1 | f(1,0,0) | f(1,0,1) | f(1,1,1) | f(1,1,0) |
Рис. 2.2. Структура карты Карно для функции трех переменных
| х3х4 х1х2 | 00 | 01 | 11 | 10 |
| 00 | f(0, 0, 0, 0) | f(0, 0, 0, 1) | f(0, 0, 1, 1) | f(0, 0, 1, 0) |
| 01 | f(0, 1, 0, 0) | f(0, 1, 0, 1) | f(0, 1, 1, 1) | f(0, 1, 1, 0) |
| 11 | f(1, 1, 0, 0) | f(1, 1, 0, 1) | f(1, 1, 1, 1) | f(1, 1, 1, 0) |
| 10 | f(1, 0, 0, 0) | f(1, 0, 0, 1) | f(1, 0, 1, 1) | f(1, 0, 1, 0) |
Рис. 2.3. Структура карты Карно для функции четырех переменных
Карта Карно размечается системой координат, соответствующих значениям входных переменных, например, верхняя строка карты для функции трех переменных соответствует нулевому значению переменной х1, а нижняя – ее единичному значе- нию. Каждый столбец этой карты характеризуется значениями двух переменных: х2 и х3. Комбинация цифр, которыми отмечается каждый столбец, показывает, для каких значенийпеременныхх3 их2 вычисляетсяфункция,размещаемаявклеткахэтого
столбца. Так, в случае карты Карно для функции четырех переменных, функция, рас- положенная в ячейках столбца с координатами 01, вычисляется при значениях пе- ременных х3 = 0, х4 = 1. Функция, расположенная в ячейке на пересечении этого столбца и строки с координатами 11, определяется при наборе входных переменных x1=l,x2=l,х3=0,х4=1.
Если на указанном наборе функция равна 1, то ее СДНФ обязательносодержит
элементарное произведение х1 × х2 × х 3 × х4, принимающее при этом наборе единичное значение. Таким образом ячейки карты Карно, представляющие функцию, содержат столько единиц, сколько элементарных произведений содержится в ее СДНФ, причем каждой единице соответствует одно из элементарных произведений.
Координаты строк и столбцов в карте Карно следуют не в естественном поряд- ке возрастания двоичных кодов, а в порядке 00; 01; 11; 10. Изменение порядка следо- вания наборов кодов сделано для того, чтобы соседние наборы, отличающиеся между собой лишь цифрой какого-либо одного разряда, были соседними в геометрическом смысле.
Рассмотрим таблицу истинности (таблица 2.6) и структуру карты Карно
(рис. 2.4) для функции f(xl, x2, x3) = х1 Ú х 2 × х 3.
Таблица 2.6
| х1 | х2 | х3 | f(x1, x2, х3) |
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
| х2х3 х1 | 00 | 01 | 11 | 10 | ||||
| 0 | 1 | 1 | 1 | 1 | ||||
| 1 | 0 |
| 1 |
| 0 | 0 | ||
Рис. 2.4. Структура карты Карно для функции
Ячейки, в которых функция принимает значение 1, заполняются единицами. Процесс минимизации заключается в формировании прямоугольников, содержащих по 2kячеек, где k – целое число. В прямоугольники объединяются соседние ячейки, которые соответствуют соседним элементарным произведениям. Например, на рис. 2.4 объединены ячейки с координатами 001 и 101. При объединении этих ячеек образовался прямоугольник, в котором х1 изменяет свое значение. Следовательно, оно исчезает при склеивании соответствующих элементарных произведений
х1 × х 2 × х 3 и х1 × х 2 × х 3. Ячейки, расположенные в первой строке, содержат 1 и явля-
ются соседними. Поэтому они объединяются в прямоугольник, содержащий 22 = 4 ячейки. Переменные х2 и х3 в пределах прямоугольника меняют свое значение, следо- вательно, они исчезнут из результирующего элементарного произведения. Перемен- ная х1 является неизменной и равной нулю. Таким образом, элементарное произведе- ние, полученное в результате объединения ячеек первой строки, содержит лишь эле-
мент
х1. Это следует из того, что четырем ячейкам первой строки соответствует сум-
ма четырех элементарных произведений:
х1 × х 2 × х 3 Ú х1 × х 2 × х 3 Ú х1 × х 2 × х 3 Ú х1 × х 2 × х 3 =
=х1×х2×(х3Ú х3)Úх1×х2×(х3Ú х3)=х1×х2Úх1×х2
= х1 × (х 2 Ú х 2)= х1.
Совокупность прямоугольников, покрывающих все единицы, называют покры- тием. Одна и та же ячейка может покрываться несколько раз. Итак, можно сделать следующие выводы:
1. Формула, получающаяся в результате минимизации логической функции с помощью карт Карно, содержит сумму стольких элементарных произведений, сколь- ко прямоугольников имеется впокрытии.
2. Чем больше ячеек в прямоугольнике, тем меньше переменных содержится в соответствующем ему элементарномпроизведении.
Несмотря на то, что карты Карно изображаются на плоскости, соседство ячеек устанавливается на поверхности тора или цилиндра. Верхняя и нижняя границы кар- ты Карно как бы «склеиваются», образуя цилиндр. При склеивании боковых границ получается тороидальная поверхность. Поэтому в примере (рис. 2.5) ячейки с коорди- натами 1011 и 0011 являются соседними и объединяются в прямоугольники. Действи- тельно, указанным ячейкам соответствует сумма элементарных произведений
х1 × х 2 × х 3 × х 4 Ú х1 × х 2 × х 3 × х 4 = х 2 × х 3 × х 4 × (х1 Ú х1) = х 2 × х 3 × х 4.
| х3х4 х1х2 | 00 | 01 | 11 | 10 | ||||
| 00 | 0 | 0 | 1 | 0 | ||||
|
| ||||||||
| 01 | 1 | 0 | 0 | 1 | ||||
| 11 | 1 | 0 | 0 | 1 | ||||
|
|
| |||||||
| 10 | 0 | 0 | 1 | 0 | ||||
Рис. 2.5. Карта Карно для функции четырех переменных
Аналогично объединяются и остальные четыре единичные ячейки. В результа- те их объединения получаем:
х1 × х 2 × х 3 × х 4 Ú х1 × х 2 × х 3 × х 4 Ú х1 × х 2 × х 3 × х 4 Ú х1 × х 2 × х 3 × х 4 =
= х 2 × х 3 × х 4 × (х1 Ú х1) Ú х 2 × х 3 × х 4 × (х1 Ú х1) = х 2 × х 4 (х 3 Ú х 3)= х 2 × х 4.
Поэтому окончательно f(x1, x2, x3, x4) =
х 2 × х3 × х 4 Ú х 2 × х 4.
Рассмотренные примеры позволяют сформулировать последовательность дей- ствий, выполняемых при минимизации логических функций с использованием карт Карно.
1. Изображается таблица для n переменных и производится разметка еесторон.
2. Ячейки таблицы, соответствующие набором переменных, обращающих функцию в 1, заполняются единицами, остальные ячейки –нулями.
3. Выбирается наилучшее покрытие таблицы правильными прямоугольниками. Наилучшим считается такое покрытие, которое образовано минимальным числом прямоугольников, а если таких вариантов несколько, то из них выбирается тот, кото- рый дает максимальную суммарную площадьпрямоугольников.
Качество минимизации оценивается коэффициентом покрытия:
k = m/s,
где m – общее количество прямоугольников; s – суммарное количество покры- тых ячеек. Покрытиесчитаетсятемлучше, чемменьшеегокоэффициент k.
