Functional completeness is the property of a set of logical connectives that every Boolean function of one or more variables can be expressed using only those connectives and variables, with repeated use of variables allowed.
The operations NOT, AND, and OR together are functionally complete, as follows from disjunctive normal form. In fact, either AND or OR together with NOT suffices. Each of NAND and NOR is functionally complete by itself. In contrast, AND and OR without NOT are not functionally complete, since any expression formed from these operations is true when all its input variables are true and hence cannot express NOT.
