On the Numbers of Variables to Represent Multi-valued Incompletely Specified Functions

In an incompletely specified function f, don´t care values can be chosen to minimize the number of variables to represent f. We consider incompletely specified functions f: Pⁿ → Q, where P={0,1,..., p-1}, Q={0,1,..., q-1}, u combinations are mapped to i (i=0,1,...,q-1), uq=k, and other combinations are mapped to don´t cares. We show that most functions can be represented with 2 [log_p (k+1)] variables or less. Experimental results are shown to support this.