[Math] Use rules of inference to show

logicpropositional-calculus

Premises:

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

Conclusion:

  • $(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

Best Answer

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.

Related Question