Геометрическая интерпретация минимизации ДНФ.

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

Соответственно, первая задача (1-ый этап) решается перечислением всех максимальных подкубов, содержащихся в графе связности множества M_f.

Вторая задача (2-ой этап) заключается в нахождении минимальных (по числу подкубов) покрытий множества M_f максимальными подкубами.

Рассмотрим пример. Пусть двоичная функция f (x₁, x₂, x₃, x₄) имеет геометрическое задание, изображённое на рис. 5.2.1:

 

 

 

 

Граф связности такой функции имеет вид:

Выпишем сокращённую ДНФ, записывая простые импликанты в том же порядке, в каком они изображены в графе связности:

Легко видеть, что тупиковыми будут две ДНФ:

,

,

соответствующие покрытиям:

 

Минимальной будет только вторая тупиковая ДНФ.