[Math] Prove constructive dilemma without using additional assumptions

formal-proofslogicproof-writingpropositional-calculus

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?

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