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

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

Минимизация булевых функций методом Квайна Мак-Класски

Можно минимизировать функции, используя Диаграмму Вейча и Карты Карно.

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

Пример. Построим одномерный, двухмерный и трехмерный гиперкуб (рис. 1). У двухмерного гиперкуба будет вершин, а у трехмерного – 23 вершин.

Часто двоичные наборы задают десятичными эквивалентами , булеву функцию – перечислением десятичных эквивалентов, соответствующих конституентам (конъюнкциям предельного разложения Шеннона). Например, = (таблица 1).

Переменные или будем называть термами. Полный набор из n термов образует конституенту. В процессе же минимизации некоторые термы из конституент пропадут. Тогда оставшуюся часть дизъюнкта или конъюнкта называют импликантой.

Таблица 1

Десятичный эквивалент		полностью определенная функция	слабоопределенная функция
0	0 0 0	1	-
1	0 0 1	1	1
2	0 1 0	1	-
3	0 1 1	1	-
4	1 0 0	0	-
5	1 0 1	0	-
6	1 1 0	0	0
7	1 1 1	1	0

Определение. Множество вершин гиперкуба, на которых функция равна 0 и которые сами образуют гиперкуб, называется нулевым интервалом.

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

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

В данном примере единичными интервалами являются множества вершин:

; максимальными интервалами - .

Из рис. 1 видим, что интервалы входят в интервал , след., интервал будет максимальным. А также интервал будет максимальным, т. к. интервалы и входят в интервал

Определение. Конъюнкция, соответствующая максимальному единичному интервалу, функции , называется простой импликантой этой функции:

, .

Для вершин общей переменной будет , значит максимальному единичному интервалу будет соответствовать конъюнкция, состоящая только из . Для вершин общими переменными будут , значит максимальному единичному интервалу будет соответствовать конъюнкция (см. таблицу 1).

Будем задавать единичный интервал перечислением вершин, а также с помощью последовательности символов 0, 1 - , где прочерк означает отсутствие в конъюнкции соответствующей переменной: , . Импликанты появляются в результате склейки смежных конституент, различающихся одним термом.

Определение. Дизъюнкция всех простых импликант булевой функции называется сокращенной ДНФ этой функции.

Первый этап минимизации полностью определенной функции

Переход от совершенной ДНФ к сокращенной однозначен и осуществляется с помощью попарного сравнения конституент ярусов (номера которых отличаются на единицу). Например, когда задавали единичный интервал перечислением вершин и с помощью последовательности символов 0,1, - , то для единичного интервала получим .

После попарного сравнения ярусов, получим два максимальных единичных интервала (рис. 2). В итоге сокращенная ДНФ: .

Второй этап минимизации полностью определенной функции

Построение и покрытие табдицы Квайна [ Горбатов, стр. 40]. Таблица Квайна – двумерная таблица, каждой строке которой взаимно однозначно соответствует максимальный интервал, столбцу – конституента, а на пересечении -й строки и -го столбца находится единица, если -я конституента входит в -й максимальный интервал, в противном случае в клетке ставят "0".

Для рассмотренного примера приведем таблицу Квайна (таблица 2).

Таблица 2

	0 0 0	0 0 1	0 1 0	0 1 1	1 1 1
0 - -	1	1	1	1	0
- 1 1	0	0	0	1	1

В данном случае: Сокращенная ДНФ = MinДНФ =

.

Вывод: Таким образом, после минимизации, во-первых, сокращается количество переменных от 15 (3переменные × 5 наборов, где функция равна 1) до 3 во-вторых уменьшается количество операций.

Минимизация слабоопределенных функций

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

1)  число переменных велико;

2)  единичная и нулевая области задаются соответствующими интервалами.

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

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

, , ,

, , ,

, , ,

причем в качестве первого аргумента берется значение -го разряда единичного интервала, в качестве второго – значение -го разряда нулевого интервала.

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

Пример. Рассмотрим нахождение минимальной ДНФ булевой функции

(1)

7(2)

Для каждого единичного интервала строится своя таблица различий.

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

Таблица 3

Единичный интервал (0,42)	Нулевые интервалы
10-0-01		1101-0-
*a	0	1	0	1
b	-	0	0	0
c	0	0	0	0
d	-	0	0	0
*e	0	0	1	0
g	-	0	0	0
h	0	1	0	0

Получим таблицу 3. Сначала складываем значения единичного интервала 0-0-0-0 со значениями интервала (65, 85), который соответствует 10-0-01 . Получим в столбце (65, 85) значения: . Аналогично можно получить столбцы (4,29) и (104,109).

