Using the truth table method, determine whether these formulas are:
(1) tautologous, contingent, or contradictory, (2) logically true or not, (3) satisfiable or not:
1. [Exercise 1] p ∧ q → p
| p | q | p∧q | p ∧ q → p |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 1 |
TAUTOLOGY, SATISFIABLE, LOGICAL TRUTH
2. [Exercise 2] p ∨ p → r
| p | r | p ∨ p | p ∨ p → r |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 1 |
CONTINGENT, SATISFIABLE, NOT A LOGICAL TRUTH
3. [Exercise 3] p ∨ (q → r)
| p | q | r | q → r | p ∨ (q → r) |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 0 | 1 | 1 |
CONTINGENT, SATISFIABLE, NOT A LOGICAL TRUTH
4. [Exercise 4] (p → q) ∧ (q → r) → (p → r)
| p | q | r | p → q | q → r | (p → q) ∧ (q → r) | p → r | (p → q) ∧ (q → r) → (p → r) |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
TAUTOLOGY, SATISFIABLE, LOGICAL TRUTH
5. [Exercise 5] p → (q → r)
| p | q | r | q → r | p → (q → r) |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 0 | 1 | 1 |
CONTINGENT, SATISFIABLE, NOT A LOGICAL TRUTH
6. [Exercise 6] p ∨ q → (r ∨ s → p)
| p | q | r | s | p ∨ q | r ∨ s | r ∨ s → p | p ∨ q → (r ∨ s → p) |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
CONTINGENT, SATISFIABLE, NOT A LOGICAL TRUTH
7. [Exercise 7] p ∧ q → q ∧ p
| p | q | p ∧ q | q ∧ p | p ∧ q → q ∧ p |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 1 |
TAUTOLOGY, SATISFIABLE, LOGICAL TRUTH
8. [Exercise 8] (p → q) ∧ p → q
| p | q | p → q | (p → q) ∧ p | (p → q) ∧ p → q |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 |
TAUTOLOGY, SATISFIABLE, LOGICAL TRUTH
9. [Exercise 9] (p → q) ∧ p ∧ ¬q
| p | q | ¬q | p → q | (p → q) ∧ p | (p → q) ∧ p ∧ ¬q |
|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 |
CONTRADICTION, UNSATISFIABLE, NOT A LOGICAL TRUTH
10. [Exercise 10] (p → q) ∧ (p → q)
| p | q | p → q | (p → q) ∧ (p → q) |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 |
CONTINGENT, SATISFIABLE, NOT A LOGICAL TRUTH
11. [Exercise 11] (p → q) ∧ q → p
| p | q | p → q | (p → q) ∧ q | (p → q) ∧ q → p |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 |
CONTINGENT, SATISFIABLE, NOT A LOGICAL TRUTH
12. [Exercise 12] (p → q) ∧ ¬q → ¬p
| p | q | ¬p | ¬q | p → q | p → q ∧ ¬q | (p → q) ∧ ¬q → ¬p |
|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 |
TAUTOLOGY, SATISFIABLE, LOGICAL TRUTH
13. [Exercise 13] (p → q) ∧ ¬p → ¬q
| p | q | ¬p | ¬q | p → q | (p → q) ∧ ¬p | (p → q) ∧ ¬p → ¬q |
|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 |
CONTINGENT, SATISFIABLE, NOT A LOGICAL TRUTH
14. [Exercise 14] ¬(p ∧ q) ↔ ¬p ∧ ¬q
| p | q | ¬p | ¬q | ¬p ∧ ¬q | p ∧ q | ¬(p ∧ q) | ¬(p ∧ q) ↔ ¬p ∧ ¬q |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
CONTINGENT, SATISFIABLE, NOT A LOGICAL TRUTH
15. [Exercise 15] ¬(p ∧ q) ↔ ¬p ∨ ¬q
| p | q | ¬p | ¬q | p ∧ q | ¬(p ∧ q) | ¬p ∨ ¬q | ¬(p ∧ q) ↔ ¬p ∨ ¬q |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
TAUTOLOGY, SATISFIABLE, LOGICAL TRUTH (De Morgan's Law)
16. [Exercise 16] [(p → q) ∧ (q → r)] ∧ ¬(p → r)
| p | q | r | p → q | q → r | p → q ∧ q → r | p → r | ¬(p → r) | (p → q) ∧ (q → r)] ∧ ¬(p → r) |
|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
CONTRADICTION, UNSATISFIABLE, NOT A LOGICAL TRUTH
17. [Exercise 17] p → (q ∧ ¬r → ¬q)
| p | q | r | ¬r | ¬q | q ∧ ¬r | q ∧ ¬r → ¬q | p → (q ∧ ¬r → ¬q) |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 |
CONTINGENT, SATISFIABLE, NOT A LOGICAL TRUTH
18. [Exercise 18] ¬(p ∨ q) ↔ ¬r ∨ ¬q
| p | q | r | ¬r | ¬q | p ∨ q | ¬(p ∨ q) | ¬r ∨ ¬q | ¬(p ∨ q) ↔ ¬r ∨ ¬q |
|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
CONTINGENT, SATISFIABLE, NOT A LOGICAL TRUTH
19. [Exercise 19] ¬(p ∨ q) ↔ ¬p ∨ ¬r
| p | q | r | ¬p | ¬r | p ∨ q | ¬(p ∨ q) | ¬p ∨ ¬r | ¬(p ∨ q) ↔ ¬p ∨ ¬r |
|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
CONTINGENT, SATISFIABLE, NOT A LOGICAL TRUTH
20. [Exercise 20] ¬(p → q) ↔ (p ∧ r)
| p | q | r | p ∧ r | p → q | ¬(p → q) | ¬(p → q) ↔ p ∧ r |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | 1 | 0 | 1 |
CONTINGENT, SATISFIABLE, NOT A LOGICAL TRUTH