Минимизация недоопределённой ФАЛ

ФАЛ называется недоопределённой (частично определённой), если часть её значений y_i не задана (см. п. 1.5). При минимизации такой ФАЛ необязательным значениям, которые обычно обозначают *, можно произвольно присваивать единичные или нулевые значения из условия получения на карте Вейча - Карно минимального числа максимально больших областей.

Рассмотрим пример минимизации ФАЛ, заданной таблицей истинности:

Составим карту Вейча – Карно.

Как видно из карты, ни единичные, ни нулевые значения ФАЛ невозможно объединить друг с другом. Поэтому ДНФ имеет вид

,                                 (2.5)

а КНФ

.     (2.6)

Предположим, что для доопределения ФАЛ принято решение присвоить всем необязательным значениям функции единичные значения. В результате получим следующий вид карты, на которой выделены области единичных значений, и соответствующую МДНФ.

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

Поскольку выделить область из восьми клеток не удалось, выбрано решение о выделении двух областей из четырёх клеток каждая. Полученное выражение МДНФ проще исходной ДНФ и требует для своей реализации два инвертора, два элемента 2И и один элемент 2ИЛИ.

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

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

Для дальнейших преобразований воспользуемся теоремой Де-Моргана:

.

В результате получилось выражение существенно проще, чем исходная КНФ (2.6), для реализации которого потребуется два инвертора, два элемента 2ИЛИ и один элемент 2И. Следует также отметить, что в варианте МКНФ не нужна переменная Х2.

Окончательный выбор варианта технической реализации ФАЛ будет зависеть от типа заданных (или имеющихся в наличии) ЛЭ.