Preview

Информатика

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

РЕШЕНИЕ СИСТЕМЫ ДИЗЪЮНКТИВНЫХ УРАВНЕНИЙ МЕТОДОМ ПЕРЕМНОЖЕНИЯ ДНФ

Аннотация

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

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


Торопов Н.Р. РЕШЕНИЕ СИСТЕМЫ ДИЗЪЮНКТИВНЫХ УРАВНЕНИЙ МЕТОДОМ ПЕРЕМНОЖЕНИЯ ДНФ. Информатика. 2008;(3(19)):81-89.

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


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


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