Минимизация булевых функций

5. Минимизация булевых функций

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

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

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

Методов минимизации булевых функций в настоящее время существует довольно много. Все они, как правило, состоят из двух этапов. На первом этапе получают список всех простых импликант, т.е. сокращенную ДНФ. На втором этапе, используя таблицу покрытий, удаляют “лишние” импликанты, покрывемые другими импликантами. В результате получают ДНФ, из которой нельзя удалить ни одной импликанты. Такую ДНФ называют тупиковой.

5.1 Метод Квайна

На первом этапе в методе Квайна попарно сравнивают все импликанты, входящие в СДНФ, в целях выявления возможности поглощения какой-то переменной на основе закона склеивания:

.

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

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

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

5.2 Метод Квайна с применением п-мерных кубов

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

При решении задачи минимизации булевой функции удобно вместо конъюнктивных термов использовать, соответствующие им, двоичные наборы.

Пример.

Минимизировать булеву функцию

.

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

Представим функцию в виде СДНФ:

Запишем конъюнктивные термы в виде двоичных наборов:

.

Построим единичный 4 – мерный куб и выделим вершины, соответствующие двоичным наборам, входящим в заданную булеву функцию (рис. 10):

Рис. 10

1 этап. Определение сокращенной ДНФ.

Применим закон склеивания для отмеченных вершин (для двоичных наборов) куба, соединенных ребром:

Прочерк означает, что переменная в этом месте отсутствует.

Для некоторых простых импликант склеивание можно продолжить:

По закону идемпотентности:

Дизъюнкция полученных простых импликант является сокращенной ДНФ:

2 этап. Определение тупиковой ДНФ.

Для определения тупиковой ДНФ построим таблицу покрытий, в которую следует включать и двоичные наборы, не участвовавшие в склеивании:

Определяя минимальное число строк, покрывающих все столбцы таблицы, находим тупиковую ДНФ:

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

5.3 Метод Квайна – Мак-Класки

Метод Квайна – Мак-Класки представляет собой предыдущий метод, но без геометрического построения п – мерных кубов: кубы присутствуют, но абстрактно.

Метод основан на кубическом представлении конъюнктивных термов ДНФ с предварительным разбиением кубов на подгруппы, определяемые одинаковым числом единиц. Разбиение дает возможность сравнивать кубы только соседних по числу единиц групп для уменьшения количества переборов.

В итеративной процедуре минимизации попарное сравнение можно производить только между соседними группами.

Нахождение простых импликат на первом этапе:

1. Все исходные конъюнктивные термы записываются в виде их двоичных наборов.

2. Все наборы разбиваются на непересекающиеся группы по числу единиц. Условие образования r-куба – наличие расхождения в (r-1)-кубах только по одной координате в одном двоичном разряде и наличие общих независимых координат.

3. В i-группу включают все двоичные наборы, имеющие в своей записи i единиц.

4. Попарное сравнение производится только между соседними по номеру группами. Группы, которые различаются в двух разрядах и более, не имеет смысла сравнивать.

Пример.

(Предыдущий пример)

Минимизировать булеву функцию