Using Decision Trees to Derive the Complement of a Binary Function with Multiple-Valued Inputs

Abstract

An algorithm to minimize decision trees of Boolean functions with multiple-valued inputs is presented. The recursive algorithm is used to obtain a complement of a sum-of-products expression for a binary function with multiple-valued inputs. In the case where each input is p-valued, the algorithm produces at most pn−l products for n-variable functions, whereas Sasao's algorithm produces pn/2 products. This upper bound on the number of products is the best possible.