Title :
Concerning the maximum size of the terms in the realization of symmetric functions
Author_Institution :
Victoria Univ., BC, Canada
Abstract :
One method for realizing symmetric functions uses terms which consist of sums of fundamental symmetric functions. In many situations these sums simplify considerably. It is shown that, in the worst case, the size of these sums could approach half the number of possible fundamental symmetric functions without any simplification being possible. An expression for the number of fundamental symmetric functions is derived. For three- and four-valued systems, the size of the largest disjunction of fundamental symmetric functions is shown, and these results are extrapolated to the general case. It appears that the ratio between the maximum size and the total number of fundamental symmetric functions rapidly approaches one-half
Keywords :
many-valued logics; symmetric switching functions; disjunction; four-valued systems; fundamental symmetric functions; multiple valued symmetric functions; simplification; Algebra; Algorithm design and analysis; Decision trees; State feedback; Testing;
Conference_Titel :
Multiple-Valued Logic, 1990., Proceedings of the Twentieth International Symposium on
Conference_Location :
Charlotte, NC
Print_ISBN :
0-8186-2046-3
DOI :
10.1109/ISMVL.1990.122636