МЕТОДЫ МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ

аранов Виктор Павлович. Дискретная математика. Раздел 5. ДНФ и схемы из ФЭ.

Лекция 27. Методы минимизации булевых функций

Лекция 27. МЕТОДЫ МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ

План лекции:

1. Минимизация булевых функций на основе построения тупиковых ДНФ.

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

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

Минимизация булевых функций на основе построения тупиковых ДНФ

Сокращенная, тупиковая и минимальная ДНФ находятся в следующем соотношении.

Тупиковая ДНФ получается из сокращенной путем удаления некоторых членов.

Минимальная ДНФ является тупиковой.

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

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

Минимальные д .н .ф.

Рис. 1. Процесс построения минимальных ДНФ

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

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

При использовании этого метода производится покрытие функций алгебры логики (ФАЛ) с помощью правильных конфигураций, содержащих нули или единицы. Правильными конфигурациями на карте Карно для ФАЛ от переменных являются все прямоугольники (горизонтальные, вертикальные, квадраты), имеющие площадь . При этом стремятся, чтобы число покрытий ФАЛ на карте было минимально, а площадь, покрываемая каждой конфигурацией – максимальна. Конфигурации могут перекрываться. Принцип минимизации заключается в объединении соседних полей карты в пределах правильной конфигурации.

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

Например, функция от четырех переменных компактно записывается в форме матрицы размера [], как это показано на рис. 2.

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


	00	01	11	10
00	1	1	0	1
01	1	1	0	1
11	0	1	1	0
10	1	1	1	1

Рис. 2. Карта Карно

Для функции от четырех переменных имеем.

Конъюнкции ранга 4 соответствует одна клетка:


	00	01	11	10		00	01	11	10
00					00
01					01
11					11
10					10

Конъюнкции ранга 3 соответствует пара соседних клеток:


	00	01	11	10		00	01	11	10		00	01	11	10
00					00					00
01					01					01
11					11					11
10					10					10

Конъюнкции ранга 2 соответствуют 4 клетки, образующие горизонтальный или вертикальный ряд, либо подматрицу размера []:


	00	01	11	10		00	01	11	10		00	01	11	10
00					00					00
01					01					01
11					11					11
10					10					10


	00	01	11	10		00	01	11	10
00					00
01					01
11					11
10					10

Конъюнкции ранга 1 соответствуют 8 клеток из двух соседних горизонтальных или вертикальных рядов:


	00	01	11	10		00	01	11	10
00					00
01					01
11					11
10					10

Пример 1. Для функции (см. рис. 1) разобьем множество единичных клеток на следующие подмножества:


	00	01	11	10		00	01	11	10
00	1			1	00		1
01	1			1	01		1
11					11		1
10					10		1


	00	01	11	10		00	01	11	10
00					00	1			1
01					01
11		1	1		11
10		1	1		10	1			1

Объединение этих подмножеств дает все единичные клетки функции . Поэтому

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

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

элементарная конъюнкция (набор ) ; номер 010(2); индекс 1;

элементарная конъюнкция (набор ) ; номер 110(6); индекс 2.

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

Пример 2. Реализацию алгоритма рассмотрим на примере минимизации функции

На первом этапе минимизации определяем номера и индексы каждого набора, записывая функцию в виде

На втором этапе группируем наборы, располагая их в порядке возрастания индексов (табл. 1).

Таблица 1. Минимизация ФАЛ методом Квайна-Мак-Класски

Индекс

Номер

Результаты склеивания

0001(1)

00-1

0-01

-001

0--1

-0-1

0--1

-0-1

0011(3)

0101(5)

1001(9)

0-11

-011

01-1

10-1

III

0111(7)

1011(11)

На третьем этапе производим склеивание различных наборов, руководствуясь приведенной выше формулировкой алгоритма. При склеивании не совпадающие в числах разряды отмечаются прочерками. Например, склеивание чисел 0001 и 0011 дает число 00-1. Результат склеивания записывается в следующий столбец таблицы 1, также разделяемый на строки с индексами, отличающимися на единицу. После склеивания всех групп первого столбца таблицы переходят ко второму, записывая результат склеивания в третий столбец. При объединении второго и последующих столбцов таблицы возможно склеивать только числа, содержащие прочерки в одноименных разрядах. Склеивание продолжается до тех пор, пока образование нового столбца станет невозможно.

На четвертом этапе после окончания склеивания приступают к построению импликантной таблицы (табл. 2), записывая в нее в качестве простых импликант наборы, содержащиеся в последнем столбце таблицы 1. В таблицу 2 также вписываются в качестве простых импликант наборы из других столбцов таблицы 1, не принимавшие участия в склеивании. Если импликанта, содержащаяся в -ой строке таблицы, составляет часть конституенты -го столбца, то на пересечении -ой строки и -го столбца ставится символ *. Для получения минимальной формы ФАЛ из таблицы 2 необходимо выбрать минимальное число строк, чтобы для каждого столбца среди выбранных строк нашлась хотя бы одна, содержащая в этом столбце символ *.

Таблица 2. Импликантная таблица минимизируемой функции

Импликаты	Наборы

	*	*		*		*
	*		*		*	*

В результате минимизации функция представится в виде

Совершенная ДНФ

Сокращенная ДНФ

Тупиковая ДНФ

МЕТОДЫ МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