В результате, можно получить разные минимальные ДНФ.

Более простая минимальная ДНФ получается, если произвести доопределение так, как это сделано на диаграмме Карно-Вейча в таблице 16.

 

Таблица 14

Таблица 15

Таблица 16

Алгоритм поиска минимальной ДНФ частично определенной переключательной функции f можно представить следующим образом:

1) найти (любым известным способом) сокращенную ДНФ переключательной функции, получающейся в результате доопределения единицами исходной функции f на всех неопределенных наборах;

2) выбрать минимальную ДНФ переключательной функции по импликантной матрице, где в столбцах будут выписаны лишь те конституенты единицы функции f, которые соответствуют полностью определенным единичным наборам.

Аналогичный алгоритм (с доопределением нулевыми наборами) может быть предложен для поиска КНФ.

Доопределение таблицы истинности функции f может быть произведено по разному для КНФ и ДНФ.

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

Приведем далее несколько примеров. Если минимальных форм несколько, будем приводить одну из них.

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

МДНФ: x1x2 v /x1/x3 v /x3/x4; МКНФ: (x1 v /x3)(/x3 v x4)(x2 v /x4).

Таблица 17

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

ДНФ: x3 v x2x4; КНФ: (x2 v x3)(x3 v x4).

 

Таблица 18

Рассмотрим функцию, представленную таблицей 19. Результаты минимизации: ДНФ: x1/x4 v /x1x2x4; КНФ: (/x1 v /x4)(x1 v x2)(x1 v x4).

 

Таблица 19

Рассмотрим функцию, представленную таблицей 20. Результаты миними-зации будут следующими: ДНФ: x3 v x1x4 v x1/x2; КНФ: (x1 v /x3)(/x2 v /x3 v x4).

 

Таблица 20

Минимизация систем переключательных функций

 

На практике достаточно часто приходится реализовывать совокупности переключательных функций и производить их минимизацию.

Система дизъюнктивных нормальных форм переключательных функций называется минимальной, если:

- полное множество элементарных конъюнкций системы содержит минимальное количество букв;

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

Дизъюнктивная нормальная форма представления переключательной функции в минимальной системе в общем случае не совпадает с ее минимальной дизъюнктивной нормальной формой.

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

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

Задача минимизации систем переключательных функций хорошо исследована в следующем классе функционально полных систем: "дизъюнкция", "конъюнкция" и "отрицание".