Functionally Complete Logical Connectives

From ProofWiki
Jump to navigation Jump to search


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


$\set \uparrow$: NAND


$\set \downarrow$: NOR

There are others, but these are the main ones.

Also see