On Complete Sets of Logic Primitives

A complete set of logic primitives is a set of devices which can be connected to represent any Boolean function of binary variables. This paper deals with the number of devices required in a complete set of logic primitives. It is well known that a complete set of logic primitives may contain as few as one element, e.g., NOR. It is the purpose of this paper to establish a least upper bound on the number of nonredundant elements in a complete set. It is shown that every complete set contains a complete subset with at most four elements. Further, a complete set with four elements is presented which is incomplete if any element is deleted.