Discrete Mathematical Structures

by Kolman, Bernard; Busby, Robert; Ross, Sharon C.

• ISBN13: 9780130457974
• ISBN10: 0130457973
• Edition: 5th
• Format: Hardcover
• Copyright: 2009-01-01
• Publisher: Prentice Hall

Summary

Combining a careful selection of topics with coverage of theirgenuineapplications in computer science, this book, more than any other in this field, is clearly and concisely written, presenting the basic ideas of discrete mathematical structures in a manner that is understandable.Limiting its scope and depth of topics to those that readers can actually utilize, this book covers first the fundamentals, then follows with logic, counting, relations and digraphs, functions, order relations and structures, trees, graph theory, semigroups and groups, languages and finite-state machines, and groups and coding.With its comprehensive appendices and index, this book can be an excellent reference work for mathematicians and those in the field of computer science.

Table of Contents

Preface	viii
A Word to Students	xii
1 Fundamentals	1	(49)
1.1 Sets and Subsets	2	(3)
1.2 Operations on Sets	5	(8)
1.3 Sequences	13	(7)
1.4 Division in the Integers	20	(12)
1.5 Matrices	32	(9)
1.6 Mathematical Structures	41	(9)
2 Logic	50	(28)
2.1 Propositions and Logical Operations	51	(6)
2.2 Conditional Statements	57	(5)
2.3 Methods of Proof	62	(5)
2.4 Mathematical Induction	67	(11)
3 Counting	78	(32)
3.1 Permutations	79	(4)
3.2 Combinations	83	(5)
3.3 Pigeonhole Principle	88	(3)
3.4 Elements of Probability	91	(9)
3.5 Recurrence Relations	100	(10)
4 Relations and Digraphs	110	(58)
4.1 Product Sets and Partitions	111	(4)
4.2 Relations and Digraphs	115	(8)
4.3 Paths in Relations and Digraphs	123	(6)
4.4 Properties of Relations	129	(7)
4.5 Equivalence Relations	136	(4)
4.6 Computer Representation of Relations and Digraphs	140	(7)
4.7 Operations on Relations	147	(10)
4.8 Transitive Closure and Warshall's Algorithm	157	(11)
5 Functions	168	(32)
5.1 Functions	169	(9)
5.2 Functions for Computer Science	178	(5)
5.3 Growth of Functions	183	(5)
5.4 Permutation Functions	188	(12)
6 Order Relations and Structures	200	(54)
6.1 Partially Ordered Sets	201	(10)
6.2 Extremal Elements of Partially Ordered Sets	211	(5)
6.3 Lattices	216	(10)
6.4 Finite Boolean Algebras	226	(7)
6.5 Functions on Boolean Algebras	233	(4)
6.6 Circuit Design	237	(17)
7 Trees	254	(36)
7.1 Trees	254	(5)
7.2 Labeled Trees	259	(5)
7.3 Tree Searching	264	(9)
7.4 Undirected Trees	273	(7)
7.5 Minimal Spanning Trees	280	(10)
8 Topics in Graph Theory	290	(39)
8.1 Graphs	291	(5)
8.2 Euler Paths and Circuits	296	(8)
8.3 Hamiltonian Paths and Circuits	304	(3)
8.4 Transport Networks	307	(8)
8.5 Matching Problems	315	(5)
8.6 Coloring Graphs	320	(9)
9 Semigroups and Groups	329	(43)
9.1 Binary Operations Revisited	330	(4)
9.2 Semigroups	334	(7)
9.3 Products and Quotients of Semigroups	341	(6)
9.4 Groups	347	(11)
9.5 Products and Quotients of Groups	358	(5)
9.6 Other Mathematical Structures	363	(9)
10 Languages and Finite-State Machines	372	(44)
10.1 Languages	373	(8)
10.2 Representations of Special Grammars and Languages	381	(9)
10.3 Finite-State Machines	390	(6)
10.4 Monoids, Machines, and Languages	396	(5)
10.5 Machines and Regular Languages	401	(6)
10.6 Simplification of Machines	407	(9)
11 Groups and Coding	416	(27)
11.1 Coding of Binary Information and Error Detection	417	(11)
11.2 Decoding and Error Correction	428	(8)
11.3 Public Key Cryptology	436	(7)
Appendix A: Algorithms and Pseudocode	443	(11)
Appendix B: Additional Experiments in Discrete Mathematics	454	(5)
Answers to Odd-Numbered Exercises	459	(38)
Answers to Chapter Self-Tests	497
Glossary	G-1
Index	I-1
Photo Credits	P-1
0521016983
List of Figures and Tables	ix
Acknowledgments	xiii
Abbreviations	xvii
1 THE POLITICS OF TAXATION	1	(37)
The Problem in Perspective	5	(4)
The Argument	9	(14)
Alternative Explanations	23	(9)
Plan of the Book: A "Nested" Approach to Comparative Analysis	32	(6)
2 THE TAX STATE IN COMPARATIVE PERSPECTIVE	38	(30)
The Tax State Defined	39	(4)
Toward a Typology of the Tax State	43	(17)
Measurement and Classification	60	(7)
Conclusion	67	(1)
3 CRITICAL JUNCTURE: DEFINING NATIONAL POLITICAL COMMUNITY	68	(38)
Cleavages: Race and Region	70	(8)
Two Definitions of National Political Community	78	(11)
Influence on Class Relations	89	(15)
Conclusion	104	(2)
4 THE RISE OF THE MODERN TAX STATE IN BRAZIL AND SOUTH AFRICA	106	(67)
Legacies of Pre-Modern Taxation	107	(6)
The Context of 20th-Century State-Building	113	(4)
Patterns of Taxation and State Development (1900-1975)	117	(5)
Three Episodes of Politics and Taxation	122	(45)
Implications: Weathering Economic and Political Crises (1975-1990)	167	(4)
Conclusion	171	(2)
5 SHADOWS OF THE PAST: TAX REFORM IN AN ERA OF GLOBALIZATION AND DEMOCRATIZATION	173	(64)
Pressures for Tax Reform from Home and Abroad	177	(8)
The Reconstruction of Racial and Regional Identities	185	(10)
Class Relations and Political Strategies	195	(18)
Patterns of Tax Reform Compared	213	(22)
Conclusion	235	(2)
6 POLITICAL COMMUNITY AND TAXATION BEYOND BRAZIL AND SOUTH AFRICA	237	(34)
Case Selection	238	(1)
Estimating the Impact of National Political Community on Taxation	239	(25)
Alternative Explanations	264	(5)
Conclusion	269	(2)
7 CONCLUSION	271	(13)
The Influence of Identity Politics and Political Community	274	(3)
Implications for Brazil and South Africa in the 21st Century	277	(7)
APPENDIX COMPARATIVE-HISTORICAL ANALYSIS	284	(7)
References	291	(18)
Index	309

