for questions or link request: module admin

Further Theorems of Propositional Calculus

name: prophilbert3, module version: 1.00.00, rule version: 1.00.00, original: prophilbert3, author of this module: Michael Meyling

Description

This module includes proofs of popositional calculus theorems. The following theorems and proofs are adapted from D. Hilbert and W. Ackermann's `Grundzuege der theoretischen Logik' (Berlin 1928, Springer)

References

This document uses the results of the following documents:

Content

First distributive law (first direction):

1. Proposition
      ((P Ú (Q Ù A)) ® ((P Ú Q) Ù (P Ú A)))     (hilb36)

Proof:
1 ((P Ù Q) ® P) add proposition hilb24
2 ((P Ù A) ® P) replace proposition variable Q by A in 1
3 ((B Ù A) ® B) replace proposition variable P by B in 2
4 ((Q Ù A) ® Q) replace proposition variable B by Q in 3
5 ((P ® Q) ® ((A Ú P) ® (A Ú Q))) add axiom axiom4
6 ((P ® Q) ® ((B Ú P) ® (B Ú Q))) replace proposition variable A by B in 5
7 ((P ® C) ® ((B Ú P) ® (B Ú C))) replace proposition variable Q by C in 6
8 ((D ® C) ® ((B Ú D) ® (B Ú C))) replace proposition variable P by D in 7
9 ((D ® C) ® ((P Ú D) ® (P Ú C))) replace proposition variable B by P in 8
10 ((D ® Q) ® ((P Ú D) ® (P Ú Q))) replace proposition variable C by Q in 9
11 (((Q Ù A) ® Q) ® ((P Ú (Q Ù A)) ® (P Ú Q))) replace proposition variable D by (Q Ù A) in 10
12 ((P Ú (Q Ù A)) ® (P Ú Q)) modus ponens with 4, 11
13 ((P Ù Q) ® Q) add proposition hilb25
14 ((P Ù A) ® A) replace proposition variable Q by A in 13
15 ((B Ù A) ® A) replace proposition variable P by B in 14
16 ((Q Ù A) ® A) replace proposition variable B by Q in 15
17 ((D ® A) ® ((P Ú D) ® (P Ú A))) replace proposition variable C by A in 9
18 (((Q Ù A) ® A) ® ((P Ú (Q Ù A)) ® (P Ú A))) replace proposition variable D by (Q Ù A) in 17
19 ((P Ú (Q Ù A)) ® (P Ú A)) modus ponens with 16, 18
20 (P ® (Q ® (P Ù Q))) add proposition hilb28
21 (P ® (A ® (P Ù A))) replace proposition variable Q by A in 20
22 (B ® (A ® (B Ù A))) replace proposition variable P by B in 21
23 (B ® ((P Ú A) ® (B Ù (P Ú A)))) replace proposition variable A by (P Ú A) in 22
24 ((P Ú Q) ® ((P Ú A) ® ((P Ú Q) Ù (P Ú A)))) replace proposition variable B by (P Ú Q) in 23
25 ((P ® Q) ® ((A ® P) ® (A ® Q))) add proposition hilb1
26 ((P ® Q) ® ((B ® P) ® (B ® Q))) replace proposition variable A by B in 25
27 ((P ® C) ® ((B ® P) ® (B ® C))) replace proposition variable Q by C in 26
28 ((D ® C) ® ((B ® D) ® (B ® C))) replace proposition variable P by D in 27
29 ((D ® C) ® (((P Ú (Q Ù A)) ® D) ® ((P Ú (Q Ù A)) ® C))) replace proposition variable B by (P Ú (Q Ù A)) in 28
30 ((D ® ((P Ú A) ® ((P Ú Q) Ù (P Ú A)))) ® (((P Ú (Q Ù A)) ® D) ® ((P Ú (Q Ù A)) ® ((P Ú A) ® ((P Ú Q) Ù (P Ú A)))))) replace proposition variable C by ((P Ú A) ® ((P Ú Q) Ù (P Ú A))) in 29
31 (((P Ú Q) ® ((P Ú A) ® ((P Ú Q) Ù (P Ú A)))) ® (((P Ú (Q Ù A)) ® (P Ú Q)) ® ((P Ú (Q Ù A)) ® ((P Ú A) ® ((P Ú Q) Ù (P Ú A)))))) replace proposition variable D by (P Ú Q) in 30
32 (((P Ú (Q Ù A)) ® (P Ú Q)) ® ((P Ú (Q Ù A)) ® ((P Ú A) ® ((P Ú Q) Ù (P Ú A))))) modus ponens with 24, 31
33 ((P Ú (Q Ù A)) ® ((P Ú A) ® ((P Ú Q) Ù (P Ú A)))) modus ponens with 12, 32
34 ((P ® (Q ® A)) ® (Q ® (P ® A))) add proposition hilb16
35 ((P ® (Q ® B)) ® (Q ® (P ® B))) replace proposition variable A by B in 34
36 ((P ® (C ® B)) ® (C ® (P ® B))) replace proposition variable Q by C in 35
37 ((D ® (C ® B)) ® (C ® (D ® B))) replace proposition variable P by D in 36
38 ((D ® (C ® ((P Ú Q) Ù (P Ú A)))) ® (C ® (D ® ((P Ú Q) Ù (P Ú A))))) replace proposition variable B by ((P Ú Q) Ù (P Ú A)) in 37
39 ((D ® ((P Ú A) ® ((P Ú Q) Ù (P Ú A)))) ® ((P Ú A) ® (D ® ((P Ú Q) Ù (P Ú A))))) replace proposition variable C by (P Ú A) in 38
40 (((P Ú (Q Ù A)) ® ((P Ú A) ® ((P Ú Q) Ù (P Ú A)))) ® ((P Ú A) ® ((P Ú (Q Ù A)) ® ((P Ú Q) Ù (P Ú A))))) replace proposition variable D by (P Ú (Q Ù A)) in 39
41 ((P Ú A) ® ((P Ú (Q Ù A)) ® ((P Ú Q) Ù (P Ú A)))) modus ponens with 33, 40
42 ((D ® ((P Ú (Q Ù A)) ® ((P Ú Q) Ù (P Ú A)))) ® (((P Ú (Q Ù A)) ® D) ® ((P Ú (Q Ù A)) ® ((P Ú (Q Ù A)) ® ((P Ú Q) Ù (P Ú A)))))) replace proposition variable C by ((P Ú (Q Ù A)) ® ((P Ú Q) Ù (P Ú A))) in 29
43 (((P Ú A) ® ((P Ú (Q Ù A)) ® ((P Ú Q) Ù (P Ú A)))) ® (((P Ú (Q Ù A)) ® (P Ú A)) ® ((P Ú (Q Ù A)) ® ((P Ú (Q Ù A)) ® ((P Ú Q) Ù (P Ú A)))))) replace proposition variable D by (P Ú A) in 42
44 (((P Ú (Q Ù A)) ® (P Ú A)) ® ((P Ú (Q Ù A)) ® ((P Ú (Q Ù A)) ® ((P Ú Q) Ù (P Ú A))))) modus ponens with 41, 43
45 ((P Ú (Q Ù A)) ® ((P Ú (Q Ù A)) ® ((P Ú Q) Ù (P Ú A)))) modus ponens with 19, 44
46 ((P ® (P ® Q)) ® (P ® Q)) add proposition hilb33
47 ((P ® (P ® A)) ® (P ® A)) replace proposition variable Q by A in 46
48 ((B ® (B ® A)) ® (B ® A)) replace proposition variable P by B in 47
49 ((B ® (B ® ((P Ú Q) Ù (P Ú A)))) ® (B ® ((P Ú Q) Ù (P Ú A)))) replace proposition variable A by ((P Ú Q) Ù (P Ú A)) in 48
50 (((P Ú (Q Ù A)) ® ((P Ú (Q Ù A)) ® ((P Ú Q) Ù (P Ú A)))) ® ((P Ú (Q Ù A)) ® ((P Ú Q) Ù (P Ú A)))) replace proposition variable B by (P Ú (Q Ù A)) in 49
51 ((P Ú (Q Ù A)) ® ((P Ú Q) Ù (P Ú A))) modus ponens with 45, 50
qed

