Минимизация логических функций: общие сведения
Минимизация: для чего?
Задача минимизации логических выражений возникает в практике создания логических схем. В качестве исходной аналитической формы обычно рассматриваются совершенные дизъюнктивная нормальная форма (ДНФ) и конъюнктивная нормальная форма (КНФ), которые во многих случаях оказываются излишне сложными. Из-за этой сложности их техническая или программная реализация получается избыточной. Для упрощения СДНФ и СКНФ используются различные методы минимизации - преобразования логической функции с целью упрощения её аналитической записи.
Наиболее широкое распространение получили следующие методы минимизации логических функций:
Минимальный вариант булевой функции обычно ищут применительно к какому-либо логическому базису. Наилучшие результаты получаются с функциями "НЕ", "И", "ИЛИ", в силу чего именно эти функции будем использовать в качестве основного логического базиса.
Сложность реализации логического выражения обычно характеризуют с помощью коэффициента
сложности Кс. ДЛя вычисления этого коэффициента нужно сложить количествл термов, образующих выражение
(слагаемых в ДНФ или сомножителей в КНФ), и сумму рангов всех этих термов. Ранг терма равен количеству
переменных в терме, например, ранг терма x1x2x3
равен трём. Следовательно, для функции 
,
содержащей 4 терма (три терма с рангом 2 и один терм рангом 3), коэффициент сложности Кс=4+(2+2+2+3)=13.
Целью минимизации является получение такой аналитической записи логической функции, которая имеет наименьший коэффициент сложности среди всех других эквивалентных вариантов записи данной функции. Подобную аналитическую запись логической функции называбт минимальной, то есть целью минимизации является получение минимальной дизъюнктивной нормальной формы (МДНФ) или минимальной конъюнктивной нормальной формы (МКНФ).
В основе практически всех методов минимизации - операция склеивания. Два элементарных произведения одинакового ранга (для ДНФ) или две элементарные суммы одинакового ранга (для КНФ) склеиваются, если они различаются только по одной переменной, а это различие состоит в присутствии знака инверсии над этой переменной в одном из произведений (сумм) и в его отсутствии в другом.
Прежде чем перейти к рассмотрению методов минимазации логических функций, приведём используемые в этом случае положения и определения.
Этапы минимизации ДНФ
Элементарные логические произведения, образовавшиеся результате склеивания, называют
импликантами. Склеивания начинаются с минтермов и продолжаются с импликантами, полученными в предшествующих
операциях склеивания. Так, если СДНФ описывается выражением 
,
то после склеивания минтермов 
и
получим импликанту
, которая поглощает
участвовавшие в склеивании минтермы. Склеивание другой пары минтермов -
и
даёт импликанту
, также поглощающую
минтермы, из которых она была получена. В результате исходная ДНФ приобретает следующий вид:
. Конъюнкции в правой части
выражения (обратим внимание, что это уже не минтермы, а импликанты) также можно склеить, получив при
этом импликанту 
. Импликанты,
дальнейшее склеивание которых невозможно, называют простыми, или первичными импликантами. В нашем примере
является простой импликантой.
Выражение, полученное из совершенной ДНФ и состоящее только из простых импликант, называется сокращённой нормальной формой.
Следующим этапом минимизации является нахождение тупиковых ДНФ. Тупиковой дизъюнктивной нормальной формой называется ДНФ, полученная из сокращённой ДНФ, в результате исключения из последней всех лишних простых импликант. В зависимости от того, какие из простых импликант были признаны лишними, может получиться несколько вариантов тупиковых ДНФ.
Тупиковая ДНФ, имеющая наименьший коэффициент сложности по сравнению с другими тупиковыми формами данной функции, называется минимальной дизъюнктивной нормальной формой (МДНФ). Если среди возможных тупиковых форм имеется несколько с одинаковым коэффициентом сложности, это означает, что существует и несколько МДНФ.
Аналитическая минимизация производится в такой последовательности:
- находят сокращённую дизюнктивную нормальную форму (любая функция имеет только одну такую форму);
- находят все тупиковые нормальные формы;
- из полученных тупиковых форм выбирают минимальные формы.
Аналоги для КНФ
Для приведённых выше понятий имеются аналоги, относящиеся к конъюнктивным нормальным формам.
Имплицентой называется элементарная логическая сумма, получаемая при склеивании пары макстермов или имплицент, образовавшихся в результате предшествующих склеиваний.
Простая имплицента - это имплицента, которую уже нельзя склеить ни с одной другой.
Сокращённая конъюнктивная нормальная форма - это конъюнкция все простых имплицент.
Тупиковая конъюнктивная нормальная форма - это логическое произведение простых имплицент, из которых ни одна не является лишней.
Минимальная конъюнктивная нормальная форма (МКНФ) - тупиковая КНФ, имеющая наименьший коэффициент сложности среди других тупиковых форм данной логической функции.
Последовательность процедуры минимизации для КНФ аналогична описанной в предыдущем параграфе для ДНФ.
