Having assigned truth values to the variables we can work our way up to assign values to more and more complicated expressions. The way values are combined is summarised in “truth tables”. The ones for the four basic operators are
P | Q | ( P ∧ Q ) |
---|---|---|
F | F | F |
F | T | F |
T | F | F |
T | T | T |
P | Q | ( P ∨ Q ) |
---|---|---|
F | F | F |
F | T | T |
T | F | T |
T | T | T |
P | ( ¬ P ) |
---|---|
F | T |
T | F |
P | Q | ( P ⊃ Q ) |
---|---|---|
F | F | T |
F | T | T |
T | F | F |
T | T | T |
I’ve written these with expressions \({ P }\) and \({ Q }\) rather than variables \({ p }\) and \({ q }\) because these can be applied to any expression in our language, not just to variables.
As an example of combining these to assign truth values to more complicated expressions consider the expression \({ \{ [(p ⊃ q) ∧ (q ⊃ r) ] ⊃ (p ⊃ r) \} }\).
We have
p | q | r | (p⊃q) | (q⊃r) | [(p⊃q)∧(q⊃r)] | (p⊃r) | {[(p⊃q)∧(q⊃r)]⊃(p⊃r)} |
---|---|---|---|---|---|---|---|
F | F | F | T | T | T | T | T |
F | F | T | T | T | T | T | T |
F | T | F | T | F | F | T | T |
F | T | T | T | T | T | T | T |
T | F | F | F | T | F | F | T |
T | F | T | F | T | F | T | T |
T | T | F | T | F | F | F | T |
T | T | T | T | T | T | T | T |
So the expression \({ \{ [(p ⊃ q) ∧ (q ⊃ r) ] ⊃ (p ⊃ r) \} }\) evaluates as true no matter what truth values are assigned to \({ p }\), \({ q }\) and \({ r }\). In the terminology introduced earlier it is a tautology.
The fact that truth tables apply to expressions as well as variables has an important consequence. If a statement in the language is a tautology, i.e. is true for all possible values of the variables, then it must remain a tautology when any expressions are substituted in for those variables. This is called the “rule of substitution” and a statement obtained in this way is called a “substitution instance” of the tautology we started with. It is commonly used as a rule of inference in formal systems for zeroeth order logic. Using the rule of substitution we can see that since \({ \{ [(p ⊃ q) ∧ (q ⊃ r) ] ⊃ (p ⊃ r) \} }\) is a tautology so is \({ \{ [(P ⊃ Q) ∧ (Q ⊃ R) ] ⊃ (P ⊃ R) \} }\) for any expressions \({ P }\), \({ Q }\) and \({ R }\).