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

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

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

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

Рис.5.1

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

Рис.5.2

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

.

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

, ,

соответствующие покрытиям (рис.5.3).

Рис.5.3

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

Л е к ц и я 6