Discrete Mathematical Structures (4th Edition) - Hardcover

Bernard Kolman

Hardcover

ISBN 10: 0130831433 ISBN 13: 9780130831439

Publisher: Prentice Hall, 1999

Synopsis

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.

About this title

From the Publisher

More than any other text in this field, this text ties together discrete topics with a theme. Written at an appropriate level of rigor -- with a strong pedagogical focus -- it limits depth of coverage and areas covered to topics of genuine use in computer science. It stresses both basic theory and applications -- providing students with a firm foundation for more advanced courses.

Excerpt. © Reprinted by permission. All rights reserved.

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

Edition details

• Publisher: Prentice Hall
• Publication date: 1999
• ISBN 10: 0130831433
• ISBN 13: 9780130831439
• Binding: Hardcover
• Language: English
• Edition number: 4
• Number of pages: 505