Disjoint disjunctive form of boolean functions and its applications

Abstract Due to upscaling of digital systems, the development of efficient representations and manipulating algorithms of Boolean functions is becoming increasingly important. This paper considers the representation by the disjoint disjunctive form from representations of Boolean functions, and describes the properties, characteristics and manipulating algorithms. Conventionally used sharp operation and disjoint sharp operation are made more efficient for the algorithm which generates disjoint disjunctive forms. Moreover, a binary tree method is proposed as a method which generates disjoint disjunctive forms of positive and negative functions simultaneously. This binary tree method is also very powerful as a method to obtain negation of logical formulas, and is five to ten times faster than the conventional one using disjoint sharp operation in a case of 10‐variable function. Also, for the problem of number of product terms, which is generally regarded as a shortcoming of the disjoint disjunctive form, we conduct further studies by considering the simplest disjoint disjunctive form. Moreover, we show a unique negation algorithm as an example of using the properties of the disjoint disjunctive form more aggressively.