Понятие о минимизации логических функций

При построении цифровых устройств, реализующих заданные

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

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

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

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

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

3.4.1. Основные понятия и определения

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

Рассмотрим три полностью определенные функции f(x), g(x) и d(x). Функция f(x) определена на множестве единичных наборов M1[f(x)] и множестве нулевых наборов M0[f(x)].

Функция g(x) определена на множестве единичных наборов M1[g(x)], а функция d(x) - на множестве нулевых наборов M0[d(x)].

Логическая функция g(x) называется импликантой логической функции f(x) , если множество единичных наборов функции g(x) совпадает или является подмножеством множества единичных наборов функции f(x), т.е.

M1[g(x)]Í M1[f(x)].

Логическая функция d(x) называется имплицентой логической функции f(x), если множество нулевых наборов функции d(x) совпадает или является подмножеством множества нулевых наборов функции f(x) т.е.

M0[d(x)]Í M0[f(x)].

Например, логическая функция g(x)= Понятие о минимизации логических функций - student2.ru является импликантой логической функции

Понятие о минимизации логических функций - student2.ru ,

так как множество M1[g(x)] составляют наборы 100 110, которые входят в множество M1[f(x)]. Аналогично логическая функция Понятие о минимизации логических функций - student2.ru является имплицентой этой же логической функции f(x), так как множество M0[d(x)]составляют наборы 001 и 011, которые входят во множество M0[f(x)].

Простой импликантой функции f(x) называется любая элементарная функция g(x), являющаяся импликантой этой функции и обладающая тем свойством, что никакая ее собственная часть (т.е. конъюнкция, получаемая из элементарной путем исключения одной или нескольких переменных или их отрицаний) уже не является импликантой данной функции.

Следует обратить внимание, что простой импликантой может быть только элементарная конъюнкция. Докажем это утверждение.

Пусть Понятие о минимизации логических функций - student2.ru есть импликанта функции f(x), т.е.

M1[g(x)]Í M1[f(x)],

где

M1[g(x)]= M1[g1(x)] Понятие о минимизации логических функций - student2.ru .

Отсюда следует, что

M1[g1(x)]Í M1[f(x)];

M1[g2(x)]Í M1[f(x)].

Следовательно, функции Понятие о минимизации логических функций - student2.ru и Понятие о минимизации логических функций - student2.ru также являются импликантами функции f(x), а поэтому функция g(x) не может быть простой импликантой. Например, для логической функции

Понятие о минимизации логических функций - student2.ru

функция Понятие о минимизации логических функций - student2.ru является простой импликантой, так как после исключения из Понятие о минимизации логических функций - student2.ru переменной Понятие о минимизации логических функций - student2.ru получим импликанту Понятие о минимизации логических функций - student2.ru .

Простой имплицентой функции f(x) называется элементарная дизъюнкция d(x), являющаяся имплицентой этой функции и обладающая тем свойством, что никакая ее собственная часть (т.е. дизъюнкция, получаемая из элементарной дизъюнкции путем исключения одной или нескольких переменных или их отрицаний), уже не является имплицентой этой функции. Например, для СКНФ логической функции

Понятие о минимизации логических функций - student2.ru ,

функция Понятие о минимизации логических функций - student2.ru является простой имплицентой, а функция Понятие о минимизации логических функций - student2.ru не является простой имплицентой, так как после исключения из Понятие о минимизации логических функций - student2.ru переменной Понятие о минимизации логических функций - student2.ru получим более короткую имплиценту ( Понятие о минимизации логических функций - student2.ru .

Предположим, что на некотором наборе Понятие о минимизации логических функций - student2.ru значений переменных логическая функция Понятие о минимизации логических функций - student2.ru принимает значение , равное единице (нулю). Условимся, что эта 1 (0) накрывается импликантой g(x) (имплицентой d(x) функции Понятие о минимизации логических функций - student2.ru , если на наборе Понятие о минимизации логических функций - student2.ru импликанта g(x) (имплицента Понятие о минимизации логических функций - student2.ru ) также равна единице (нулю).

Система импликант (имплицент) функции Понятие о минимизации логических функций - student2.ru называется полной, если все единичные (нулевые) значения функции Понятие о минимизации логических функций - student2.ru накрываются хотя бы одной импликантой(имплицентой) системы.

Пусть система импликант Понятие о минимизации логических функций - student2.ru , Понятие о минимизации логических функций - student2.ru ,. . . , Понятие о минимизации логических функций - student2.ru является полной системой импликант функции Понятие о минимизации логических функций - student2.ru . Тогда

Понятие о минимизации логических функций - student2.ru Понятие о минимизации логических функций - student2.ru Понятие о минимизации логических функций - student2.ru . . . Понятие о минимизации логических функций - student2.ru = Понятие о минимизации логических функций - student2.ru .

Отсюда следует, что дизъюнкция полной системы простых импликант функции Понятие о минимизации логических функций - student2.ru образует функцию, эквивалентную Понятие о минимизации логических функций - student2.ru . Для полной системы простых имплицент справедливо равенство

Понятие о минимизации логических функций - student2.ru Понятие о минимизации логических функций - student2.ru Понятие о минимизации логических функций - student2.ru . . . Понятие о минимизации логических функций - student2.ru = Понятие о минимизации логических функций - student2.ru ,

т.е. конъюнкция полной системы простых имплицент образует функцию, эквивалентную функции Понятие о минимизации логических функций - student2.ru .

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

Понятие о минимизации логических функций - student2.ru

простыми импликантами являются

Понятие о минимизации логических функций - student2.ru ;

Понятие о минимизации логических функций - student2.ru ;

Понятие о минимизации логических функций - student2.ru ,

а сокращенная ДНФ этой функции имеет вид

Понятие о минимизации логических функций - student2.ru = Понятие о минимизации логических функций - student2.ru Понятие о минимизации логических функций - student2.ru Понятие о минимизации логических функций - student2.ru .

Для этой же функции простыми имлицентами являются

Понятие о минимизации логических функций - student2.ru ;

Понятие о минимизации логических функций - student2.ru ;

Понятие о минимизации логических функций - student2.ru ,

а сокращенная КНФ этой функции имеет вид

Понятие о минимизации логических функций - student2.ru Понятие о минимизации логических функций - student2.ru Понятие о минимизации логических функций - student2.ru Понятие о минимизации логических функций - student2.ru .

Представление любой логической функции в виде сокращенной ДНФ (КНФ) является единственным.

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

Дизъюнкция (конъюнкция) простых импликант (имплицент), составляющих приведенную систему импликант (имплицент) функции, называется ее тупиковой дизъюнктивной (конъюнктивной) нормальной формой - ТДНФ (ТКНФ). Например, для логической функции

Понятие о минимизации логических функций - student2.ru = Понятие о минимизации логических функций - student2.ru Понятие о минимизации логических функций - student2.ru Понятие о минимизации логических функций - student2.ru

простыми импликантами, составляющими приведенную систему, являются

Понятие о минимизации логических функций - student2.ru ;

Понятие о минимизации логических функций - student2.ru ,

а ТДНФ этой функции имеет вид

Понятие о минимизации логических функций - student2.ru = Понятие о минимизации логических функций - student2.ru Понятие о минимизации логических функций - student2.ru .

Приведенная система имплицент этой функции включает:

Понятие о минимизации логических функций - student2.ru ;

Понятие о минимизации логических функций - student2.ru ,

а ТКНФ этой функции имеет вид

Понятие о минимизации логических функций - student2.ru Понятие о минимизации логических функций - student2.ru Понятие о минимизации логических функций - student2.ru .

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

Наши рекомендации