Prove that if $p,q,r$ are propositions, then the following rule of inference holds: $$\begin{array}{l}p\to q\\r\to s\\p\lor r\\\hline q\lor s\end{array}$$ Note 1. Prove it not using additional assumptions, such as $p\quad\text{Assumption}$.

Note 2. You must not use other inference rules than the following:

  • Modus Ponens $p\to q,\;p\therefore q$.
  • Mods Tollens $p\to q,\;\neg q\therefore\neg p$.
  • Hypothetical syllogism $p\to q,\;q\to r\therefore p\to r$.
  • Disjunctive syllogism $p\lor q,\;\neg p\therefore q$.
  • Combination law $p,\;q\therefore p\wedge q$.

And of course you can use logical laws, e.g, $p\equiv p\wedge(p\lor q)$, $p\to q\equiv\neg p\lor q$ etc.

I am stuck after I apply conditional equivalence:

$$ \begin{array}{lll} 1)&p\to q&\text{Premise}\\ 2)&r\to s&\text{Premise}\\ 3)&p\lor s&\text{Premise}\\ 4)&\neg p\lor q&\text{Conditional equivalence 1)}\\ 5)&\neg r\lor s&\text{Conditional equivalence 2)}\\ 6)&\text{????} \end{array} $$

What would be the next step?

  • 1
    $\begingroup$ Exactly what logical laws can you use? I think think of some that would make this trivial ... $\endgroup$ – Bram28 Apr 22 at 1:36
  • $\begingroup$ This is just a proof by cases: Case 1 = $p$, case 2 = $r$. In both cases, we can show that $q\lor s$ is true. $\endgroup$ – Dan Christensen Apr 23 at 15:18

Rewrite the $p \lor r$ as $\neg \neg p \lor r$, which can then be rewritten as $\neg p \to r$

Also, $p \to q$ can be rewritten as $\neg q \to \neg p$

And now it is just a bunch of Hypothetical Syllogisms and you're pretty much there.


$$ \begin{array}{lll} 1)&p\to q&\text{Premise}\\ 2)&r\to s&\text{Premise}\\ 3)&p\lor r&\text{Premise}\\ 4)&\neg \neg p\lor r&\text{Double Negation 3)}\\ 5)&\neg p\to r&\text{Conditional equivalence 4)}\\ 6)&\neg q\to \neg p&\text{Contraposition 1)}\\ 7)&\neg q\to r&\text{Hypothetical Syllogism 5,6)}\\ 8)&\neg q\to s&\text{Hypothetical Syllogism 2,7)}\\ 9)&\neg \neg q\lor s&\text{Conditional equivalence 8)}\\ 10)&q\lor s&\text{Double Negation 9)}\\ \end{array} $$

| cite | improve this answer | |
  • $\begingroup$ I have dealt with the proof a lot of time and you were capable to solve it in the way I was looking for. Thank you!! $\endgroup$ – manooooh Apr 22 at 5:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.