Proving a certain theorem in L1 logic.

logicpropositional-calculus

Description of Logic $L_1$:

Primary connectives: $\lnot$ , $\lor$

$A\rightarrow B$ is $\lnot A \lor B$

Axioms:
(A1) $B \lor B \rightarrow B$
(A2) $B \rightarrow B \lor C$
(A3) $B \lor C \rightarrow C \lor B$
(A4) $(C \rightarrow D ) \rightarrow (B \lor C \rightarrow B \lor D)$

The only rule of inference is $MP$

With these , I was able to prove the following theorem about $L_1$

a. $B \rightarrow C \vdash_{L_1} D \lor B \rightarrow D \lor C$
b. $\vdash_{L_1} ( B \rightarrow C ) \rightarrow ((D \rightarrow B) \rightarrow (D \rightarrow C))$
c. $D \rightarrow B , B \rightarrow C \vdash_{L_1} D \rightarrow C$
d. $\vdash_{L_1} B \rightarrow B$
e. $\vdash_{L_1} B \lor \lnot B$
f. $\vdash_{L_1} B \rightarrow \lnot \lnot B$
g. $\vdash_{L_1} \lnot B \rightarrow (B \rightarrow C)$
h. $\vdash_{L_1} B \lor (C \lor D) \rightarrow ((C \lor (B \lor D)) \lor B)$

But I got stumped at the next question:

i. $\vdash_{L_1} ((C \lor (B \lor D)) \lor B) \rightarrow (C \lor (B \lor D))$

I tried every theorem and axiom relentlessly (except the ones with negation) to prove this theorem.My best guess is that it is either so easy that I am missing out. Or , it imvolves theorems with negation.

Can someone give me a clue about this?

Best Answer

We have to use (A4) to "import" all the needed transformations:

  1. $(D \lor B) \to (B \lor D)$ --- (A3)

Thus, using (A4), we have:

  1. $[C \lor (D \lor B)] \to [C \lor (B \lor D)]$.

Consider now: $[(C \lor D) \lor (B \lor B)]$. By (A1) using (A4) we get:

  1. $[(C \lor D) \lor (B \lor B)] \to [(C \lor D) \lor B]$

We need also the Associativity Lemma:

$\vdash [(A \lor B) \lor C)] \to [A \lor (B \lor C)]$ to get, by (b):

  1. $[(C \lor D) \lor (B \lor B)] \to [C \lor (D \lor B)]$,

Using 2) above and (b) again we get:

  1. $[(C \lor D) \lor (B \lor B)] \to [C \lor (B \lor D)]$.

Now, the same approach must be used to derive:

  1. $[(C ∨ (B ∨ D)) ∨ B] \to [(C \lor D) \lor (B \lor B)].$

Proof of Associativity:

Lemma 1: if $\vdash A \to C$ and $\vdash B \to C$, then $\vdash A \lor B \to C$.

  1. $B \to C$

  2. $(A \lor B) \to (C \lor A)$ --- from 1) and (A4) with (A3), by MP

  3. $A \to C$

  4. $(C \lor A) \to (C \lor C)$ --- as above

  1. $(A \lor B) \to C$ --- from 2) and 4) and (A1) using (b).

Lemma 2: if $\vdash A \to B$, then $A \to (C \lor B)$ and $A \to (B \lor C)$

  1. $A \to B$

  2. $A \to (B \lor C)$ --- from 1) and (A2) using (b)

  3. $A \lor (C \lor B)$ --- from 2) and (A3).

Lemma:

  1. $A \to [A \lor (B \lor C)]$ --- (A2)

  2. $B \to (B \lor C)$ --- (A2)

  3. $B \to [A \lor (B \lor C)]$ --- from 2) by Lemma 2

  4. $(A \lor B) \to [A \lor (B \lor C)]$ --- from 1) and 3) by Lemma 1

  5. $C \to [A \lor (B \lor C)]$ --- from $\vdash C \to C$ [your (d)] and Lemma 2 twice.

  1. $\vdash [(A \lor B) \lor C] \to [A \lor (B \lor C)]$ --- from 4) and 5) by Lemma 1
Related Question