《数理语言学》

1.0 Basic Concepts1

1.1 Sets and Members1

1 Set Theory1

1.2 Specification of a Set2

1.3 Types of Sets5

1.4 Infinities8

1.5 Operations on Sets14

1.5.1 Union14

1.5.2 Intersection15

1.5.3 Difference16

1.5.4 Complement17

1.6 Some Useful Laws in Set Theory17

1.7 Fuzzy Sets24

2.1 Cartesian Product27

2 Relations27

2.2 Relations30

2.3 Relational Diagrams36

2.4 Properties of Relations36

2.5 Equivalence Relations39

2.6 Ordering Relations41

3 Functions50

3.1 Ways to Indicate a Function50

3.2 Definition of a Function51

3.3 Into Functions52

3.4 Onto Functions53

3.5 One-to-one Functions54

3.7 Inverse Functions55

3.8 Total Functions55

3.6 One-to-one Correspondences55

3.9 Partial Functions56

3.10 Composite Functions57

3.11 Identity Functions59

3.12 Inverses of Composite Functions61

3.13 Characteristic Functions62

4 Algebra:Preliminaries65

4.1 Definition66

4.2 Operations66

4.3 Morphisms71

5 Groups and Integral Domains75

5.1 Semigroups75

5.2 Monoids76

5.3 Groups80

5.4 Subgroups88

5.5 Integral Domains90

6 Lattices and Boolean Algebras95

6.1 Lattices as Posets and as Algebras95

6.2 Properties of a Lattice97

6.3 Types of Lattices101

6.4 Boolean Algebras109

7 Logic:Preliminaries115

7.1 Definition115

7.2 Logical Form118

7.3 Deductive Logic121

7.4 Axiomatic Systems123

7.5 Models125

7.6 Formal Languages126

8 Propositional Logic129

8.1 Proposition129

8.2 Syntax131

8.3 Semantics135

8.3.1 Negation137

8.3.2 Conjunction138

8.3.3 Disjunction139

8.3.4 Implication141

8.3.5 Equivalence143

8.4 Tautologies and Contradictions146

8.5 Logical Equivalences and Logical Implications150

8.6 Deduction154

9 Predicate Logic162

9.1 The Internal Structure of a Sentence162

9.1.1 Individual Terms and Predicate Terms163

9.1.2 Quantifiers166

9.2 Syntax173

9.3 Semantics175

9.4 Translation183

9.5 Logical Equivalences and Logical Implications193

9.6 Deduction199

10 Higher-order Logic206

10.0 Deficiency of Predicate Logic206

10.1 A Typed Logical Language208

10.2 The Lambda Operator214

10.3 Syntax219

10.4 Translation220

10.5 Semantics222

10.6 Type-raising226

10.7 An Alternative Approach229

11 Tense Logic and Modal Logic243

11.1 Moments of Time243

11.2 Tense Operators246

11.3 Possible Worlds250

11.4 Modal Operators253

11.5 Relationships between Formulas261

12 Intensional Logic264

12.0 Semantic Puzzles264

12.1 Extension and Intension267

12.2 New Operators272

12.3 Syntax273

12.4 Semantics277

12.5 Interpretation283

13 Theory of Formal Languages289

13.1 Strings and Formal Languages289

13.2 Formal Grammars and Trees291

13.3 Types of Grammars and Languages299

13.3.1 Type 3 Grammars and Languages302

13.3.2 Type 2 Grammars and Languages307

13.3.3 Type 1 Grammars and Languages316

13.3.4 Type 0 Grammars and Languages317

13.4 The Complexity of Natural Languages318

14 Theory of Automata320

14.1 Definition320

14.2 Finite Automata322

14.3 Pushdown Automata328

14.4 Linear Bounded Automata336

14.5 Turing Machines337

14.6 The Relation between Formal Language Theory and Linguistic Theory349

Key to Exercises352

References384

Index392