2020-01-15
138
При минимизации по данному методу предполагается, что минимизируемая функция задана в СДНФ. Метод Квайна – Мак – Класки состоит из последовательного выполнения следующий этапов.
Метод Квайна состоит из последовательного выполнения этапов:
1) Нахождение первичных импликант
2) Расстановка меток
3) Нахождение существенных импликант
4) Вычеркивание лишних столбцов
5) Вычеркивание лишних
6) Получение минимального покрытия
Выполним, приведенные этапы, для функции У3.
Нахождение первичных импликант. Все минитермы (элементарные конъюнкции, входящие в ДНФ) данной функции записываются в виде их двоичных номеров. Все номера разбиваются по числу единиц в этих номерах на не пересекающиеся группы. При этом в i -тую группу войдут все номера, имеющие в своей двоичной записи ровно i единиц. По парное сравнение (склеивание) можно производить только между соседними по номеру группами. При образовании минитермов с рангом выше нулевого в разряды, соответствующие исключенным переменным, пишется знак тире. Минитермы, не склеивающиеся между собой, называются первичными импликантами.
|
|
|
СДНФ, которую мы нашли ранее, для функции У3 имеет вид:
Составим минитермы для этой функции:
Таблица 2.2.1
| Минитермы длиной 4 | Минитермы длиной 3 | ||
| Нулевая группа | 0000+ | Нулевая группа | 0-00 |
| Первая группа | 0100+ | Первая группа | -100, -011 |
| Вторая группа | 1100, 1010, 0011 | Вторая группа | 11-0, 1-10, 101- |
| Третья группа | 1110, 1011 | ||
Расстановка меток. Остальные этапы нужны, чтобы отбросить некоторые первичные импликанты. На данном этапе составляется таблица, число строк которой равно числу полученных первичных импликант, число столбцов совпадает с числом минитермов СДНФ. Если в некоторый минитерм СДНФ входит какая – либо из первичных импликант, то на пересечении соответствующего столбца и строки ставится метка. В таблице 2.2.2 приведем результат расстановки меток:
Таблица 2.2.2
| 0000 | 0100 | 1100 | 1010 | 0011 | 1110 | 1011 | ||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| 1 | 0-00 | У | У | |||||
| 2 | -100 | У | У | |||||
| 3 | -011 | У | У | |||||
| 4 | 11-0 | У | У | |||||
| 5 | 1-10 | У | У | |||||
| 6 | 101- | У | У |
Нахождение существенных импликант. Если в каком – либо из столбцов таблицы меток стоит только одна метка, то первичная импликанта, стоящая в соответствующей строке, называется существенной импликантой. Все существенные импликанты запоминаются. А из таблицы меток исключаются строки, соответствующие существенным импликантам, и столбцы минитермов «покрываемых» этими существенными импликантами.
|
|
|
Существенными являются импликанты 0-00 и -011. Поэтому вычеркиваем 1-ю и 3-ю строки и столбцы: 1, 5, 2, 7.
Составим сокращенную таблицу меток:
Таблица 2.2.3
| 1100 | 1010 | 1110 | |
| -100 | У | ||
| 11-0 | У | У | |
| 1-10 | У | У | |
| 101- | У |
Выбор минимального покрытия. Исследуется результирующая таблица. Выбирается такая совокупность первичных импликант, которая иссключает метки во всех столбцах (по крайней мере по одной в каждом столбце). При нескольких возможных вариантах такого выбора отдается предпочтение варианту покрытия с минимальным суммарным числом букв в простых импликантах, образующих покрытие.
С учетом существенных импликант получим две МДНФ для этой функции имеет вид:
1. 
2. 
Число букв составляющих простые импликации в каждом варианте одинаково. Во втором варианте на одно отрицание меньше, поэтому берем его за искомое:
