Минимизация ПФ от большого числа переменных методом Квайна

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

Метод Квайна основывается на применении двух основных соотношений.

Соотношение склеивания

где А – любое элементарное произведение.

Соотношение поглощения

Справедливость обоих соотношений легко проверяется.

Минимизация по методу Квайна выполняется по следующему алгоритму:

1. Выполняются все склеивания в СДНФ.

2. Выполняются все поглощения.

3. Результирующая функция проверяется на возможность дальнейшего склеивания и поглощения.

4. После получения сокращенной ДНФ строится импликантная матрица, по которой находятся «лишние» импликанты.

Например. Пусть имеется булева функция, заданная таблицей истинности.

Ее СДНФ имеет вид:

Для удобства изложения пометим каждое слагаемое функции f каким-либо десятичным номером.

Выполняем склеивания. Слагаемое 1 склеивается только со слагаемым 2 (по переменной х3) и с слагаемым 3 (по переменной х2), слагаемое 2 со слагаемым 4 и т.д. В результате получаем:

1-2 (x₃):

1-3 (x₂):

2-4 (x₂):

3-4 (x₃):

4-6 (x₁):

5-6 (x₄):

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

Далее производим склеивания получаемых элементарных произведений. Склеиваются только те произведения, которые содержат одинаковые переменные. Имеет место два случая склеивания:

и →

и →

с появлением одного и того же элементарного произведения . Дальнейшие склеивания невозможны.

Произведя поглощения (из полученной ДНФ вычеркиваем все поглощаемые элементарные произведения), получим сокращенную ДНФ:

++

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

Таблица – Импликантная матрица

Простые импликанты	Слагаемые функции
	Х	Х	Х	Х
				Х		Х
					Х	Х

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

Минимальные ДНФ строятся по импликантной матрице следующим образом:

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

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

Ядром нашей функции являются импликанты и . Импликанта – лишняя, так как ядро накрывает все столбцы импликантной матрицы.

Поэтому функция имеет единственную тупиковую и минимальную ДНФ: fmin=+.

Следует отметить, что число N крестиков в одной строке всегда является степенью 2. Более того, читатель может легко убедиться в том, что N = 2n-k, где k – число букв, содержащихся в простой импликанте.

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

Дата добавления: 2014-01-15