2
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ Exactly what logical laws can you use? I think think of some that would make this trivial ... $\endgroup$
    – Bram28
    Apr 22, 2020 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$ Apr 23, 2020 at 15:18

1 Answer 1

4
$\begingroup$

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.

Formally:

$$ \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} $$

$\endgroup$
1
  • $\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, 2020 at 5:47

You must log in to answer this question.

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