logo search
Diskretnaya_matematika_1_semestr

Тупиковые днф и решение задачи минимизации.

Покрытие множества Nf максимальными гранями(возможно не всеми) называется неприводимым если при удалении из него любой грани оно перестаёт быть покрытием.

ДНФ, которая соответствует неприводимому покрытию называется тупиковой.

Если решать задачу минимизации перебором всевозможных покрытий множества Nf максимальными гранями, то можно ограничиться только перебором неприводимых покрытий и соответственно тупиковых ДНФ, так как удаление любой грани из покрытия приводят к уменьшению, как числа конъюнкций, так и числа букв. Среди неприводимых покрытий (тупиковых ДНФ) всегда существует минимальное покрытие и минимальная ДНФ как для числа букв так и для числа элементов конъюнкции. Следовательно, задача минимизации сводится к перебору всевозможных тупиковых ДНФ.

Алгоритм построения всех тупиковых ДНФ

1.Находим все максимальные грани{σ1,σ2,…,σl}.

2.По множеству Nf и множеству максимальных граней строится таблица размера Lxp, где p-мощность множества Nf. Строки этой таблицы соответствуют максимальным граням, а столбцы-элементам множества. На пересечении строки и столбца ставится 1, если соответствующая грань покрывает вершину, и 0 в противном случае.

3.Для каждой вершины множества Hf (каждого столбца таблицы) находим множество, покрывающих эту вершину, граней σi1,σi2,…,σit и записываем их в виде элементарной ∪. Дi=σi1∪σi2∪…∪σit. По этим элементарным дизъюнкциям строится КНФ:D1,D2,…Dp.

4.КНФ преобразовывается в ДНФ и упрощаем по алгоритму сокращённой ДНФ. Множество элементарных & упрощённой ДНФ соответствует множеству всех тупиковых ДНФ исходной ф-ции. По элементарным & соответствующие тупиковые ДНФ восстанавливаются след образом:σi1, σi2,…,σik. Тогда соответствующая тупиковая ДНФ имеет вид:Kσi1∪Kσi2∪…∪Kσik.

5.Решаем задачу минимизации перебором всех тупиковых ДНФ.