How to prove $p\land q\to \neg r \vdash r \to p \to \neg q$ using natural deduction?

60 Views Asked by At

I'm having a lot of trouble proving the sequent below with Natural Deduction rules. I'm new to this and find it difficult to come up with proof strategies. The first thing I do is to assume $r$ but really confused on where I could go from there.

The sequent: $$(p\land q)\to \neg r \vdash r \to (p \to \neg q)$$

Thanks so much, any help appreciated!

1

There are 1 best solutions below

6
On BEST ANSWER

Your first step seems good, assume $r$ Now you want to show that $p\to\neg q$, so what do you want to do? well you are trying to prove an implication again, so assume $p$ and show $\neg q$!

You are given that $p\wedge q\to \neg r$ if you already have that $(a\to b) \leftrightarrow (\neg b \to \neg a)$ then this would be a good place to use it. If you dont have this, then you can prove $\neg(p\wedge q)$ using contradiction. (using the fact that you are assuming $r$)

once you have $\neg(p\wedge q)$ you can now just assume $p$ and prove $\neg q$ again by contradiction by assuming $q$.