Giving a formal proof of p ⇒(q ⇒ r) $\vdash$ (p ⇒ r)∨(q ⇒ r) using the rules of inference.

Question

I can prove this with semantic equivalences and truth tables but I'm struggling on the formal proof using rules of inference front.

Given its format I would assume it must finish on V-introduction which means using if-introduction at some point on p⇒r or q⇒r?

I've made 3 or 4 attempts now and I can't seem to get there!

Any advice or pointers in the right direction would be very much appreciated, Thanks!

Edit: We've been using Γ ├ B to mean ‘B can be formally proved from the set of Γ of assumptions’.

Edit: The rules at my disposal are:

• &-I
• &-E
• V-I
• V-E
• ⇔-I
• ⇔-E
• ⇒-I
• ⇒-E
• $\lnot$-I
• $\lnot$-E
• true-I
• false-E

Answer 1

Since $(a \Rightarrow b) \Leftrightarrow (\lnot a \vee (a \wedge b)) \Leftrightarrow (\lnot a \vee b ) $ for all $a,b$ by the material implication rule.

$$ [ p \Rightarrow (q \Rightarrow r) ] \Leftrightarrow [ \lnot p \vee (q \Rightarrow r) ] \Leftrightarrow [ \lnot p \vee ( \lnot q \vee r) ] \Leftrightarrow [ \lnot p \vee \lnot q \vee r ] $$ By the same rule, $$ [ (p \Rightarrow r ) \vee (q \Rightarrow r) ] \Leftrightarrow [ (\lnot p \vee r ) \vee ( \lnot q \vee r) ] \Leftrightarrow [ \lnot p \vee \lnot q \vee r] $$ Hence the result.

Answer 2

Your strategy of ending with a $\lor$ Introduction on either $p \rightarrow r$ or $q \rightarrow r$ is not going to work

If $p$ is true, but $q$ and $r$ is false, then $p \rightarrow (q \rightarrow r)$ is true, but $p \rightarrow r$ is false, so you will not be able to derive $p \rightarrow r$ by itself.

If $q$ is true, but $p$ and $r$ is false, then $p \rightarrow (q \rightarrow r)$ is true, but $q \rightarrow r$ is false, so you will not be able to derive $q \rightarrow r$ by itself.

Indeed, here is a general 'tip': if you ever have to prove a disjunction as your ultimate conclusion, then most likely you will not be able to prove either of then disjuncts by themselves!

So, what to do instead? I would recommend either:

1. Doing this by a proof by contradiction: if $(p \rightarrow r) \lor (q \rightarrow r)$ is false, then both $p \rightarrow r$ and $q \rightarrow r$ are false, hence $p$ and $q$ are true but $r$ is false, contradicting $p \rightarrow (q \rightarrow r)$

or:

2. Start by proving $p \lor \neg p$. And then: if $p$, then $q \rightarrow r$ using Modus Ponens ($\rightarrow$ Elim I suspect) between $p$ and the premise. And if $\neg p$, then you can show $p \rightarrow r$. So, you can show $(p \rightarrow r) \lor (q \rightarrow r)$ in either case (so now you do $\lor$ Intro within each subproof .. that is something that will frequently occur in formal proofs). So, using proof by cases (presumably your $\lor$ Elim), you definitely have $(p \rightarrow r) \lor (q \rightarrow r)$

Answer 3

$$p \to(q \to r) \vdash (p \to r)\lor(q \to r)$$ LHS:$$p \to(q \to r)$$ $$\neg p \lor (q\to r)$$ $$\neg p \lor (\neg q\lor r)$$ $$\color{red}{\neg p\lor r\lor \neg q}$$

RHS: $$(p\to r)\lor(q\to r)$$ $$(\neg p \lor r)\lor(\neg q \lor r)$$ $$\color{red}{\neg p\lor r\lor \neg q}$$