Перед тем как найти все покрытия этой таблицы необходимо найти обязательные строки (если интервал включен только в одну строку, то такую строку будем называть обязательной. В таблице 3 такими строками будут две: . Обязательные строки образуют ядро покрытия. Но обязательная строка покрывает только два столбца с интервалам и , затем находим еще одну обязательную строку , которая покрывает столбец с интервалом . Следовательно, ядром покрытия этой таблицы будет: , соответствующее максимальному интервалу (ставим цифры, которые соответствуют буквам из таблицы 3, а другие буквы соответствуют прочеркам, так как они нас не интересуют), которому соответствует простая импликанта ).

След.,

Аналогично находим множества максимальных интервалов, содержащих остальные единичные интервалы. Строим таблицы различий 4 и 5.

Таблица 4

Единичный интервал (97,117)	Нулевые интервалы
10-0-01		1101-0-
a	1	0	1	0
*b	1	1	1	0
c	-	0	0	0
*d	0	0	0	1
e	-	0	0	0
g	0	0	0	0
h	1	0	0	0

Таблица 5

Единичный интервал (2,51)	Нулевые интервалы
10-0-01		1101-0-
*a	0	1	0	1
b	-	0	0	0
c	-	0	0	0
d	0	0	0	1
*e	0	0	1	0
**g	1	1	1	1
h	-	0	0	0

Найдем все покрытия таблицы 4: . Имеем одно покрытие, соответствующее максимальному интервалу , которому соответствует простая импликанта .

След.,

Найдем все покрытия таблицы 5: и . Имеем два ядра покрытия, соответствующие максимальным интервалам и (!Пояснение: ставим цифры, которые соответствуют буквам из таблицы 5, а другие буквы соответствуют прочеркам, так как они нас не интересуют), которым соответствуют простые импликанты ; .

След.,

Таким образом, получили множество максимальных интервалов (1).

В результате получена сокращенная ДНФ булевой функции , являющейся уже полностью определенной:.

Выделение максимальных интервалов, построение сокращенной ДНФ функции - первый этап минимизации в классе ДНФ. Вторым этапом является переход от сокращенной ДНФ функции к тупиковой ДНФ этой функции (рис. 3).

Тупиковая ДНФ булевой функции получается в результате покрытия столбцов строками импликантной таблицы (двумерной таблицы, каждой строке которой взаимно однозначно соответствует максимальный единичный интервал, столбцу – единичный интервал, а на пересечении -й строки с -м столбцом находится 1, если -й единичный интервал входит в -й максимальный интервал, в противном случае на пересечении находится 0).

Построим для рассматриваемого примера импликантную таблицу (таблица 6).

Таблица 6

Максимальные единичные интервалы функции	Единичные интервалы функции - столбец
- строка	1	0	1
	0	1	0
	0	1	1

Замечание! Нельзя интервалы в таблице ставить двоичные, надо обязательно десятичные.

Таблица имеет два покрытия: Первое покрытие образуют первая и вторая строки. Это покрытие порождает тупиковую ДНФ функции . Второе покрытие образуют первая и третья строки. Это порождает тупиковую ДНФ функцию .

Перебор всех тупиковых ДНФ булевой функции определяет выбор минимальной ДНФ этой функции.

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

Таблица Карно и коды с единичным расстоянием

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

Например, при n=3 на единичном кубе представлены элементарные конъюнкции Множеству соответствует плоскость, множеству ребро, а вершина.

Рассмотрим таблицы Карно при числе переменных от 2 до 5 (таблицы 1).

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

Таблица 1 - Таблицы Карно

a)

0	1
0
1

б)

0 0	0 1	1 1	1 0
0
1

в) (24=16 – количество значений функций)

0 0	0 1	1 1	1 0
0 0
0 1
1 1
1 0

г) (25=32)

0 0 0	0 0 1	0 1 1	0 1 0	1 1 0	1 1 1	1 0 1	1 0 0
0 0
0 1
1 1
1 0

д) (26=64)

0 0 0	0 0 1
000
001

Пример 1. Таблица 2 представляет собой таблицы Карно конъюнкций от трех переменных. Используя описанные свойства, можно сравнительно просто определить простые импликанты функции при .

Таблица 2 - Примеры таблиц Карно, представляющих конъюнкции

а)
0 0	0 1	1 1	1 0
0	0	0	0	0
1	1	1	1	1

Простая импликанта x1

б)
0 0	0 1	1 1	1 0
0	0	1	1	0
1	0	1	1	0

Простая импликанта x3

Пример 2. Построим таблицу Карно (таблица 3) для полностью определенной функции

Таблица 3

0 0	0 1	1 1	1 0
0	1	1	1	1
1	0	0	1	0

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

Например, при n=3 на единичном кубе представлены элементарные конъюнкции Множеству соответствует плоскость, множеству - ребро. Получим две простые импликанты

и соответсвующие максимальным единичным интервалам 0 - - и – 11.