МЕТОД МИНИМИЗАЦИИ СИСТЕМЫ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ БУЛЕВЫХ ФУНКЦИЙ
Abstract
Рассматривается задача минимизации системы дизъюнктивных нормальных форм (ДНФ) произвольного вида, заданной в матричной форме. Критерием минимизации является общее число различных элементарных конъюнкций в получаемой системе ДНФ. Предлагается оригинальный способ сведения данной задачи к задаче о кратчайшем покрытии, основанный на простой операции пересечения множеств. Приводятся результаты испытаний компьютерной программы.
About the Authors
Ю. Поттосин
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
Н. Торопов
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
Е. Шестаков
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
References
1. Глушков, В.М. Синтез цифровых автоматов / В.М. Глушков. – М.: ГИФМЛ, 1962. – 476 с.
2. Закревский, А.Д. Логический синтез каскадных схем / А.Д. Закревский. – М.: Наука, 1981. – 416 с.
3. Шестаков, Е.А. Декомпозиция системы полностью определенных булевых функций по покрытию аргументов / Е.А. Шестаков // Автоматика и вычислительная техника. – 1994. – № 1. – С. 12–20.
4. Brzozowski, J.A. Decomposition of Boolean functions specified by cubes. Research Report CS-97-01 / J.A. Brzozowski, J.J. Lou. – Waterloo, ON, Canada: Department of Computer Science, University of Waterloo, 1997. – 36 p.
5. Поттосин, Ю.В. Декомпозиция систем полностью определенных булевых функций по их заданию в виде компактных таблиц / Ю.В. Поттосин, Е.А. Шестаков // Информатика. – 2004. – № 2. – С. 35–44.
6. Поттосин, Ю.В. Поиск существенных аргументов системы полностью определенных булевых функций / Ю.В. Поттосин, Е.А. Шестаков // Методы логического проектирования.– Минск: ОИПИ НАН Беларуси, 2003. – Вып. 2. – С. 69–78.
7. Поттосин, Ю.В. Ортогонализация системы полностью определенных булевых функций / Ю.В. Поттосин, Е.А. Шестаков // Логическое проектирование. – Минск: Ин-т техн. кибернетики НАН Беларуси, 2000. – Вып. 5.– С. 107–115.
8. Фридман, А. Теория и проектирование переключательных схем / А. Фридман, П. Менон. – М.: Мир, 1978. – 580 с.
9. Миллер, Р. Теория переключательных схем. Т. I / Р. Миллер. – М.: Наука, 1970. – 416 с.
10. Yang, S. Logic Synthesis and Optimization Benchmarks. User Guide: Version 3.0. Technical Report / S. Yang. – Microelectronics of North Carolina, 1991. – 43 p.
11. Романов, В.И. Программные средства для решения логико-комбинаторных задач / В.И. Романов // Информатика. – 2005. – № 4 (8). – С. 114–123.
12. Торопов, Н. Р. Минимизация систем булевых функций в классе ДНФ / Н. Р. Торопов // Логическое проектирование. – Минск: Ин-т техн. кибернетики НАН Беларуси, 1999. – Вып. 4. – С. 4–19.
13. Закревский, А.Д. Основы логического проектирования: в 3 кн. Кн. 2. Оптимизация в булевом пространстве / А.Д. Закревский, Ю.В. Поттосин, Л.Д. Черемисинова. – Минск: ОИПИ НАН Беларуси, 2004. – 240 с.
Review
For citations:
, , . Informatics. 2008;(2(18)):102-110. (In Russ.)
Views: 489
Email this article 