Step 6 Tutorial
When doing step 6 problems keep in mind our UH system symbolic reasoning goals. As in life, you are not expected to solve every problem right away. Most important for the UH hallmarks is that you show that you understand the proof process and appreciate the need for precision. Thus, like step 3, minimally you should be able to show that you can take a set of premises in step 6 and derive as many logically valid steps as you can. You may not be successful right away in deriving the conclusion.
Provided that you have done well with steps 1-5, it should be easy now to derive lots of steps. If you cannot look at premises and see at least some rules to apply, it probably means that you need more work in steps 1 and 4. The frustration for students is usually that there are so many things that one can do with nineteen rules. This tutorial will mostly focus on seeing how to do as many steps as possible. It will eventually show how to solve the problem below in 20 steps, but keep in mind that if you were only able to see about half of these steps that would be good on an exam. Solving problems usually takes time and insight, as well as preparation. These tutorials, the book, and the lectures hopefully will help with the preparation.
Suppose we have the following argument to prove for validity.
1. C ⊃ (A ≡~B)
2. Z • C
3. ~B ⊃ (S • H)
4. P ⊃ ~S / ∴ ~(P • A)
Any of these premises ring a bell? See the hints below.
1. C ⊃ (A ≡~B) -- Hint 1
2. Z • C ----- Hint 2
3. ~B ⊃ (S • H)
4. P ⊃ ~S / ∴ ~(P • A)
Since it is usually best to start a proof as simply as possible, suppose we applied Hint 2 above. Here is what we would have:
1. C ⊃ (A ≡~B)
2. Z • C
3. ~B ⊃ (S • H)
4. P ⊃ ~S / ∴ ~(P • A)
5. Z (2) Simp.
6. C • Z (5) Com.
7. C (6) Simp.
Notice that now we could do the MP suspected in Hint 1 and then the Equivalence as follows:
1. C ⊃ (A ≡~B)
2. Z • C
3. ~B ⊃ (S • H)
4. P ⊃ ~S / ∴ ~(P • A)
5. Z (2) Simp.
6. C • Z (5) Com.
7. C (6) Simp.
8. A ≡~B (1)(7) MP
9. (A ⊃ ~B) • (~B ⊃ A) (8) Equiv. --- Hint 3
Let's apply Hint 3. Here is what we would have:
1. C ⊃ (A ≡~B)
2. Z • C
3. ~B ⊃ (S • H)
4. P ⊃ ~S / ∴ ~(P • A)
5. Z (2) Simp.
6. C • Z (5) Com.
7. C (6) Simp.
8. A ≡~B (1)(7) MP
9. (A ⊃ ~B) • (~B ⊃ A) (8) Equiv.
10. A ⊃ ~B (9) Simp.
11. (~B ⊃ A) • (A ⊃ ~B) (9) Com.
12. ~B ⊃ A (11) Simp.
13. ??
Ok, pretty good. We have developed 8 valid steps. What now? Well notice that we have not used lines 3 and 4 yet. How can we get those lines involved?
1. C ⊃ (A ≡~B)
2. Z • C
3. ~B ⊃ (S • H) --- Hint 4
4. P ⊃ ~S / ∴ ~(P • A)
5. Z (2) Simp.
6. C • Z (5) Com.
7. C (6) Simp.
8. A ≡~B (1)(7) MP
9. (A ⊃ ~B) • (~B ⊃ A) (8) Equiv.
10. A ⊃ ~B (9) Simp.
11. (~B ⊃ A) • (A ⊃ ~B) (9) Com.
12. ~B ⊃ A (11) Simp.
13. ??
Ok, let's try the subroutine noted in Hint 4. Here is what we would get:
1. C ⊃ (A ≡~B)
2. Z • C
3. ~B ⊃ (S • H)
4. P ⊃ ~S / ∴ ~(P • A)
5. Z (2) Simp.
6. C • Z (5) Com.
7. C (6) Simp.
8. A ≡~B (1)(7) MP
9. (A ⊃ ~B) • (~B ⊃ A) (8) Equiv.
10. A ⊃ ~B (9) Simp.
11. (~B ⊃ A) • (A ⊃ ~B) (9) Com.
12. ~B ⊃ A (11) Simp.
13. B v (S • H) (3) Impl.
14. (B v S) • (B v H) (13) Dist.
15. B v S (14) Simp.
16. (B v H) • (B v S) (14) Com.
17. B v H (16) Simp.
18. ?
Pretty good, but now what? We have not used line 4 yet. Successful proofs get as many premises to work together and/or with their derivations as possible. So, we should be looking at ways to get lines 10, 12, 15, and/or 17 to work with line 4. Notice that line 4 has (⊃) as a connective, as well as lines 10 and 12. A wise move would be to change lines 15 and 17 also into (⊃). This would mean applying Implication to those lines.
Let's try it and see what we get.
1. C ⊃ (A ≡~B)
2. Z • C
3. ~B ⊃ (S • H)
4. P ⊃ ~S / ∴ ~(P • A)
5. Z (2) Simp.
6. C • Z (5) Com.
7. C (6) Simp.
8. A ≡~B (1)(7) MP
9. (A ⊃ ~B) • (~B ⊃ A) (8) Equiv.
10. A ⊃ ~B (9) Simp.
11. (~B ⊃ A) • (A ⊃ ~B) (9) Com.
12. ~B ⊃ A (11) Simp.
13. B v (S • H) (3) Impl.
14. (B v S) • (B v H) (13) Dist.
15. B v S (14) Simp.
16. (B v H) • (B v S) (14) Com.
17. B v H (16) Simp.
18. ~B ⊃ S (15) Impl.
19. ~B ⊃ H (17) Impl.
This looks promising now. Notice lines 10 and 18.
1. C ⊃ (A ≡~B)
2. Z • C
3. ~B ⊃ (S • H)
4. P ⊃ ~S / ∴ ~(P • A)
5. Z (2) Simp.
6. C • Z (5) Com.
7. C (6) Simp.
8. A ≡~B (1)(7) MP
9. (A ⊃ ~B) • (~B ⊃ A) (8) Equiv.
10. A ⊃ ~B (9) Simp. ----- Hint 5
11. (~B ⊃ A) • (A ⊃ ~B) (9) Com.
12. ~B ⊃ A (11) Simp.
13. B v (S • H) (3) Impl.
14. (B v S) • (B v H) (13) Dist.
15. B v S (14) Simp.
16. (B v H) • (B v S) (14) Com.
17. B v H (16) Simp.
18. ~B ⊃ S (15) Impl. ----- Hint 5
19. ~B ⊃ H (17) Impl.
Let's do the HS and see what we have.
1. C ⊃ (A ≡~B)
2. Z • C
3. ~B ⊃ (S • H)
4. P ⊃ ~S / ∴ ~(P • A)
5. Z (2) Simp.
6. C • Z (5) Com.
7. C (6) Simp.
8. A ≡~B (1)(7) MP
9. (A ⊃ ~B) • (~B ⊃ A) (8) Equiv.
10. A ⊃ ~B (9) Simp.
11. (~B ⊃ A) • (A ⊃ ~B) (9) Com.
12. ~B ⊃ A (11) Simp.
13. B v (S • H) (3) Impl.
14. (B v S) • (B v H) (13) Dist.
15. B v S (14) Simp.
16. (B v H) • (B v S) (14) Com.
17. B v H (16) Simp.
18. ~B ⊃ S (15) Impl
19. A ⊃ S (10)(18) HS
Here we could be overwhelmed with so many steps. But we remember that we have not used line 4 yet and line 19 is the product of getting many premises to work together. So we focus on lines 4 and 19. See a possible subroutine? See the hint below.
1. C ⊃ (A ≡~B)
2. Z • C
3. ~B ⊃ (S • H)
4. P ⊃ ~S / ∴ ~(P • A)
5. Z (2) Simp.
6. C • Z (5) Com.
7. C (6) Simp.
8. A ≡~B (1)(7) MP
9. (A ⊃ ~B) • (~B ⊃ A) (8) Equiv.
10. A ⊃ ~B (9) Simp.
11. (~B ⊃ A) • (A ⊃ ~B) (9) Com.
12. ~B ⊃ A (11) Simp.
13. B v (S • H) (3) Impl.
14. (B v S) • (B v H) (13) Dist.
15. B v S (14) Simp.
16. (B v H) • (B v S) (14) Com.
17. B v H (16) Simp.
18. ~B ⊃ S (15) Impl
19. A ⊃ S (10)(18) HS -- Hint 6
Let's do the subroutine.
1. C ⊃ (A ≡~B)
2. Z • C
3. ~B ⊃ (S • H)
4. P ⊃ ~S / ∴ ~(P • A)
5. Z (2) Simp.
6. C • Z (5) Com.
7. C (6) Simp.
8. A ≡~B (1)(7) MP
9. (A ⊃ ~B) • (~B ⊃ A) (8) Equiv.
10. A ⊃ ~B (9) Simp.
11. (~B ⊃ A) • (A ⊃ ~B) (9) Com.
12. ~B ⊃ A (11) Simp.
13. B v (S • H) (3) Impl.
14. (B v S) • (B v H) (13) Dist.
15. B v S (14) Simp.
16. (B v H) • (B v S) (14) Com.
17. B v H (16) Simp.
18. ~B ⊃ S (15) Impl
19. A ⊃ S (10)(18) HS
20. ~S ⊃ ~A (19) Trans.
21. P ⊃ ~A (4)(20) HS
Now we must be getting close. How do we get from 21 to the conclusion? We need to make line 21 into an (v) statement before we have any chance of getting ~(P • A). Implication let's us do that and here would be one way to finish.
1. C ⊃ (A ≡~B)
2. Z • C
3. ~B ⊃ (S • H)
4. P ⊃ ~S / ∴ ~(P • A)
5. Z (2) Simp.
6. C • Z (5) Com.
7. C (6) Simp.
8. A ≡~B (1)(7) MP
9. (A ⊃ ~B) • (~B ⊃ A) (8) Equiv.
10. A ⊃ ~B (9) Simp.
11. (~B ⊃ A) • (A ⊃ ~B) (9) Com.
12. ~B ⊃ A (11) Simp.
13. B v (S • H) (3) Impl.
14. (B v S) • (B v H) (13) Dist.
15. B v S (14) Simp.
16. (B v H) • (B v S) (14) Com.
17. B v H (16) Simp.
18. ~B ⊃ S (15) Impl
19. A ⊃ S (10)(18) HS
20. ~S ⊃ ~A (19) Trans.
21. P ⊃ ~A (4)(20) HS
22. ~~P ⊃ ~A (21) DN -- Note
23. ~P v ~A (22) Impl.
24. ~(P • A) (23) DeM. --- !!!!
Inspecting this proof carefully shows that we have some extra lines. No problem. We were probing with subroutines.
If you are still struggling, can you write out the scratch paper summary for ever proof line above as we did in the previous tutorials? It would help with preparation. For instance, for lines 5-7, we have:
(2) Z • C
/ ∴ (5) Z Simp.
p • q
/ ∴ p
(2) Z • C
/ ∴ (6) C • Z Com.
(p • q) ≡ (q • p)
(6) C • Z
/ ∴ (7) C Simp.
p • q
/ ∴ p
See if you can do lines 8-24. If not, you probably need to go back to steps 1 and 4.