1
$\begingroup$

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
$\endgroup$
  • $\begingroup$ What is the meaning of ├ ? $\endgroup$ – Robin Vogel Apr 20 '17 at 9:27
  • 2
    $\begingroup$ @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) $\endgroup$ – Jean Marie Apr 20 '17 at 9:37
  • $\begingroup$ @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. $\endgroup$ – Jonathan Apr 20 '17 at 9:38
  • 2
    $\begingroup$ Use "vdash" for the "turnstyle" symbol $\vdash$ $\endgroup$ – Jean Marie Apr 20 '17 at 9:44
  • $\begingroup$ You can use Material Implication rule. $\endgroup$ – Mauro ALLEGRANZA Apr 20 '17 at 9:55
0
$\begingroup$

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)$
$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.