РЕШЕНИЕ СИСТЕМЫ ДИЗЪЮНКТИВНЫХ УРАВНЕНИЙ МЕТОДОМ ПЕРЕМНОЖЕНИЯ ДНФ
Рассматривается система логических уравнений, представленных в дизъюнктивной нормальной форме (ДНФ), и предлагаются алгоритмы поиска всех ее корней, базирующиеся на операции перемножения ДНФ. Алгоритмы реализованы биполярными программами. Один полюс активизируется при большом числе неизвестных (n &a...
Saved in:
| Format: | Article |
|---|---|
| Language: | Russian |
| Published: |
National Academy of Sciences of Belarus, the United Institute of Informatics Problems
2018-11-01
|
| Series: | Informatika |
| Online Access: | https://inf.grid.by/jour/article/view/580 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Рассматривается система логических уравнений, представленных в дизъюнктивной нормальной форме (ДНФ), и предлагаются алгоритмы поиска всех ее корней, базирующиеся на операции перемножения ДНФ. Алгоритмы реализованы биполярными программами. Один полюс активизируется при большом числе неизвестных (n > 32), когда приходится использовать «дорогостоящие» операции над длинными векторами (превышающими длину машинного слова). Другой полюс действует при малом числе неизвестных (n £ 32), когда можно использовать векторное представление булевых функций и более быстрые операции над короткими векторами, что приводит к значительному ускорению процесса решения. Приводятся результаты экспериментальных испытаний алгоритмов на потоках псевдослучайных систем логических уравнений и на примерах конкретных систем из практики логического проектирования. |
|---|---|
| ISSN: | 1816-0301 |