informИнформатикаInformatics1816-03012617-6963UIIP NASB10.37661/1816-0301-2025-22-1-40-65inform-1321Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNДизъюнктивные и конъюнктивные разложения не полностью определенных булевых функций в бинарной диаграмме решенийDisjunctive and conjunctive decompositions of incompletely defined Boolean functions in a Binary Decision DiagramБибилоП. Н.BibiloP. N.

Бибило Петр Николаевич - доктор технических наук, профессор.

Ул. Сурганова, 6, Минск, 220012

Petr N. Bibilo - D. Sc. (Eng.), Prof.

St. Surganova, 6, Minsk, 220012

bibilo@newman.bas-net.byОбъединенный институт проблем информатики Национальной академии наук БеларусиThe United Institute of Informatics Problems of the National Academy of Sciences of Belarus2025310320252214065Copyright © Бибило П.Н., 20252025Бибило П.Н.Bibilo P.N.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/1321Цели

Цели. Рассматриваются задачи минимизации числа функций – кофакторов (подфункций) разложения Шеннона, находящихся на одном уровне бинарной диаграммы решений (Binary Decision Diagram, BDD), которая представляет систему не полностью определенных (частичных) булевых функций. Для сокращения числа функций предлагается находить подмножество таких функций, которые могут быть выражены в виде алгебраических разложений – дизъюнкций либо конъюнкций других доопределенных частичных функций. При этом ориентированный граф вхождений функций в разложения не должен содержать контуров.

Методы

Методы. Нахождение дизъюнктивных и конъюнктивных разложений требует поиска соответствующих доопределений частичных функций. Задача определения наибольшего числа раздельных алгебраических разложений сводится к нахождению взвешенного строчного покрытия булевой матрицы вхождений функций системы в отдельные разложения. Задача нахождения согласованных доопределений частичных функций для различного вида совместных разложений сводится к составлению и решению логических уравнений.

Результаты

Результаты. Показано, что составляемые логические уравнения легко преобразуются к конъюнктивной нормальной форме (КНФ), а нахождение корней таких уравнений сведено к задаче выполнимости булевой формулы, представленной в виде КНФ, для решения которой известны эффективные методы и программы.

Заключение

Заключение. Предложенные алгоритмы могут быть обобщены для других видов алгебраических разложений, когда кроме логических операций дизъюнкции и конъюнкции могут использоваться отрицания данных операций. Применение предложенных алгоритмов и уже известных алгоритмов минимизации многоуровневых BDD-представлений систем частичных функций позволяет получать лучшие результаты технологически независимой логической оптимизации – начального этапа синтеза логических схем.

Objectives

Objectives. The problems of minimizing the number of cofactors (subfunctions) of the Shannon expansions located at the same level of the BDD, representing a system of incompletely defined (partial) Boolean functions, are considered. To reduce the number of functions, it is proposed to find a subset of such functions that can be expressed as algebraic decompositions of disjunctions or conjunctions of other predefined partial functions, while the directed graph of function occurrences in decompositions should not contain contours.

Methods

Methods. Finding disjunctive and conjunctive decompositions requires searching for appropriate additional definitions of partial functions. Finding the largest number of separate algebraic decompositions reduces to the problem of finding a weighted row cover of a Boolean matrix of occurrences of system functions in separate decompositions. The task of finding consistent predefinitions of partial functions for various types of joint decompositions is reduced to the formulation and solution of logical equations.

Results

Results. It is shown that the constructed logical equations can be easily transformed to a conjunctive normal form (CNF), and finding the roots of such equations is reduced to the problem of satisfiability of a Boolean formula presented in the form of CNF, for which effective methods and programs are known.

Conclusion

Conclusion. The proposed algorithms can be generalized to other types of algebraic decompositions, when, in addition to the logical operations of disjunction and conjunction, negations of these operations can be used. The application of the proposed algorithms and already known algorithms for minimizing multilevel BDD representations of partial function systems allows us to obtain the best results of technologically independent logical optimization, the initial stage of logic circuit synthesis.

