# Using natural deduction to prove P ∧ ¬Q ∧ (R → S), ¬(P → S) ⊢ R → Q

I would like to prove:

$1. \qquad P ∧ ¬Q ∧ R → S \qquad (Premise)$

$2. \qquad ¬(P → S) \qquad (Premise)$

$...$

$3. \qquad R → Q \qquad$

with access to these rules (http://imgur.com/kPZEYtG) However I am not sure how to proceed after this step: As a side note does anyone know how to enter $P ∧ ¬Q ∧ R → S, ¬(P → S) ⊢ R → Q$ into this great online natural deduction with steps tool I am not sure how to enter premises.

• The question appears to be wrong because $(¬Q \land R)$ and $(R \rightarrow Q)$ is a contradiction – Harambe Mar 21 '17 at 4:59
• Is the first premise supposed to say $P ∧ ¬Q ∧ R \rightarrow S$? – browngreen Mar 21 '17 at 5:04
• sorry fixed @Shanye2020 – Fidel Castro Mar 21 '17 at 5:32
• yes @browngreen – Fidel Castro Mar 21 '17 at 5:33
• Are you allowed to use deduction theorem? You can prove (P & -Q & R => S) => ((-(P=>S))=>(R=>Q)) with the tool. – ged Mar 21 '17 at 5:49

Here is a straightforward proof: • What tool is that? – Fidel Castro Mar 25 '17 at 3:18
• It's called Fitch, it comes with the book Language, Proof, and Logic. – Bram28 Mar 25 '17 at 12:18

We will try to make the Premises as True and Conclusion as False. (If we are not able to do this, then the inference is True)

To make the conclusion R→Q false, we must take R as True and Q as False (no other way we can make it false).

Considering these values of R and Q let us try to make the premises as True.

Premise 1: P ^ -Q ^ R→S

We have to take R as True and Q as false. So, P ^ -Q (True) ^ R (True)→S

This expression can be made True only by putting P as True and S as True. If any of these are False, Premise 1 becomes False.

Premise 2: -(P→S)

We have already taken P as True and S as True. So Premise 2 becomes False.

Therefore there is no such case when the Premises are True and Conclusion is False.

Hence the Inference is True. Proved.

Hope it helped.