Functionally Complete Logical Connectives

Theorem

These sets of logical connectives are functionally complete:

Negation, Conjunction, Disjunction and Implication

$\set {\neg, \land, \lor, \implies}$: Not, And, Or and Implies

Conjunction, Negation and Disjunction

$\set {\neg, \land, \lor}$: Not, And and Or

Negation and Conjunction

$\set {\neg, \land}$: Not and And

Negation and Disjunction

$\set {\neg, \lor}$: Not and Or

Negation and Conditional

$\set {\neg, \implies}$: Not and Implies

NAND

$\set \uparrow$: NAND

NOR

$\set \downarrow$: NOR

There are others, but these are the main ones.

Also see

• Functionally Complete Singleton Sets, in which it is seen that the only functionally complete singletons are $\left\{{\uparrow}\right\}$ and $\left\{{\downarrow}\right\}$.
• Functionally Incomplete Logical Connectives