Минимизация по методу Квайна с применением карт Карно

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

1. Нанесение функции на карту Карно.

2. Анализ каждой клетки с «единицей» и нахождение для нее простых и существенных импликант. Если найдена существенная импликанта, то клетки с «единицами», составляющие эту импликанту, при дальнейшем поиске простых импликант не рассматривают. Для этого их отмечают точками. Поэтому при рассмотрении карт Карно необходимо прежде всего обнаружить клетки с «единицами», которые дают существенные импликанты. Это уменьшает количество рассматриваемых клеток с «единицами».

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

4. Как и по методу Квайна составляется импликантная таблица, строки которой обозначаются простыми импликантами, полученными на этапе 2, а столбцы – конституентами единицы, оставшимися после выполнения этапа 3.

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

Пример 7. Найти минимальную ДНФ функции f(х₄, х₃, х₂, х₁), которая равна единице на наборах переменных: 2, 3, 4, 5, 7, 9, 11, 12, 13.

Решение.

1. Нанесем заданную ФАЛ на карту Карно (рис. 4,а).

Рис. 4. Карты Карно ФАЛ четырех переменных

2.Найдем простые и существенные импликанты функции.

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

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

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

Конституента единицы склеивается с соседними слева и снизу. В результате получим простые импликанты и .

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

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

3. Составим импликантную таблицу (табл. 5), столбцы и строки которой озаглавим оставшимися конституентами единицы и простыми импликантами соответственно, и расставим метки.

Таблица 5

Конституента Простая единицы импликанта
А =	*
B =	*
C =		*
D =		*	*
E =			*

4. Нахождение тупиковых и минимальных ДНФ функции.