procyberВестник кибернетикиProceedings in Cybernetics1999-7604Бюджетное учреждение высшего образования Ханты-Мансийского автономного округа – Югры «Сургутский государственный университет»10.35266/1999-7604-2023-2-87-91procyber-523Research ArticleФИЗИКО-МАТЕМАТИЧЕСКИЕ НАУКИPhysics and MathematicsМОДИФИЦИРОВАННЫЙ АЛГОРИТМ МИНИМИЗАЦИИ ДИЗЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМЫA MODIFIED ALGORITHM FOR MINIMIZING THE DISJUNCTIVE NORMAL FORMНазинА. Г.NazinA. G.

кандидат физико-математических наук, доцент

E-mail: nazin_ag@surgu.ru

Candidate of Sciences (Physics and Mathematics), Docent

E-mail: nazin_ag@surgu.ru

Сургутский государственный университет, СургутРоссияSurgut State University, SurgutRussian Federation2023070720232228791Copyright © Назин А.Г., 20232023Назин А.Г.Nazin A.G.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.vestcyber.ru/jour/article/view/523

В статье изложен алгоритм, позволяющий осуществить направленный перебор для поиска минимальной дизъюнктивной нормальной формы с использованием лексикографического порядка.

The article describes an algorithm for a directed search to find the minimum disjunctive normal form using the lexicographic order.

простая импликантаДНФМДНФалгоритмсокращенная ДНФprime implicantDNFMDNFalgorithmreduced DNFReferencesГэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи / пер. с англ. Е. В. Левнера, М. А. Фрумкина. М. : Мир, 1982. 416 с.Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи / пер. с англ. Е. В. Левнера, М. А. Фрумкина. М. : Мир, 1982. 416 с.Андреев А. Е. К проблеме минимизации дизъюнктивных нормальных форм // Доклады Академии наук СССР. 1984. Т. 274, № 2. С. 265–269.Андреев А. Е. К проблеме минимизации дизъюнктивных нормальных форм // Доклады Академии наук СССР. 1984. Т. 274, № 2. С. 265–269.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.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.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.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.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.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.Brayton R. K., Hachtel G. D., McMullen C. et al. Logic minimization algorithms for VLSI synthesis. Hingham, MA: Kluwer Academic Publishers; 1984. 194 p.Brayton R. K., Hachtel G. D., McMullen C. et al. Logic minimization algorithms for VLSI synthesis. Hingham, MA: Kluwer Academic Publishers; 1984. 194 p.Hachtel G. D., Somenzi F. Logic synthesis and verification algorithms. Boston, MA: Kluwer Academic Publishers; 1996. 564 p.Hachtel G. D., Somenzi F. Logic synthesis and verification algorithms. Boston, MA: Kluwer Academic Publishers; 1996. 564 p.Журавлев Ю. И. Алгоритмы построения минимальных дизъюнктивных нормальных форм для функций алгебры логики // Дискретная математика и математические вопросы кибернетики / под общ. ред. С. В. Яблонского, О. Б. Лупанова. Т. 1. М. : Наука, 1974. 312 с.Журавлев Ю. И. Алгоритмы построения минимальных дизъюнктивных нормальных форм для функций алгебры логики // Дискретная математика и математические вопросы кибернетики / под общ. ред. С. В. Яблонского, О. Б. Лупанова. Т. 1. М. : Наука, 1974. 312 с.Стрыгин В. З. Полиномиальный алгоритм минимизации случайных («почти всех») булевых функ-ций. М. : ЦАГИ, 1992. 8 с.Стрыгин В. З. Полиномиальный алгоритм минимизации случайных («почти всех») булевых функ-ций. М. : ЦАГИ, 1992. 8 с.Назин А. Г. Алгоритм получения всех минимальных дизъюнктивных нормальных форм из сокращенной дизъюнктивной нормальной формы с использованием лексикографического порядка // Исследовано в России. 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).Назин А. Г. Алгоритм получения всех минимальных дизъюнктивных нормальных форм из сокращенной дизъюнктивной нормальной формы с использованием лексикографического порядка // Исследовано в России. 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).Колдуэлл С. Х. Логический синтез релейных устройств / пер. с англ. Г. К. Москатова, А. Д. Таланцева ; под ред. М. А. Гаврилова. М. : Изд-во иностр. лит., 1962. 740 с.Колдуэлл С. Х. Логический синтез релейных устройств / пер. с англ. Г. К. Москатова, А. Д. Таланцева ; под ред. М. А. Гаврилова. М. : Изд-во иностр. лит., 1962. 740 с.

The authors declare that there are no conflicts of interest present.