LOGIC: Lecture Notes For Philosophy, Mathematics, And Computer Science

Preface......Page 6
Contents......Page 8
1.1 What Is Logic?......Page 12
1.2 Arguments and Their Formulation......Page 14
1.3 Complex Reasoning......Page 15
1.4 Truth and Falsity......Page 17
1.5 Bivalence......Page 19
Exercises......Page 20
2.1 Some Set-Theoretical Notions......Page 22
2.2 True Premises......Page 23
2.3 Validity as Necessary Truth Preservation......Page 24
2.4 Other Logical Properties and Relations......Page 26
2.5 Important Facts About Validity......Page 27
2.6 Validity Is Not Everything......Page 31
Exercises......Page 33
3.1 Formal Validity......Page 35
3.2 Formal Invalidity......Page 38
3.3 Formal Language......Page 39
3.4 Formal System......Page 40
3.5 Object Language and Metalanguage......Page 41
3.6 Further Set-Theoretical Notions......Page 42
Exercises......Page 43
4.1 Sentence Letters......Page 45
4.2 Sentential Connectives......Page 46
4.3 Brackets......Page 48
4.4 Expressive Completeness......Page 49
4.6 Formalization in a Propositional Language......Page 51
Exercises......Page 52
5.1 Formation Rules......Page 54
5.2 Syntactic Trees......Page 55
5.3 Scope......Page 56
5.4 Interpretation......Page 57
5.5 Truth Tables......Page 58
Exercises......Page 59
6.1 Definition of Logical Consequence......Page 61
6.2 Other Logical Properties and Relations......Page 62
6.3 Important Facts About Logical Consequence......Page 63
6.4 Logical Consequence as a Test for Validity......Page 64
6.5 Effective Computability......Page 65
Exercises......Page 67
7.1 Derivation......Page 68
7.2 Rules for......Page 69
7.3 Rules for......Page 71
7.4 Rules for......Page 72
7.5 Rules for......Page 75
Exercises......Page 77
8.1 Derivability and Related Notions......Page 78
8.2 Important Facts About Derivability......Page 79
8.3 Some Tips......Page 80
8.4 Derived Rules......Page 82
8.5 Other Natural Deduction Systems......Page 83
Exercises......Page 84
9.1 Axioms and Inference Rule......Page 86
9.2 Deduction Theorem......Page 88
9.3 Explosion, Double Negation, Contraposition......Page 90
9.4 Substitution of Equivalents......Page 92
9.5 Reductio Ad Absurdum......Page 94
9.6 Deductive Equivalence Between G- and L......Page 95
9.7 Systems and Theories......Page 96
Exercises......Page 97
10.1 Consistency of L......Page 98
10.2 Definitions of Soundness and Completeness......Page 99
10.4 Completeness of L......Page 100
10.5 Extension to G-......Page 103
Exercises......Page 104
11.1 Quantified Sentences......Page 105
11.2 A Brief Historical Survey......Page 107
11.3 Existential Import......Page 109
11.4 Multiple Generality......Page 110
11.5 Definite Descriptions......Page 112
Exercises......Page 113
12.1 Non-logical Expressions......Page 115
12.2 Logical Constants and Auxiliary Symbols......Page 116
12.3 Other Symbols......Page 117
12.4 Numerical Expressions......Page 119
12.5 Multiple Generality and Scope Ambiguity......Page 120
12.6 Existence......Page 121
Exercises......Page 122
13.1 Syntax......Page 124
13.2 Basic Semantic Notions......Page 126
13.3 Satisfaction......Page 127
13.4 Truth......Page 128
13.5 Logical Consequence......Page 131
13.6 Undecidability......Page 132
Exercises......Page 134
14.1 Axioms and Inference Rule......Page 136
14.2 Derivability in Q......Page 137
14.4 Validity and Derivability......Page 138
14.5 Deduction Theorem and Other Syntactic Results......Page 139
14.6 Alphabetic Variants......Page 140
Exercises......Page 142
15.1 Consistency of Q......Page 144
15.2 Soundness of Q......Page 145
15.3 Completeness of Q......Page 146
15.4 Compactness Theorem......Page 148
15.5 Final Remarks......Page 149
Exercises......Page 150
16.1 Undecidability of Q......Page 151
16.2 Gödel Numbering......Page 152
16.4 A Further Corollary......Page 153
16.5 Recursive Axiomatization and Decidability......Page 154
Exercises......Page 155
17.1 First-Order Languages and Systems......Page 157
17.2 First-Order Logic with Identity......Page 158
17.3 First-Order Theory......Page 159
17.4 The Language of Basic Arithmetic......Page 160
17.5 Peano Arithmetic......Page 162
Exercises......Page 164
18.1 Cardinality......Page 165
18.2 Löwenheim-Skolem Theorems......Page 166
18.3 Isomorphism......Page 168
18.4 Isomorphic Models of a Theory......Page 170
18.5 Categoricity......Page 171
Exercises......Page 173
19.1 Overview......Page 175
19.2 The Arithmetization of Syntax......Page 176
19.3 The Gödel Sentence......Page 178
19.4 First Incompleteness Theorem: Semantic Version......Page 179
19.5 First Incompleteness Theorem: Syntactic Version......Page 180
19.6 Second Incompleteness Theorem......Page 182
Exercises......Page 183
20.1 Modal Operators......Page 184
20.2 A Modal Propositional Language......Page 185
20.3 The System K......Page 187
20.4 The Systems T,B,S4,S5......Page 190
20.5 A Modal Predicate Language......Page 194
20.6 Systems of Modal Predicate Logic......Page 196
20.7 Soundness and Completeness......Page 198
Exercises......Page 199
Chapter 1......Page 201
Chapter 3......Page 202
Chapter 5......Page 203
Chapter 6......Page 204
Chapter 7......Page 206
Chapter 8......Page 209
Chapter 9......Page 211
Chapter 11......Page 213
Chapter 13......Page 215
Chapter 14......Page 216
Chapter 15......Page 218
Chapter 17......Page 219
Chapter 18......Page 220
Chapter 20......Page 221
Bibliography......Page 223
Index......Page 226