Natural Deduction Proof
1.
1 ~Y ⇒ ~L
2 W v ~Y
3 W ⇒ ~B
/ ~B v ~L
2.
1 ~U • (G = ~T)
2 (~U v D) ⇒ (W • ~R)
/ W • ~U
3.
1 (M ⇒ P) ⇒ ~P
2 H ⇒ P
3 M ⇒ H
/ ~H
4.
1 ~Z
2 S
3 Zv(S ⇒ H)
/ H
To solve each of the given natural deduction proofs, we will walk through the steps of the proof and explain the rules and reasoning used.
1. Proof: ~B v ~L
1. ~Y ⇒ ~L (Given)
2. W v ~Y (Given)
3. W ⇒ ~B (Given)
To obtain ~B v ~L as the goal, we can use a proof by contradiction.
4. Assume B. By the rule of indirect proof (proof by contradiction), we assume the opposite of what we want to prove and then derive a contradiction.
5. Since ~Y ⇒ ~L (premise 1) and W v ~Y (premise 2), we can derive ~Y using the disjunction elimination rule (proof by cases).
6. From ~Y and W ⇒ ~B (premise 3), we can derive ~B using the modus ponens rule (if you have ~Y and W ⇒ ~B, you can infer ~B).
7. This leads to a contradiction since we initially assumed B in step 4. So, we can conclude ~B using proof by contradiction.
8. Since we derived ~B, we can use the disjunction introduction rule (~A ⇒ A v B).
9. Therefore, we have ~B v ~L as our desired conclusion.
2. Proof: W • ~U
1. ~U • (G = ~T) (Given)
2. (~U v D) ⇒ (W • ~R) (Given)
To prove W • ~U, we can use the conjunction introduction rule, which allows us to introduce a conjunction when we have both parts of the conjunction.
3. From ~U • (G = ~T) (premise 1), we can derive ~U using the simplification rule (if you have A • B, you can infer A).
4. From ~U • (G = ~T) (premise 1), we can derive G = ~T using the simplification rule (if you have A • B, you can infer B).
5. Since ~U (step 3) and (~U v D) ⇒ (W • ~R) (premise 2), we can derive W • ~R using the modus ponens rule (if you have A and A ⇒ B, you can infer B).
6. From W • ~R, we can then derive W using the simplification rule (if you have A • B, you can infer A).
7. Now we have both W and ~U, so we can use the conjunction introduction rule (if you have A and B, you can infer A • B).
8. Therefore, we have W • ~U as our desired conclusion.
3. Proof: ~H
1. (M ⇒ P) ⇒ ~P (Given)
2. H ⇒ P (Given)
3. M ⇒ H (Given)
To prove ~H, we need to apply the rule of indirect proof or proof by contradiction.
4. Assume H. By assuming H and deriving a contradiction, we can conclude ~H.
5. From H ⇒ P (premise 2) and M ⇒ H (premise 3), we can derive M ⇒ P using the transitivity rule (if you have A ⇒ B and B ⇒ C, you can infer A ⇒ C).
6. Then, using the assumption H and M ⇒ P (step 5), we can derive P using the modus ponens rule (if you have A and A ⇒ B, you can infer B).
7. From (M ⇒ P) ⇒ ~P (premise 1) and M ⇒ P (step 6), we can derive ~P using the modus ponens rule.
8. This leads to a contradiction since we derived both P and ~P. So, we can conclude ~H using proof by contradiction.
9. Therefore, our desired conclusion is ~H.
4. Proof: H
1. ~Z (Given)
2. S (Given)
3. Z v (S ⇒ H) (Given)
To prove H, we need to apply a proof by cases (disjunction elimination) to the premise Z v (S ⇒ H) and derive H in both cases.
4. Assume Z. By assuming Z, we need to derive H.
5. This leads to a contradiction since we are assuming ~Z (premise 1). So, Z cannot be true.
6. Now, assume S ⇒ H. By assuming S ⇒ H, we need to derive H.
7. From S (premise 2) and S ⇒ H (assumption in step 6), we can derive H using the modus ponens rule.
8. Therefore, in both cases, we have derived H.
9. Using disjunction elimination, we can apply the rule to Z v (S ⇒ H) (premise 3) and the two subproofs for the cases Z and S ⇒ H.
10. Since we derived H in both cases, we can conclude H using the disjunction elimination rule.
11. Therefore, our desired conclusion is H.