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