Worst case number of terms in symmetric multiple-valued functions

Abstract

A symmetric multiple-valued function can be realized as the disjunction of fundamental symmetric functions. A simpler disjunction can be formed when the latter functions combine in the same way that minterms combine to form simpler product terms for sum-of-products expressions. We solve a problem posed by Muzio [7], who seeks the worst case symmetric function in the sense that the maximum number of fundamental symmetric functions is needed. The worst case is presented for 3- and 4-valued systems in 171, but the case for general radix is left open. We solve this problem for general radix, and show that the ratio of the maximum size of the disjunction to the total number of fundamental symmetric functions approaches one-half as the number of variables increases.