CONTENTS
LIST OF SYMBOLS = xiii
PREFACE = xvii
PART A: SET THEORY
CHAPTER 1. BASIC CONCEPTS OF SET THEORY = 3
1.1. The concept of a set = 3
1.2. Specification of sets = 4
1.3. Set-theoretic identity and cardinality = 8
1.4. Subsets = 9
1.5. Power sets = 11
1.6. Union and intersection = 11
1.7. Difference and complement = 14
1.8. Set-theoreticequalities = 17
Exercises = 23
CHAPTER 2: RELATIONS AND FUNCTIONS = 27
2.1. Ordered pairs and Cartesian products = 27
2.2. Relations = 28
2.3. Functions = 30
2.4. Composition = 33
Exercises = 36
CHAPTER 3: PROPERTIES OF RELATIONS = 39
3.1. Reflexivity, symmetry, transitivity, and connectedness = 39
3.2. Diagrams of relations = 43
3.3. Properties of inverses and complements = 44
3.4, Equivalence relations and partitions = 45
3.5. Orderings = 47
Exercises = 51
CHAPTER 4: INFINITIES = 55
4.1. Equivalent sets and cardinality = 55
4.2. Denumerability of sets = 58
4.3. Nondenumerable sets = 62
4.4 Infinite vs. unbounded = 69
Exercises = 71
APPENDIX A: SET-THEORETIC RECONSTRUCTION OF NUMBER SYSTEMS = 75
A.1 The natural numbers = 75
A.2. Extension to the set of all integers = 78
A.3. Extension to the set of all rational numbers = 80
A.4. Extension to the set of all real numbers = 82
REVIEW EXERCISES = 85
PART B: LOGIC AND FORMAL SYSTEMS
CHAPTER 5: BASIC CONCEPTS OF LOGIC AND FORMAL SYSTEMS = 87
5.1. Formal systems and models = 89
5.2. Natural languages and formal languages = 93
5.3. Syntax and semantics = 94
5.4, About statement logic and predicate logic = 95
CHAPTER 6: STATEMENT LOGIC = 99
6.1. Syntax = 99
6.2. Semantics: Truth values and truth tables = 101
6.2.1. Negation = 101
6.2.2. Conjunction = 102
6.2.3. Disjunction = 103
6.2.4 The Conditional = 104
6.2.5 The Biconditional = 105
6.3. Tautologies, contradictions and contingencies = 107
6.4. Logical equivalence, logical consequence and laws = 110
6.5. Natural deduction = 115
6.5.1. Conditional Proof = 120
6.5.2. Indirect Proof = 122
6.6. Beth Tableaux = 123
Exercises = 130
CHAPTER 7: PREDICATE LOGIC = 137
7.1. Syntax = 137
7.2. Semantics = 142
7.3. Quantifier laws and prenex normal form = 148
7.4. Natural deduction = 154
7.5. Beth Tableaux = 165
7.6. Formal and informal proofs = 170
7.7. Informal style in mathematical proofs = 172
Exercises = 175
CHAPTER 8: FORMAL SYSTEMS, AXIOMATIZATION, AND MODEL THEORY = 181
8.1. The syntactic side of formal systems = 181
8.1.1. Recursive definitions = 181
8.2. Axiomatic systems and derivations = 185
8.2.1. Extended axiomatic systems = 188
8.3. Semi-Thue systems = 191
8.4. Peano's axioms and proof by induction = 194
8.5. The semantic side of formal systems: model theory = 200
8.5.1. Theories and models = 200
8.5.2. Consistency, completeness, and independence = 202
8.5.3. Isomorphism = 203
8.5.4. An elementary formal system = 205
8.5.5. Axioms for ordering relations = 207
8.5.6. Axioms for string concatenation = 213
8.5.7. Models for Peano's axioms = 215
8.5.8. Axiomatization of set theory = 217
8.6. Axiomatizing logic = 219
8.6.1. An axiomatization of statement logic = 219
8.6.2. Consistency and independence proofs = 222
8.6.3. An axiomatization of predicate logic = 225
8.6.4. About completeness proofs = 227
8.6.5. Decidability = 229
8.6.6. G$$\ddot o$$del's incompleteness theorems = 230
8.6.7. Higher-order logic = 231
Exercises = 234
APPENDIX B-Ⅰ: ALTERNATIVE NOTATIONS AND CONNECTIVES = 239
APPENDIX B-Ⅱ: KLEENE'S THREE-VALUED LOGIC = 241
REVIEW EXERCISES = 245
PART C: ALGEBRA
CHAPTER 9: BASIC CONCEPTS OF ALGEBRA = 249
9.1. Definition of algebra = 249
9.2. Properties of operations = 250
9.3. Special elements = 251
9.4. Maps and morphisms = 253
Exercises = 255
CHAPTER 10: OPERATIONAL STRUCTURES = 257
10.1. Groups = 257
10.2. Subgroups, semigroups and monoids = 263
10.3. Integral domains = 266
10.4. Morphisms = 271
Exercises = 273
CHAPTER 11: LATTICES = 277
11.1. Posets, duality and diagrams = 277
11.2. Lattices, semilattices and sublattices = 280
11.3. Morphisms in lattices = 285
11.4. Filters and ideals = 287
11.5. Complemented, distributive and modular lattices = 290
Exercises = 295
CHAPTER 12: BOOLEAN AND HEYTING ALGEBRAS = 297
12.1. Boolean algebras = 297
12.2. Models of BA = 300
12.3. Representation by sets = 301
12.4. Heyting algebra = 303
12.5. Kripke semantics = 306
Exercises = 309
REVIEW EXERCISES = 311
PART D: ENGLISH AS A FORMAL LANGUAGE
CHAPTER 13: BASIC CONCEPTS = 317
13.1. Compositionality = 317
13.1.1. A compositional account of statement logic = 319
13.1.2. A compositional account of predicate logic = 323
13.1.3. Natural language and compositionality = 333
13.2. Lambada-abstraction = 338
13.2.1. Type theory = 338
13.2.2. The syntax and semantics of λ-abstraction = 341
13.2.3. A sample fragment = 343
13.2.4. The lambda-calculus = 348
13.2.5. Linguistic applications = 351
Exercises = 367
CHAPTER. 14: GENERALIZED QUANTIFIERS = 373
14.1. Determiners and quantifiers = 373
14.2 Conditions and quantifiers = 375
14.3. Properties of determiners and quantifiers = 380
14.4. Determiners as relations = 391
14.5. Context and quantification = 395
Exercises = 400
CHAPTER 15: INTENSIONALITY = 403
15.1. Frege's two problems = 403
15.2. Forms of opacity = 409
15.3. Indices and accessibility relations = 414
15.4. Tense and time = 423
15.5. Indexicality = 427
Exercises = 429
PART E: LANGUAGES, GRAMMARS, AND AUTOMATA
CHAPTER 16: BASIC CONCEPTS = 433
16.1. Languages, grammars and automata = 433
16.2. Grammars = 437
16.3. Trees = 439
16.3.1. Dominance = 440
16.3.2. Precedence = 441
16.3.3. Labeling = 443
16.4. Grammars and trees = 446
16.5. The Chomsky Hierarchy = 451
16.6. Languages and automata = 453
CHAPTER 17: FINITE AUTOMATA, REGULAR LANGUAGES AND TYPE 3 GRAMMARS = 455
17.1. Finite automata = 455
17.1.1. State diagrams of finite automata = 457
17.1.2. Formal definition of deterministic finite automata = 458
17.1.3. Non-deterministic finite automata = 460
17.1.4. Formal definition of non-deterministic finite automata = 462
17.1.5. Equivalence of deterministic and non-deterministic finite automata = 462
17.2. Regular languages = 464
17.2.1. Pumping Theorem for fal's = 471
17.3. Type 3 grammars and finite automaton languages = 473
17.3.1. Properties of regular languages = 477
17.3.2. Inadequacy of right-linear grammars for natural languages = 480
Exercises = 482
CHAPTER 18: PUSHDOWN AUTOMATA, CONTEXT FREE GRAMMARS AND LANGUAGES = 487
18.1. Pushdown automata = 487
18.2. Context free grammars and languages = 492
18.3. Pumping Theorem for cfl's = 494
18.4. Closure properties of context free languages = 497
18.5. Decidability questions for context free languages = 499
18.6. Are natural languages context free? = 503
Exercises = 505
CHAPTER 19: TURING MACHINES, RECURSIVELY ENUMERABLE LANGUAGES AND TYPE 0 GRAMMARS = 507
19.1. Turing machines = 507
19.1.1. Formal definitions = 510
19.2 Equivalent formulations of Turing machines = 514
19.3. Unrestricted grammars and Turing machines = 515
19.4. Church's Hypothesis = 517
19.5. Recursive versus recursively enumerable sets = 519
19.6. The universal Turning machine = 520
19.7. The Halting Problem for Turing machines = 522
Exercises = 525
CHAPTER 20: LINEAR BOUNDED AUTOMATA, CONTEXT SENSITIVE LANGUAGES AND TYPE 1 GRAMMARS = 529
20.1. Linear bounded automata = 529
20.1.1. Lba's and context sensitive grammars = 530
20.2. Context sensitive languages and recursive sets = 531
20.3. Closure and decision properties = 533
Exercises = 534
CHAPTER 21: LANGUAGES BETWEEN CONTEXT FREE AND CONTEXT SENSITIVE = 535
21.1. Indexed grammars = 536
21.2. Tree adjoining grammars = 542
21.3. Head grammars = 549
21.4. Categorial grammars = 550
CHAPTER 22: TRANSFORMATIONAL GRAMMARS = 555
APPENDIX E-Ⅰ: THE CHOMSKY HIERARCHY = 561
APPENDIX E-Ⅱ: SEMANTIC AUTOMATA = 565
REVIEW EXERCISES = 573
SOLUTIONS TO SELECTED EXERCISES = 575
Part A Chapter 1 = 575
Chapter 2 = 577
Chapter 3 = 578
Chapter 4 = 579
Review Problems, Part A = 581
Part B. Chapter 6 = 584
Chapter 7 = 589
Chapter 8 = 596
Review Problems, Part B = 599
Part C Chapter 9 = 603
Chapter 10 = 604
Chapter 11 = 609
Chapter 12 = 610
Review Exercises, Part C = 612
Part D. Chapter 13 = 616
Chapter 14 = 618
Chapter 15 = 621
Part E. Chapter 17 = 622
Chapter 18 = 628
Chapter 19 = 631
Chapter 20 = 632
Appendix E-Ⅱ = 633
Review Problems, Part E = 634
BIBLIOGRAPHY = 637
INDEX = 643
