1. Найти любым известным способом сокращенную ДНФ функции, получающейся доопределением единицами исходной функции fна всех неопределенных наборах.
2. Выбрать минимальную ДНФ по импликантной матрице, где в столбцах выписаны лишь те конституенты единицы функции f, которые соответствуют полностью определенным единичным наборам.
Аналогичный алгоритм (с доопределением нулевыми наборами) может быть предложен для поиска КНФ. При этом доопределение таблицы истинности функции fможет быть произведено по-разному для КНФ и ДНФ.
Заметим, что для решения рассматриваемой задачи практически достаточно тех навыков, которые были получены при минимизации полностью определенных булевых функций непосредственно по диаграмме Вейча. В случаях, когда минимальных форм несколько, приводится одна из них.
На практике очень часто приходится реализовывать совокупности булевых функций. Если произвести минимизацию булевых функций, входящих в систему, независимо друг от друга, то общая схема будет состоять из изолированных подсхем. Ее можно иногда упростить за счет объединения участков подсхем, реализующих одинаковые члены, входящие в несколько булевых функций системы.
Задача минимизации систем булевых функций хорошо исследована в классе функционально полных систем: «дизъюнкция», «конъюнкция», «отрицание». Рассмотрим один из наиболее распространенных методов минимизации.
Определение. Система дизъюнктивных нормальных форм булевых функций называется минимальной, если ее полное множество элементарных конъюнкций содержит минимальное количество букв, а каждая дизъюнктивная нормальная форма булевой функции системы включает минимальное число элементарных конъюнкций наименьшего ранга. При этом дизъюнктивная нормальная форма представления булевой функции в минимальной системе в общем случае не совпадает с ее минимальной дизъюнктивной нормальной формой. Минимизация систем полностью определенных булевых функций может производиться по алгоритму, аналогичному алгоритму метода Квайна с небольшими отличиями. Алгоритм минимизации следующий.
1. Построить полное множество А элементарных конъюнкций минимизируемой системы функций, считая, что вначале каждая из функций системы представлена в СДНФ. Каждой конституенте единицы множества А присвоить признак, содержащий номера функций системы, в которые входит рассматриваемая конституента.
2. Произвести минимизацию СДНФ функции L, конституентами единицы которой являются все элементы множества A. При выполнении склеивания двух конституент единицы каждой вновь образуемой элементарной конъюнкции присвоить признак, состоящий из номеров функций, общих для двух склеиваемых конституент единицы. Последнее справедливо и для двух склеиваемых элементарных конъюнкций с признаками. Если признаки склеиваемых конституент единицы не содержат общих номеров, то склеивание не производится. Поглощение производится только для элементарных конъюнкций с одинаковыми признаками. Полученные в результате склеивания и поглощения конъюнкции называются простыми импликантами системы функций.
3. Построить импликантную матрицу функции L, аналогичную матрице Квайна с той разницей, что для каждой конституенты единицы выделяется столько столбцов, сколько различных номеров функций содержит ее признак. Покрытие матрицы импликантами производится аналогично методу Квайна.
Наиболее интересна задача поиска абсолютно минимальной формы — формы, содержащей минимальное число операций заданной функционально полной системы. В общем виде эта задача не решена. Более того, известно, что абсолютно минимальная форма не всегда может быть получена из минимальной ДНФ. В то же время отыскание формы, близкой к абсолютно минимальной,— реальная и практически достижимая задача.
Здесь уместно сказать о типах и классах булевых функций в определении Шеннона. Выше уже упоминалось о взаимно однозначном соответствии между схемами и формами представления булевых функций. В то же время, очевидно, что одна и та же схема может реализовать несколько различных булевых функций, если какие-то входные переменные поменять местами. В этом случае функции принадлежат к одному классу. Если же переменные переставлять, допуская их отрицания, то функции принадлежат к одному типу. Если найти абсолютно минимальную форму представления хотя бы одной функции каждого класса и построить соответствующие таблицы, то задачу синтеза переключательных схем можно было бы свести к поиску нужного класса в таблице. Такие таблицы для функций 4-х переменных были составлены (при реализации функций контактными схемами), практического распространения этот подход не получил. Одной из причин является тот факт, что число классов очень быстро растет с ростом n.
Выводы
Известна более простая задача — задача факторизации, заключающаяся в упрощении дизъюнктивно-конъюнктивных форм, допуская отрицания лишь над переменными. Часто она называется задачей скобочной минимизации, и в настоящее время известно достаточно много методов такого упрощения. В общем виде задача факторизации не решена, но для булевого базиса, в ряде случаев, используя операцию вынесения за скобки общих членов, можно получить скобочную форму, значительно более простую, чем минимальная ДНФ булевой функции.
Литература
1. Самофалов К.Г., Романкевич А.М., и др. Прикладная теория цифровых автоматов. - Киев. “Вища школа” 1987.
2. Соловьев Г.Н. Арифметические устройства ЭВМ. - М. “Энергия”. 1978.
3. Савельев А.Я. Прикладная теория цифровых автоматов - М. “Высшая школа”. 1987.
4. Каган Б.М. Электронные вычислительные машины и системы. - М. Энергоатомиздат. 1985.
5. Лысиков Б.Г. Арифметические и логические основы цифровых автоматов. - Минск. “Вышэйшая школа”. 1980.