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

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
• What is the meaning of ├ ? – Robin Vogel Apr 20 '17 at 9:27
• @Robin Vogel It is the "provable" symbol. It is very classical if you have had lectures in logic... (en.wikipedia.org/wiki/List_of_logic_symbols) – Jean Marie Apr 20 '17 at 9:37
• @Robin Vogel We've been using Γ ├ B to mean ‘B can be formally proved from the set of Γ of assumptions’. I'll add this to the question if this isn't common notation. – Jonathan Apr 20 '17 at 9:38
• Use "vdash" for the "turnstyle" symbol $\vdash$ – Jean Marie Apr 20 '17 at 9:44
• You can use Material Implication rule. – Mauro ALLEGRANZA Apr 20 '17 at 9:55

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:

1. 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)$

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.

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