A Fast Algorithm for the Disjunctive Decomposition of Switching Functions

Abstract

An algorithm for obtaining all simpledisjunctive 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 theexistence 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 n3. Previous methods, on the other hand, have an exponential growth rate. Copyright © 1971 by The Institute of Electrical and Electronics Engineers, Inc.