Предположим, что функция задана в ДСНФ.
Элементарные конъюнкции ранга n будем называть минитермами ранга n.
Шаг 1. Нахождение первичных импликант.
Все минитермы данной ФАЛ сравниваются между собой попарно.
Если минитермы mi и mj таковы, что их можно попарно представить в виде , то выписывается конъюнкция, которая является минитермом ранга n-1: .
Минитермы n-го ранга, для которых произошло склеивание отмечаются (*).
После построения всех минитермов (n-1)-го ранга вновь сравнивают их попарно, выписывают минитермы (n-2)-го ранга и отмечают склеивающиеся минитермы и т.д.
Этап заканчивается, когда вновь полученные минитермы l-го ранга уже не склеиваются между собой.
Все неотмеченные минитермы называются первичными или простыми импликантами.
Шаг 2. Расстановка меток.
Для данной функции
, где - первичные импликанты. (1)
Соотношение (1) определяет СДНФ для данной функции.
Для нахождения минимального покрытия интервалами максимального ранга необходимо произвести выбрасывание некоторого количества первичных импликант.
|
|
На этапе расстановки меток составляется таблица, число строк в которой равно числу первичных импликант, число столбцов равно числу минитермов ДСНФ.
Если в минитерм ДСНФ входит какой-либо из первичных импликант, то на пересечении соответствующего столбца и строки ставим метку.
Шаг 3. Нахождение существенных импликант.
Если в столбце стоит всего одна метка, то соответствующая импликанта – существенная.
Существенная импликанта не может быть исключена из правой части (1), т.к. без нее не будет получено покрытие всего множества данной функции. Поэтому из таблицы меток исключаем строки, соответствующие существенным импликантам, и столбцы минитермов, покрываемых ими.
Шаг 4. Вычеркивание лишних столбцов.
Если в таблице есть два столбца с метками в одинаковых строках, то один из них вычеркивается (так как покрытие одного обеспечивает и покрытие другого).
Шаг 5. Вычеркивание лишних первичных импликант.
Если после этапа 4 в таблице есть строки без единой метки, то они вычеркиваются.
Шаг 6. Выбор минимального покрытия максимальными интервалами.
Исследуется полученная таблица: выбирается такая совокупность первичных импликант, которая включает метки во всех столбцах (по крайней мере по 1 в каждом столбце).
При нескольких вариантах отдается предпочтение варианту покрытия с минимальным суммарным числом букв в простых импликантах.
Метод Мак-Класки минимизации булевых функций
Метод Мак-Класки - модификация первого этапа метода Квайна.
Шаг 1. Всем минитермам ставим в соответствие их двоичный эквивалент.
|
|
Шаг 2. Все номера-минитермы разбиваем на группы по числу единиц в этих номерах.
Шаг 3. Все минитермы сравниваются между собой попарно.
Попарное сравнение можно производить только между соседними группами, т.к. только эти группы отличаются для входящих в них минитермов в одном разряде.
Шаг 4. Преобразование новых минитермов:
В разрядах, соответствующих исключенным переменным, ставим черточку. Такая модификация удобна еще и отсутствием громоздкой записи.
Шаг 5. Строим таблицу и расставляем метки, как и в методе Квайна (п.2).
Шаг 6. Далее минимизация проводится по таблице как и в методе Квайна (п.3-6).
Например:
Задана функция f(x1,x2,x3,x4,), которая равна единице на наборах с номерами – 0, 1, 2, 3, 4, 6, 7, 8, 9, 11, 15.
Минимизировать ее методом Квайна - Мак-Класки.
Решение:
1. Построим двоичные наборы, на которых задана функция.
№ набора | Наборы | f (x 1,x 2,x 3,x4) |
2. Разобьем минитермы на группы по числу единиц.
0000* ------------------------------ – нулевая группа
0001*, 0010*, 0100*, 1000* --- – первая группа
0011*, 0110*, 1001* ------------ – вторая группа
0111*, 1011* --------------------- – третья группа
1111* ------------------------------ – четвертая группа
3. Сравним все минитермы попарно между собой, и произведем преобразование. Полученные минитермы также разобьем на группы.
000_*, 00_0*, 0_00*, _000* ----------------- – нулевая группа
00_1*, _001*, 001_*, 0_10*, 01_0*, 100_* – первая группа
0_11*, _011*, 011*_, 10_1* ----------------- – вторая группа
_111*, 1_11* ----------------------------------- – третья группа
4. Продолжим сравнение и преобразование минитермов до тех пор пока преобразование станет невозможным.
00_ _, _00 _, 0__0 ---------------- – нулевая группа
_0_1, 0_1_ ------------------------ – первая группа
_ _11 ------------------------------- – вторая группа
5. Построим таблицу и расставим метки.
6.
00_ _ | Ö | Ö | Ö | Ö | |||||||
_ 00 _ | Ö | Ö | Ö | Ö | |||||||
0_ _0 | Ö | Ö | Ö | Ö | |||||||
_0_1 | Ö | Ö | Ö | Ö | |||||||
0_1_ | Ö | Ö | Ö | Ö | |||||||
_ _11 | Ö | Ö | Ö | Ö |
7. Проведем преобразования таблицы (п. 3-6 метода Квайна).
Вычеркиваем столбцы, соответствующие существенным импликантам и отметим (●) столбцы минитермов, покрываемых ими.
●1 | ●2 | ●1 | ●3 | ●1 | ●1 | ●3 | ●2 | ●2 | ●3 | ●3 | |
00__ | Ö | Ö | Ö | Ö | |||||||
_ 00 _ | Ö | Ö | Ö | Ö | |||||||
0__0 | Ö | Ö | Ö | Ö | |||||||
_0_1 | Ö | Ö | Ö | Ö | |||||||
0_1_ | Ö | Ö | Ö | Ö | |||||||
__11 | Ö | Ö | Ö | Ö |
8. Выберем совокупность первичных импликант, которая включает метки во всех столбцах (по крайней мере по 1 в каждом столбце).
В результате получаем