Try It Now

Exercises

1. Prove with truth tables:
   1. p∨ q, ¬q⇒ p
   2. p → q, ¬q ⇒ ¬p
      
      
3. Give direct and indirect proofs of:
   
   1. a → b, c → b, d → (a ∨ c), d ⇒ b.
   2. (p → q) ∧ (r → s), (q → t) ∧ (s → u), ¬(t ∧ u), p → r ⇒ ¬p.
   3. p → (q → r), ¬s ∨ p, q ⇒ s → r.
   4. p → q, q → r, ¬(p ∧ r), p ∨ r ⇒ r.
   5. ¬q,p → q, p ∨ t ⇒ t
      
      
5. Are the following arguments valid? If they are valid, construct formal proofs; if they aren’t valid, explain why not.
   
   1. If wages increase, then there will be inflation. The cost of living will not increase if there is no inflation. Wages will increase. Therefore, the cost of living will increase.
   2. If the races are fixed or the casinos are crooked, then the tourist trade will decline. If the tourist trade decreases, then the police will be happy. The police force is never happy. Therefore, the races are not fixed.
      
      
7. Describe how p₁, p₁→ p₂, . . . , p₉₉→ p₁₀₀⇒ p100 could be proved in 199 steps.

Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.

Solutions

1. 3.5.4.1. Answer.
   1. 
   2. 
      
      
2. 3. Answer:
   
   1. Direct proof:
      1. d → (a ∨ c)
      2. d
      3. a ∨ c 
      4. a → b 
      5. ¬a ∨ b
      6. c → b 
      7. ¬c ∨ b
      8. (¬a ∨ b) ∧ (¬c ∨ b)
      9. (¬a ∧ ¬c) ∨ b
      10. ¬(a ∨ c) ∨ b 
      11. b □
   1. Indirect proof:
      1. ¬b Negated conclusion
      2. a → b Premise
      3. ¬a Indirect Reasoning (1), (2)
      4. c → b Premise
      5. ¬c Indirect Reasoning (1), (4)
      6. (¬a ∧ ¬c) Conjunctive (3), (5)
      7. ¬(a ∨ c) DeMorgan's law (6)
      8. d → (a ∨ c) Premise
      9. ¬d Indirect Reasoning (7), (8)
      10. d Premise
      11. ⊬ (9), (10) □
   2. Direct proof:
      1. (p → q) ∧ (r → s)
      2. p → q
      3. (p → t) ∧ (s → u)
      4. q → t 
      5. p → t 
      6. r → s 
      7. s → u 
      8. r → u 
      9. p → r
      10. p → u
      11. p → (t ∧ u) Use (x → y) ∧ (x → z) ⇔ x → (y ∧ z)
      12. ¬(t ∧ u) → ¬p
      13. ¬(t ∧ u)
      14. ¬p □
   2. Indirect proof:
      1. p
      2. p → q
      3. q
      4. q → t
      5. t
      6. ¬(t ∧ u)
      7. ¬t ∨ ¬u 
      8. ¬u
      9. s → u 
      10. ¬s
      11. r → s 
      12. ¬r 
      13. p → r 
      14. r
      15. 0 □
   3. Direct proof:
      
      1. ¬s ∨ p Premise
      2. s Added premise (conditional conclusion)
      3. ¬(¬s) Involution (2)
      4. p Disjunctive simplification (1), (3)
      5. p → (q → r) Premise
      6. q → r Detachment (4), (5)
      7. q Premise
      8. r Detachment (6), (7) □
   3. Indirect proof:
      1. ¬(s → r) Negated conclusion
      2. ¬(¬s ∨ r) Conditional equivalence (I)
      3. s ∧ ¬r DeMorgan (2)
      4. s Conjunctive simplification (3)
      5. ¬s ∨ p Premise
      6. s → p Conditional equivalence (5)
      7. p Detachment (4), (6)
      8. p → (q → r) Premise
      9. q → r Detachment (7), (8)
      10. q Premise
      11. r Detachment (9), (10)
      12. ¬r Conjunctive simplification (3)
      13. 0 Conjunction (11), (12) □
   4. Direct proof:
      
      1. p → q
      2. q → r
      3. p → r
      4. p ∨ r
      5. ¬p ∨ r
      6. (p ∨ r) ∧ (¬p ∨ r)
      7. (p ∧ ¬p) ∨ r
      8. 0 ∨ r
      9. r □
   4. Indirect proof:
      1. ¬r Negated conclusion
      2. p ∨ r Premise
      3. p (1), (2)
      4. p → q Premise
      5. q Detachment (3), (4)
      6. q → r Premise
      7. r Detachment (5), (6)
      8. 0 (1), (7) □
         
         
5. Answer:
   
   1. Let W stand for "Wages will increase", I stand for "there will be in- flation", and C stand for "cost of living will increase". Therefore the argument is: W → I , ¬I → ¬C, W ⇒ C . The argument is invalid. The easiest way to see this is through a truth table, which has one case, the seventh, that this false. Let x be the conjunction of all premises.
      
      
   2. Let r stand for "the races are fixed", c stand for "casinos are crooked", t stand for "the tourist trade will decline", and p stand for "the police will be happy". Therefore, the argument is:
      
      (r ∨ c) → t, t → p, ¬p → ¬r.
      
      The argument is valid. Proof:
      
      1. t → p Premise
      2. ¬p Premise
      3. ¬t Indirect Reasoning (1), (2)
      4. (r ∨ c) → t Premise
      5. ¬(r ∨ c) Indirect Reasoning (3), (4)
      6. (¬r) ∧ (¬c) DeMorgan (5)
      7. ¬r Conjunction simplification (6) □
         
         
7. Answer: p₁→ p_kand p_k→ p_k+1 implies p₁→ p_k+1. It takes two steps to get to p₁→ p_k+1 from p₁→ p_kThis means it takes 2(100 − 1) steps to get to p₁→ p₁₀₀ (subtract 1 because p₁→ p₂ is stated as a premise). A final step is needed to apply detachment to imply p₁₀₀