4

I have the following formula and need to prove it with natural deduction:

$$p \to (\neg q \leftrightarrow (r \lor s)), \neg s \vdash (p \land \neg q) \to r$$

I was able to get the below finished but can't fill in what is missing.

1.   p -> (~q <-> (r v s))
2.   ~s
3.  | (p ^ ~q)              (assumption)
4.  | p                    (elim ^) 3
5.  | ~q                    (elim ^) 3
6.  | (~q <-> (r v s))      (elim ->) 1.
7.  | (r v s)              (elim ->) 6.

n-1.| r 

n.  (p ^ ~q) -> r
Lord_Farin
  • 17,743
Joel Malchiondo
  • 41

2 Answers2

4

You have $\;(7): \quad\mid\;\;r \lor s$, and you have $\;(2): \;\lnot s$.

Can you see how this gives $\;(8): \quad \mid \;\; r\quad $?

We can use the rule of inference known as the disjunctive syllogism to obtain $r$

Then, you have shown that the assumption $(p \land \lnot q)$ implies $r$, i.e., you're finished with $$(9): (p \land \lnot q) \rightarrow r$$

amWhy
  • 209,954
  • 1
    I looked in my course notes and it does not state the disjunctive syllogism rule anywhere. could you provide an alternate solution? – Joel Malchiondo Oct 08 '13 at 20:49
  • Some call it disjunction elimination; Others reserve the term disjunction elimination the rule where you assume each of $r$ and $s$ and derive $r$. That's immediate if you assume $r$. If you assume $s$, you derive a contradiction: $\lnot s \land s$, and can therefore assert anything, which in this case, you can assert r. This gives you $r\rightarrow r$ and $s\rightarrow r$ which means, by $\lor$-E, $(r\lor s)\rightarrow r$. Therefore with the premise $r \lor s$, you have $r$ by $\rightarrow$-E. – amWhy Oct 08 '13 at 20:56
2

So, I'll guess you have disjunction elimination. You have the disjunction (r v s), and you want r. What happens if you assume r? Can you then get r? What happens if you assume s? Can you then get r?

Tell me if you need more help than that.

Doug Spoonwood
  • 11,211