informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-566Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNМЕТОД МИНИМИЗАЦИИ СИСТЕМЫ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ БУЛЕВЫХ ФУНКЦИЙПоттосинЮ. В.ТороповН. Р.ШестаковЕ. А.Объединенный институт проблем информатики НАН БеларусиBelarus20083110201802(18)102110Copyright © Поттосин Ю.В., Торопов Н.Р., Шестаков Е.А., 20182018Поттосин Ю.В., Торопов Н.Р., Шестаков Е.А.Поттосин Ю.В., Торопов Н.Р., Шестаков Е.А.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/566

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

ReferencesГлушков, В.М. Синтез цифровых автоматов / В.М. Глушков. – М.: ГИФМЛ, 1962. – 476 с.Глушков, В.М. Синтез цифровых автоматов / В.М. Глушков. – М.: ГИФМЛ, 1962. – 476 с.Закревский, А.Д. Логический синтез каскадных схем / А.Д. Закревский. – М.: Наука, 1981. – 416 с.Закревский, А.Д. Логический синтез каскадных схем / А.Д. Закревский. – М.: Наука, 1981. – 416 с.Шестаков, Е.А. Декомпозиция системы полностью определенных булевых функций по покрытию аргументов / Е.А. Шестаков // Автоматика и вычислительная техника. – 1994. – № 1. – С. 12–20.Шестаков, Е.А. Декомпозиция системы полностью определенных булевых функций по покрытию аргументов / Е.А. Шестаков // Автоматика и вычислительная техника. – 1994. – № 1. – С. 12–20.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.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.Поттосин, Ю.В. Декомпозиция систем полностью определенных булевых функций по их заданию в виде компактных таблиц / Ю.В. Поттосин, Е.А. Шестаков // Информатика. – 2004. – № 2. – С. 35–44.Поттосин, Ю.В. Декомпозиция систем полностью определенных булевых функций по их заданию в виде компактных таблиц / Ю.В. Поттосин, Е.А. Шестаков // Информатика. – 2004. – № 2. – С. 35–44.Поттосин, Ю.В. Поиск существенных аргументов системы полностью определенных булевых функций / Ю.В. Поттосин, Е.А. Шестаков // Методы логического проектирования.– Минск: ОИПИ НАН Беларуси, 2003. – Вып. 2. – С. 69–78.Поттосин, Ю.В. Поиск существенных аргументов системы полностью определенных булевых функций / Ю.В. Поттосин, Е.А. Шестаков // Методы логического проектирования.– Минск: ОИПИ НАН Беларуси, 2003. – Вып. 2. – С. 69–78.Поттосин, Ю.В. Ортогонализация системы полностью определенных булевых функций / Ю.В. Поттосин, Е.А. Шестаков // Логическое проектирование. – Минск: Ин-т техн. кибернетики НАН Беларуси, 2000. – Вып. 5.– С. 107–115.Поттосин, Ю.В. Ортогонализация системы полностью определенных булевых функций / Ю.В. Поттосин, Е.А. Шестаков // Логическое проектирование. – Минск: Ин-т техн. кибернетики НАН Беларуси, 2000. – Вып. 5.– С. 107–115.Фридман, А. Теория и проектирование переключательных схем / А. Фридман, П. Менон. – М.: Мир, 1978. – 580 с.Фридман, А. Теория и проектирование переключательных схем / А. Фридман, П. Менон. – М.: Мир, 1978. – 580 с.Миллер, Р. Теория переключательных схем. Т. I / Р. Миллер. – М.: Наука, 1970. – 416 с.Миллер, Р. Теория переключательных схем. Т. I / Р. Миллер. – М.: Наука, 1970. – 416 с.Yang, S. Logic Synthesis and Optimization Benchmarks. User Guide: Version 3.0. Technical Report / S. Yang. – Microelectronics of North Carolina, 1991. – 43 p.Yang, S. Logic Synthesis and Optimization Benchmarks. User Guide: Version 3.0. Technical Report / S. Yang. – Microelectronics of North Carolina, 1991. – 43 p.Романов, В.И. Программные средства для решения логико-комбинаторных задач / В.И. Романов // Информатика. – 2005. – № 4 (8). – С. 114–123.Романов, В.И. Программные средства для решения логико-комбинаторных задач / В.И. Романов // Информатика. – 2005. – № 4 (8). – С. 114–123.Торопов, Н. Р. Минимизация систем булевых функций в классе ДНФ / Н. Р. Торопов // Логическое проектирование. – Минск: Ин-т техн. кибернетики НАН Беларуси, 1999. – Вып. 4. – С. 4–19.Торопов, Н. Р. Минимизация систем булевых функций в классе ДНФ / Н. Р. Торопов // Логическое проектирование. – Минск: Ин-т техн. кибернетики НАН Беларуси, 1999. – Вып. 4. – С. 4–19.Закревский, А.Д. Основы логического проектирования: в 3 кн. Кн. 2. Оптимизация в булевом пространстве / А.Д. Закревский, Ю.В. Поттосин, Л.Д. Черемисинова. – Минск: ОИПИ НАН Беларуси, 2004. – 240 с.Закревский, А.Д. Основы логического проектирования: в 3 кн. Кн. 2. Оптимизация в булевом пространстве / А.Д. Закревский, Ю.В. Поттосин, Л.Д. Черемисинова. – Минск: ОИПИ НАН Беларуси, 2004. – 240 с.

The authors declare that there are no conflicts of interest present.