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

4)       Записывают минимальное выражение как функцию Пирса над логическими выражениями, которые описывают контура таблицы. Логическое выражение для контура представляет собой операцию Пирса от аргументов. Для поиска логического выражения для контура  выясняют, от каких аргументов он зависит. Если все нули контура приписаны к аргументу , то в логическое выражение этот аргумент входит. Если все единицы контура помечены инверсией аргумента, то в выражение вписывается . Если в контуре есть нули, помеченные   и нули, помеченные , то в описание контура этот аргумент не входит.

ВАЖНО! При минимизации в базисах Шеффера и Пирса действуют два дополнительных правила:

Если контур занимает половину таблицы, то над аналитическим описанием этого контура ставится дополнительное отрицание;

Если в таблице только один контур, то над ним также следует поставить дополнительное отрицание.

Естественно, если в таблице только один контур, и он занимает половину таблицы, то над ним ставятся два дополнительных отрицания.

Пример: минимизировать в базисе Пирса функции:

,    ,  ,  .

Очевидно Вы заметили, что правила заполнения и обводки одинаковы при минимизации в базисе Пирса и при получении минимальных конъюнктивных нормальных форм. Следовательно, МКНФ можно получить из этих же таблиц:, ,  ,  .

        Минимизация булевых функций большого числа аргументов.

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

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

В начале рассмотрим получение МДНФ.

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

                               кратчайших претендентов.

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

Число аргументов претендента будем называть длиной претендента.

Рассмотрим метод получения МДНФ методом подбора кратчайших произведений.

Пример. Задана не полностью определенная булева функция

,

Берем первый набор матрицы единиц 0100. Произведения, покрывающие этот набор, рассматриваются как претенденты на вхождение в минимальную форму: