Natural Deduction: $(p \lor q)\to r\vdash p \to r$ and $p\to\neg q\leftrightarrow(r\lor s),\neg s\vdash (p\land \neg q)\to r$

Question

I am having trouble applying Natural Deduction rule and solving these two questions. How do I start this.

\begin{align} \{(p\lor q)\to r\}&\vdash_{\sf ND} p\to r\\ \{p\to\neg q\leftrightarrow(r\lor s),\neg s\}&\vdash_{\sf ND} (p\land\neg q)\to r \end{align}

Answer 1

It oftentimes works out easiest to start by hypothesizing the antecedent or "left side" of the conditionals you want to prove. Then use the assumptions and the hypothesis to help you deduce the conclusion, and then use conditional introduction. So, if you want to prove (p→r), hypothesize p, and use p along with the assumptions given. Then deduce the consequent r. Finally use conditional introduction to get to the desired well-formed formula.

Answer 2

Here's a hint for the second question.

You need to think strategically. You are aiming to prove a conditional. The default way of establishing a conditional $A \to C$ is to temporarily assume the antecedent $A$ and aim for the consequent $C$. If you can get there, you can then discharge the assumption $A$ and derive the conditional.

So the expected overall shape of the proof will be (inserting what look like necessary brackets)

$p \to (\neg q \leftrightarrow (r \lor s)) \quad\quad\quad\text{Premiss}\\ \neg s \quad\quad\quad\quad\quad\quad\quad\quad\quad\ \ \ \text{Premiss}\\ \quad\quad|\quad (p \land \neg q)\quad\quad\quad\quad\text{Temporary assumption}\\ \quad\quad|\quad \ldots\\ \quad\quad|\quad r\\ (p \land \neg q) \to r \quad\quad\quad\ \ \quad\quad\text{Discharging temporary assumption}\\ $

It is obvious what you have to do next. Disassemble the conjunction!

$p \to (\neg q \leftrightarrow (r \lor s)) \\ \neg s \quad\quad\quad\quad\quad\quad\quad\quad\quad\ \\ \quad\quad|\quad (p \land \neg q) \\ \quad\quad|\quad p\\ \quad\quad|\quad \neg q\\ \quad\quad|\quad \ldots\\ \quad\quad|\quad r\\ (p \land \neg q) \to r \quad\quad\quad\ \ \\ $

Where do you go from here. You'll have to start using the initial premisses. So Which to use? Again it is obvious. Start using the initial premiss and use modus ponens, and you should get soon to

$p \to (\neg q \leftrightarrow (r \lor s)) \\ \neg s \quad\quad\quad\quad\quad\quad\quad\quad\quad\ \\ \quad\quad|\quad (p \land \neg q) \\ \quad\quad|\quad p\\ \quad\quad|\quad \neg q\\ \quad\quad|\quad \ldots\\ \quad\quad|\quad (r \lor s)\\ \quad\quad|\quad \ldots\\ \quad\quad|\quad r\\ (p \land \neg q) \to r \quad\quad\quad\ \ \\ $

So now you need to get from $\neg s$ and $r \lor s$ to $r$. How you do this will depend on the details of your ND system, but it is a standard "bookwork" proof. So you can fill in the dots yourself, I hope!