Preview

Информатика

Расширенный поиск

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

Аннотация

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

Об авторах

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


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


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


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

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.


Рецензия

Для цитирования:


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

Просмотров: 752


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)