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