Disjunction Elimination Proof

988 Views Asked by At

P∨(Q∨R) ⊢ Q∨(P∨R)

Proof:

1.) P∨(Q∨R) Assumption

2.) P Assumption

3.) P∨R 2.) Disjunction Introduction

4.) Q∨(P∨R) 3.) Disjunction Introduction

5.) Q∨R Assumption

6.) Q Assumption

7.) Q∨(P∨R) 6.) Disjunction Introduction

8.) R Assumption

9.) P∨R .8) Disjunction Introduction

10.) Q∨(P∨R) .9) Disjunction Introduction

11.) Q∨(P∨R) 5.), 6.), 7.), 8.), 10.) Disjunction Elimination

12.) Q∨(P∨R) 1.), 2.), 4.), 5.), 11.) Disjunction Elimination

I'm having a hard time understanding this proof. Why is it necessary to state line 5? Why is line 11 stated again in line 12?


1

There are 1 best solutions below

1
On BEST ANSWER

I'm having a hard time understanding this proof. Why is it necessary to state line 5?

If you have $A\vee B$ and wish to show it proves $C$ -- that is $A\vee B\vdash C$ -- then you may use Disjunctive Elimination.

Disjunctive Elimination is the rule that:

$$A\vee B, A\to C, B\to C \vdash C$$

So Lines 2 and 5 are where you take(assume) two halves of the disjunction $P \;\vee\; (Q\vee R)$ and aim to show that they prove the same thing.   If you can do that you have:

$$\overbrace{\underbrace{P\vee (Q\vee R)}_\text{line 1.)}, \underbrace{P\to Q\vee(P\vee R)}_\text{Line 2.), 3.), 4.)}, \underbrace{(Q\vee R)\to Q\vee(P\vee R)}_\text{Line 5), 11.)} \vdash Q\vee(P\vee R)}^\text{Line 12.)}$$

Why is line 11 stated again in line 12?

Because you use Disjunctive Elimination to conclude line 11 from the assumption of $Q\vee R$.

Does this indentation help?

$\require{cancel}\begin{array}{l|l} 1.) & P∨(Q∨R) \qquad\cancelto{\text{Premise}}{\text{Assumption }} \\ & \begin{array}{l|l} 2.) & P \qquad\text{Assumption} \\ 3.) & P∨R \qquad 2.)\text{ Disjunction Introduction} \\\hline 4.) & Q∨(P∨R) \qquad 3.)\text{ Disjunction Introduction} \end{array} \\ & \begin{array}{l|l} 5.) & Q∨R \qquad\text{Assumption } \\ & \begin{array}{l|l} 6.) & Q \qquad\text{Assumption} \\ \hline 7.) & Q∨(P∨R) \qquad 6.)\text{ Disjunction Introduction} \end{array} \\ & \begin{array}{l|l} 8.) & R \qquad\text{Assumption} \\ 9.) & P∨R \qquad 8)\text{ Disjunction Introduction} \\ \hline 10.) & Q∨(P∨R) \qquad 9)\text{ Disjunction Introduction} \end{array} \\ \hline 11.) & Q∨(P∨R) \qquad\text{5.), 6.), 7.), 8.), 10.) Disjunction Elimination} \end{array} \\ \hline 12.) & Q∨(P∨R) \qquad\text{1.), 2.), 4.), 5.), 11.) Disjunction Elimination} \end{array}$


$$ \dfrac{ (1): P\vee (Q\vee R) }{ \dfrac{ \dfrac{ \dfrac{ (2): P }{ (3):P\vee R }{\small\text{DI}} }{ (4): Q\vee (P\vee R) }{\small\text{DI}} \quad,\quad \dfrac{ \dfrac{ (5):(Q\vee R) }{ \dfrac{ (6):Q }{ (7):Q\vee(P\vee R) }{\small\text{DI}} \quad,\quad \dfrac{ \dfrac{ (8):R }{ (9):P\vee R }{\small\text{DI}} }{ (10):Q\vee(P\vee R) }{\small\text{DI}} } }{ (11):Q\vee(P\vee R) }{\small\text{DE}} }{ (12):Q\vee (P\vee R) }{\small\text{DE}} } $$