24小时热门版块排行榜

返回列表

【奖励】本帖被评价12次，作者pkusiyuan增加金币 9.6 个

pkusiyuan

银虫 (正式写手)

应助: 0 (幼儿园)
金币: 15204.9
帖子: 773
在线: 130小时
虫号: 3451204

[资源] A First Course in Logic

Contents
1 Propositional logic 1
1.1 What is propositional logic? 1
1.2 Validity, satisfiability, and contradiction 7
1.3 Consequence and equivalence 9
1.4 Formal proofs 12
1.5 Proof by induction 22
1.5.1 Mathematical induction 23
1.5.2 Induction on the complexity of formulas 25
1.6 Normal forms 27
1.7 Horn formulas 32
1.8 Resolution 37
1.8.1 Clauses 37
1.8.2 Resolvents 38
1.8.3 Completeness of resolution 40
1.9 Completeness and compactness 44
2 Structures and first-order logic 53
2.1 The language of first-order logic 53
2.2 The syntax of first-order logic 54
2.3 Semantics and structures 57
2.4 Examples of structures 66
2.4.1 Graphs 66
2.4.2 Relational databases 69
2.4.3 Linear orders 70
2.4.4 Number systems 72
2.5 The size of a structure 73
2.6 Relations between structures 79
2.6.1 Embeddings 80
2.6.2 Substructures 83
2.6.3 Diagrams 86
2.7 Theories and models 89
x Contents
3 Proof theory 99
3.1 Formal proofs 100
3.2 Normal forms 109
3.2.1 Conjunctive prenex normal form 109
3.2.2 Skolem normal form 111
3.3 Herbrand theory 113
3.3.1 Herbrand structures 113
3.3.2 Dealing with equality 116
3.3.3 The Herbrand method 118
3.4 Resolution for first-order logic 120
3.4.1 Unification 121
3.4.2 Resolution 124
3.5 SLD-resolution 128
3.6 Prolog 137
4 Properties of first-order logic 147
4.1 The countable case 147
4.2 Cardinal knowledge 152
4.2.1 Ordinal numbers 153
4.2.2 Cardinal arithmetic 156
4.2.3 Continuum hypotheses 161
4.3 Four theorems of first-order logic 163
4.4 Amalgamation of structures 170
4.5 Preservation of formulas 174
4.5.1 Supermodels and submodels 175
4.5.2 Unions of chains 179
4.6 Amalgamation of vocabularies 183
4.7 The expressive power of first-order logic 189
5 First-order theories 198
5.1 Completeness and decidability 199
5.2 Categoricity 205
5.3 Countably categorical theories 211
5.3.1 Dense linear orders 211
5.3.2 Ryll-Nardzewski et al. 214
5.4 The Random graph and 0–1 laws 216
5.5 Quantifier elimination 221
5.5.1 Finite relational vocabularies 222
5.5.2 The general case 228
5.6 Model-completeness 233
5.7 Minimal theories 239
Contents xi
5.8 Fields and vector spaces 247
5.9 Some algebraic geometry 257
6 Models of countable theories 267
6.1 Types 267
6.2 Isolated types 271
6.3 Small models of small theories 275
6.3.1 Atomic models 276
6.3.2 Homogeneity 277
6.3.3 Prime models 279
6.4 Big models of small theories 280
6.4.1 Countable saturated models 281
6.4.2 Monster models 285
6.5 Theories with many types 286
6.6 The number of nonisomorphic models 289
6.7 A touch of stability 290
7 Computability and complexity 299
7.1 Computable functions and Church’s thesis 301
7.1.1 Primitive recursive functions 302
7.1.2 The Ackermann function 307
7.1.3 Recursive functions 309
7.2 Computable sets and relations 312
7.3 Computing machines 316
7.4 Codes 320
7.5 Semi-decidable decision problems 327
7.6 Undecidable decision problems 332
7.6.1 Nonrecursive sets 332
7.6.2 The arithmetic hierarchy 335
7.7 Decidable decision problems 337
7.7.1 Examples 338
7.7.2 Time and space 344
7.7.3 Nondeterministic polynomial-time 347
7.8 NP-completeness 348
8 The incompleteness theorems 357
8.1 Axioms for first-order number theory 358
8.2 The expressive power of first-order number theory 362
8.3 Gödel’s First Incompleteness theorem 370
8.4 Gödel codes 374
8.5 Gödel’s Second Incompleteness theorem 380
8.6 Goodstein sequences 383
xii Contents
9 Beyond first-order logic 388
9.1 Second-order logic 388
9.2 Infinitary logics 392
9.3 Fixed-point logics 395
9.4 Lindström’s theorem 400
10 Finite model theory 408
10.1 Finite-variable logics 408
10.2 Classical failures 412
10.3 Descriptive complexity 417
10.4 Logic and the P = NP problem 423
Bibliography 426
Index 428

回复此楼