A MODIFIED ALGORITHM FOR MINIMIZING THE DISJUNCTIVE NORMAL FORM
https://doi.org/10.35266/1999-7604-2023-2-87-91
Abstract
The article describes an algorithm for a directed search to find the minimum disjunctive normal form using the lexicographic order.
About the Author
A. G. Nazin
Surgut State University, Surgut
Russian Federation
Russian Federation
Candidate of Sciences (Physics and Mathematics), Docent
E-mail: nazin_ag@surgu.ru
References
1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи / пер. с англ. Е. В. Левнера, М. А. Фрумкина. М. : Мир, 1982. 416 с.
2. Андреев А. Е. К проблеме минимизации дизъюнктивных нормальных форм // Доклады Академии наук СССР. 1984. Т. 274, № 2. С. 265–269.
3. McGeer P., Sanghavi J., Brayton R. et al. ESPRESSOSIGNATURE: A new exact minimizer for logic functions. In: 30th ACM/IEEE Design Automation Conference, Dallas, TX, USA. 1993. p. 618‒624.
4. Hong S. J., Cain R. G., Ostapko D. L. МINI: A heueristic approach for logic minimization. IBM Journal Research and Development. 1974;18(5):443–458.
5. Hlavička J., Fišer P. BOOM – a Heuristic Boolean Minimizer. In: IEEE/ACM International Conference on Computer Aided Design ICCAD-2001, San Jose, California (USA), November 4–8, 2001. p. 439–442.
6. Brayton R. K., Hachtel G. D., McMullen C. et al. Logic minimization algorithms for VLSI synthesis. Hingham, MA: Kluwer Academic Publishers; 1984. 194 p.
7. Hachtel G. D., Somenzi F. Logic synthesis and verification algorithms. Boston, MA: Kluwer Academic Publishers; 1996. 564 p.
8. Журавлев Ю. И. Алгоритмы построения минимальных дизъюнктивных нормальных форм для функций алгебры логики // Дискретная математика и математические вопросы кибернетики / под общ. ред. С. В. Яблонского, О. Б. Лупанова. Т. 1. М. : Наука, 1974. 312 с.
9. Стрыгин В. З. Полиномиальный алгоритм минимизации случайных («почти всех») булевых функ-ций. М. : ЦАГИ, 1992. 8 с.
10. Назин А. Г. Алгоритм получения всех минимальных дизъюнктивных нормальных форм из сокращенной дизъюнктивной нормальной формы с использованием лексикографического порядка // Исследовано в России. 2002. С. 942–947. URL: https://cyberleninka.ru/article/n/algoritm-polucheniya-vseh-minimalnyh-dizyunk-tivnyh-normalnyh-form-iz-sokraschyonnoy-dizyunk-tivnoy-normalnoy-formy-s-ispolzovaniem (дата обращения: 01.03.2023).
11. Колдуэлл С. Х. Логический синтез релейных устройств / пер. с англ. Г. К. Москатова, А. Д. Таланцева ; под ред. М. А. Гаврилова. М. : Изд-во иностр. лит., 1962. 740 с.
Review
For citations:
Nazin A.G. A MODIFIED ALGORITHM FOR MINIMIZING THE DISJUNCTIVE NORMAL FORM. Proceedings in Cybernetics. 2023;22(2):87-91. (In Russ.) https://doi.org/10.35266/1999-7604-2023-2-87-91
Views:
150
Email this article 