6.2.1 Аналитическая минимизация фал

Метод применяется при числе переменных n <= 3 и основан на использовании операций склеивания, поглощения и развертывания.

В общем случае минимизация ФАЛ, заданной в СДНФ, требует выполнения процедур следующих трех этапов:

1 этап - переход от СДНФ к сокращенной ДНФ (СокрДНФ). СокрДНФ - это форма ФАЛ, членами которой являются изолированные (несклеивающиеся) элементарные произведения. Этот этап основан на выполнении всех возможных склеиваний друг с другом сначала конституент единицы, а затем произведений меньшего ранга (импликант). Отметим, что существуют ФАЛ, у которых СДНФ совпадает с СокрДНФ.

2 этап - переход от СокрДНФ к тупиковой ДНФ (ТДНФ). ТДНФ - это форма ФАЛ, членами которой являются импликанты, среди которых нет ни одной лишней. Лишней импликантой называется член ФАЛ, удаление которого из выражения не изменяет ФАЛ. Отметим, что возможны случаи, когда в СокрДНФ нет лишних импликант. Иногда из одной СокрДНФ можно получить несколько различных ТДНФ. Термин “тупиковая” говорит о том, что дальнейшая минимизация в рамках нормальных форм уже невозможна.

3 этап - переход от ТДНФ к минимальной форме. Этот этап основывается на использовании групповых инверсий и скобочных форм, не является система-тическим и во многом определяется опытом разработчика.

Определения: Булева функция называется импликантой булевой функции , если на любом наборе значений переменных , на котором значение функции ‘Z’ равно 1, значение функции ‘Y’ также равно 1.

Простой импликантой функции ‘y’ называется всякое элементарное произведение , являющееся импликантой функции ‘Y’ и такое, что никакая его собственная часть (то есть произведение, полученное из произведения ‘Z’ выбрасыванием одного или нескольких сомножителей ) уже не является импликантой функции ‘y’.