数理语言学PDF电子书下载

1.0 Basic Concepts 1

1.1 Sets and Members 1

1 Set Theory 1

1.2 Specification of a Set 2

1.3 Types of Sets 5

1.4 Infinities 8

1.5 Operations on Sets 14

1.5.1 Union 14

1.5.2 Intersection 15

1.5.3 Difference 16

1.5.4 Complement 17

1.6 Some Useful Laws in Set Theory 17

1.7 Fuzzy Sets 24

2.1 Cartesian Product 27

2 Relations 27

2.2 Relations 30

2.3 Relational Diagrams 36

2.4 Properties of Relations 36

2.5 Equivalence Relations 39

2.6 Ordering Relations 41

3 Functions 50

3.1 Ways to Indicate a Function 50

3.2 Definition of a Function 51

3.3 Into Functions 52

3.4 Onto Functions 53

3.5 One-to-one Functions 54

3.7 Inverse Functions 55

3.8 Total Functions 55

3.6 One-to-one Correspondences 55

3.9 Partial Functions 56

3.10 Composite Functions 57

3.11 Identity Functions 59

3.12 Inverses of Composite Functions 61

3.13 Characteristic Functions 62

4 Algebra:Preliminaries 65

4.1 Definition 66

4.2 Operations 66

4.3 Morphisms 71

5 Groups and Integral Domains 75

5.1 Semigroups 75

5.2 Monoids 76

5.3 Groups 80

5.4 Subgroups 88

5.5 Integral Domains 90

6 Lattices and Boolean Algebras 95

6.1 Lattices as Posets and as Algebras 95

6.2 Properties of a Lattice 97

6.3 Types of Lattices 101

6.4 Boolean Algebras 109

7 Logic:Preliminaries 115

7.1 Definition 115

7.2 Logical Form 118

7.3 Deductive Logic 121

7.4 Axiomatic Systems 123

7.5 Models 125

7.6 Formal Languages 126

8 Propositional Logic 129

8.1 Proposition 129

8.2 Syntax 131

8.3 Semantics 135

8.3.1 Negation 137

8.3.2 Conjunction 138

8.3.3 Disjunction 139

8.3.4 Implication 141

8.3.5 Equivalence 143

8.4 Tautologies and Contradictions 146

8.5 Logical Equivalences and Logical Implications 150

8.6 Deduction 154

9 Predicate Logic 162

9.1 The Internal Structure of a Sentence 162

9.1.1 Individual Terms and Predicate Terms 163

9.1.2 Quantifiers 166

9.2 Syntax 173

9.3 Semantics 175

9.4 Translation 183

9.5 Logical Equivalences and Logical Implications 193

9.6 Deduction 199

10 Higher-order Logic 206

10.0 Deficiency of Predicate Logic 206

10.1 A Typed Logical Language 208

10.2 The Lambda Operator 214

10.3 Syntax 219

10.4 Translation 220

10.5 Semantics 222

10.6 Type-raising 226

10.7 An Alternative Approach 229

11 Tense Logic and Modal Logic 243

11.1 Moments of Time 243

11.2 Tense Operators 246

11.3 Possible Worlds 250

11.4 Modal Operators 253

11.5 Relationships between Formulas 261

12 Intensional Logic 264

12.0 Semantic Puzzles 264

12.1 Extension and Intension 267

12.2 New Operators 272

12.3 Syntax 273

12.4 Semantics 277

12.5 Interpretation 283

13 Theory of Formal Languages 289

13.1 Strings and Formal Languages 289

13.2 Formal Grammars and Trees 291

13.3 Types of Grammars and Languages 299

13.3.1 Type 3 Grammars and Languages 302

13.3.2 Type 2 Grammars and Languages 307

13.3.3 Type 1 Grammars and Languages 316

13.3.4 Type 0 Grammars and Languages 317

13.4 The Complexity of Natural Languages 318

14 Theory of Automata 320

14.1 Definition 320

14.2 Finite Automata 322

14.3 Pushdown Automata 328

14.4 Linear Bounded Automata 336

14.5 Turing Machines 337

14.6 The Relation between Formal Language Theory and Linguistic Theory 349

Key to Exercises 352

References 384

Index 392