Булевы функции. Основные формулы булевой алгебры. Аналитическая запись булевых функций в булевом базисе. Дешифраторы. Мультиплексоры, страница 14

,

Выписываем набор 0001 матрицы единиц и аналогично ищем кратчайшее произведение равное единице на этом наборе:

 - не подходит, поскольку дает значение 1 наборам 0101, 0110, 0111 матрицы нулей;

 -подходит, поскольку не равно 1 ни на одном наборе матрицы нулей и покрывает наборы 0001, 1001 матрицы единиц. Вписываем  в МДНФ и удаляем наборы 0001 и 1001 в матрице единиц: ,

, .

Выписываем набор 1110 и, поочередно рассматривая претенденты , находим кратчайшее произведение  равное 1 на наборах 1110 и 1100 и равное нулю на всех наборах матрицы нулей. Вычеркиваем наборы 1110 и 1100 из матрицы единиц. Поскольку матрица единиц пуста – минимизация закончена. МДНФ имеет вид: .

Замечание: если искать покрытие матрицы единиц функцией Шеффера с минимальным числом аргументов, то получим минимальную форму в базисе Шеффера. Естественно, что следует учитывать особенности этой функции:

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

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

Видно, что при работе алгоритма многократно проверяются уже отвергнутые претенденты, что сильно увеличивает время, затрачиваемое  на минимизацию. Рассмотрим модификацию алгоритма свободного от этого недостатка на примере получения МДНФ.

Рассматривается матрица нулей и формируется очередь допустимых претендентов, описываемых одним аргументом. Допустимым будет претендент, который равен нулю на всех наборах матрицы нулей. Если допустимый претендент покрывает хотя бы один набор матрицы единиц, он вписывается в формулу, а покрываемые наборы исключаются из матрицы единиц. Если – нет, то претендент в формулу не входит и рассматривается следующий  допустимый претендент из очереди. Если все наборы матрицы единиц удалены, работа алгоритма закончена, если же нет, рассматривается следующий допустимый претендент из очереди, а если очередь пуста, то формируется новая очередь допустимых претендентов, зависящих уже от двух аргументов и т.д.

Алгоритм получения МДНФ:

1) Задать длину претендента ;

2) Рассматривая матрицу нулей сформировать очередь всех допустимых претендентов длины ;

3) Если очередь пуста, принять  и перейти к пункту 2, иначе – к пункту 4;

4) Взять первого допустимого претендента из очереди и проверить покрывает ли он хотя бы один набор в матрице единиц. Если – нет, то допустимый претендент удалить из очереди и перейти к пункту 3, если – да, то перейти к пункту 5.

5) Включить допустимый претендент в формулу, представляющую собой сумму претендентов;

6) Исключить наборы, покрываемые претендентом из матрицы единиц;

7) Исключить претендент из очереди;

8) Если матрица единиц не пуста, то перейти к пункту 3, иначе – конец.

В рассматриваемом примере претенденты  недопустимы, поскольку обращают в единицу один или несколько наборов  матрицы нулей.

Очередь состоит только из одного допустимого претендента , который равен нулю на всех наборах матрицы нулей. Этот претендент покрывает  наборы 0000, 0001,1001 матрицы единиц, поэтому он входит в формулу

. Матрица единиц после удаления этих наборов примет вид:

,  .

Поскольку после удаления  очередь пуста, формируем очередь допустимых претендентов, зависящих от двух аргументов: . 

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

, .