МЕТОД МИНИМИЗАЦИИ СИСТЕМЫ НЕ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ БУЛЕВЫХ ФУНКЦИЙ
Abstract
Рассматривается задача минимизации системы не полностью определенных булевых функций в классе дизъюнктивных нормальных форм (ДНФ) при задании исходной системы функций в интервальной форме. Критерием минимизации является общее число различных элементарных конъюнкций в получаемой системе ДНФ. Предлагается метод решения данной задачи, который представляет собой обобщение предложенного авторами ранее метода минимизации системы полностью определенных булевых функций. В основе метода лежит оригинальный способ сведения данной задачи к задаче о кратчайшем покрытии, использующий простую операцию пересечения множеств. Приводятся результаты испытаний компьютерной программы, реализующей предлагаемый метод.
About the Authors
Ю. Поттосин
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
Н. Торопов
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
Е. Шестаков
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
References
1. Поттосин, Ю.В. Метод минимизации системы полностью определенных булевых функций / Ю.В. Поттосин, Н.Р. Торопов, Е.А. Шестаков // Информатика. – 2008. – № 2 (18). – С. 102–110.
2. Торопов, Н.Р. Минимизация систем булевых функций в классе ДНФ / Н. Р. Торопов // Логическое проектирование. – Минск : Ин-т техн. кибернетики НАН Беларуси, 1999. – Вып. 4. – С. 4–19.
3. Шестаков, Е.А. Декомпозиция системы полностью определенных булевых функций по покрытию аргументов / Е.А. Шестаков // Автоматика и вычислительная техника. – 1994. – № 1. – С. 12–20.
4. Фридман, А. Теория и проектирование переключательных схем / А. Фридман, П. Менон. – М. : Мир, 1978. – 580 с.
5. Закревский, А.Д. Логический синтез каскадных схем / А.Д. Закревский. – М. : Наука, 1981. – 416 с.
6. Закревский, А.Д. Логические основы проектирования дискретных устройств / А.Д. Закревский, Ю.В. Поттосин, Л.Д. Черемисинова. – М. : Физматлит, 2007. – 592 с.
7. Yang, S. Logic Synthesis and Optimization Benchmarks. User Guide: Version 3.0 / S. Yang. – Technical Report, Microelectronics of North Carolina. – USA, 1991. – 43 p.
Review
For citations:
, , . Informatics. 2009;(3(23)):16-26. (In Russ.)
Views: 907
Email this article 