Disjunctive and conjunctive decompositions of incompletely defined Boolean functions in a Binary Decision Diagram - P. N. Bibilo (Informatika)
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. 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. 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. 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.