Propositional Logic – A Primer
3. Proofs Using Truth Tables
Of the three methods for determining the formal validity of an argument, the truth table method is the simplest. Consider this basic argument from the Introduction.
Premise 1: If it is raining, it is wet outside.
Premise 2: It is raining.
Conclusion: It is wet outside.
Translating it into symbolic form using propositional variables and logical connectives, we get the following:
P1: P → Q
P2: P
C: Q
The argument is valid if the conclusion follows logically from the two premises. To use a truth table to determine the validity of the argument, we first construct a truth table that includes all of the premises and the conclusion. Testing for validity, we then verify that there is no case in which the premises are true and the conclusion false.
First, list all possible truth values for the component propositions in the left-most columns. Then, in the next column, work out the possible truth values for the compound proposition. For the final column, add the conclusion with its possible truth values. The truth table looks as follows:
Example 1 – Truth table proof
| P | Q | P → Q | Q |
|---|---|---|---|
| T | T | T | T |
| T | F | F | F |
| F | T | T | T |
| F | F | T | F |
To determine validity, look at every row in which both premises ('P → Q'; 'P') are true. For those rows (the first row only, in this case), is there a case in which the conclusion ('Q') is not true? There is not. Therefore, the argument is valid.
Consider a more complicated argument with three premises.
Premise 1: Either Tom is a man or Tom is a teacher.
Premise 2: If Tom is a man, then Tom is a bachelor.
Premise 3: It is not the case that Tom is a teacher.
Conclusion: Tom is a bachelor..
Translating to symbolic form yields:
P1: P ∨ Q
P2: P → R
P3: ¬Q
C: R
We construct the truth table as follows.
Example 2 – Truth table proof
| P | Q | R | P ∨ Q | P → R | ¬Q | R |
|---|---|---|---|---|---|---|
| T | T | T | T | T | F | T |
| T | T | F | T | F | F | F |
| T | F | T | T | T | T | T |
| T | F | F | T | F | T | F |
| F | T | T | T | T | F | T |
| F | T | F | T | T | F | F |
| F | F | T | F | T | T | T |
| F | F | F | F | T | T | F |
The first three columns list all of the possible truth values for the atomic propositions. The next three columns list the possible truth values of the compound propositions making up the three premises. The final column lists the possible truth values for the conclusion ('R'). This final column is a repeat of the third column in order to make a comparison of the truth values of the conclusion with those of the three premises. On inspection, we see that there is no line of the truth table in which all three premises are true (the third row only, in this case) and the conclusion is false. Therefore, the argument is valid.
In propositional logic, a valid argument is an argument in which the conclusion necessarily follows from the premises. In other words, if the premises of a valid argument are true, then the conclusion must also be true. Note that the conclusion of a valid argument is not necessarily true. The truth of the conclusion is only guaranteed by the truth of the premises and the logical structure of the argument. If one or more of the premises are false, the conclusion may be false. If both conditions are met (that is, the premises are true and the argument is valid), logicians call that kind of argument a 'sound' argument.
Now, some compound propositions are necessarily true independently of the truth of other propositions. Logicians call this kind of proposition a 'tautology'. For a tautology, it is impossible for it to be false under any circumstances. They are always true, regardless of the truth values of its component propositions. 'It is raining or it is not the case that it is raining' (expressed as 'P ∨ ¬P') is an example of a tautology. It can't be otherwise than true.
We can use truth tables to prove a compound proposition is a tautology. By constructing a truth table and inspecting it, we can verify that a proposition is true for all possible truth values of its component propositions.
As a simple example, we can prove that 'P ∨ ¬P' is a tautology. Lay out all of the possible truth values of the component propositions in a truth table along with the resulting possible truth values of the tautology.
Example 3 – Truth table proof
| P | ¬P | P ∨ ¬P |
|---|---|---|
| T | F | T |
| F | T | T |
The truth table shows that 'P ∨ ¬P' is true for all possible truth values of 'P' and '¬P'. Therefore, 'P ∨ ¬P' is a tautology.
Just as we can use truth tables to prove a compound proposition to be necessarily true, we can also use them to prove a proposition to be necessarily false—a logical contradiction. A logical contradiction is a compound proposition that is always false, regardless of the truth values of its component propositions. For example, we can prove that 'P ∧ ¬P' is a logical contradiction using the following truth table:
Example 4 – Truth table proof
| P | ¬P | P ∧ ¬P |
|---|---|---|
| T | F | F |
| F | T | F |
The truth table shows that 'P ∧ ¬P' is false for all possible truth values of 'P' and '¬P'. Therefore 'P ∧ ¬P' is a contradiction.
Let's now prove a more complex tautology, such as this equivalence to the negation of a conjunction:
¬(P ∧ Q) ↔ ¬P ∨ ¬Q
The equivalence is necessarily true if both sides of the equivalence operator have the same truth value for all possible truth values of 'P' and 'Q'.
Example 5 – Truth table proof
| P | Q | P ∧ Q | ¬(P ∧ Q) | ¬P | ¬Q | ¬P ∨ ¬Q |
|---|---|---|---|---|---|---|
| T | T | T | F | F | F | F |
| T | F | F | T | F | T | T |
| F | T | F | T | T | F | T |
| F | F | F | T | T | T | T |
Look down each row of the truth table to see whether for one or more truth assignments of 'P' and 'Q' the truth value of '¬(P ∧ Q)' is not identical to the truth value of '¬P ∨ ¬Q'. As there are no such instances, '¬(P ∧ Q) ↔ ¬P ∨ ¬Q' is a tautology.
We can do the same now with the negation of a disjunction:
¬(P ∨ Q) ↔ ¬P ∧ ¬Q
Is this also a tautology? As before, construct the truth table and inspect the result.
Example 6 – Truth table proof
| P | Q | P ∨ Q | ¬(P ∨ Q) | ¬P | ¬Q | ¬P ∧ ¬Q |
|---|---|---|---|---|---|---|
| T | T | T | F | F | F | F |
| T | F | T | F | F | T | F |
| F | T | T | F | T | F | F |
| F | F | F | T | T | T | T |
The truth table shows that '¬(P ∨ Q)' and '¬P ∧ ¬Q' have the same truth values for all possible truth values of 'P' and 'Q'. Therefore, '¬(P ∨ Q) ↔ ¬P ∧ ¬Q' is a tautology.
These latter two tautologies are known as De Morgan's Laws. They state that the negation of a conjunction is the disjunction of the negations, and the negation of a disjunction is the conjunction of the negations.
It is important to note that while truth tables are useful for proving validity and tautologies in propositional logic, they can become very large and difficult to read for compound propositions with many component propositions. In such cases, it is often more practical to use other methods, such as the natural deduction method and truth trees.
