Q350 Inference Rules and Proofs - Handout 4: Sample Proofs for the Arguments in Handout 3

  1. 1. | A → B    
    2. |_ ¬B    
    3. | |_ A    
    4. | | B     → Elim: 1,3
    5. | | B ^ ¬B (Contradiction)     ^ Intro: 4, 2
    6. | ¬A     ¬ Intro: 3-5


  2. 1. |_ B → C    
    2. | |_ A ^ B    
    3. | | B     ^ Elim: 2
    4. | | C     → Elim: 1, 3
    5. | (A ^ B) → C     → Intro: 2-4


  3. 1. |_ A → B    
    2. | |_ A    
    3. | | B     → Elim: 1, 2
    4. | | B vC     v Intro: 3
    5. | A → (B v C)     → Intro: 2-4


  4. 1. | A v B
    2. | A → C
    3. |_ B → D
    4. | |_ A    
    5. | | C     → Elim: 2, 4
    6. | | C v D     v Intro: 5
    |    
    7. | |_ B    
    8. | | D     → Elim: 3, 7
    9. | | C v D     v Intro: 8
    10. | C v D     v Elim: 1, 4-6, 7-9


  5. 1. | A v B
    2. |_ ¬A
    3. | |_ A  
    4. | | |_ ¬B
    5. | | | A ^ ¬A (contradiction)   ^ Intro: 3, 2
    6. | | B ¬ Elim: 4-5
    |
    7. | |_ B  
    8. | B v Elim: 1, 3-6, 7-7


  6. 1. | (A v C) → (B ^ G)
    2. |_ A ^ (E ↔ D)
    3. | A ^ Elim: 2
    4. | A v C v Intro: 3
    5. | B ^ G → Elim: 1, 4
    6. | B ^ Elim: 5
    7. | A ^ B ^ Intro: 3, 6


  7. 1. | (P → R) → (M → P)    
    2. | (P v M) → (P → R)    
    3. |_ P v M    
    4. | P → R     → Elim: 2, 3
    5. M → P     → Elim: 1, 4
    6. | |_ P
    7. | | R v P         v Intro: 6
    |
    8. | |_ M
    9. | | P         → Elim: 5, 8
    10. | | R v P         v Intro: 9
    11. | R v P     v Elim: 3, 6-7, 8-10


  8. 1. (F ^ C) → (B v D)
    2. | (¬B v A) → F
    3. | (¬B v E) → C
    4. |_ ¬B
    5. ¬B v A v Intro: 4
    6. | F → Elim: 2, 5
    7. | ¬B v E v Intro: 4
    8. | C → Elim: 3, 7
    9. | F ^ C ^ Intro: 6, 8
    10. | B v D → Elim: 1, 9
    11. | D   DS: 10, 4


  9. 1. A ^ B    
    2. | (A v C) → D
    3. |_ D → F
    4. A ^ Elim: 1
    5. | A v C v Intro: 4
    6. | D → Elim: 2, 5
    7. | F     → Elim: 3, 6








  10. 1. A ^ B    
    2. | C ^ D
    3. |_ (A ^ C) → (E ^ F)
    4. A ^ Elim: 1
    5. C ^ Elim: 2
    6. | A ^ C ^ Intro: 4, 5
    7. | E ^ F → Elim: 3, 6
    8. | E     ^ Elim: 7
    9. | E v G     v Intro: 8


  11. 1. (A ^ B) ↔ (C ^ D)    
    2. | C v E
    3. | ¬E
    4. |_ C → D
    5. C D.S.: 2, 3
    6. | D → Elim: 4, 5
    7. | C ^ D ^ Intro: 5, 6
    8. | A ^ B     ↔ Elim: 1, 7
    9. | A     ^ Elim: 8


  12. 1. A v B    
    2. | ¬B
    3. | A → (C ^ D)
    4. | C ↔ (E v F)
    5. |_ ¬F
    6. A D.S.: 1, 2
    7. | C ^ D → Elim: 3, 6
    8. | C ^ Elim: 7
    9. | E v F     ↔ Elim: 4, 8
    10. | E     D.S.: 9, 5


  13. 1. A → C    
    2. | ¬C
    3. |_ ¬A → (C v D)
    4. ¬A M.T.: 1, 2
    5. | C v D → Elim: 3, 4
    6. | D D.S.: 5, 2


  14. 1. ¬(A v B) → ¬C    
    2. | C
    3. |_ ¬A
    4. A v B M.T.: 1, 2
    5. | B D.S.: 4, 3


  15. 1. A → ¬B    
    2. | B
    3. | (¬A v D) ↔ (E v F)
    4. |_  ¬F
    5. | ¬A M.T.: 1, 2
    6. | ¬A v D v Intro: 5
    7. | E v F ↔ Elim: 3, 6
    8. | E D.S.: 7, 4


  16. 1. | (A v B) → C    
    2. | ¬C v D    
    3. |_ A → ¬D    
    4. | |_ A    
    5. | | ¬D     → Elim: 3, 4
    6. | | A v B     v Intro: 4
    7. | | C     → Elim: 1, 6
    8. | | D     D.S.: 2, 7
    9. | | D ^ ¬D (Contradiction)     ^ Intro: 8, 5
    10. | ¬A     ¬ Intro: 4-9


  17. 1. | ¬B → ¬C    
    2. |_ A → C    
    3. | |_ A    
    4. | | C     → Elim: 2, 3
    5. | | B     M.T.: 1, 4
    6. | | B v D     v Intro: 5
    7. | A → (B v D)     → Intro: 3-6


  18. 1. | B ↔ (E v D)    
    2. |_ ¬E    
    3. | |_ B    
    4. | | E v D     ↔ Elim: 1, 3
    5. | | D     D.S.: 4, 2
    6. | | D v F     v Intro: 5
    7. | B → (D v F)     → Intro: 3-6
















  19. 1. | A v B    
    2. | A → C    
    3. | B ↔ D    
    4. |_ D → E    
    5. | |_ A
    6. | | C         → Elim: 2, 5
    7. | | C v E         v Intro: 6
    |
    8. | |_ B
    9. | | D         ↔ Elim: 3, 8
    10. | | E         → Elim: 4, 9
    11. | | C v E         v Intro: 10
    12. | C v E     v Elim: 1, 5-7, 8-11


  20. 1. | A → B    
    2. | C v ¬B    
    3. |_ A → ¬C    
    4. | |_ A    
    5. | | ¬C     → Elim: 3, 4
    6. | | B     → Elim: 1, 4
    7. | | ¬B     D.S.: 2, 5
    8. | | B ^ ¬B (Contradiction)     ^ Intro: 6, 7
    9. | ¬A     ¬ Intro: 4-8