КАДР
Глава 2. Минимизация днф
2.1. Введение
Известно,
что функция
булевой алгебры
(алгебры логики) может быть представлена
множеством формул, даже если для их
построения используются только
элементарные функции. Среди формул
особый интерес представляют дизъюнктивные
нормальные формы, построенные без
применения скобок на подмножестве
элементарных функций: {,
,
}.
Интерес к этим формулам объясняется, с
одной стороны, простотой их вида, а с
другой – возможностью для разработчика
аппаратуры задавать в виде ДНФ поведение
проектируемых устройств.
Функция
,
где
=
{0, 1}, называется функцией алгебры логики
или булевой функцией.
Для отдельной функции в общем случае можно построить несколько ДНФ, отличающихся числом символов, образующих формулу. Под символом будем понимать переменную и ее знак инверсии. Переменную вместе со знаком инверсии часто называют буквой или литерой.
Введенная ранее совершенная дизъюнктивная нормальная форма, как правило, не является компактной формулой по сравнению с другими ДНФ, представляющими эту же функцию.
Например, мажоритарная функция, значения которой определяются значениями большинства ее аргументов, представляется следующей совершенной ДНФ:
.
В то же время она может быть представлена в виде ДНФ:
.
Вторая формула содержит 6 символов переменных, а первая – 12.
При решении различных задач проектирования дискретных систем важно получать для булевых функций по возможности более компактные их представления в виде ДНФ. Теория ДНФ позволяет это делать.
КАДР
Для выяснения главной проблемы теории ДНФ введем ряд определений.
Определение.
Элементарной конъюнкцией называется
логическое произведение K
=
r
переменных, в котором все
различны. Число r
называется рангом конъюнкции. При r
= 0 конъюнкция полагается равной единице.
Определение.
Дизъюнктивной нормальной формой
называется дизъюнкция D
=
…
элементарных конъюнкций
,
в которой все
различны, j
= 1,…, n.
Число l
называется длиной ДНФ. Для l
= 0 ДНФ называется пустой и полагается
равной 0.
Определение.
Минимальной ДНФ функции f(
,…,
)
называется ДНФ, реализующая f
и содержащая наименьшее число символов
переменных по сравнению со всеми другими
ДНФ, реализующими эту функцию.
Определение. Кратчайшей ДНФ функции f( ,…, ) называется ДНФ, реализующая f и содержащая наименьшее число элементарных конъюнкций по сравнению со всеми другими ДНФ, реализующими эту функцию.
Главной проблемой теории ДНФ является проблема построения минимальных и кратчайших ДНФ для булевых функций.
Существует тривиальный алгоритм построения минимальной (кратчайшей) ДНФ для произвольной булевой функции.
Все
ДНФ, составленные из символов переменных
,…,
,
,…,
,
упорядочиваются по числу символов
переменных (числу конъюнкций), и для
каждой ДНФ проверяется соотношение D
= f(
,…,
).
Первая по порядку ДНФ, для которой это соотношение выполняется, есть минимальная (кратчайшая) ДНФ для функции f( ,…, ).
Этот алгоритм не применим на практике, так как уже для небольших значений n требует перебора огромного числа ДНФ.
Теорема
2.1. Число
различных ДНФ функций, зависящих от n
переменных, равно
.
Доказательство.
Число различных элементарных конъюнкций,
составленных из n
переменных, равно
.
Действительно, каждая из n
переменных либо не входит в конъюнкцию,
либо входит в нее с отрицанием, либо
входит в нее без отрицания. Это значит,
что всевозможных конъюнкций
.
В конкретную ДНФ каждая из конъюнкций
либо входит, либо нет. Это значит, что
число различных ДНФ функций, зависящих
от n
переменных, равно числу подмножеств
множества из
элементов:
.
Ч.Т.Д.
Из
теоремы 2.1 следует, что число различных
ДНФ от n
переменных существенно больше числа
(
)
функций от n
переменных.
КАДР