Mathematical Methods in Linguistics

by Partee, Barbara H.; Wall, Robert E.; Ter Meulen, Alice

• ISBN13: 9789027722454
• ISBN10: 9027722455
• Format: Paperback
• Copyright: 1987-07-01
• Publisher: Kluwer Academic Pub

Summary

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

List of Symbols	xv
Preface	xix
A SET THEORY	1	(74)
Basic Concepts of Set Theory	3	(24)
The concept of a set	3	(1)
Specification of sets	4	(4)
Set-theoretic identity and cardinality	8	(2)
Subsets	10	(1)
Power sets	11	(1)
Union and intersection	11	(4)
Difference and complement	15	(2)
Set-theoretic equalities	17	(10)
Exercises	23	(4)
Relations and Functions	27	(12)
Ordered pairs and Cartesian products	27	(1)
Relations	28	(2)
Functions	30	(3)
Composition	33	(6)
Exercises	36	(3)
Properties of Relations	39	(16)
Reflexivity, symmetry, transitivity, and connectedness	39	(4)
Diagrams of relations	43	(1)
Properties of inverses and complements	44	(1)
Equivalence relations and partitions	45	(2)
Orderings	47	(8)
Exercises	51	(4)
Infinities	55	(20)
Equivalent sets and cardinality	55	(3)
Denumerability of sets	58	(4)
Nondenumerable sets	62	(8)
Infinite vs. unbounded	70	(5)
Exercises	71	(4)
Appendix A: Set-theoretic Reconstruction of Number Systems	75	(10)
A.1 The natural numbers	75	(3)
A.2 Extension to the set of all integers	78	(2)
A.3 Extension to the set of all rational numbers	80	(1)
A.4 Extension to the set of all real numbers	81	(4)
Review Exercises	83	(2)
B LOGIC AND FORMAL SYSTEMS	85	(152)
Basic Concepts of Logic and Formal Systems	87	(10)
Formal systems and models	87	(4)
Natural languages and formal languages	91	(1)
Syntax and semantics	92	(1)
About statement logic and predicate logic	93	(4)
Statement Logic	97	(38)
Syntax	97	(2)
Semantics: Truth values and truth tables	99	(5)
Negation	99	(1)
Conjunction	100	(1)
Disjunction	101	(1)
The Conditional	102	(1)
The Biconditional	103	(1)
Tautologies, contradictions and contingencies	104	(4)
Logical equivalence, logical consequence and laws	108	(4)
Natural deduction	112	(9)
Conditional Proof	118	(2)
Indirect Proof	120	(1)
Beth Tableaux	121	(14)
Exercises	128	(7)
Predicate Logic	135	(44)
Syntax	135	(5)
Semantics	140	(6)
Quantifier laws and prenex normal form	146	(6)
Natural deduction	152	(11)
Beth Tableaux	163	(5)
Formal and informal proofs	168	(2)
Informal style in mathematical proofs	170	(9)
Exercises	173	(6)
Formal Systems, Axiomatization, and Model Theory	179	(58)
The syntactic side of formal systems	179	(4)
Recursive definitions	179	(4)
Axiomatic systems and derivations	183	(7)
Extended axiomatic systems	186	(4)
Semi-Thue systems	190	(2)
Peano's axioms and proof by induction	192	(6)
The semantic side of formal systems: model theory	198	(19)
Theories and models	198	(2)
Consistency, completeness, and independence	200	(2)
Isomorphism	202	(2)
An elementary formal system	204	(2)
Axioms for ordering relations	206	(5)
Axioms for string concatenation	211	(3)
Models for Peano's axioms	214	(1)
Axiomatization of set theory	215	(2)
Axiomatizing logic	217	(20)
An axiomatization of statement logic	217	(3)
Consistency and independence proofs	220	(3)
An axiomatization of predicate logic	223	(2)
About completeness proofs	225	(2)
Decidability	227	(1)
Godel's incompleteness theorems	228	(1)
Higher-order logic	229	(3)
Exercises	232	(5)
Appendix B-I: Alternative Notations and Connectives	237	(2)
Appendix B-II: Kleene's Three-Valued Logic	239	(6)
Review Exercises	243	(2)
C ALGEBRA	245	(68)
Basic Concepts of Algebra	247	(8)
Definition of algebra	247	(1)
Properties of operations	248	(1)
Special elements	249	(2)
Maps and morphisms	251	(4)
Exercises	253	(2)
Operational Structures	255	(20)
Groups	255	(6)
Subgroups, semigroups and monoids	261	(3)
Integral domains	264	(5)
Morphisms	269	(6)
Exercises	271	(4)
Lattices	275	(20)
Posets, duality and diagrams	275	(3)
Lattices, semilattices and sublattices	278	(5)
Morphisms in lattices	283	(2)
Filters and ideals	285	(3)
Complemented, distributive and modular lattices	288	(7)
Exercises	293	(2)
Boolean and Heyting Algebras	295	(18)
Boolean algebras	295	(3)
Models of BA	298	(1)
Representation by sets	299	(2)
Heyting algebra	301	(3)
Kripke semantics	304	(9)
Exercises	307	(2)
Review Exercises	309	(4)
D ENGLISH AS A FORMAL LANGUAGE	313	(116)
Basic Concepts	315	(56)
Compositionality	315	(21)
A compositional account of statement logic	317	(4)
A compositional account of predicate logic	321	(10)
Natural language and compositionality	331	(5)
Lambda abstraction	336	(35)
Type theory	336	(3)
The syntax and semantics of λ-abstraction	339	(2)
A sample fragment	341	(5)
The lambda calculus	346	(3)
Linguistic applications	349	(16)
Exercises	365	(6)
Generalized Quantifiers	371	(30)
Determiners and quantifiers	371	(2)
Conditions on quantifiers	373	(5)
Properties of determiners and quantifiers	378	(10)
Determiners as relations	388	(4)
Context and quantification	392	(9)
Exercises	397	(4)
Intensionality	401	(28)
Frege's two problems	401	(6)
Forms of opacity	407	(5)
Indices and accessibility relations	412	(9)
Tense and time	421	(4)
Indexicality	425	(4)
Exercises	427	(2)
E LANGUAGES, GRAMMARS, AND AUTOMATA	429	(130)
Basic Concepts	431	(22)
Languages, grammars and automata	431	(4)
Grammars	435	(2)
Trees	437	(7)
Dominance	438	(1)
Precedence	439	(2)
Labeling	441	(3)
Grammars and trees	444	(4)
The Chomsky Hierarchy	448	(3)
Languages and automata	451	(2)
Finite Automata, Regular Languages and Type 3 Grammars	453	(32)
Finite automata	453	(9)
State diagrams of finite automata	455	(1)
Formal definition of deterministic finite automata	455	(3)
Non-deterministic finite automata	458	(2)
Formal definition of non-deterministic finite automata	460	(1)
Equivalence of deterministic and non-deterministic finite automata	460	(2)
Regular languages	462	(9)
Pumping Theorem for fal's	468	(3)
Type 3 grammars and finite automaton languages	471	(14)
Properties of regular languages	475	(2)
Inadequacy of right-linear grammars for natural languages	477	(3)
Exercises	480	(5)
Pushdown Automata, Context Free Grammars and Languages	485	(20)
Pushdown automata	485	(5)
Context free grammars and languages	490	(2)
Pumping Theorem for cfl's	492	(3)
Closure properties of context free languages	495	(3)
Decidability questions for context free languages	498	(3)
Are natural languages context free?	501	(4)
Exercises	503	(2)
Turing Machines, Recursively Enumerable Languages and Type 0 Grammars	505	(22)
Turing machines	505	(7)
Formal definitions	508	(4)
Equivalent formulations of Turing machines	512	(1)
Unrestricted grammars and Turing machines	513	(2)
Church's Hypothesis	515	(2)
Recursive versus recursively enumerable sets	517	(1)
The universal Turing machine	518	(2)
The Halting Problem for Turing machines	520	(7)
Exercises	523	(4)
Linear Bounded Automata, Context Sensitive Languages and Type 1 Grammars	527	(6)
Linear bounded automata	527	(2)
Lba's and context sensitive grammars	528	(1)
Context sensitive languages and recursive sets	529	(2)
Closure and decision properties	531	(2)
Exercises	532	(1)
Languages Between Context Free and Context Sensitive	533	(26)
Indexed grammars	534	(12)
Tree adjoining grammars	540	(6)
Head grammars	546	(1)
Categorial grammars	547	(6)
Transformational Grammars	553	(6)
Appendix E-I: The Chomsky Hierarchy	559	(4)
Appendix E-II: Semantic Automata	563	(10)
Exercises	570	(1)
Review Exercises	571	(2)
Solutions to Selected Exercises	573	(62)
Chapter 1	573	(2)
Chapter 2	575	(1)
Chapter 3	576	(1)
Chapter 4	577	(2)
Review problems, Part A	579	(3)
Chapter 6	582	(5)
Chapter 7	587	(7)
Chapter 8	594	(3)
Review problems, Part B	597	(4)
Chapter 9	601	(1)
Chapter 10	602	(4)
Chapter 11	606	(2)
Chapter 12	608	(2)
Review problems, Part C	610	(4)
Chapter 13	614	(2)
Chapter 14	616	(3)
Chapter 15	619	(1)
Chapter 17	620	(6)
Chapter 18	626	(3)
Chapter 19	629	(1)
Chapter 20	630	(1)
Appendix E-II	631	(1)
Review problems, Part E	632	(3)
Bibliography	635	(12)
Index	647