В предыдущем разделе мы познакомились с различными типами ДНФ и научились их находить визуально по матрице Грея. Перейдем к изучению формальных методов построения сокращенной, безызбыточных, минимальных и кратчайших ДНФ булевой функции, заданной совершенной или произвольной ДНФ.
Интерес к кратчайшим и минимальным ДНФ основан на их оптимальности (по длине и рангу соответственно), которая положительно проявляется, по крайней мере, в следующих двух случаях. Во-первых, с оптимальными ДНФ легче оперировать, то есть вычислять значения функции, строить матрицу Грея и подставлять в другие формулы. Во-вторых, оптимальные ДНФ более предпочтительны для построения по ним схем из логических элементов: дизъюнкторов, конъюнкторов и инверторов.
Пример. Рассмотрим мажоритарную функцию.
Нарисуем схемы по совершенной и кратчайшей ДНФ. Логические элементы изобразим в виде соответственно обозначенных прямоугольников.
Схема, построенная по кратчайшей ДНФ (справа), оказалась проще: она содержит меньше элементов. •
Интерес к сокращенной ДНФ вызван тем, что она является промежуточной при построении кратчайших, минимальных и безызбыточных ДНФ.
Безызбыточные ДНФ интересны как сами по себе, так как часто оказываются близкими к оптимальным, так и тем, что среди них находятся все минимальные и простые кратчайшие ДНФ.
Определение. Минимизировать булеву функцию это значит построить ее кратчайшую или минимальную ДНФ или все кратчайшие или все минимальные ДНФ (постановка задачи уточняется дополнительно).
Рассмотрим двухэтапный подход к минимизации булевой функции, основанный на теоремах о кратчайшей и минимальных ДНФ (подраздел 9.2), утверждающих, что все минимальные и хотя бы одна из кратчайших ДНФ состоят из простых импликант.
Первый этап: найдем все простые импликанты функции, то есть конъюнкции ее сокращенной ДНФ.
Второй этап: из сокращенной ДНФ выделим конъюнкции искомых ДНФ (кратчайших или минимальных).
Далее наряду с языком ДНФ будем использовать язык интервалов как более наглядный при визуальном решении и более удобный при компьютерной реализации алгоритмов. Напомним аналогию между рядом понятий (относящихся к одной и той же булевой функции) на упомянутых языках.
| Язык ДНФ | Язык интервалов |
| полная конъюнкция-импликанта | точка |
| элементарная конъюнкция-импликанта | допустимый интервал |
| простая импликанта | максимальный интервал |
| ДНФ | достаточное множество интервалов |
| совершенная ДНФ | множество всех точек |
| сокращенная ДНФ | множество всех максимальных интервалов |
| кратчайшая ДНФ | достаточное множество из минимального числа максимальных интервалов |
| минимальная ДНФ | достаточное множество максимальных интервалов с минимальной суммой рангов |
| безызбыточная ДНФ | достаточное множество максимальных интервалов, которое при удалении любого интервала перестает быть достаточным |