The History of Logic 1
A Logic - patterns of reasoning 1
A.I Rediictio ad absurdum ..................................I
A.2 Aristotle.......................................... 2
A.3 Other patterns and later developments.....................4
B Logic — a language about something 5
B.I Karly semantic observations and problems ...............6
B.2 The Scholastic theory of supposition......................0
B-3 Intension vs. extension.................................. 0
B.4 Modalities......................................... 7
C Logic - a symbolic language 8
C. I The "lijjjvwrsviiiy characteristic language".............8
D 19th and 20th Century — mathematization of logic 10
D.I George Boole........................................ 10
D.2 Gottlob Frege....................................... 12
D.3 Set theory......................................... II
D.4 20th century logic..................................... 15
E Modern Symbolic Logic 17
E.l Formal logical systems: syntax............................... I 7
K.2 Formal semantics ..................................... 19
E.3 Compntability and Decidability ............................. 2[
F Summary 24
Bibliography 24
Part T. Basic Set Theory 29
1. Sets, Functions, Relations 29
1.1. Sets and Functions.................................... 29
1.2. Relations.......................................... 33
L.3. Ordering Relations.................................... 34
1.4. Infinities.......................................... 3G
2. Induction 43
2.1. Well Founded Orderings................................. 43
2.LI. Inductive Proof's on Well-founded Orderings.................. 45
2.2. Inductive Definitions................................... 48
2.2.1. "I I" Definitions.................................. 50
2.2.2. Inductive Definitions and Recursive Programming............... 52
2.2.3. Proof's by Structural Induction.......................... 54
2.3. Transfinite Induction [optional.............................. 58
Part TT. Turing Machines 6]
3. Turing Machines 61
3.1. Alphabets and Languages................................. Gl
3.2. Turing Machines...................................... 62
3.2.1. Composing Turing machines........................... 66
3.2.2. Alternative representation of TMs [optional .................. 67
3.3. Universal Tiring Machine................................. 68
3.4. Decidability and the Halting Problem.......................... 71
Part TTT. Statement Logic 75
4. Syntax and Proof Systems 75
4.1. Axiomatic Systems.................................... 75
4.2. Syntax of SL........................................ 79
4.3. The axiomatic system of Hilbert's............................ 80
4.4. Natural Deduction system ................................ 81
1.5. Hilbert vs. ND....................................... 83
4.6. Provable Kqui valence of formulae............................ 8-1
1.7. Consistency ........................................ 85
4.8. The axiomatic system of Gent/.en's........................... 86
4.8.1. Decidability of the axiomatic systems for SL.................. 86
4.8.2. Gent/.en's rules for abbreviated connectives................... 88
4.9. Some proof techniques .................................. 88
5. Semantics of SL 91
5.1. Semantics of SL...................................... 91
5.2. Semantic properties of formulae............................. 9")
5.3. Abbreviations....................................... 90
5.4. Sets, Propositions and Boolean Algebras........................ 97
o.l.l. Laws........................................ 97
5.4.2. Sets and SL..................................... 98
5.1.3. Boolean Algebras [optional]............................ 100
6. Soundness and Completeness 104
6.1. Adequate Sets of Connectives .............................. 101
6.2. DNF, CNF......................................... 106
6.3. Soundness......................................... 107
6.4. Completeness ....................................... 109
6.4-1. Some Applications of Soundness and Completeness .............. 112
Part TV. Predicate Logic 116
7. Syntax and Proof System of FOL 116
7.1. Syntax of FOL....................................... 117
7.1.1. Abbreviations................................... 119
7.2. Scope of Quantifiers, Free Variables, Substitution................... I If!
7.2.1. Some examples................................... 120
7.2.2. Substitution.................................... 122
7.3. Proof System........................................ 123
7.3.1. Deduction Theorem in FOL............................ 124
7.4. Gent/.en's system for FOL................................. 126
8- Semantics 130
8.1- Semantics of'FOL..................................... 130
8.2. Semantic properties of formulae............................. 13-1
8-3. Open vs. closed formulae................................. 135
8.3.1. Deduction Theorem in Q and A'......................... 137
9. More Semantics 140
9.1. I'renex operations..................................... 110
9.2. A few bits of Model Theory ............................... 113
9.2.1. Substructures ................................... 143
9.2.2. v.\\ classification ................................. Ill
9.3. "Syntactic" semantic and Computations ........................ 145
9.3.1. Reachable structures and Term structures.................... 145
9-3-2. Herbrand's theorem................................ 148
9.3.3. Horn clauses and logic programming....................... I 19
10. Soundness. Completeness 155
10.1. Soundness......................................... loo
10.2. Completeness....................................... 155
10.2.1. Some Applications................................ 100
11. Identity and Some Consequences . 164
I I.I. FOL with Identity.........].......................... 161
I I.I.I. Axioms for Identity ............................... 105
11.1.2. Some examples.................................. 166
11.1.3. Soundness and Completeness of FOL~..................... IG7
11.2. A few more bits of Model Theory............................ 169
I 1.2.1. Compactness................................... 169
11.2.2. Skolem-Lowenheim................................ 170
11.3. Semi-Decidability and Undecidability of FOL..................... 170
11.4. Why is First-Order Logic "First-Order"? ....................... 171