Цель минимизации переключательных функций

При технической реализации переключательных функций, широко используемых в вычислительной технике, системах автоматического (автоматизированного) управления и контроля возникает задача нахождения наиболее экономичного представления соответствующих переключательных функций. По существу решается задача оптимизации, причем минимизируется стоимость реализации. Понятие стоимости устройства, реализующего переключательную функцию, — дискретного устройства — относительно. Для переключательных схем, реализуемых в виде релейно-контактных схем, для схем из корпусных транзисторов и резисторов, из микросхем логических элементов малой степени интеграции минимизация числа реле, контактов, транзисторов, числа микросхем и означает снижение стоимости. Это было особенно актуально на ранних этапах развития дискретной, цифровой техники. Для современных цифровых автоматов на больших и сверхбольших интегральных схемах (БИС и СБИС) стоимость определяется площадью схемы на кристалле кремния и непосредственно не связана с числом микротранзисторов и других элементов. Нередко схема с большим числом элементов, но обладающая высокой регулярностью, занимает небольшую площадь, кроме того, она выгодна с точки зрения проектирования, ведь стоимость проектирования, как и стоимость изготовления, входит в суммарную стоимость устройства.

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

Ограничимся в дальнейшем целью нахождения наиболее простого представления переключательной функции в смысле наименьшего числа входящих в нее символов (букв). Процесс получения такого представления будем называть минимизацией. Под различными символами (буквами) будем понимать вхождения одной и той же переменной в различные дизъюнктивные (конъюнктивные) члены функции. Так, функция z 1( abc ) = ab ∨ ā c ∨ bc ∨ bc содержит шесть букв, а функция z 2( abc ) = ab ∨ ā c — четыре буквы, хотя обе функции зависят от трех переменных а, b , с (закон обобщенного склеивания z 1= z 2).

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

При этом задача минимизации переключательной функции сводится к нахождению такой ее формы, которая содержит наименьшее число дизъюнкций, конъюнкций и инверсий.

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

Будем рассматривать в основном минимизацию переключательных функций в классе ДНФ, не требуя минимизации числа инверсий.

Цит. по: Дискретная математика и математическая логика: учебник /
Ю.А. Аляев, С.Ф. Тюрин. — М.: Финансы и статистика, 2006. — С. 76–92, 97–105, 118–120.