# Prove constructive dilemma without using additional assumptions

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?

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