МЕТОД МИНИМИЗАЦИИ СИСТЕМЫ  НЕ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ БУЛЕВЫХ ФУНКЦИЙ

Поттосин Ю. В.; Торопов Н. Р.; Шестаков Е. А.

МЕТОД МИНИМИЗАЦИИ СИСТЕМЫ НЕ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ БУЛЕВЫХ ФУНКЦИЙ

Поттосин Ю. В., Торопов Н. Р., Шестаков Е. А.

2009

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

Поттосин Ю. В., Торопов Н. Р., Шестаков Е. А. МЕТОД МИНИМИЗАЦИИ СИСТЕМЫ НЕ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ БУЛЕВЫХ ФУНКЦИЙ. Информатика. 2009;(3(23)):16-26.

Цитирование

Список литературы

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.

Источник

Информация

Автор

Поттосин Ю. В. Объединенный институт проблем информатики НАН Беларуси
Торопов Н. Р. Объединенный институт проблем информатики НАН Беларуси
Шестаков Е. А. Объединенный институт проблем информатики НАН Беларуси

Страницы

16-26

Год издания

2009

Коллекции

Информатика