Functionally Complete Logical Connectives/Negation and Disjunction

From ProofWiki
Jump to navigation Jump to search

Theorem

The set of logical connectives:

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

is functionally complete.


Proof

From Functionally Complete Logical Connectives: Negation and Conjunction, $\set {\neg, \land}$ is functionally complete.

That is: any expression can be expressed in terms of $\neg$ and $\land$.

From De Morgan's laws: Conjunction, we have that:

$p \land q \dashv \vdash \neg \paren {\neg p \lor \neg q}$

Thus all occurrences of $\land$ can be replaced by $\lor$ and $\neg$.

Thus any expression can be expressed in terms of $\neg$ and $\lor$.

That is: $\set {\neg, \lor}$ is functionally complete.

$\blacksquare$


Sources