• $p \land \lnot s$
  • $q \to (r \to s)$


  • $(p \to q) \to \lnot r$

Use rules of inference to show the above argument is valid.

I only manage to get $(p \to q) \to (p \land \lnot r)$.

  1. $p \land \lnot s$ Assumption
  2. $q \to (r \to s)$ Assumption
  3. $\lnot q \lor (\lnot r \lor s)$ from 2, implication rule
  4. $\lnot s$ from 1, conjunctive simplification
  5. $\lnot q \lor \lnot r$ from 3,4 disjunctive syllogism
  6. $p$ from 1, conjunctive simplification
  7. $p \land (\lnot q \lor \lnot r)$ from 5,6 conjunction
  8. $(p \land \lnot q) \lor (p \land \lnot r)$ from 7, Distributive rule
  9. $(p \to q) \to (p \land \lnot r)$ from 8, implication rule
  • 1
    $\begingroup$ It's not really enough to just say "rules of inference". There are lots of proof systems out there, each with its own set of permissible rules of inference. What inference rules are permitted? $\endgroup$ Apr 26, 2013 at 20:17

3 Answers 3


Joshua Taylor has given a correct proof using one common set of inference rules, but it appears, from the work you've shown, that your system of inference rules is a little different. So let me try it with rules that look like what you used. I'll start with the conclusion, $(p\to q)\to(p\land\neg r)$ that you arrived at. The "implication rule" that you used to go from 2 to 3 should allow me to convert this to $(\neg(p\to q))\lor(p\land\neg r)$. Next, a distributive law (admittedly dual to the one you used going from 7 to 8, so I hope both versions of distributivity are available to you) gives me $[(\neg(p\to q))\lor p]\land[(\neg(p\to q))\lor\neg r]$. Then conjunctive simplification, which got you from 1 to 4, should produce $(\neg(p\to q))\lor\neg r$. Finally, the implication rule, now in the other direction, as in your inference from 8 to 9, gives $(p\to q)\to\neg r$, as desired.

  • $\begingroup$ Thank you so much. All answers given here seems to be correct. Didn't know there are so many ways to prove it. $\endgroup$ Apr 26, 2013 at 21:01
  • $\begingroup$ Nice, Andreas. This is the approach I took, too, "picking up where the OP left off"...Was just too tired to type it out. So +1 for doing that! $\endgroup$
    – amWhy
    Apr 26, 2013 at 21:05

You haven't specified what inference rules can be used, so here's a natural deduction argument of that demonstrates the consequence:

  1. $p \land \lnot s$ Given.
  2. $q \to (r \to s)$ Given.
    • $p \to q$ Assumption.
    • $p$ Conjunction elimination from 1.
    • $q$ Conditional elimination (modus ponens) from 3 and 4.
    • $r \to s$ Conditional elimination from 2 and 5.
      • $r$ Assumption.
      • $s$ Conditional elimination from 6 and 7.
      • $\lnot s$ Conjunction elimination from 1.
      • $\bot$ Contradiction introduction from 8 and 9.
    • $\lnot r$ Negation introduction from 7–10.
  3. $(p \to q) \to \lnot r$ Conditional introduction from 3–11.

I'm going to solve it assuming that you have a very large and relatively standard set of inference rules.

  1. Assume $r$ for proof of a conditional. (Ultimately this will be the conditional $r\rightarrow \neg(p\rightarrow q)$)

  2. Infer $\neg s$ from the first premise.

  3. Infer $r \land \neg s$ from 1 and 2.

  4. Infer $\neg(\neg r \lor s)$ by De Morgan's and 3.

  5. Infer $\neg (r\rightarrow s)$ by equivalence of 4.

  6. Infer $\neg q$ from 5 and the second premise using Modus Tollens.

  7. Infer $p$ from the first premise.

  8. Infer $p\land \neg q$ from 6 and 7.

  9. Infer $\neg(\neg p \lor q)$ by De Morgan's of 8.

  10. Infer $\neg(p\rightarrow q)$ by equivalence of 9.

  11. Therefore, by lines 1 through 10, we have shown $r\rightarrow \neg(p\rightarrow q)$.

  12. By equivalence of contraposition with 11, infer $(p\rightarrow q)\rightarrow r$.

  • $\begingroup$ It would help for readability purposes to list, prior to the assumption: 1. first premise; 2. second premise; 3. assumption you've numbered as 1; 4 - 14. from what you've numbered as 2 - 12. $\endgroup$
    – amWhy
    Apr 26, 2013 at 20:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .