# Tautologies

As mentioned several times in various sections of this document, some
formulas are always true without regard to the truth values of the
terms of which they are composed. Such “self-confirming” or
“self-evidently true” statements are called *tautologies*. A tautology
actually contributes no new information to the world, since there is
no possible state of the world in which it is false and so they are
considered “vacuous”. Some tautologies have traditional names due to
their historical importance, such as the “law of the excluded middle:”

$$ \begin{array}{cc|c} P & \neg P & P \vee \neg P \\ \hline \\ T & F & T \\ F & T & T \end{array} $$

Many of these “named” tautologies are closely aligned with the axioms of symbolic logic and with the core set of inference rules that are used in carrying out proofs.

Others are simply interesting in their own right, or for their applicability outside of the domain of “pure” logic. For example, consider the following simple equivalence:

$$ \begin{array}{cccc|c} P & Q & P \rightarrow Q & \neg P \vee Q & (P \rightarrow Q) \leftrightarrow (\neg P \vee Q) \\ \hline \\ T & T & T & T & T \\ T & F & F & F & T \\ F & T & T & T & T \\ F & F & T & T & T \end{array} $$

It says that the conditional connective has the same meaning as a particular formula involving negation and disjunction. This implies that the conditional connective is in some sense “superfluous,” since any formula using a conditional could be rewritten using negation and disjunction in its place.

In fact, it turns out that any set of such connectives can always be
reduced in this way to only a single connective – though such single
connectives do not correspond neatly to “atomic” natural language
concepts like “not,” “and,” “or,” “implies” etc. One such “all
purpose” connective is “not or,” also known as *nor*:

$$ \begin{array}{cc|c} \Phi & \Psi & \Phi \text{ nor } \Psi \\ \hline \\ T & T & F \\ T & F & F \\ F & T & F \\ F & F & T \end{array} $$

The preceding truth table can be seen to be equivalent to that of ¬ (Φ ∨ Ψ):

$$ \begin{array}{ccc|c} \Phi & \Psi & \Phi \vee \Psi & \neg \left( \Phi \vee \Psi \right) \\ \hline \\ T & T & T & F \\ T & F & T & F \\ F & T & T & F \\ F & F & F & T \end{array} $$

One can see that *nor* can be used in place of ¬ quite directly:

$$ \begin{array}{c|c} P & P \text{ nor } P \\ \hline \\ T & F \\ F & T \end{array} $$

The truth tables showing the equivalence of *nor* to the rest of the
various “traditional” connectives get rather verbose. For example,
here is the truth table for conjunction expressed only using *nor*:

$$ \begin{array}{cccc|c} \Phi & \Psi & \Phi nor \Phi & \Psi nor \Psi & \left( \Phi nor \Phi \right) nor \left( \Psi nor \Psi \right) \\ \hline \\ T & T & F & F & T \\ T & F & F & T & F \\ F & T & T & F & F \\ F & F & T & T & F \end{array} $$

Note carefully the number of rows in the preceding truth table and the
pattern of *T* and *F* for the primitive terms Φ, Ψ and the
right-most column. That pattern matches that of the truth table for
conjunction, thus demonstrating the equivalence:

$$ \left( \Phi \wedge \Psi \right) \leftrightarrow \left( \Phi nor \Phi \right) nor \left( \Psi nor \Psi \right) $$

Determining the equivalence of *nor* and the remainder of the
“traditional” connectives is left as an exercise for the reader.

Other “all purpose” connectives can be devised with even less direct
correspondence to “natural” logical relationships. Another such
example is “not and,” also known as *nand*:

$$ \begin{array}{cc|c} \Phi & \Psi & \Phi \text{ nand } \Psi \\ \hline \\ T & T & F \\ T & F & T \\ F & T & T \\ F & F & T \end{array} $$

One can express all of the axioms of symbolic logic and carry out all proof procedures involving formulas that are composed only using any single such “all purpose” connective. Besides being an intellectual curiosity, such reductions in the number of distinct types of logical connectives find real-world engineering applications in disciplines like electrical and electronic engineering. It is far cheaper and more reliable to design a digital circuit composed of only a small number of distinct types of logic gate than the equivalent circuit composed from the multiplicity of types of connectives in traditional logic.

All of this shows the importance and power of certain tautologies even though they are in a literal sense vacuously true and so say nothing.