9.6. АБСОЛЮТНО МИНИМАЛЬНАЯ ФОРМА ПРЕДСТАВЛЕНИЯ БУЛЕВЫХ ФУНКЦИЙ

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

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

Здесь уместно сказать о типах и классах булевых функций в определении Шеннона. Выше уже упоминалось о взаимнооднозначном соответствии между схемами и формами представления булевых функций. В то же время, очевидно, что одна и та же схема может реализовать несколько различных булевых функций, если какие-то входные переменные поменять местами. В этом случае функции принадлежат к одному классу Если же переменные переставлять, допуская их отрицания, то функции принадлежат к одному типу. Если найти абсолютно минимальную форму представления хотя бы одной функции каждого класса и построить соответствующие таблицы, то задачу синтеза переключательных схем можно было бы свести к поиску нужного класса [в таблице Такие таблицы для функций 4-х переменных были составлен (при реализации функций контактными схемами), практического распространения этот подход не получил. Одной из причин является тот факт, что число классов очень быстро растет с ростом

Известна более простая задача — задача факторизации, заключающаяся в упрощении дизъюнктивно-конъюнктивных форм, допуская отрицания лишь над переменными. Часто она называется задачей скобочной минимизации, и в настоящее время известно достаточно много методов такого упрощения. В общем виде задача факторизации не решена, но для левого базиса, в ряде случаев, используя операцию вынесения за скобки общих членов, можно получить скобочную форму, значительно более простую, чем минимальная ДНФ булевой функции.

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

Обозначим каждую конъюнкцию заданного выражения буквами: Тогда функцию можно представить множеством:

На первом этапе работы алгоритма ищутся все попарные пересечения элементов множества Р. В нашем случае имеем

Выбирается та пара элементов множества пересечение которых дает конъюнкцию наибольшей длины. Для рассматриваемого примера

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

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

Обозначив получим множество Ищем пересечение элементов Получаем Окончательно имеем

В итоге полученная форма содержит 9 операций типа И, ИЛИ, в отличие от минимальной ДНФ, содержащей 14 операций.

В заключение приведем еще один пример, подтверждающий возможность сильного упрощения минимальной ДНФ. Функция являющаяся суммой по модулю переменных очень неудобна для минимизации: склеивания невозможны и ее минимальная ДНФ совпадает с СДНФ. Она содержит двухместных операций типа И и ИЛИ. В то же время можно записать функцию в виде полинома и использовать представление операции через конъюнкцию и дизъюнкцию, включающее 4 операции: Заменяя в полиноме все двухместные операции суммы по модулю 2 в соответствии с этим соотношением, приходим к выраженню функции содержащему всего операции из системы И, ИЛИ, НЕ. Приведенное соотношение для легко получается из КНФ этой функции: