Mathematical Methods in Linguistics

✍ Scribed by Barbara B.H. Partee, A.G. ter Meulen, R. Wall

• Publisher: Springer
• Year: 1990
• Tongue: English
• Leaves: 686
• Series: Studies in Linguistics and Philosophy
• Edition: 1
• Category: Library

✦ Synopsis

Elementary set theory accustoms the students to mathematical abstraction, includes the standard constructions of relations, functions, and orderings, and leads to a discussion of the various orders of infinity. The material on logic covers not only the standard statement logic and first-order predicate logic but includes an introduction to formal systems, axiomatization, and model theory. The section on algebra is presented with an emphasis on lattices as well as Boolean and Heyting algebras. Background for recent research in natural language semantics includes sections on lambda-abstraction and generalized quantifiers. Chapters on automata theory and formal languages contain a discussion of languages between context-free and context-sensitive and form the background for much current work in syntactic theory and computational linguistics. The many exercises not only reinforce basic skills but offer an entry to linguistic applications of mathematical concepts. For upper-level undergraduate students and graduate students in theoretical linguistics, computer-science students with interests in computational linguistics, logic programming and artificial intelligence, mathematicians and logicians with interests in linguistics and the semantics of natural language.

✦ Table of Contents

Cover......Page 1
Title Page......Page 3
Table of Contents......Page 5
List of Symbols......Page 13
Preface......Page 17
Part A: Set Theory......Page 21
1.1 The concept of a set......Page 23
1.2 Specification of sets......Page 24
1.3 Set-theoretic identity and cardinality......Page 28
1.4 Subsets......Page 29
1.6 Union and intersection......Page 31
1.7 Difference and complement......Page 34
1.8 Set-theoretic equalities......Page 37
Exercises......Page 43
2.1 Ordered pairs and Cartesian products......Page 47
2.2 Relations......Page 48
2.3 Functions......Page 50
2.4 Composition......Page 53
Exercises......Page 56
3.1 Reflexivity, symmetry, transitivity, and connectedness......Page 59
3.2 Diagrams of relations......Page 63
3.3 Properties of inverses and complements......Page 64
3.4 Equivalence relations and partitions......Page 65
3.5 Orderings......Page 67
Exercises......Page 71
4.1 Equivalent sets and cardinality......Page 75
4.2 Denumerability of sets......Page 78
4.3 Nondenumerable sets......Page 82
4.4 Infinite vs. unbounded......Page 89
Exercises......Page 91
A.1 The natural numbers......Page 95
A.2 Extension to the set of all integers......Page 98
A.3 Extension to the set of all rational numbers......Page 100
A.4 Extension to the set of all real numbers......Page 102
Review Exercises......Page 105
Part B: Logic and Formal Systems......Page 107
5.1 Formal systems and models......Page 109
5.2 Natural languages and formal languages......Page 113
5.3 Syntax and semantics......Page 114
5.4 About statement logic and predicate logic......Page 115
6.1 Syntax......Page 119
6.2.1 Negation......Page 121
6.2.2 Conjunction......Page 122
6.2.3 Disjunction......Page 123
6.2.4 The Conditional......Page 124
6.2.5 The Biconditional......Page 125
6.3 Tautologies, contradictions and contingencies......Page 127
6.4 Logical equivalence, logical consequence and laws......Page 130
Laws of statement logic......Page 132
6.5 Natural deduction......Page 135
Rules of Inference......Page 138
6.5.1 Conditional Proof......Page 140
6.5.2 Indirect Proof......Page 142
6.6 Beth Tableaux......Page 143
Construction Rules for Beth Tableaux......Page 148
Exercises......Page 150
7.1 Syntax......Page 157
7.2 Semantics......Page 162
7.3 Quantifier laws and prenex normal form......Page 168
7.4 Natural deduction......Page 174
7.5 Beth Tableaux......Page 185
7.6 Formal and informal proofs......Page 190
7.7 Informal style in mathematical proofs......Page 192
Exercises......Page 195
8.1.1 Recursive definitions......Page 201
8.2 Axiomatic systems and derivations......Page 205
8.2.1 Extended axiomatic systems......Page 208
8.3 Semi-Thue systems......Page 211
8.4 Peano’s axioms and proof by induction......Page 214
8.5.1 Theories and models......Page 220
8.5.2 Consistency, completeness, and independence......Page 222
8.5.3 Isomorphism......Page 223
8.5.4 An elementary formal system......Page 225
8.5.5 Axioms for ordering relations......Page 227
S.5.6 Axioms for string concatenation......Page 233
8.5.7 Models for Peano’s axioms......Page 235
8.5.8 Axiomatization of set theory......Page 237
8.6.1 An axiomatization of statement logic......Page 239
8.6.2 Consistency and independence proofs......Page 242
8.6.3 An axiomatization of predicate logic......Page 245
8.6.4 About completeness proofs......Page 247
8.6.5 Decidability......Page 249
8.6.6 Gödel’s incompleteness theorems......Page 250
8.6.7 Higher-order logic......Page 251
Exercises......Page 254
Appendix B-I Alternative Notations and Connectives......Page 259
Appendix B-II Kleene’s Three-valued Logic......Page 261
Review Exercises......Page 265
Part C: Algebra......Page 267
9.1 Definition of algebra......Page 269
9.2 Properties of operations......Page 270
9.3 Special elements......Page 271
9.4 Maps and morphisms......Page 273
Exercises......Page 275
10.1 Groups......Page 277
10.2 Subgroups, semigroups and monoids......Page 283
10.3 Integral domains......Page 286
10.4 Morphisms......Page 291
Exercises......Page 293
11.1 Posets, duality and diagrams......Page 297
11.2 Lattices, semilattices and sublattices......Page 300
11.3 Morphisms in lattices......Page 305
11.4 Filters and ideals......Page 307
11.5 Complemented, distributive and modular lattices......Page 310
Exercises......Page 315
12.1 Boolean algebras......Page 317
12.2 Models of BA......Page 320
12.3 Representation by sets......Page 321
12.4 Heyting algebra......Page 323
12.5 Kripke semantics......Page 326
Exercises......Page 329
Review Exercises......Page 331
Part D: English as a Formal Language......Page 335
13.1 Compositionality......Page 337
13.1.1 A compositional account of statement logic......Page 339
13.1.2 A compositional account of predicate logic......Page 343
13.1.3 Natural language and compositionality......Page 353
13.2.1 Type theory......Page 358
13.2.2 The syntax and semantics of A-abstraction......Page 361
I. Syntax of TL......Page 363
II. Semantics of TL......Page 366
13.2.4 The lambda-calculus......Page 368
13.2.5 Linguistic applications......Page 371
I. Phrasal conjunction......Page 372
II. Relative clauses......Page 375
III. Generalized quantifiers......Page 378
IV. VP-deletion......Page 380
V. Passive......Page 382
VI. Meaning postulates and lexical rules......Page 384
Exercises......Page 387
14.1 Determiners and quantifiers......Page 393
14.2 Conditions on quantifiers......Page 395
14.3 Properties of determiners and quantifiers......Page 400
14.4 Determiners as relations......Page 411
14.5 Context and quantification......Page 415
Exercises......Page 420
15.1 Frege’s two problems......Page 423
15.2 Forms of opacity......Page 429
15.3 Indices and accessibility relations......Page 434
15.4 Tense and time......Page 443
15.5 Indexicality......Page 447
Exercises......Page 449
Part E: Languages, Grammars and Automata......Page 451
16.1 Languages, grammars and automata......Page 453
16.2 Grammars......Page 457
16.3 Trees......Page 459
16.3.1 Dominance......Page 460
16.3.2 Precedence......Page 461
16.3.3 Labeling......Page 463
16.4 Grammars and trees......Page 466
16.5 The Chomsky Hierarchy......Page 471
16.6 Languages and automata......Page 473
17.1 Finite automata......Page 475
17.1.1 State diagrams of finite automata......Page 477
17.1.2 Formal definition of deterministic finite automata......Page 478
17.1.3 Non-deterministic finite automata......Page 480
17.1.5 Equivalence of deterministic and non-deterministic finite automata......Page 482
17.2 Regular languages......Page 484
17.2.1 Pumping Theorem for fal’ s......Page 491
17.3 Type 3 grammars and finite automaton languages......Page 493
17.3.1 Properties of regular languages......Page 497
17.3.2 Inadequacy of right-linear grammars for natural languages......Page 500
Exercises......Page 502
18.1 Pushdown automata......Page 507
18.2 Context free grammars and languages......Page 512
18.3 Pumping Theorem for cfl’s......Page 514
18.4 Closure properties of context free languages......Page 517
18.5 Decidability questions for context free languages......Page 519
18.6 Are natural languages context free?......Page 523
Exercises......Page 525
19.1 Turing machines......Page 527
19.1.1 Formal definitions......Page 530
19.2 Equivalent formulations of Turing machines......Page 534
19.3 Unrestricted grammars and Turing machines......Page 535
19.4 Church’s Hypothesis......Page 537
19.5 Recursive versus recursively enumerable sets......Page 539
19.6 The universal Turing machine......Page 540
19.7 The Halting Problem for Turing machines......Page 542
Exercises......Page 545
20.1 Linear bounded automata......Page 549
20.1.1 Lba’s and context sensitive grammars......Page 550
20.2 Context sensitive languages and recursive sets......Page 551
20.3 Closure and decision properties......Page 553
Exercises......Page 554
21 Languages Between Context Free and Context Sensitive......Page 555
21.1 Indexed grammars......Page 556
21.2 Tree adjoining grammars......Page 562
21.3 Head grammars......Page 568
21.4 Categorial grammars......Page 570
22 Transformational Grammars......Page 575
Appendix E-I: The Chomsky Hierarchy......Page 581
Appendix E-II: Semantic Automata......Page 585
Exercises......Page 592
Review Exercises......Page 593
CHAPTER 1......Page 595
CHAPTER 2......Page 597
CHAPTER 3......Page 598
CHAPTER 4......Page 599
REVIEW PROBLEMS, PART A......Page 601
CHAPTER 6......Page 604
CHAPTER 7......Page 609
CHAPTER 8......Page 616
REVIEW PROBLEMS, PART B......Page 619
CHAPTER 9......Page 623
CHAPTER 10......Page 624
CHAPTER 11......Page 629
CHAPTER 12......Page 630
REVIEW EXERCISES, PART C......Page 632
CHAPTER 13......Page 636
CHAPTER 14......Page 638
CHAPTER 15......Page 641
CHAPTER 17......Page 642
CHAPTER 18......Page 648
CHAPTER 19......Page 651
CHAPTER 20......Page 652
APPENDIX E II......Page 653
REVIEW PROBLEMS, PART E......Page 654
Bibliography......Page 657
Index......Page 663