Mathematical Methods in LinguisticsElementary 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. |
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 |
643 | |
Other editions - View all
Mathematical Methods in Linguistics Barbara B.H. Partee,A.G. ter Meulen,R. Wall Limited preview - 2012 |
Mathematical Methods in Linguistics Barbara Partee,Alice ter Meulen,Robert Wall No preview available - 1990 |
Mathematical Methods in Linguistics Barbara Partee,Alice ter Meulen,Robert Wall No preview available - 1990 |
Common terms and phrases
accepts algebra alphabet applied argument assignment atomic statements automata automaton axiomatic system axioms called cardinality Chapter complement computation concatenation conditional conditional proof construct contains context free corresponding defined definition derivation determiners diagram empty example existential expression false finite number formal systems formula function given grammar identity element infinite input integers integral domain intensional interpretation intersection inverse irreflexive isomorphic John L₁ lattice linguistic logically equivalent mathematical natural language natural numbers negation node non-deterministic non-terminal notation notion one-to-one operation ordered pairs poset predicate logic premise proof properties prove pv q quantifiers rational numbers real numbers recursive reflexive regular languages relation rules of inference semantic value semilattice sentences sequence set theory set-theoretic statement logic string subset symbol syntactic syntax tableau tautology theorem transitive tree true truth table truth value Turing machine V₁ V₂ valid variable verbs