Functional completeness

In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression. A well-known complete set of connectives is { AND, NOT }, consisting of binary conjunction and negation. The singleton sets { NAND } and { NOR } are also functionally complete.

In a context of propositional logic, functionally complete sets of connectives are also called (expressively) adequate.

From the point of view of digital electronics, functional completeness means that every possible logic gate can be realized as a network of gates of the types prescribed by the set. In particular, all logic gates can be assembled from either only binary NAND gates, or only binary NOR gates.

Modern texts on logic typically take as primitive some subset of the connectives: conjunction (${\displaystyle \land }$); disjunction (${\displaystyle \lor }$); negation (${\displaystyle \neg }$); material conditional (${\displaystyle \to }$); and possibly the biconditional (${\displaystyle \leftrightarrow }$). Further connectives can be defined, if so desired, by defining them in terms of these primitives. For example, NOR (sometimes denoted ${\displaystyle \downarrow }$, the negation of the disjunction) can be expressed as conjunction of two negations:

...
Wikipedia