Abstract. This paper discusses 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 choices 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 (where constants are excluded) are added to $F$. This paper proves that there are $2^r+w(r)-3$ Boolean maximal sets in $r$-valued set logic (here $w(r)$ is the number of equivalence relations on an $r$-element set) and gives a description of them using equivalence- and unary central relations. A set of functions $F$ is then Boolean complete iff it is not a subset of any of these Boolean maximal sets. This is a completeness criterion in many-valued set logic under compositions with Boolean functions. The lattice of clones containing all Boolean functions is also studied.

AMS Subject Classification (1991): 03B50, 68Q05

Received February 27, 1996. (Registered under 6119/2009.)