About this title Adopting a user-friendly, conversational—and at times humorous—style, these authors make the principles and practices of discrete mathematics as stimulating as possible while presenting comprehensive, rigorous coverage. Examples and exercises integrated throughout each chapter serve to pique reader interest and bring clarity to even the most complex concepts. More than worked examples and problems, as well as over exercises are included. Full solutions are provided in the back of the book.
|Published (Last):||19 April 2009|
|PDF File Size:||7.2 Mb|
|ePub File Size:||20.60 Mb|
|Price:||Free* [*Free Regsitration Required]|
About this title Far more "user friendly" than the vast majority of similar books, this volume is truly written with the unsophisticated reader in mind. The pace is leisurely, but the authors are rigorous and maintain a serious attitude towards theorem proving throughout.
Emphasizes "Active Reading" throughout, a skill vital to success in learning how to write proofs. Offers two sections on probability 2. Moves material on depth-first search, which previously comprised an entire very short chapter, to an earlier chapter where it fits more naturally. Rewrites section on RNA chains to include a new and easier algorithm for the recovery of an RNA chain from its complete enzyme digest.
Features an appendix on matrices. A useful reference for mathematics enthusiasts who want to learn how to write proofs. From the Back Cover: Adopting a user-friendly, conversational and at times humorous style, these authors make the principles and practices of discrete mathematics as stimulating as possible while presenting comprehensive, rigorous coverage.
Examples and exercises integrated throughout each chapter serve to pique reader interest and bring clarity to even the most complex concepts. More than worked examples and problems, as well as over exercises are included. Full solutions are provided in the back of the book. More than Pauses short questions inserted at strategic points are included.
Full solutions to Pauses are included at the end of each section. For educators in area of discrete mathematics. All rights reserved. So we begin by answering the question most frequently asked by the readers of our manuscript: "What does BB mean?
Those which do are marked BB for "Back of Book. So, in a sense, there is a free Student Solutions Manual at the end of this text. We are active mathematicians who have always enjoyed solving problems. It is our hope that our enthusiasm for mathematics and, in particular, for discrete mathematics is transmitted to our readers through our writing. The word "discrete" means separate or distinct. Mathematicians view it as the opposite of "continuous.
Instead of the real numbers, it is the natural numbers 1, 2, 3,. Perhaps the best way to summarize the subject matter of this book is to say that discrete mathematics is the study of problems associated with the natural numbers. You should never read a mathematics book or notes taken in a mathematics course the way you read a novel, in an easy chair by the fire.
You should read at a desk, with paper and pencil at hand, verifying statements which are less than clear and inserting question marks in margins so that you are ready to ask questions at the next available opportunity. Definitions and terminology are terribly important in mathematics, much more so than many students think. In our experience, the number one reason why students have difficulty with "proofs" in mathematics is their failure to understand what the question is asking.
This book contains a glossary of definitions often including examples at the end as well as a summary of notation inside the front and back covers. We urge you to consult these areas of the book regularly. As an aid to interaction between author and student, we occasionally ask you to "pause a moment" and think about a specific point we have just raised.
Our Pauses are little questions intended to be solved on the spot, right where they occur, like this. Pause 1: Where will you find BB in this book and what does it mean? The answers to Pauses are given at the end of every section just before the exercises. So when a Pause appears, it is easy to cheat by turning over the page and looking at the answer, but that, of course, is not the way to learn mathematics!
We believe that writing skills are terribly important, so, in this edition, we have highlighted some exercises where we expect answers to be written in complete sentences and good English. Discrete mathematics is quite different from other areas in mathematics which you may have already studied, such as algebra, geometry, or calculus.
It is much less structured; there are far fewer standard techniques to learn. It is, however, a rich subject full of ideas at least some of which we hope will intrigue you to the extent that you will want to learn more about them. Related sources of material for further reading are given in numerous footnotes throughout the text.
To the Student from a Student I am a student at Memorial University of Newfoundland and have taken a course based on a preliminary version of this book. I spent one summer working for the authors, helping them to try to improve the book. As part of my work, they asked me to write an introduction for the student.
They felt a fellow student would be the ideal person to prepare warn? There are many things which can be said about this textbook. The authors have a unique sense of humor, which often, subtly or overtly, plays a part in their presentation of material.
It is an effective tool in keeping the information interesting and, in the more subtle cases, in keeping you alert. They try to make discrete mathematics as much fun as possible, at the same time maximizing the information presented. While the authors do push a lot of new ideas at you, they also try hard to minimize potential difficulties.
This is not an easy task considering that there are many levels of students who will use this book, so the material and exercises must be challenging enough to engage all of them. To balance this, numerous examples in each section are given as a guide to the exercises. Also, the exercises at the end of every section are laid out with easier ones at the beginning and the harder ones near the end.
The purpose of the exercises is to help clarify the material and to make sure you understand what has been covered. The authors intend that you stop and think before you start writing.
Inevitably, not everything in this book is exciting. Some material may not even seem particularly useful. As a textbook used for discrete mathematics and graph theory, there are many topics which must be covered. Generally, less exciting material is in the first few chapters and more interesting topics are introduced later. For example, the chapter on sets and relations may not captivate your attention, but it is essential for the understanding of almost all later topics.
The chapter on principles of counting is both interesting and useful, and it is fundamental to a subsequent chapter on permutations and combinations.
This textbook is written to engage your mind and to offer a fun way to learn some mathematics. The authors do hope that you will not view this as a painful experience, but as an opportunity to begin to think seriously about various areas of modern mathematics.
The best way to approach this book is with pencil, paper, and an open mind. To the Instructor Since the first printing of this book, we have received a number of queries about the existence of a solutions manual.
Let us begin then with the assurance that a complete solutions manual does exist and is available from the publisher, for the benefit of instructors. The material in this text has been taught and tested for many years in two one-semester courses, one in discrete mathematics at the sophomore level with no graph theory and the other in applied graph theory at the junior level. We believe this book is more elementary and written with a far more leisurely style than comparable books on the market.
For example, since students can enter our courses without calculus or without linear algebra, this book does not presume that students have backgrounds in either subject. The few places where some knowledge of a first calculus or linear algebra course would be useful are clearly marked. With one exception, this book requires virtually no background.
The exception is Section If desired, this section can easily be omitted without consequences. The material for our first course can be found in Chapters 1 through 7, although we find it impossible to cover all the topics presented here in the thirty-three minute lectures available to us. There are various ways to shorten the course.
One possibility is to omit Chapter 4 The Integers , although it is one of our favorites, especially if students will subsequently take a number theory course. Another solution is to omit all but the material on mathematical induction in Chapter 5, as well as certain other individual topics, such as partial orders Section 2.
Graph theory is the subject of Chapters 9 through 15, and again we find that there is more material here than can be successfully treated in thirty-three lectures. Usually, we include only a selection of the various applications and algorithms presented in this part of the text.
We do not always discuss the puzzles in Section 9. Chapter 13 Depth-First Search and Applications can also be omitted without difficulty.
In fact, most of the last half of this book is self-contained and can be treated to whatever extent the instructor may desire. Chapter 8, which introduces the concepts of algorithm and complexity, seems to work best as the introduction to the graph theory course. Wherever possible, we have tried to keep the material in various chapters independent of material in earlier chapters.
There are, of course, obvious situations where this is simply not possible. It is necessary to understand equivalence relations Section 2.
For the most part, however, the graph theory material can be read independently of earlier chapters. Some knowledge of such basic notions as function Chapter 3 and equivalence relation is needed in several places and, of course, many proofs in graph theory require- mathematical induction Section 5.
On the other hand, we have deliberately included in most exercise sets some problems which relate to material in earlier sections, as well as some which are based solely on the material in the given section. This opens a wide variety of possibilities to instructors as to the kind of syllabus they wish to follow and to the level of exercise that is most appropriate to their students.
We hope students of our book will appreciate the complete solutions, not simply answers, provided for many of the exercises at the back. One of the main goals of this book is to introduce students in a rigorous, yet friendly, way to the "mysteries" of theorem proving.
Sections 1. Because many instructors wish to include more formal topics in logic, this edition includes sections on truth tables, the algebra of propositions, and logical arguments Sections 1.
In addition, there is a student website of activities available by November 1, at the following address: www. New in the Second Edition The most common negative criticism of our first edition was the short treatment of logic and the absence of truth tables. This problem has been remedied with Chapter 1 previously Chapter 0 completely rewritten and expanded significantly to include new sections on truth tables, the algebra of propositions, and logical arguments.
The text now includes more than enough material for instructors who wish to include a substantial unit on formal logic, while continuing to permit a shorter treatment dealing exclusively with the major points and jargon of proofs in mathematics. In fact, the first edition contained over solved problem.
Discrete Mathematics with Graph Theory (2nd Edition)
Discrete Mathematics with Graph Theory, 2nd Edition