Axioms and rules of inference for propositional logic.

1. Keep going...

We axiomatize propositional logic by using following rules of inference.

Suppose A, B, C are statements. Then

(

)

Ex

{A}, (A B)

Contr

(

)

{(A A)}, A

(

)

Ass

{A (B C)}, (A B) C

(

)

EM

, A A

(

)

Cut

{(A B), ( A C))}, (B C)

are rules of inference. Ex stands for "expansion"; Contr stands for "contraction"; Ass stands for

"associative"; EM stands for "excluded middle"; and Cut stands for "cut". An axiom is a rule of inference where the set of hypotheses is empty; thus EM

is an axiom.

Theorem 1.1. OrComm

({A B}, B A) .

Proof. Hyp

AB

EM

AA

Cut

BA

Theorem 1.2. OtherOrAss

({(A B) C}, A (B C)).

Proof.

(A B) C

C (A B) OrComm

(C A) B)) HalfAss

B (C A) OrComm

(B C) A HalfAss

A (B C) OrComm

Definition 1.1.

A B A B A B ( A B) A B (A B) (B A)

1

2

Theorem 1.3. ModusPonens ({A, A B}, B) .

Proof. 1. A Hyp 2. A B 1, Ex 3. A B Hyp 4. B B 2, 3, Cut 5. B 4, Contr

Theorem 1.4.

({A, B}, A B)

Proof. A B

(A B) (A B) ( A B) (A B) Not so fast!

A ( B (A B) B (A B) AB

Theorem 1.5.

({A}, A) .

Proof.

Hyp

A

EM

A A

OrComm

A A

ModusPonens

A

Theorem 1.6.

({ A}, A) .

Proof.

Hyp

A

Ex

A A

EM

AA

Cut

AA

Contr

A

3

2. Maybe...

{ B, C} (B C)

B C (B C) (B C) B(C) (B C) C (B C) (B C)

{ A C, B C, A B} C

AC BC AB BC C

{A C, B C, A B} C

AC BC AB BC C AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA Theorem 2.1. We have A (B C) (A B) (A C) and A (B C) (A B) (A C).

4

Proof. Let D = (A B) (A C).

A (B C) A BC BB BA B AB D C C C A C AC D BC D D

so A (B C) (A B) (A C).

Replacing A, B, C by A, B, C we find that

(( A B) ( A C)) ( A ( B C))

which implies that (A B) (A B) A (B C).

Let D = (A B) (A C).

A (B C) AAB AAC AD BC B AB BC C AC BC D A (B C) D D

so A (B C) (A B) (A C).

Replacing A, B, C by A, B, C we find that

(( A B) ( A C)) ( A ( B C))

which implies that (A B) (A C) A (B C).

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

5

3. The awful axioms.

A (B A) A ( B A)

AAB AA

(A (B C)) ((A B) (A C)) ( A ( B C)) ( ( A B) ( A C))

( A

4. Really neat!

Lemma 4.1. Suppose A, B, C are formulae and A B. Then (AC) (BC)

if is one of , , , .

Proof. It will be enough to show that

(AC) (BC) if A B and is one of , , , . Since A B we have

A B and B A.

Case One. = . Case Two. = .

AC AB AB C B BC

AC A C AB B BC

Case Three. =.

AC BA BC

6

Case Four. =.

AC AC BC C A C B C A AB BC BC

Case Three. Case Three.

Theorem 4.1. Suppose F is a formula, S is a formula F and S is a substring of T . Then S is a subformula of F .

Moreover, if T is a formula, S T and G is the string obtained from F with S replaced by T then G is a formula and F G.

Proof. Let S = (M, r, P, ) and F = (N , s, o) be parse trees for S and F , respectively.

Part One. S is a subformula of F . Induct on the length L of S. If L = 1 then S is a leaf node T . Since S is a formula it must be a statement letter so S is a subformula of T . Suppose L > 1. Apply the inductive hypothesis to the branches of the children of s and conclude that the yield of each of these branches is a subformula of F ; we may then conclude that S is a subformula of F . Part Two. Suppose T is a formula, S T and G is the string obtained from F with S replaced by T . Let G be the tree obtained by replacing the s branch of S by the parse tree for T . Clearly, G is a parse tree for G so G is a formula. Now one only has to note that S T and SH T H if is one of , , , .

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download