Functionally Complete Logical Connectives

From ProofWiki
Jump to navigation Jump to search

Theorem

These sets of logical connectives are functionally complete:


Negation, Conjunction, Disjunction and Implication

$\left\{{\neg, \land, \lor, \implies}\right\}$: 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