Минимизация функций. 
Цифровые устройства и микропроцессоры

Задача минимизации

Пусть требуется построить логическую схему, которая реализует следующую таблицу истинности:

Для реализации схемы запишем СДНФ:

Каждый минтерм реализован своим конъюнктором. Инверсии выполнены на входах, чтобы не пользоваться дополнительными инверторами и не загромождать схему. Получаем результат, показанный на рис. 1.13.

Рис. 1.13. Схемная реализация таблицы истинности.

Сложность логической схемы принято оценивать общим числом входов всех ее элементов, которые условно называют ценой схемы. Инверторы не учитываются.

Найдем, чему равна цена нашей схемы:

Она складывается из числа входов конъюнкторов (элементы первого уровня) и числа входов дизъюнктора (элемент второго уровня).

Число входов элементов первого уровня равно числу символов в записи функции. Число входов элементов второго уровня равно числу термов в записи функции, т. е. цену схемной реализации можно подсчитать сразу по исходной логической формуле.

Используя законы алгебры логики, попытаемся упростить исходную функцию. Для этого вынесем за скобки:

Очевидно, что реализация такой формулы значительно проще, ее цена Ц₂ = 4 + 2 = 6.

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

Таким образом, получаем минимальную дизъюнктивную нормальную форму (МДНФ) и, соответственно, МКНФ.

Процесс отыскания минимальной формы называется минимизацией логической функции, или просто минимизацией.

Минимизировать функции можно тремя методами:

• 1) расчетным путем, используя законы алгебры логики;
• 2) графическим путем (метод карт Карно или диаграмм Вейча), используя специальные карты;
• 3) расчетно-графическим путем (метод Квайна и его модификации).

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