I'm working through The Science of Programming by David Gries. This question is #18 in section 3.3.
Prove $((P \land \lnot Q) \to Q) \to (P \to Q)$
Using the natural deduction system here is my proof.
$(P \land \lnot Q) \to Q)$ (premise)
From $P$ infer $Q$ (subproof)
2.1 $P$ (premise)
2.2 From $\lnot Q$ infer $Q$ (subproof)
2.2.1 $\lnot Q$ (premise)
2.2.2 $P \land \lnot Q$ ($\land$-Introduction, 2.1, 2.2.1)
2.2.3 $Q$ ($\to$-E, 1, 2.2.2)
- $P \to Q$ ($\to$-I, 2)
Is this correct? I feel like I'm really stretching in trying to prove $P\to Q$ especially with the subproof of $\lnot Q \to Q$.