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

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

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

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

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

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

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

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

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

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

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

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

M₁[g(x)]Í M₁[f(x)].

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

M₀[d(x)]Í M₀[f(x)].

Например, логическая функция g(x)= является импликантой логической функции

,

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

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

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

Пусть есть импликанта функции f(x), т.е.

M₁[g(x)]Í M₁[f(x)],

где

M₁[g(x)]= M₁[g1(x)] .

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

M₁[g1(x)]Í M₁[f(x)];

M₁[g2(x)]Í M₁[f(x)].

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

функция является простой импликантой, так как после исключения из переменной получим импликанту .

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

,

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

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

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

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

. . . = .

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

. . . = ,

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

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

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

;

;

,

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

= .

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

;

;

,

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

.

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

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

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

=

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

;

,

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

= .

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

;

,

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

.

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