система частичных булевых функцийдоопределение частичной булевой функциибинарная диаграмма решенийалгебраические разложения булевых функцийразложение Шеннонапроблема выполнимостиsystem of partial Boolean functionsadditional definition of a partial Boolean functionBinary Decision Diagramalgebraic decompositions of Boolean functionsShannon expansionSAT-problemReferencesБибило, П. Н. Бинарные диаграммы решений в логическом проектировании / П. Н. Бибило. – М. : Ленанд, 2024. – 560 с.Bibilo P. N. Binarnye diagrammy reshenij v logicheskom proektirovanii. Binary Decision Diagrams in Logical Design. Moscow, Lenand, 2024, 560 p. (In Russ.).Yang, S. BDS: a BDD-based logic optimization system / S. Yang, M. Ciesielski // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. – 2002. – Vol. 21, no. 7. – P. 866–876.Yang S., Ciesielski M. BDS: a BDD-based logic optimization system. IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems, 2002, vol. 21, no. 7, pp. 866–876.Бибило, П. Н. Экспериментальное исследование алгоритмов минимизации BDDI-представлений систем булевых функций с использованием алгебраических разложений кофакторов / П. Н. Бибило, В. И. Романов // Программная инженерия. – 2022. – Т. 13, № 2. – С. 51–67.Bibilo P. N., Romanov V. I. Experimental study of algorithms for minimization of binary decision diagrams using algebraic representations of cofactors. Programmnaya ingeneria [Software Engineering], 2022, vol. 13, no. 2, pp. 51–67 (In Russ.).Handbook of Satisfiability / ed.: A. Biere, M. Heule, H. van Maaren, T. Valsh. – IOS Press, 2009. – 980 p.Handbook of Satisfiability. In A. Biere, M. Heule, H. van Maaren, T. Valsh (eds.). IOS Press, 2009, 980 p.Goldberg, E. BerkMin: a fast and robust sat-solver / E. Goldberg, Y. Novikov // Discrete Applied Mathematics. – 2007. – Vol. 155, no. 12. – P. 1549–1561.Goldberg E., Novikov Y. BerkMin: a fast and robust SAT-solver. Discrete Applied Mathematics, 2007, vol. 155, no. 12, pp. 1549–1561.Закревский, А. Д. Логический синтез каскадных схем / А. Д. Закревский. – М. : Наука, 1981. – 416 c.Zakrevskij A. D. Logicheskij sintez kaskadnyh skhem. Logical Synthesis of Cascading Circuit. Moscow, Nauka, 1981, 416 р. (In Russ.).Еремеев, А. В. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования / А. В. Еремеев, Л. А. Заозерская, А. А. Колоколов // Дискретный анализ и исследование операций. – 2000. – Т. 7, вып. 2. – С. 22–46.Eremeev A. V., Zaozerskaya L. A., Kolokolov A. A. The problem of covering the set: complexity, algorithms, experimental studies. Diskretnyj analiz i issledovanie operacij [Discrete Analysis and Operations Research], 2000, vol. 7, no. 2, pp. 22–46 (In Russ.).Закревский, А. Д. Логические уравнения / А. Д. Закревский. – Минск : Наука и техника, 1975. – 96 c.Zakrevskij A. D. Logicheskie uravneniya. Logical Equations. Minsk, Nauka i tekhnika, 1975, 96 p. (In Russ.).Бибило, П. Н. Декомпозиция булевых функций на основе решения логических уравнений / П. Н. Бибило. – Минск : Беларус. навука, 2009. – 211 с.Bibilo P. N. Dekompoziciya bulevyh funkcij na osnove resheniya logicheskih uravnenij. Decomposition of Boolean Functions Based on Solving Logical Equations. Minsk, Belaruskaja navuka, 2009, 211 p. (in Russ.).Лекции по теории графов / В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. – М. : Наука, 1990. – 384 с.Emelichev V. A., Mel'nikov O. I., Sarvanov V. I., Tyshkevich R. I. Lekcii po teorii grafov. Lectures on Graph Theory. Moscow, Nauka, 1990, 384 p. (In Russ.).Бибило, П. Н. Минимизация BDDI-представлений систем не полностью определенных булевых функций / П. Н. Бибило // Программная инженерия. – 2020. – Т. 11, № 3. – С. 152–168.Bibilo P. N. Minimization of binary decision diagrams for systems of incompletely defined Boolean functions using inverse cofactors. Programmnaya ingeneria [Software Engineering], 2020, vol. 11, no. 3, pp. 152–168 (In Russ.).Бибило, П. Н. Минимизация многоуровневых представлений систем полностью определенных булевых функций с использованием разложений Шеннона и алгебраических представлений кофакторов / П. Н. Бибило, В. И. Романов // Информатика. – 2021. – Т. 18, № 2. – С. 7−32.Bibilo P. N., Romanov V. I. Minimization of binary decision diagrams for systems of completely defined Boolean functions using Shannon expansions and algebraic representations of cofactors. Informatika [Informatics], 2021, vol. 18, no. 2, pp. 7−32 (In Russ.).Брейтон, Р. К. Синтез многоуровневых комбинационных логических схем / Р. К. Брейтон, Г. Д. Хэчтел, А. Л. Санджованни-Винчентелли // Труды Института инженеров по электротехнике и радиоэлектронике. – 1990. – Т. 78, № 2. – С. 38–83.Brayton R. K., Hachtel G. D., Sangiovanni-Vincentelli A. L. Synthesis of multilevel combinational logic circuits. Trudy Instituta inzhenerov po jelektrotehnike i radiojelektronike [Proceedings of the IEEE], 1990, vol. 78, no. 2, рр. 38–83 (In Russ.).

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