2014-02-09
1684
Зададим двоичную функцию на n-мерном двоичном кубе. Как было отмечено ранее, при таком задании элементарным конъюнкциям ранга k соответствуют такие множества вершин, графы связности которых имеют вид (k-n)-мерных кубов. Поскольку дизъюнкции элементарных конъюнкций соответствует объединение множеств вершин таких подкубов, то каждой ДНФ функции f соответствует некоторое покрытие множества M f единичных вершин функции f (области истинности) подмножествами, имеющими в качестве графов связности подкубы. Простым импликантам функции f будут соответствовать подкубы максимальных размерностей, покрывающие вершины из M f.
Соответственно, первая задача (1-ый этап) решается перечислением всех максимальных подкубов, содержащихся в графе связности множества M f.
Вторая задача (2-ой этап) заключается в нахождении минимальных (по числу подкубов) покрытий множества M f максимальными подкубами.
Рассмотрим пример. Пусть двоичная функция f (x1, x2, x3, x4) имеет геометрическое задание, изображённое на рис. 5.2.1:
Граф связности такой функции имеет вид:
Выпишем сокращённую ДНФ, записывая простые импликанты в том же порядке, в каком они изображены в графе связности:
Легко видеть, что тупиковыми будут две ДНФ:
,
,
соответствующие покрытиям:
Минимальной будет только вторая тупиковая ДНФ.
