Boolean Completeness in Multiple-Valued Set Logic
Pedro Acevedo Contla, Ivo G. Rosenberg, Dan A. Simovici and Ivan Stojmenovic
This paper discusses the functional completeness problems in r-valued set logic, which is the logic of functions mapping n-tuples of subsets into subsets over r values. Boolean functions are convenient choice as building blocks in the design of set logic functions. A set of functions F is Boolean complete if any set logic function can be composed from F once all Boolean functions are added to F. This paper proves that there are 2r-2 Boolean maximal sets in r-valued set logic and gives their description using equivalence relations. A set F is then Boolean complete if it is not a subset of any of these 2r-2 Boolean maximal sets, which is a completeness criteria in many-valued set logic under compositions with Boolean functions.