A Fast Algorithm for the Disjunctive Decomposition of Switching Functions

Abstract

An algorithm for obtaining all simple disjunctive decompositions of a switching function is described. It operates on a function given as an expression using the operations AND, EXCLUSIVE OR, and complementation. It uses necessary conditions for the existence of a decomposition to eliminate sets of bound sets from consideration. Thus this technique differs from existing methods in that it attempts to test fewer bound sets at the expense of additional analysis. The algorithm can also be applied to functions given in a canonical form. It is shown that for a collection of functions of n variables chosen at random, the time required grows as n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> . Previous methods, on the other hand, have an exponential growth rate.