Examples of Proofs

Examples of Deductive Proofs

Lemma 2. For any well-formed formula B, ~~B→ B.

Proof. We shall construct a proof in L of ~~B → B.

1.	(~ B → ~~B) → ((~B → B)) → B)	Instance of Axiom A3 by Substituting ~B for A in Axiom A3.
2.	~B → ~B	By Lemma 1.
3.	(~B → B)) → B	By Corollary II.
4.	~~B → (~B → ~~B)	Instance of Axiom A1 by substituting ~~B for A and ~B for B in Axiom A1.
5.	~~B → B	From 3 and 4 by hypothetical syllogism - Corollary I.

So, we have

~~B → B

And by applying the Deduction Theorem, we get

~~B → B

Therefore, for any well-formed formula B, (~~B → B) is theorem of L.

This completes the proof.

Lemma 3. For any well-formed formula B, B → ~~B.

Proof. We shall construct a proof in L of B → ~~B.

1.	(~~~B → ~B) → ((~~~B → B) → ~~B)	Instance of Axiom 3 by Substituting ~~B for B and B for A in the Axiom 3.
2.	~~~B → B	By Lemma 2.
3.	(~~~B → B) → ~~B	From 1 and 2 by modus ponens.
4.	B → (~~~B → B)	Instance of Axiom A1 by substituting ~~~B for B and B for A in Axiom A1.
5.	B → ~~B	Form 3 and 4 by hypothetical syllogism - Corollary I.

So, we have

B → ~~B

And by applying the Deduction Theorem, we get

B → ~~B

Therefore, for any well-formed formula B, (B → ~~B) is theorem of L.

This completes the proof.

Lemma 4. For any well-formed formulas A and B, ~A → (A → B).

Proof. We shall construct a proof in L of ~A → (A → B).

1.	~A	Hypothesis.
2.	A	Hypothesis.
3.	~A → (~B → A)	Instance of Axiom A1 by substituting ~B for B in Axiom A1.
4.	~A → (~B → ~A)	Instance of Axiom by substituting ~A for A and ~B for B in Axiom A1.
5.	~B → A	From 2 and 3 by modus ponens.
6.	~B → ~A	From 1 and 4 by modus ponens.
7.	(~B → ~A) → ((~B → A) → B)	Axiom A3.
8.	(~B → A) → B	From 6 and 7 by modus ponens.
9.	B	From 5 and 8 by modus ponens.

Thus, by proof (i.e. lines 1-9)

~A, A B

Applying the Deduction Theorem, we have

~A A → B

And apply the Deduction Theorem one more time and we get

~A → (A → B)

Therefore, for any well-formed formula A and B, ~A → (A → B) is theorem of L.

And this completes the proof.

Let us swap the variable in the Lemma 4 and see what happens. [Well its not difficult to see what will happen. By the rule of substitution nothing will happen and we will get the same thing but we will do any way.]

Lemma 4a. For any well-formed formulas A and B, ~B → (B → A).

Proof. We shall construct a proof in L of ~B → (B → A).

1.	~B	Hypothesis.
2.	B	Hypothesis.
3.	~B → (~A → B)	Instance of Axiom A1 by substituting B for A and ~A for B in Axiom A1.
4.	~B → (~A → ~B)	Instance of Axiom by substituting ~B for A and ~A for B in Axiom A1.
5.	~A → B	From 2 and 3 by modus ponens.
6.	~A → ~B	From 1 and 4 by modus ponens.
7.	(~A → ~B) → ((~A → B) → A)	Instance of Axiom 3 by substituting A for B and B for A in Axiom A3.
8.	(~B → A) → B	From 6 and 7 by modus ponens.
9.	B	From 5 and 8 by modus ponens.

Thus, by proof (i.e. lines 1-9)

~B, B A

Applying the Deduction Theorem, we have

~B B → A

And apply the Deduction Theorem one more time and we get

~B → (B → A)

Therefore, for any well-formed formula A and B, ~B → (B → A) is theorem of L as expected.

