Functional Completeness

To those new to logic and new to junctors, it is sometimes surprising, that we do not need all the junctors to be functionally complete. As Wikipedia states and those already familiar with propositional or predicate logic know: the conjunction and the negation are already functionally complete.

It is quite easy to show this with some basic knowledge about junctors. Also this is quite easy to confirm with truth-tables which I won't do here.

Implication And Equivalency

We have to figure out a way to build the implication or conditional: \(\rightarrow\). We already know the truth values for it, so I asked myself: When is the implication true?

Easy! It is true iff \(\neg p \lor q\) so if \(p\) is false or \(q\) is true. Using DeMorgan's law \(\neg ( p \land q) \leftrightarrow (\neg p \lor \neg q)\), we can express the disjunction with the conjunction and get \(\neg (p \land \neg q)\) as equivalent to \(p \rightarrow q\). If you do not understand De Morgan's law, try to figure it out and use Venn-diagrams from set theory.

And with the implication we can easily express equivalency \(\leftrightarrow\), because \(p \leftrightarrow q\) is equivalent to \((p \rightarrow q) \land (q \rightarrow p)\). So if \(\neg (p \land \neg q)\) is the implication, equivalency is \(\neg ( p \land \neg q) \land \neg ( q \land \neg p)\).


The last thing we want to express is the disjunction and this is also easy, because we can use DeMorgan's law to express the disjunction via a conjunction: \(\neg ( p \land q) \leftrightarrow (\neg p \lor \neg q)\).

But we don't want \(\neg p \lor \neg q\), we want \(p \lor q\)! And we get it by negating the conjunction again:

\(\neg ( \neg p \land \neg q ) \leftrightarrow (p \lor q)\).


I just wanted to show my thought process when constructing the other junctors. This is quite easy using only DeMorgan's law and some basic knowledge about junctors. But functional completeness shows up during history (pierce arrow, sheffer stroke, aso.) and is used in chip layouts. And after all: chips & computers & the internet are the reason you are able to read this.