Week 3: Quantifiers
Hummingbird problem (from Epp):
All hummingbirds are richly colored.
No large birds live on honey.
Birds that do not live on honey are dull in color.
Prove Hummingbirds are small.
1. Step: Create Functions that evaluate to true or false
| H(x) | x is a humminngbird |
| C(x) | x is richly colored |
| LH(x) | x lives on honey |
| L(x) | x is large |
2. Step: Translate sentences into logic
| 1. | All hummingbirds are richly colored. | ∀ x (H(x) => C(x)) |
| 2. | No large birds live on honey. | ¬∃ x (L(x) ∧ LH(x)) |
| 3. | Birds that do not live on honey are dull in color. | ∀ x (¬ LH(x) => ¬ C(x)) |
| Prove: | Hummingbirds are small. | ∀ x (H(x) => ¬ L(x)) |
3. Step: Prove using Inference
| 4. | H(d) => C(d) | Universal Instantiation of (1) |
| 6. | C(d) | Modus Ponens (4 & 5) |
| 7. | ¬LH(d) => ¬C(d) | Universal Instantiation of (3) |
| 8. | LH(d) | Modus Tollens (6 & 7) |
| 9. | ∀ x, ¬ (L(x) ∧ LH(x)) | Negating Quantifiers (2) |
| 10. | ¬ (L(d) ∧ LH(d)) | Universal Instantiation of (9) |
| 11. | ¬ L(d) &or ¬ LH(d) | De Morgan's Law (10) |
| 12. | ¬ L(d) | Disjunctive Syllogism (11 & 8) |
| 13. | H(d) => ¬ L(d) | Anything implies something true |
| 14. | ∀ x (H(x) => ¬ L(x)) | Universal Generalization (13) |