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

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

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

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

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

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

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

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

Решение.

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

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

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

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

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

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

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

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

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

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

Таблица 5

Конституента Простая единицы импликанта Минимизация по методу Квайна с применением карт Карно - student2.ru Минимизация по методу Квайна с применением карт Карно - student2.ru Минимизация по методу Квайна с применением карт Карно - student2.ru
А = Минимизация по методу Квайна с применением карт Карно - student2.ru *    
B = Минимизация по методу Квайна с применением карт Карно - student2.ru *    
C = Минимизация по методу Квайна с применением карт Карно - student2.ru   *  
D = Минимизация по методу Квайна с применением карт Карно - student2.ru   * *
E = Минимизация по методу Квайна с применением карт Карно - student2.ru     *

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

Наши рекомендации