Excerpts

Discrete mathematics is an interesting course to teach and to study at the freshman and sophomore level for several reasons. Its content is mathematics, but most of its applications and more than half its students are from computer science. Thus careful motivation of topics and previews of applications are important and necessary strategies. Moreover, there are a number of substantive and diverse topics covered in the course, so a text must proceed clearly and carefully, emphasizing key ideas with suitable pedagogy. In addition, the student is often expected to develop an important new skill: the ability to write a mathematical proof. This skill is excellent training for writing good computer programs. This text can be used by students in mathematics as an introduction to the fundamental ideas of discrete mathematics, and a foundation for the development of more advanced mathematical concepts. If used in this way, the topics dealing with specific computer science applications can be ignored or selected independently as important examples. The text can also be used in a computer science or computer engineering curriculum to present the foundations of many basic computer-related concepts and provide a coherent development and common theme for these ideas. The instructor can easily develop a suitable course by referring to the chapter prerequisites which identify material needed by that chapter. Approach First, we have limited both the areas covered and the depth of coverage to what we deem prudent in a first course taught at the freshman and sophomore level. We have identified a set of topics that we feel are of genuine use in computer science and elsewhere and that can be presented in a logically coherent fashion. We have presented an introduction to these topics along with an indication of how they can be pursued in greater depth. This approach makes our text an excellent reference for upper-division courses. Second, the material has been organized and interrelated to minimize the mass of definitions and the abstraction of some of the theory. Relations and digraphs are treated as two aspects of the same fundamental mathematical idea, with a directed graph being a pictorial representation of a relation. This fundamental idea is then used as the basis of virtually all the concepts introduced in the book, including functions, partial orders, graphs, and mathematical structures. Whenever possible, each new idea introduced in the text uses previously encountered material and, in turn, is developed in such a way that it simplifies the more complex ideas that follow. What Is New in the Fifth Edition We continue to believe that this book works well in the classroom because of the unifying role played by the two key concepts: relations and digraphs. In this edition we have woven in a thread of coding in all its aspects, efficiency, effectiveness, and security. Two new sections, Other Mathematical Structures and Public Key Cryptology are the major components of this thread, but smaller related insertions begin in Chapter 1. The number of exercises for this edition has been increased by more than 25%. Whatever changes we have made, our objective has remained the same as in the first four editions:to present the basic notions of discrete mathematics and some of its applications .in a clear and concise manner that will be understandable to the student. A cryptology thread begins in Chapter 1 and presents the basic ideas of the field. The thread concludes in Public Key Cryptology. Included now is coding in all its aspects, efficiency, effectiveness, and security. A new section, Other Mathematical Structures, introduces the basic concepts of rings and fields, in particularZ p . More opportunities for students to build modeling skills are provided. Whether seen as modeling, abstraction, pattern recognition, or problem solving, the ability to see the m