Минимизация частично определенных булевых функций

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

 

Алгоритм поиска МДНФ частично определенной функции:

 

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

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

 

По диаграмме Вейча:

 

ДНФ: ДНФ:

КНФ: КНФ:

 

ДНФ: КНФ: