Постановка и методы решения задачи минимизации функции алгебры логики (ФАЛ)

На основе ФАЛ осуществляется построение схем различных ДУ. Поэтому актуальной задачей является преобразование ФАЛ к виду, обеспечивающему наиболее простую по количеству используемых логических элементов, схемную реализацию. Решение этой задачи в полном объёме сопряжено со значительными трудностями, обусловленными необходимостью учёта индивидуальных особенностей используемой элементной базы. Однако существуют методы, позволяющие преобразовывать ФАЛ к виду, содержащему минимальное число термов.

Под минимизацией логической функции понимается выполнение преобразований с целью получения наиболее простого представления ФАЛ. В инженерной практике исполь­зуются следующие основные методы минимизации: последовательного перебора, последовательного упрощения аналитического выражения, карт Карно, Квайна, Квайна–Мак-Класки, Л.Т. Мавренкова и т. д.

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

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

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

Метод Квайна основан на последовательном применении к ДСНФ функции АЛ операций неполного склеивания и элементарного поглощения. Метод применим в основном для ФАЛ от небольшого количества аргументов.

Метод Квайна–Мак-Класки основан на использовании предложенного Мак-Класки более удобного подхода к практической реализации алгоритма Квайна. При применении данного метода функция также должна быть представлена одной из совершенных нормальных форм. Однако конституенты единицы (нуля) данной функции записываются не в натуральном виде, как в методе Квайна, а в виде условных чисел, называемых номерами соответствующих конституент. Такой подход существенно упрощает использование метода для функций с большим количеством аргументов и значительно уменьшает вероятность появления ошибки на этапе выполнения преобразований.

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