Functional completeness

In logic, a set of logical connectives is functionally complete if all other possible connectives can be defined in terms of it.

Usually, in an exposition of classical logic, the following connectives are defined: conjunction ($\land$), disjunction ($\lor$), negation ($\neg$), implication ($\to$) and possibly bi-implication ($\leftrightarrow$). This constitutes a functionally complete set. However, it is not a minimal functionally complete set, as implication and bi-implication may be defined as:

$A\to B:=\neg A\lor B$

$A\leftrightarrow B:=(A\to B)\land (B\to A)$

So ${\neg ,\land ,\lor }$ is also functionally complete. But then, $\lor$ can be defined as:

$A\lor B:=\neg (\neg A\land \neg B)$

($\land$ can also be defined in terms of $\lor$ in a similar manner.)

This cannot be further simplified, so ${\neg ,\land }$ is a minimal functionally complete subset of ${\neg ,\land ,\lor ,\to ,\leftrightarrow }$. However, the (non-standard) connectives NOR and NAND are functionally complete on their own, and are called sole sufficient operators.