Quick summary
A decision procedure is a method that tells us, in a fixed number of steps, whether an argument is valid or whether a statement form is a tautology. In 11th you used the full truth table. This chapter teaches the shorter truth table (STT) method, which tests a statement form for tautology in a single line. It works by reductio ad absurdum: we assume the opposite and look for a contradiction.
Key points
- I.M. Copi defines logic as the study of the methods and principles used to tell correct reasoning from incorrect reasoning.
- Two main jobs of logic: decide whether an argument is valid, and decide whether a statement form is a tautology, contradiction or contingency.
- A good (effective) decision procedure must be reliable, mechanical and finite.
- A full truth table becomes very long: 4 variables = 16 rows, 5 variables = 32 rows (rows = 2ⁿ). So a shorter method is needed.
- STT is also an effective decision procedure, and it can be done in one row.
- STT is based on reductio ad absurdum – show that the opposite of what is to be proved leads to an absurdity. So it is called an indirect method.
- To test for tautology, we assume the form is NOT a tautology: put F under the main connective and mark it with a star (*).
- Then assign values step by step using the basic truth tables, numbering every step.
- Inconsistency is of two kinds: (i) a rule of a basic truth table is broken, (ii) the same variable gets both T and F. Mark it with "x".
- Inconsistency → assumption wrong → the form is a tautology. No inconsistency → it is not a tautology (it is a contradiction or a contingency).
- When the main connective can be false in more than one way (conjunction: 3 ways; equivalence: 2 ways), check every possibility. The form is a tautology only if every possibility gives an inconsistency.
Important terms
- Decision procedure – a method that decides validity of an argument or the nature of a statement form.
- Tautology – a statement form that is true for all truth values of its components.
- Contradiction – a statement form that is false in every case.
- Contingency – a statement form that is true in some cases and false in others.
- Main connective – the connective that joins the largest parts of the expression.
- Reductio ad absurdum – proving something by showing its denial leads to absurdity.
- Inconsistency – a clash in the assigned truth values.
Formulas
Basic truth tables used in STT:
| p | q | ∼p | p · q | p ∨ q | p ⊃ q | p ≡ q |
|---|---|---|---|---|---|---|
| T | T | F | T | T | T | T |
| T | F | F | F | T | F | F |
| F | T | T | F | T | T | F |
| F | F | T | F | F | T | T |
When the main connective is assumed F:
- p ⊃ q is F in one way only: p = T, q = F.
- p ∨ q is F in one way only: p = F, q = F.
- p · q is F in three ways: (T, F), (F, T), (F, F).
- p ≡ q is F in two ways: (T, F), (F, T).
Worked example 1: (p · q) ⊃ p
| p | · | q | ⊃ | p |
|---|---|---|---|---|
| T | T | T | F* | F |
| 3 | 2 | 3 | 1 | 2 |
Step 1: F under ⊃. Step 2: antecedent T, consequent p = F. Step 3: a true conjunction needs p = T and q = T. Now p is T (step 3) and F (step 2) – inconsistency (x under both p's). So the form is a tautology.
Worked example 2: (p ⊃ q) ⊃ (q ⊃ p)
| p | ⊃ | q | ⊃ | q | ⊃ | p |
|---|---|---|---|---|---|---|
| F | T | T | F* | T | F | F |
| 4 | 2 | 4 | 1 | 3 | 2 | 3 |
Step 2: first part T, second part F. Step 3: q ⊃ p is F, so q = T, p = F. Step 4: put the same values in the first part: F ⊃ T = T, which agrees with step 2. No inconsistency, so it is not a tautology.
Worked example 3 (three possibilities): (p ∨ ∼p) · (q ⊃ q)
- (i) first conjunct T, second F: q ⊃ q = F needs q = T and q = F → x.
- (ii) first F, second T: p ∨ ∼p = F needs p = F and ∼p = F (so p = T) → x.
- (iii) both F: the same clashes as above → x.
Every possibility is inconsistent, so it is a tautology.
5 important questions
Q1. What are the conditions of an effective decision procedure?
It must be reliable (always gives the correct answer), mechanical (steps followed by rule, no guessing or imagination needed) and finite (it ends after a limited number of steps).
Q2. Why is the shorter truth table method needed?
A full truth table doubles in size with each new variable (2ⁿ rows), so with 4 or 5 variables it is long, tiring and error-prone. STT decides the same question in one row.
Q3. Why is STT called an indirect method?
It does not prove the result directly. It assumes the opposite (that the form is not a tautology) and shows that this assumption leads to an inconsistency. This is the principle of reductio ad absurdum.
Q4. What are the two types of inconsistency in STT?
(1) Violation of a rule of a basic truth table, e.g. a conjunction marked T with a false conjunct. (2) One propositional variable getting both T and F.
Q5. Test by STT whether p ⊃ (q ⊃ p) is a tautology.
Step 1: F under the main ⊃. Step 2: p = T, (q ⊃ p) = F. Step 3: q ⊃ p is F, so q = T and p = F. Now p is T (step 2) and F (step 3) – inconsistency. Hence p ⊃ (q ⊃ p) is a tautology.
Exam tip
Always write the star under the main connective, number every step, and mark each inconsistency with "x". With conjunction or equivalence as the main connective, show all possibilities – marks are lost if you test only one.