First distributive law (second direction):

2. Proposition
      (((P Ú Q) Ù (P Ú A)) ® (P Ú (Q Ù A)))     (hilb37)

Proof:
1 (P ® (Q ® (P Ù Q))) add proposition hilb28
2 (P ® (A ® (P Ù A))) replace proposition variable Q by A in 1
3 (B ® (A ® (B Ù A))) replace proposition variable P by B in 2
4 (Q ® (A ® (Q Ù A))) replace proposition variable B by Q in 3
5 ((P ® Q) ® ((A Ú P) ® (A Ú Q))) add axiom axiom4
6 ((P ® Q) ® ((B Ú P) ® (B Ú Q))) replace proposition variable A by B in 5
7 ((P ® C) ® ((B Ú P) ® (B Ú C))) replace proposition variable Q by C in 6
8 ((D ® C) ® ((B Ú D) ® (B Ú C))) replace proposition variable P by D in 7
9 ((D ® C) ® ((P Ú D) ® (P Ú C))) replace proposition variable B by P in 8
10 ((D ® (Q Ù A)) ® ((P Ú D) ® (P Ú (Q Ù A)))) replace proposition variable C by (Q Ù A) in 9
11 ((A ® (Q Ù A)) ® ((P Ú A) ® (P Ú (Q Ù A)))) replace proposition variable D by A in 10
12 ((P ® Q) ® ((A ® P) ® (A ® Q))) add proposition hilb1
13 ((P ® Q) ® ((B ® P) ® (B ® Q))) replace proposition variable A by B in 12
14 ((P ® C) ® ((B ® P) ® (B ® C))) replace proposition variable Q by C in 13
15 ((D ® C) ® ((B ® D) ® (B ® C))) replace proposition variable P by D in 14
16 ((D ® C) ® ((Q ® D) ® (Q ® C))) replace proposition variable B by Q in 15
17 ((D ® ((P Ú A) ® (P Ú (Q Ù A)))) ® ((Q ® D) ® (Q ® ((P Ú A) ® (P Ú (Q Ù A)))))) replace proposition variable C by ((P Ú A) ® (P Ú (Q Ù A))) in 16
18 (((A ® (Q Ù A)) ® ((P Ú A) ® (P Ú (Q Ù A)))) ® ((Q ® (A ® (Q Ù A))) ® (Q ® ((P Ú A) ® (P Ú (Q Ù A)))))) replace proposition variable D by (A ® (Q Ù A)) in 17
19 ((Q ® (A ® (Q Ù A))) ® (Q ® ((P Ú A) ® (P Ú (Q Ù A))))) modus ponens with 11, 18
20 (Q ® ((P Ú A) ® (P Ú (Q Ù A)))) modus ponens with 4, 19
21 ((P ® (Q ® A)) ® (Q ® (P ® A))) add proposition hilb16
22 ((P ® (Q ® B)) ® (Q ® (P ® B))) replace proposition variable A by B in 21
23 ((P ® (C ® B)) ® (C ® (P ® B))) replace proposition variable Q by C in 22
24 ((D ® (C ® B)) ® (C ® (D ® B))) replace proposition variable P by D in 23
25 ((D ® (C ® (P Ú (Q Ù A)))) ® (C ® (D ® (P Ú (Q Ù A))))) replace proposition variable B by (P Ú (Q Ù A)) in 24
26 ((D ® ((P Ú A) ® (P Ú (Q Ù A)))) ® ((P Ú A) ® (D ® (P Ú (Q Ù A))))) replace proposition variable C by (P Ú A) in 25
27 ((Q ® ((P Ú A) ® (P Ú (Q Ù A)))) ® ((P Ú A) ® (Q ® (P Ú (Q Ù A))))) replace proposition variable D by Q in 26
28 ((P Ú A) ® (Q ® (P Ú (Q Ù A)))) modus ponens with 20, 27
29 ((D ® (P Ú (Q Ù A))) ® ((P Ú D) ® (P Ú (P Ú (Q Ù A))))) replace proposition variable C by (P Ú (Q Ù A)) in 9
30 ((Q ® (P Ú (Q Ù A))) ® ((P Ú Q) ® (P Ú (P Ú (Q Ù A))))) replace proposition variable D by Q in 29
31 ((D ® C) ® (((P Ú A) ® D) ® ((P Ú A) ® C))) replace proposition variable B by (P Ú A) in 15
32 ((D ® ((P Ú Q) ® (P Ú (P Ú (Q Ù A))))) ® (((P Ú A) ® D) ® ((P Ú A) ® ((P Ú Q) ® (P Ú (P Ú (Q Ù A))))))) replace proposition variable C by ((P Ú Q) ® (P Ú (P Ú (Q Ù A)))) in 31
33 (((Q ® (P Ú (Q Ù A))) ® ((P Ú Q) ® (P Ú (P Ú (Q Ù A))))) ® (((P Ú A) ® (Q ® (P Ú (Q Ù A)))) ® ((P Ú A) ® ((P Ú Q) ® (P Ú (P Ú (Q Ù A))))))) replace proposition variable D by (Q ® (P Ú (Q Ù A))) in 32
34 (((P Ú A) ® (Q ® (P Ú (Q Ù A)))) ® ((P Ú A) ® ((P Ú Q) ® (P Ú (P Ú (Q Ù A)))))) modus ponens with 30, 33
35 ((P Ú A) ® ((P Ú Q) ® (P Ú (P Ú (Q Ù A))))) modus ponens with 28, 34
36 ((P Ú (Q Ú A)) ® ((P Ú Q) Ú A)) add proposition hilb14
37 ((P Ú (Q Ú B)) ® ((P Ú Q) Ú B)) replace proposition variable A by B in 36
38 ((P Ú (C Ú B)) ® ((P Ú C) Ú B)) replace proposition variable Q by C in 37
39 ((D Ú (C Ú B)) ® ((D Ú C) Ú B)) replace proposition variable P by D in 38
40 ((D Ú (C Ú (Q Ù A))) ® ((D Ú C) Ú (Q Ù A))) replace proposition variable B by (Q Ù A) in 39
41 ((D Ú (P Ú (Q Ù A))) ® ((D Ú P) Ú (Q Ù A))) replace proposition variable C by P in 40
42 ((P Ú (P Ú (Q Ù A))) ® ((P Ú P) Ú (Q Ù A))) replace proposition variable D by P in 41
43 ((P ® Q) ® (ØP Ú Q)) add proposition defimpl1
44 ((ØP Ú Q) ® (P ® Q)) add proposition defimpl2
45 ((D ® C) ® ((Ø(P Ú Q) Ú D) ® (Ø(P Ú Q) Ú C))) replace proposition variable B by Ø(P Ú Q) in 8
46 ((D ® ((P Ú P) Ú (Q Ù A))) ® ((Ø(P Ú Q) Ú D) ® (Ø(P Ú Q) Ú ((P Ú P) Ú (Q Ù A))))) replace proposition variable C by ((P Ú P) Ú (Q Ù A)) in 45
47 (((P Ú (P Ú (Q Ù A))) ® ((P Ú P) Ú (Q Ù A))) ® ((Ø(P Ú Q) Ú (P Ú (P Ú (Q Ù A)))) ® (Ø(P Ú Q) Ú ((P Ú P) Ú (Q Ù A))))) replace proposition variable D by (P Ú (P Ú (Q Ù A))) in 46
48 ((Ø(P Ú Q) Ú (P Ú (P Ú (Q Ù A)))) ® (Ø(P Ú Q) Ú ((P Ú P) Ú (Q Ù A)))) modus ponens with 42, 47
49 ((P ® B) ® (ØP Ú B)) replace proposition variable Q by B in 43
50 ((C ® B) ® (ØC Ú B)) replace proposition variable P by C in 49
51 ((C ® (P Ú (P Ú (Q Ù A)))) ® (ØC Ú (P Ú (P Ú (Q Ù A))))) replace proposition variable B by (P Ú (P Ú (Q Ù A))) in 50
52 (((P Ú Q) ® (P Ú (P Ú (Q Ù A)))) ® (Ø(P Ú Q) Ú (P Ú (P Ú (Q Ù A))))) replace proposition variable C by (P Ú Q) in 51
53 ((D ® C) ® ((((P Ú Q) ® (P Ú (P Ú (Q Ù A)))) ® D) ® (((P Ú Q) ® (P Ú (P Ú (Q Ù A)))) ® C))) replace proposition variable B by ((P Ú Q) ® (P Ú (P Ú (Q Ù A)))) in 15
54 ((D ® (Ø(P Ú Q) Ú ((P Ú P) Ú (Q Ù A)))) ® ((((P Ú Q) ® (P Ú (P Ú (Q Ù A)))) ® D) ® (((P Ú Q) ® (P Ú (P Ú (Q Ù A)))) ® (Ø(P Ú Q) Ú ((P Ú P) Ú (Q Ù A)))))) replace proposition variable C by (Ø(P Ú Q) Ú ((P Ú P) Ú (Q Ù A))) in 53
55 (((Ø(P Ú Q) Ú (P Ú (P Ú (Q Ù A)))) ® (Ø(P Ú Q) Ú ((P Ú P) Ú (Q Ù A)))) ® ((((P Ú Q) ® (P Ú (P Ú (Q Ù A)))) ® (Ø(P Ú Q) Ú (P Ú (P Ú (Q Ù A))))) ® (((P Ú Q) ® (P Ú (P Ú (Q Ù A)))) ® (Ø(P Ú Q) Ú ((P Ú P) Ú (Q Ù A)))))) replace proposition variable D by (Ø(P Ú Q) Ú (P Ú (P Ú (Q Ù A)))) in 54
56 ((((P Ú Q) ® (P Ú (P Ú (Q Ù A)))) ® (Ø(P Ú Q) Ú (P Ú (P Ú (Q Ù A))))) ® (((P Ú Q) ® (P Ú (P Ú (Q Ù A)))) ® (Ø(P Ú Q) Ú ((P Ú P) Ú (Q Ù A))))) modus ponens with 48, 55
57 (((P Ú Q) ® (P Ú (P Ú (Q Ù A)))) ® (Ø(P Ú Q) Ú ((P Ú P) Ú (Q Ù A)))) modus ponens with 52, 56
58 ((ØP Ú B) ® (P ® B)) replace proposition variable Q by B in 44
59 ((ØC Ú B) ® (C ® B)) replace proposition variable P by C in 58
60 ((ØC Ú ((P Ú P) Ú (Q Ù A))) ® (C ® ((P Ú P) Ú (Q Ù A)))) replace proposition variable B by ((P Ú P) Ú (Q Ù A)) in 59
61 ((Ø(P Ú Q) Ú ((P Ú P) Ú (Q Ù A))) ® ((P Ú Q) ® ((P Ú P) Ú (Q Ù A)))) replace proposition variable C by (P Ú Q) in 60
62 ((D ® ((P Ú Q) ® ((P Ú P) Ú (Q Ù A)))) ® ((((P Ú Q) ® (P Ú (P Ú (Q Ù A)))) ® D) ® (((P Ú Q) ® (P Ú (P Ú (Q Ù A)))) ® ((P Ú Q) ® ((P Ú P) Ú (Q Ù A)))))) replace proposition variable C by ((P Ú Q) ® ((P Ú P) Ú (Q Ù A))) in 53
63 (((Ø(P Ú Q) Ú ((P Ú P) Ú (Q Ù A))) ® ((P Ú Q) ® ((P Ú P) Ú (Q Ù A)))) ® ((((P Ú Q) ® (P Ú (P Ú (Q Ù A)))) ® (Ø(P Ú Q) Ú ((P Ú P) Ú (Q Ù A)))) ® (((P Ú Q) ® (P Ú (P Ú (Q Ù A)))) ® ((P Ú Q) ® ((P Ú P) Ú (Q Ù A)))))) replace proposition variable D by (Ø(P Ú Q) Ú ((P Ú P) Ú (Q Ù A))) in 62
64 ((((P Ú Q) ® (P Ú (P Ú (Q Ù A)))) ® (Ø(P Ú Q) Ú ((P Ú P) Ú (Q Ù A)))) ® (((P Ú Q) ® (P Ú (P Ú (Q Ù A)))) ® ((P Ú Q) ® ((P Ú P) Ú (Q Ù A))))) modus ponens with 61, 63
65 (((P Ú Q) ® (P Ú (P Ú (Q Ù A)))) ® ((P Ú Q) ® ((P Ú P) Ú (Q Ù A)))) modus ponens with 57, 64
66 ((D ® C) ® ((Ø(P Ú A) Ú D) ® (Ø(P Ú A) Ú C))) replace proposition variable B by Ø(P Ú A) in 8
67 ((D ® ((P Ú Q) ® ((P Ú P) Ú (Q Ù A)))) ® ((Ø(P Ú A) Ú D) ® (Ø(P Ú A) Ú ((P Ú Q) ® ((P Ú P) Ú (Q Ù A)))))) replace proposition variable C by ((P Ú Q) ® ((P Ú P) Ú (Q Ù A))) in 66
68 ((((P Ú Q) ® (P Ú (P Ú (Q Ù A)))) ® ((P Ú Q) ® ((P Ú P) Ú (Q Ù A)))) ® ((Ø(P Ú A) Ú ((P Ú Q) ® (P Ú (P Ú (Q Ù A))))) ® (Ø(P Ú A) Ú ((P Ú Q) ® ((P Ú P) Ú (Q Ù A)))))) replace proposition variable D by ((P Ú Q) ® (P Ú (P Ú (Q Ù A)))) in 67
69 ((Ø(P Ú A) Ú ((P Ú Q) ® (P Ú (P Ú (Q Ù A))))) ® (Ø(P Ú A) Ú ((P Ú Q) ® ((P Ú P) Ú (Q Ù A))))) modus ponens with 65, 68
70 ((C ® ((P Ú Q) ® (P Ú (P Ú (Q Ù A))))) ® (ØC Ú ((P Ú Q) ® (P Ú (P Ú (Q Ù A)))))) replace proposition variable B by ((P Ú Q) ® (P Ú (P Ú (Q Ù A)))) in 50
71 (((P Ú A) ® ((P Ú Q) ® (P Ú (P Ú (Q Ù A))))) ® (Ø(P Ú A) Ú ((P Ú Q)