Mathematics · Ch 1 — Mathematical Logic
Some important results
1.4.1
Some important results
Four equivalences underpin most of the simplification work in this chapter. This section proves the first two with a single truth table and leaves the other two as a truth-table activity.
i)
ii)
iii)
iv)
Proving (i) and (ii).
| p | q | ~p | p→q | q→p | p↔q | ~p∨q | (p→q)∧(q→p) |
|---|---|---|---|---|---|---|---|
| T | T | F | T | T | T | T | T |
| T | F | F | F | T | F | F | F |
| F | T | T | T | F | F | T | F |
| F | F | T | T | T | T | T | T |
The p→q column and the ~p∨q column are identical (T,F,T,T both), proving . The p↔q column and the (p→q)∧(q→p) column are also identical (T,F,F,T both), proving — confirming that a biconditional is nothing more than 'the implication holds in both directions'.
Activity — proving (iii) and (iv) by truth table. With three variables there are eight rows to check:
| p | q | r | p∨(q∧r) | (p∨q)∧(p∨r) | p∧(q∨r) | (p∧q)∨(p∧r) |
|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T |
| T | T | F | T | T | T | T |
| T | F | T | T | T | T | T |
| T | F | F | T | T | F | F |
| F | T | T | T | T | F | F |
| F | T | F | F | F | F | F |
| F | F | T | F | F | F | F |
| F | F | F | F | F | F | F |
Table 1Table 1.20 — Proof that p → q ≡ ~p ∨ q and p ↔ q ≡ (p → q) ∧ (q → p)
| p | q | ~p | p → q | q → p | p ↔ q | ~p ∨ q | (p → q) ∧ (q → p) |
|---|---|---|---|---|---|---|---|
| T | T | F | T | T | T | T | T |
| T | F | F | F | T | F | F | F |