And this completes the proof.

Lemma 5. For any well-formed formulas A and B, (~B → ~A) → (A → B).

Proof. We shall construct a proof in L of (~B → ~A) → (A → B).

1.	(~B → ~A)	Hypothesis.
2.	A	Hypothesis.
3.	(~B → ~A) → ((~B → A) → B)	Axiom 3.
4.	A → (~B → A)	Instance of Axiom 1 by substituting ~B for B in Axiom 1.
5.	(~B → A) → B	From 1 and 3 by modus ponens.
6.	A → B	From 4 and 5 by hypothetical syllogism.
7.	B	From 2 and 6 by modus ponens.

Thus, by proof (i.e. lines 1-7), we have

(~B → ~A), A B

Applying the Deduction Theorem, we have

(~B → ~A) (A → B)

Apply the Deduction Theorem one more time to get

(~B → ~A) → (A → B)

Therefore, for any well-formed formula A and B, (~B → ~A) → (A → B) is theorem of L.

And this completes the proof.

Lemma 6. For any well-formed formulas A and B, (A → B) → (~B → ~A).

Proof. We shall construct a proof in L of (A → B) → (~B → ~A).

1.	A → B	Hypothesis.
2.	~~A → A	By Lemma 2 (above).
3.	~~B → B	From 1 and 2 by hypothetical syllogism i.e., Corollary I.
4.	B → ~~B	By Lemma 2 (above).
5.	~~A → ~~B	From 3 and 4 by hypothetical syllogism i.e., Corollary I.
6.	(~~A → ~~B) → (~B → ~A)	By Lemma 5 (above).
7.	~B → ~A	From 6 and 7 by modus ponens.

Thus, by proof (i.e. lines 1 through 7), we have

A → B ~B → ~A

Applying the Deduction Theorem, we get

A B → (~B → ~A)

Apply the Deduction Theorem again and we have

(A → B) → (~B → ~A)

Therefore, for any well-formed formula A and B, (A → B) → (~B → ~A) is theorem of L.

And this completes the proof.

Lemma 7. For any well-formed formulas A and B, A → (~B → ~(A →B))

Proof.

Clearly, by modus ponens, we have

A, A → B B

Applying the Deduction Theorem, we get

A (A → B) → B

Once again, apply the Deduction Theorem and we have

A → (A → B) → B _________________ (1)

From Lemma 6, we have

(A → B) → (~B → ~A)

Get a instance of Lemma 6 by substituting (A → B) for A.

((A → B) → B) → (~B → ~(A → B)) _________________ (2)

Now apply hypothetical syllogism (Corallary I) to (1) and (2), we get

A → (~B → ~(A → B))

And this is what was to be shown.

This completes the proof.

Lemma 8. For any well-formed formulas A and B, (A → B) → ((~A → B) → B).

Proof. We shall construct a proof in L of (A → B) → ((~A → B) → B).

1.	A → B	Hypothesis.
2.	~A → B	Hypothesis.
3.	(A → B) → (~B → ~A)	By Lemma 6.
4.	~B → ~A	From 1 and 3 by modus ponens.
5.	(~A → B) → (~B → ~~A)	Instance of Lemma 6 by substituting ~A for A in Lemma 6.
6.	~B → ~~A	From 2 and 5 by modus ponens.
7.	(~B → ~~A) → ((~B → ~A) → B)	Instance of Axiom A3 by substituting ~A for A in Axiom A3.
8.	(~B → ~A) → B	From 6 and 7 by modus ponens.
9.	B	Form 4 and 8 by modus ponens.

Thus, by proof (i.e., lines 1 through 9), we have

A → B, ~A → B B

Apply the Deduction Theorem, we get

A → B (~A → B) → B

Apply the Deduction Theorem one more time

(A → B) → ((~A → B) → B)

Therefore, for any well-formed formula A and B, (A → B) → ((~A → B) → B) is theorem of L.

And this completes the proof.

------------------------------------------------------------------------------------------------