Method of Truth Tables
Contents |
Proof Technique
The method of truth tables is a technique for determining the validity of logical formulas.
To start with, we establish the truth tables of the various logical connectives.
We write one line for each model of the set of atoms that we are concerned with.
From Number of Models for an Alphabet, this is $2^n$.
There are therefore two lines in the truth table for the only non-trivial unary connective:
$\begin{array}{|c||c|} \hline p & \neg p \\ \hline F & T \\ T & F \\ \hline \end{array}$
... and four lines in the truth table for the binary connectives (the usual subset of which is given below):
$\begin{array}{|cc||c|c|c|c|c|c|c|c|} \hline p & q & p \land q & p \lor q & p \implies q & p \iff q & p \ \Longleftarrow \ q & p \oplus q & p \uparrow q & p \downarrow q \\ \hline F & F & F & F & T & T & T & F & T & T \\ F & T & F & T & T & F & F & T & T & F \\ T & F & F & T & F & F & T & T & T & F \\ T & T & T & F & T & T & T & F & F & F \\ \hline \end{array}$
There are various sorts of proof this technique can be put to, as follows.
These will be illustrated by various examples.
Proof of Tautology
This is used to establish whether or not a given logical formula is a tautology; that, is true under all models.
Let $P$ be a logical formula we wish to validate, and write it as a WFF of Propositional Calculus.
We will use Peirce's Law as an example:
- $((p \implies q) \implies p) \implies p$
For each model of the set of atoms, we write its truth value underneath:
$\begin{array}{cc||ccccccc} p & q & ((p & \implies & q) & \implies & p) & \implies & p \\ \hline F & F & F & & F & & F & & F \\ \end{array}$
In the above, we are using the model $p_{\mathcal M} = F, q_{\mathcal M} = F$.
Then we fill in the truth value of each of the |WFFs on the parsing sequence of $P$, underneath its main connective:
$\begin{array}{cc||ccccccc} p & q & ((p & \implies & q) & \implies & p) & \implies & p \\ \hline F & F & F & & F & & F & & F \\ & & & T & & & & & \\ & & & & & F & & & \\ & & & & & & & T & \\ \end{array}$
In the above, this has been done on separate lines, so as to clarify the sequence in which this is done for the example.
In practice we write it like this:
$\begin{array}{cc||ccccccc} p & q & ((p & \implies & q) & \implies & p) & \implies & p \\ \hline F & F & F & T & F & F & F & F & F \\ \end{array}$
We repeat this for all models:
$\begin{array}{cc||ccccccc} p & q & ((p & \implies & q) & \implies & p) & \implies & p \\ \hline F & F & F & T & F & F & F & T & F \\ F & T & F & T & T & F & F & T & F \\ T & F & T & F & F & T & T & T & T \\ T & T & T & T & T & T & T & T & T \\ \end{array}$
In the column under the main connective of $P$ itself can be found the truth value of $P$ for each model.
- If this contains nothing but $T$, then $P$ is a tautology.
- If this contains nothing but $F$, then $P$ is a contradiction.
- If this contains $T$ for some models and $F$ for others, then $P$ is a contingent statement.
In the above example, the main connective of $P$ is the rightmost instance of $\implies$.
The column beneath that connective is all $T$, so $((p \implies q) \implies p) \implies p$ is a tautology.
$\blacksquare$
Proof of Interderivability
Suppose we have two logical formulas $P$ and $Q$ and we wish to see whether $P \dashv \vdash Q$ or not.
- Example: Let $P$ be $p \uparrow q$ and let $Q$ be $\neg \left({p \land q}\right)$.
There are two things we can do.
Express two statements as a single WFF
We express $P \dashv \vdash Q$ as a single WFF $\left({P \iff Q}\right)$ and perform the method of truth tables on that.
Demonstrating this with the example given:
$\begin{array}{cc||cccccccc} p & q & (p & \uparrow & q) & \iff & \neg & (p & \land & q) \\ \hline F & F & F & T & F & T & T & F & F & F \\ F & T & F & T & T & T & T & F & F & T \\ T & F & T & T & F & T & T & T & F & F \\ T & T & T & F & T & T & F & T & T & T \\ \end{array}$
As can be seen, the column under the main connective $\iff$ of $\left({P \iff Q}\right)$ is all $T$, so $\left({\left({p \uparrow q}\right) \iff \neg \left({p \land q}\right)}\right)$ is a tautology.
Hence from Equivalences are Interderivable, $\left({\left({p \uparrow q}\right) \dashv \vdash \neg \left({p \land q}\right)}\right)$ and the two formulas are interderivable.
$\blacksquare$
Compare two WFFs in the same table
Alternatively, we can place the two WFFs side by side in the same truth table:
$\begin{array}{cc||ccc||cccc} p & q & (p & \uparrow & q) & \neg & (p & \land & q) \\ \hline F & F & F & T & F & T & F & F & F \\ F & T & F & T & T & T & F & F & T \\ T & F & T & T & F & T & T & F & F \\ T & T & T & F & T & F & T & T & T \\ \end{array}$
This time, we need to make sure that the truth values in the columns under the main connectives of both formulae are the same.
Note that this is exactly the same as putting a $\iff$ between the two and making a WFF out of the pair of them.
$\blacksquare$
Proof of Logical Implication
Suppose we wish to prove that $P \vdash Q$ for two logical formulas $P$ and $Q$.
- Example: Let $P$ be $\neg p$ and $Q$ be $p \implies q$.
Express two statements as a single WFF
We express $P \vdash Q$ as a single WFF $\left({P \implies Q}\right)$ and perform the method of truth tables on that
Demonstrating this with the example given:
$\begin{array}{cc||cccccc} p & q & (\neg & p ) & \implies & (p & \implies & q) \\ \hline F & F & T & F & T & F & T & F \\ F & T & T & F & T & F & T & T \\ T & F & F & T & T & T & F & F \\ T & T & F & T & T & T & T & T \\ \end{array}$
As can be seen, the column under the main connective $\implies$ of $\left({P \implies Q}\right)$ is all $T$, so $\left({\left({\neg p}\right) \implies \left({p \implies q}\right)}\right)$ is a tautology.
Hence from Equivalence of Logical Implication and Conditional, $\neg p \vdash p \implies q$.
$\blacksquare$
Compare two WFFs in the same table
Alternatively, we can place the two WFFs side by side in the same truth table:
$\begin{array}{cc||cc||ccc} p & q & \neg & p & p & \implies & q \\ \hline F & F & T & F & F & T & F \\ F & T & T & F & F & T & T \\ T & F & F & T & T & F & F \\ T & T & F & T & T & T & T \\ \end{array}$
This time, we need to make sure that when the truth values in the columns under the first main connectives is $T$, then it is also $T$ under the second.
Note that this is exactly the same as putting a $\implies$ between the two and making a WFF out of the pair of them.
$\blacksquare$
Notational Convenience
It is not actually necessary to include the truth values of the atoms themselves (as we have done in the left hand most columns).
We can equally well do this:
$\begin{array}{ccccccc} ((p & \implies & q) & \implies & p) & \implies & p \\ \hline F & T & F & F & F & T & F \\ F & T & T & F & F & T & F \\ T & F & F & T & T & T & T \\ T & T & T & T & T & T & T \\ \end{array}$
... and it serves just as well.
However, it can help to clarify the derivation, as well as making the truth table easier to construct, if they are included. It's a matter of personal taste.
Comment
Note that solution by truth table is valid only for Aristotelian logic, as it takes for granted the Law of the Excluded Middle and the Principle of Non-Contradiction.
Within that context, it is a completely mechanical procedure and about as exciting as a strip-tease artist who starts the performance naked.
Sources
- D.J. O'Connor and Betty Powell: Elementary Logic (1980): $\S 1.4, \ \S 1.8$
- H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): $\S 1.6$
