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 Conditional

$\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