Tautologies

# 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.