Методы минимизации

К настоящему времени широкое применение получили:

1. Расчетный метод (метод непосредственных преобразований).

2. Расчетно-табличный метод (метод Квайна-МакКласки).

3. Метод Петрика (развитие метода Квайна-МакКласки).

4. Табличный метод (карты Карно).

5. Геометрический метод.

6. Метод факторизации.

7. Метод функциональной декомпозиции и др.

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

Второй и третий методы используются при n ≤16 в профессиональных разработках и ориентированы на использование САПР с применением ЭВМ. Здесь они рассматриваться не будут. Четвертый метод является самым распространенным инженерным методом минимизации ФАЛ для n ≤6 и будет подробно рассмотрен.

Шестой метод не имеет каких-либо существенных достижений при решении общих задач, более простых, чем метод перебора всех формул ФАЛ даже для n = 3. Практически он используется для уменьшения сложности минимальных ДНФ и КНФ, полученных с использованием первого или четвертого методов. Он основан на использовании скобочных форм и форм с групповыми инверсиями.

Седьмой метод основан на представлении ФАЛ, зависящей от n переменных, в виде суперпозиций функций, зависящих от меньшего числа переменных, для которых можно применить выше перечисленные методы и здесь не рассматривается.

Исходной формой для большинства методов являются либо таблица истинности, либо одна из совершенных форм СДНФ или СКНФ. Если ФАЛ задана в другом виде, то предполагается, что она сначала переводится в СДНФ или СКНФ с использованием основных законов булевой алгебры. Далее будут рассмотрены методы минимизации ФАЛ, представленной в СДНФ.