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

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

Пример

В этом примере мы получили более экономичную запись функции.

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

Введем ряд обозначений. Будем обозначать

Тогда любую конъюнкцию n- переменных можно записать в виде

(*)

где .

Конъюнкция (*) называется элементарной, если каждая переменная встречается в ней не более одного раза.

Рангом элементарной конъюнкции назовем число букв в ней.

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

Назовем длиной ДНФ число элементарных конъюнкций в ней. Например,

есть ДНФ длины 3 с конъюнкциями ранга 2.

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

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

Аналогичные определения можно сделать и для КНФ.

Рассмотрим геометрическую интерпретацию области определения булевой функции 3-х переменных, т. е. множество вершин единичного куба.

Элементам куба можно сопоставить конъюнкции различных рангов: вершинам – конъюнкции 3^горанга, ребрам – 2^горанга, граням – конъюнкции первого ранга.

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

По аналогии можно говорить о покрытии конъюнкции большего ранга конъюнкциями меньшего ранга. Так, например, конъюнкции покрываются конъюнкцией, а операцию покрытия можно представить так:

Если имеет место соотношение:

то такая операция называется склеиванием.

Геометрические эквиваленты конъюнкций будем называть интервалами. Интервалом l-го ранга называется подмножество вершин куба, соответствующее конъюнкцииl-го ранга.

Например, вершины являются интервалами третьего ранга, ребра – интервалы второго ранга, грани – интервалы первого ранга.

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

Пример

Мы выполнили перекрытие 4-х интервалов 3^горанга двумя интервалами 2^горанга. Таким образом, мы установили взаимо-однозначное соответствие между заданием функции в виде ДНФ и покрытием множества Т для данной функции интервалами некоторого ранга.

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

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

Интервал Yназывается максимальным, если не существует другого интервалас рангом, меньшим, чем уY, и такого, что

Пример

Здесь интервал является максимальным, а,, не являются максимальными. Интервалтоже является максимальным.

ДНФ, соответствующая покрытию множества Т всемимаксимальными интервалами, называется сокращенной ДНФ ( Сокр. ДНФ ).

Пример

Сокр. ДНФ

Очевидно, что Сокр. ДНФ не является минимальной, т. к. МДНФ в этом примере

Теорема

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

Пример

Для ДНФявляется тупиковой, но не минимальной, а МДНФ есть

Т. о. можно утверждать, что МДНФ всегда является тупиковой, хотя обратное неверно.

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

Пример

Длясуществует две МДНФ

Сравнив все ТДНФ по числу букв, можно определить МДНФ.

Для автоматизированного решения задачи минимизации булевых функций разработан ряд методов, которые мы рассмотрим.

Замечание

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