# Mathematical Methods in Linguistics

Springer Science & Business Media, Apr 30, 1990 - Language Arts & Disciplines - 666 pages
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.

### What people are saying -Write a review

We haven't found any reviews in the usual places.

### Contents

 Basic Concepts of Set Theory 3 12 Specification of sets 4 13 Settheoretic identity and cardinality 8 14 Subsets 9 15 Power sets 11 17 Difference and complement 14 18 Settheoretic equalities 17 Relations and Functions 27
 Basic Concepts 317 1311 A compositional account of statement logic 319 1312 A compositional account of predicate logic 323 1313 Natural language and compositionality 333 132 Lambdaabstraction 338 1322 The syntax and semantics of Aabstraction 341 1323 A sample fragment 343 1324 The lambdacalculus 348

 22 Relations 28 23 Functions 30 24 Composition 33 Properties of Relations 39 32 Diagrams of relations 43 33 Properties of inverses and complements 44 34 Equivalence relations and partitions 45 35 Orderings 47 Exercises 51 Infinities 55 42 Denumerability of sets 58 43 Nondenumerable sets 62 44 Infinite vs unbounded 69 Exercises 71 SetTheoretic Reconstruction of Number Systems 75 A2 Extension to the set of all integers 78 A3 Extension to the set of all rational numbers 80 A4 Extension to the set of all real numbers 82 Review Exercises 85 Basic Concepts of Logic and Formal Systems 89 52 Natural languages and formal languages 93 53 Syntax and semantics 94 54 About statement logic and predicate logic 95 Statement Logic 99 Truth values and truth tables 101 622 Conjunction 102 623 Disjunction 103 624 The Conditional 104 625 The Biconditional 105 63 Tautologies contradictions and contingencies 107 64 Logical equivalence logical consequence and laws 110 65 Natural deduction 115 651 Conditional Proof 120 652 Indirect Proof 122 66 Beth Tableaux 123 Exercises 130 Predicate Logic 137 72 Semantics 142 73 Quantifier laws and prenex normal form 148 74 Natural deduction 154 75 Beth Tableaux 165 77 Informal style in mathematical proofs 172 Exercises 175 Formal Systems Axiomatization and Model Theory 181 82 Axiomatic systems and derivations 185 821 Extended axiomatic systems 188 83 SemiThue systems 191 84 Peanos axioms and proof by induction 194 model theory 200 852 Consistency completeness and independence 202 853 Isomorphism 203 854 An elementary formal system 205 855 Axioms for ordering relations 207 856 Axioms for string concatenation 213 857 Models for Peanos axioms 215 858 Axiomatization of set theory 217 86 Axiomatizing logic 219 862 Consistency and independence proofs 222 863 An axiomatization of predicate logic 225 864 About completeness proofs 227 865 Decidability 229 866 Godels incompleteness theorems 230 867 Higherorder logic 231 Exercises 234 Alternative Notations and Connectives 239 Kleenes Threevalued Logic 241 Review Exercises 245 Basic Concepts of Algebra 249 92 Properties of operations 250 93 Special elements 251 94 Maps and morphisms 253 Exercises 255 Operational Structures 257 102 Subgroups semigroups and monoids 263 103 Integral domains 266 104 Morphisms 271 Exercises 273 Lattices 277 112 Lattices semilattices and sublattices 280 113 Morphisms in lattices 285 114 Filters and ideals 287 115 Complemented distributive and modular lattices 290 Exercises 295 Boolean and Heyting Algebras 297 122 Models of BA 300 123 Representation by sets 301 124 Heyting algebra 303 125 Kripke semantics 306 Exercises 309 Review Exercises 311
 1325 Linguistic applications 351 Exercises 367 Generalized Quantifiers 373 142 Conditions on quantifiers 375 143 Properties of determiners and quantifiers 380 144 Determiners as relations 391 145 Context and quantification 395 Exercises 400 Intensionality 403 152 Forms of opacity 409 153 Indices and accessibility relations 414 154 Tense and time 423 155 Indexicality 427 Exercises 429 Basic Concepts 433 162 Grammars 437 163 Trees 439 1631 Dominance 440 1632 Precedence 441 1633 Labeling 443 164 Grammars and trees 446 165 The Chomsky Hierarchy 451 166 Languages and automata 453 Finite Automata Regular Languages and Type 3 Grammars 455 1711 State diagrams of finite automata 457 1712 Formal definition of deterministic finite automata 458 1713 Nondeterministic finite automata 460 1714 Formal definition of nondeterministic finite automata 462 172 Regular languages 464 1721 Pumping Theorem for fals 471 173 Type 3 grammars and finite automaton languages 473 1731 Properties of regular languages 477 1732 Inadequacy of rightlinear grammars for natural languages 480 Exercises 482 Pushdown Automata Context Free Grammars and Languages 487 182 Context free grammars and languages 492 183 Pumping Theorem for cfls 494 184 Closure properties of context free languages 497 185 Decidability questions for context free languages 499 186 Are natural languages context free? 503 Exercises 505 Turing Machines Recursively Enumerable Languages and Type 0 Grammars 507 1911 Formal definitions 510 192 Equivalent formulations of Turing machines 514 193 Unrestricted grammars and Turing machines 515 194 Churchs Hypothesis 517 195 Recursive versus recursively enumerable sets 519 196 The universal Turing machine 520 197 The Halting Problem for Turing machines 522 Exercises 525 Linear Bounded Automata Context Sensitive Languages and Type 1 Grammars 529 2011 Lbas and context sensitive grammars 530 202 Context sensitive languages and recursive sets 531 203 Closure and decision properties 533 Exercises 534 Languages Between Context Free and Context Sensitive 535 211 Indexed grammars 536 212 Tree adjoining grammars 542 213 Head grammars 548 214 Categorial grammars 550 Transformational Grammars 555 The Chomsky Hierarchy 561 Semantic Automata 565 Review Exercises 573 Solutions to selected exercises 575 CHAPTER 2 577 CHAPTER 3 578 CHAPTER 4 579 REVIEW PROBLEMS PART A 581 PART B 584 CHAPTER 7 589 CHAPTER 8 596 REVIEW PROBLEMS PART B 599 PART C 603 CHAPTER 10 604 CHAPTER 11 609 CHAPTER 12 610 REVIEW EXERCISES PART C 612 PART D 616 CHAPTER 14 618 CHAPTER 15 621 PART E 622 CHAPTER 18 628 CHAPTER 19 631 CHAPTER 20 632 APPENDIX E II 633 REVIEW PROBLEMS PART E 634 Bibliography 637 Index 643 Copyright