A CHARACTERIZATION OF BOOLEAN COLLECTIONS OF SET-VALUED FUNCTIONS

We consider functions on subsets of a finite element set r={0,...,r-1} . A small fraction of these functions are Boolean functions, i.e., fun ctions that can be constructed from constants and variables, using uni on, intersection, and complementation We introduce the notion of Boole an collection of sets, and explore several combinatorial aspects of th ese collections. A collection C is a set consisting of several n-tuple s of subsets of r. We solve the following problem. Given n greater tha n or equal to 1, characterize collections C for which there exists a B oolean function F: P(r)(n) --> P(r) such that F(X-1,...,X-n)=empty set if and only if (X-1,...,X-n) is an element of C, where X-1,...,X-n is an element of P(r) and P(r) is the set of subsets of r. (C) Elsevier Science Inc. 1997.