Preview

Информатика

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

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

Полный текст:

Аннотация

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

Об авторе

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


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

1. Закревский, А.Д. Логические уравнения. Изд. 2-е стереотипное / А.Д. Закревский. – М.: Едиториал УРСС, 2003. – 96 с.

2. Закревский, А.Д. Алгоритмы синтеза дискретных автоматов / А.Д. Закревский. – М.: Наука, 1971. – 512 с.

3. Закревский, А.Д. Решение логических уравнений / А.Д. Закревский // Логическое проектирование. – Минск: Ин-т техн. кибернетики НАН Беларуси, 2001. – С. 51–68.

4. Posthoff, Ch. Binare Gleichungen: Algorithmen und Programme / Ch. Posthoff, B. Steinbach. – Karl-Marx-St., 1978.

5. Baumann, M. Criptoanaly of the Hagelin M-209 Machine / M. Baumann, R. Rohde, R. Barthel // 3rd International Workshop on Boolean Problems, Sept. 17–18, 1998. – Freiberg (Sachsen). Germany, 1998. – P. 109–116.

6. Нильсон, Н. Искусственный интеллект. Методы поиска решений / Н. Нильсон. – М.: Наука, 1971. – 512 с.

7. Zakrevskij, A.D. Parallel operations over neighbors in Boolean space / A.D. Zakrevskij // Proc. of the Sixth International Conference CAD DD-07. – Minsk, 2007. – Vol. 2. – P. 6–13.

8. Торопов, Н.Р. Минимизация систем булевых функций в классе ДНФ / Н.Р. Торопов // Логическое проектирование: cб. науч. тр. – Минск: Ин-т техн. кибернетики НАН Беларуси, 1999. – Вып. 4. – С. 4–19.

9. Торопов, Н.Р. Раздельная минимизация булевых функций в системе с поляризацией их значений / Н.Р. Торопов // Методы логического проектирования. – Минск: ОИПИ НАН Беларуси, 2002. – С. 44–55.

10. Романов, В.И. Булевы векторы и матрицы в С++ / В.И. Романов, И.В. Василькова //

11. Логическое проектирование. – Минск: Ин-т техн. кибернетики НАН Беларуси, 1997. – С. 150–158.

12. Черемисинов, Д.И. Троичные векторы и матрицы / Д.И. Черемисинов, Л.Д. Черемисинова // Логическое проектирование. – Минск: Ин-т техн. кибернетики НАН Беларуси, 1998. – С. 146–155.

13. Романов, В.И. Программные средства для решения логико-комбинаторных задач / В.И. Романов // Информатика. – 2005. – № 4. – С. 114–123.


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


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

For citation:


. . Informatics. 2008;(3(19)):81-89. (In Russ.)

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


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


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