Discrete Mathematical Structures 3rd ed - Bernard Kolman, Sharon Ross, Robert C. Busby, (Prentice Hall, 1996) WW

Overview
More than any other book in this field, this book ties together discrete topics with a theme. Written at an appropriate level of understanding for those new to the world of abstract mathematics, it limits depth of coverage and areas covered to topics of genuine use in computer science. Chapter topics include fundamentals, logic, counting, relations and digraphs, trees, topics in graph theory, languages and finite-state machines, and groups and coding. For individuals interested in computer science and other related fields — looking for an introduction to discrete mathematics, or a bridge to more advanced material on the subject.

Meet the Author
Bernard Kolman received his BS in mathematics and physics from Brooklyn College in 1954, his ScM from Brown University in 1956, and his PhD from the University of Pennsylvania in 1965, all in mathematics. He has worked as a mathematician for the US Navy and IBM. He has been a member of the mathematics department at Drexel University since 1964, and has served as Acting Head of the department. His research activities have included Lie algebra and perations research. He belongs to a number of professional associations and is a member of Phi Beta Kappa, Pi Mu Epsilon, and Sigma Xi.
Robert C. Busby received his BS in physics from Drexel University in 1963, his AM in 1964 and PhD in 1966, both in mathematics from the University of Pennsylvania. He has served as a faculty member of the mathematics department at Drexel since 1969. He has consulted in applied mathematics and industry and government, including three years as a consultant to the Office of Emergency Preparedness, Executive Office of the President, specializing in applications of mathematics to economic problems. He has written a number of books and research papers on operator algebra, group representations, operator continued fractions, and the applications of probability and statistics to mathematical demography.
Sharon Cutler Ross received a SB in mathematics from the Massachusetts Institute of Technology in 1965, an MAT in secondary mathematics from Harvard University in 1966, and a PhD in mathematics from Emory University in 1976. She has taught junior high, high school, and college mathematics, and has taught computer science at the collegiate level. She has been a member of the mathematics department at DeKalb College. Her current professional interests are in undergraduate mathematics education and alternative forms of assessment. Her interests and associations include the Mathematical Association of America, the American Mathematical Association of Two-Year Colleges, and UME Trends. She is a member of Sigma Xi and other organizations.

Preface
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 andelsewhere 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 particular Zp.
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 mathematical bones of a problem is a critical factor for success in higher-level mathematics courses.
Understanding proofs and writing simple proofs are important course goals. More occasions for students to read, analyze, complete, and produce proofs are presented throughout the text, not just in the sections that introduce formal proofs.
More applications are included. Among these are relational databases, check digits, a variety of ciphers, and weighted voting systems.
New exercises have been added to each chapter. Greater emphasis has been placed on multiple representations of concepts. There are approximately 400 more exercises than in the fourth edition.
A brief historical commentary opens each chapter and introduces some of the major contributors to that chapter's topics.
Isomorphism is presented in more contexts than before throughout the book.
Additional student experiments have been developed on weighted voting systems, Petri nets, and Catalan numbers. Experiments have been integrated into appropriate chapters and others are gathered in Appendix B. These assignments provide opportunities for exploration and discovery, as well as for writing, and are designed for collaborative work.
This edition continues to weave the discussion of proofs and proof techniques throughout the book with comments on most proofs, exercises related to the mechanics of proving statements, and Tips for Proofs sections. Many of the new exercises provide more practice in building proof-reading and proof-writing skills.
Each chapter now has a set of review questions. These are mainly conceptual in nature and help students identify the "big" ideas of the chapter.
A glossary for quick reference is now included.
The index contains approximately 100 new entries related to both new concepts and to new examples for material in previous editions.
Exercises
The exercises form an integral part of the book. Many are computational in nature, whereas others are of a theoretical type. Many of the latter and the experiments, to be further described below, require verbal solutions. Exercises to help develop proof-writing skills ask the student to analyze proofs, amplify arguments, or complete partial proofs. Guidance and practice in recognizing key elements and patterns have been extended in many new exercises. Answers to all odd-numbered exercises, review questions, and self-test items appear in the back of the book. Solutions to all exercises appear in the Instructor's Solutions Manual, which is available (to instructors only) gratis from the publisher. The Instructor's Solutions Manual also includes notes on the pedagogical ideas underlying each chapter, goals and grading guidelines for the experiments, and a test bank.

Experiments
Chapters 1 through 10 each end with a student experiment. These provide opportunities for discovery and exploration, or a more in-depth look at topics discussed in the text. They are designed as extended-time, out-of-class experiences and are suitable for group work. Each experiment requires significantly more writing than section exercises do. Some additional experiments are to be found in Appendix B. Content, prerequisites, and goals for each experiment are given in the Instructor's Solutions Manual.

End-of-Chapter Material
Each chapter contains Tips for Proofs, a summary of Key Ideas for Review, a set of Coding Exercises, an Experiment, a set of conceptual Review Questions, and a Self-Test covering the chapter's material.

Organization
Chapter 1 contains material that is fundamental to the course. This includes sets, subsets, and their operations; sequences; properties of the integers, including base n representations; matrices; and mathematical structures. A goal of this chapter is to help students develop skills in identifying patterns on many levels. Chapter 2 covers logic and related material, including methods of proof and mathematical induction. Although the discussion of proof is based on this chapter, the commentary on proofs continues throughout the book. Chapter 3, on counting, deals with permutations, combinations, the pigeonhole principle, elements of probability, and recurrence relations.

Chapter 4 presents basic types and properties of relations, along with their representation as directed graphs. Connections with matrices and other data structures are also explored in this chapter. Chapter 5 deals with the notion of a function and gives important examples of functions, including functions of special interest in computer science. An introduction to the growth of functions is developed. Chapter 6 covers partially ordered sets, including lattices and Boolean algebras. A symbolic version for finding a Boolean function for a Boolean expression joins the pictorial Kamaugh method. Chapter 7 introduces directed and undirected trees along with applications of these ideas. Elementary graph theory with applications to transport networks and matching problems is the focus of Chapter 8.

In Chapter 9, we return to mathematical structures and present the basic ideas of semigroups, groups, rings, and fields. By building on work in previous chapters, only a few new concepts are needed. Chapter 10 is devoted to finite-state machines. It complements and makes effective use of ideas developed in previous chapters. Chapter 11 finishes our discussion of coding for error detecting and correction and for security purposes. Appendix A discusses algorithms and pseudocode. The simplified pseudocode presented here is used in some text examples and exercises; these may be omitted without loss of continuity. Appendix B gives some additional experiments dealing with extensions or previews of topics in various parts of the course.


Introduction
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.