Discrete Mathematical Structures / Edition 6

Hardcover (Print)
Rent
Rent from BN.com
$30.59
(Save 82%)
Est. Return Date: 10/19/2014
Used and New from Other Sellers
Used and New from Other Sellers
from $94.92
Usually ships in 1-2 business days
(Save 43%)
Other sellers (Hardcover)
  • All (21) from $94.92   
  • New (11) from $120.99   
  • Used (10) from $94.92   

Overview

Key Message: Discrete Mathematical Structures, Sixth Edition, offers a clear and concise presentation of the fundamental concepts of discrete mathematics. This introductory book contains more genuine computer science applications than any other text in the field, and will be especially helpful for readers interested in computer science. This book is written at an appropriate level for a wide variety of readers, and assumes a college algebra course as the only prerequisite.

Key Topics: Fundamentals; Logic; Counting; Relations and Digraphs; Functions; Order Relations and Structures; Trees; Topics in Graph Theory; Semigroups and Groups; Languages and Finite-State Machines; Groups and Coding

Market: For all readers interested in discrete mathematics.

Read More Show Less

Editorial Reviews

Booknews
A text for a first course at the freshman and sophomore level, incorporating topics useful in computer science, for use in mathematics, computer science, and computer engineering programs. Chapters on subjects including logic, digraphs, trees, and finite- state machines include computational and theoretical exercises and answers, chapter reviews, and group experiment assignments. This third edition contains new material on mathematical structures and graph theory, coding exercises, and revised exercises. Annotation c. Book News, Inc., Portland, OR (booknews.com)
Read More Show Less

Product Details

  • ISBN-13: 9780132297516
  • Publisher: Pearson
  • Publication date: 8/7/2008
  • Series: Pearson Custom Mathematics Series
  • Edition description: New Edition
  • Edition number: 6
  • Pages: 552
  • Sales rank: 242,668
  • Product dimensions: 8.00 (w) x 10.00 (h) x 0.90 (d)

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.

Read More Show Less

Table of Contents

1. Fundamentals

1.1 Sets and Subsets

1.2 Operations on Sets

1.3 Sequences

1.4 Properties of Integers

1.5 Matrices

1.6 Mathematical Structures

2. Logic

2.1 Propositions and Logical Operations

2.2 Conditional Statements

2.3 Methods of Proof

2.4 Mathematical Induction

2.5 Mathematical Statements

2.6 Logic and Problem Solving

3. Counting

3.1 Permutations

3.2 Combinations

3.3 Pigeonhole Principle

3.4 Elements of Probability

3.5 Recurrence Relations 112

4. Relations and Digraphs

4.1 Product Sets and Partitions

4.2 Relations and Digraphs

4.3 Paths in Relations and Digraphs

4.4 Properties of Relations

4.5 Equivalence Relations

4.6 Data Structures for Relations and Digraphs

4.7 Operations on Relations

4.8 Transitive Closure and Warshall's Algorithm

5. Functions

5.1 Functions

5.2 Functions for Computer Science

5.3 Growth of Functions

5.4 Permutation Functions

6. Order Relations and Structures

6.1 Partially Ordered Sets

6.2 Extremal Elements of Partially Ordered Sets

6.3 Lattices

6.4 Finite Boolean Algebras

6.5 Functions on Boolean Algebras

6.6 Circuit Design

7. Trees

7.1 Trees

7.2 Labeled Trees

7.3 Tree Searching

7.4 Undirected Trees

7.5 Minimal Spanning Trees

8. Topics in Graph Theory

8.1 Graphs

8.2 Euler Paths and Circuits

8.3 Hamiltonian Paths and Circuits

8.4 Transport Networks

8.5 Matching Problems

8.6 Coloring Graphs

9. Semigroups and Groups

9.1 Binary Operations Revisited

9.2 Semigroups

9.3 Products and Quotients of Semigroups

9.4 Groups

9.5 Products and Quotients of Groups

9.6 Other Mathematical Structures

10. Languages and Finite-State Machines

10.1 Languages

10.2 Representations of Special Grammars and Languages

10.3 Finite-State Machines

10.4 Monoids, Machines, and Languages

10.5 Machines and Regular Languages

10.6 Simplification of Machines

11. Groups and Coding

11.1 Coding of Binary Information and Error Detection

11.2 Decoding and Error Correction

11.3 Public Key Cryptology

Appendix A: Algorithms and Pseudocode

Appendix B: Additional Experiments in Discrete Mathematics

Appendix C: Coding Exercises

Read More Show Less

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.

Read More Show Less

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.

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

Read More Show Less

Customer Reviews

Average Rating 5
( 1 )
Rating Distribution

5 Star

(1)

4 Star

(0)

3 Star

(0)

2 Star

(0)

1 Star

(0)

Your Rating:

Your Name: Create a Pen Name or

Barnes & Noble.com Review Rules

Our reader reviews allow you to share your comments on titles you liked, or didn't, with others. By submitting an online review, you are representing to Barnes & Noble.com that all information contained in your review is original and accurate in all respects, and that the submission of such content by you and the posting of such content by Barnes & Noble.com does not and will not violate the rights of any third party. Please follow the rules below to help ensure that your review can be posted.

Reviews by Our Customers Under the Age of 13

We highly value and respect everyone's opinion concerning the titles we offer. However, we cannot allow persons under the age of 13 to have accounts at BN.com or to post customer reviews. Please see our Terms of Use for more details.

What to exclude from your review:

Please do not write about reviews, commentary, or information posted on the product page. If you see any errors in the information on the product page, please send us an email.

Reviews should not contain any of the following:

  • - HTML tags, profanity, obscenities, vulgarities, or comments that defame anyone
  • - Time-sensitive information such as tour dates, signings, lectures, etc.
  • - Single-word reviews. Other people will read your review to discover why you liked or didn't like the title. Be descriptive.
  • - Comments focusing on the author or that may ruin the ending for others
  • - Phone numbers, addresses, URLs
  • - Pricing and availability information or alternative ordering information
  • - Advertisements or commercial solicitation

Reminder:

  • - By submitting a review, you grant to Barnes & Noble.com and its sublicensees the royalty-free, perpetual, irrevocable right and license to use the review in accordance with the Barnes & Noble.com Terms of Use.
  • - Barnes & Noble.com reserves the right not to post any review -- particularly those that do not follow the terms and conditions of these Rules. Barnes & Noble.com also reserves the right to remove any review at any time without notice.
  • - See Terms of Use for other conditions and disclaimers.
Search for Products You'd Like to Recommend

Recommend other products that relate to your review. Just search for them below and share!

Create a Pen Name

Your Pen Name is your unique identity on BN.com. It will appear on the reviews you write and other website activities. Your Pen Name cannot be edited, changed or deleted once submitted.

 
Your Pen Name can be any combination of alphanumeric characters (plus - and _), and must be at least two characters long.

Continue Anonymously
Sort by: Showing 1 Customer Reviews
  • Anonymous

    Posted September 6, 2009

    No text was provided for this review.

Sort by: Showing 1 Customer Reviews

If you find inappropriate content, please report it to Barnes & Noble
Why is this product inappropriate?
Comments (optional)