Functionally Complete Logical Connectives/Negation and Conditional

From ProofWiki
Jump to navigation Jump to search


The set of logical connectives:

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

is functionally complete.


From Functionally Complete Logical Connectives: Negation and Conjunction, we can represent any boolean expression in terms of $\land$ and $\neg$.

From Conjunction and Implication, we have that:

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

So it follows that we can replace all occurrences of $\land$ by $\implies$ and $\neg$.

Thus $\set {\neg, \implies}$ is functionally complete.