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

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

Эту функцию можно доопределить на неопределенных наборах единицами

или нулями

Это приводит к разным минимальным ДНФ. Однако более простая минимальная ДНФ получается, если произвести доопределение так, как это сделано на следующей диаграмме Вейча

Алгоритм поиска минимальной ДНФ частично определенной функции можно представить следующим образом

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

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

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

Дата добавления: 2015-07-02