Why do I need discrete mathematics?
To think logically and mathematically. To achieve these goals, this text stresses
mathematical reasoning and the different ways problems are solved. Five important themes
are interwoven in this text: mathematical reasoning, combinatorial analysis, discrete structures,
algorithmic thinking, and applications and modeling.
A successful discrete mathematics course should carefully blend and balance all five themes.
There are several important reasons for studying discrete mathematics.
First, through this course you can develop your mathematical maturity:
that is, your ability to understand and create mathematical arguments.You will not get
very far in your studies in the mathematical sciences without these skills.
Second, discrete mathematics is the gateway to more advanced courses in all parts of the mathematical sciences.
Discrete mathematics provides the mathematical foundations for
many computer science courses including data structures, algorithms, database theory, automata
theory, formal languages, compiler theory, computer security, and operating systems.
One student has sent me an e-mail message saying that she used the contents of this book in every computer science course she took!
What is discrete mathematics?
Discrete mathematics is the part of mathematics devoted to the study of discrete objects. (Here discrete means consisting of distinct or unconnected elements.)
The kinds of problems solved using discrete mathematics include:
- How many ways are there to choose a valid password on a computer system?
- What is the probability of winning a lottery?
- Is there a link between two computers in a network?
- How can I identify spam e-mail messages?
- How can I encrypt a message so that no unintended recipient can read it?
- What is the shortest path between two cities using a transportation system?
- How can a list of integers be sorted so that the integers are in increasing order?
- How many steps are required to do such a sorting?
- How can it be proved that a sorting algorithm correctly sorts a list?
- How can a circuit that adds two integers be designed?
- How many valid Internet addresses are there?
이번 Discrete Mathematics 과정을 마치면 위의 질문에 대해서 설명할 수 있어야 한다.
You will learn the discrete structures and techniques needed to solve problems such as these.
Importance of discrete mathematics
More generally, discrete mathematics is used whenever objects are counted, when relationships
between finite (or countable) sets are studied, and when processes involving a finite number of steps are analyzed.
A key reason for the growth in the importance of discrete mathematics is
that information is stored and manipulated by computing machines in a discrete fashion.
Difficulties of Studying discrete mathematics
Many students find their introductory discrete mathematics course to be significantly more
challenging than courses they have previously taken. One reason for this is that one of the
primary goals of this course is to teach mathematical reasoning and problem solving, rather
than a discrete set of skills. The exercises in this book are designed to reflect this goal. Although
there are plenty of exercises in this text similar to those addressed in the examples, a large
percentage of the exercises require original thought. This is intentional. The material discussed
in the text provides the tools needed to solve these exercises, but your job is to successfully
apply these tools using your own creativity.
One of the primary goals of this course is to lear how to attack problems that may be somewhat
different from any you may have previously seen. Unfortunately, learning how to solve only particular
types of exercises is not sufficient for success in developing the problem-solving skills needed
in subsequent courses and professional work. This text addresses many different topics, but
discrete mathematics is an extremely diverse and large area of study. One of my goals as an author
is to help you develop the skills needed to master the additional material you will need in your own future pursuits.
교재: Discrete Mathematics and Its Applications 저자: K. H. Rosen 출판사: McGraw Hill
Discrete Mathematics And Its Applications (SIE) is a study of mathematical structures that are fundamentally discrete rather than continuous. Discrete objects can often be enumerated by integers, and more formally, deal with countable sets.
This renowned, which has been used at over 600 institutions around the world, gives a focused introduction to the primary themes in a Discrete Mathematics course. It helps demonstrate the relevance and practicality of Discrete Mathematics to a wide variety of real-world applications. These application can be used in the fields of computer science, data networking, psychology, chemistry, engineering, linguistics, biology, business, and others. The 7th edition of Discrete Mathematics And Its Applications (SIE) was published by Tata McGraw-Hill Publishing Company in the year 2011. It is available in paperback.
Key Features:
- It has a new chapter on algebraic structures in coding theory.
- There are added topics to this book such as validity problem and incompleteness theorem, exponential generating function, domain transformation, range transformation, platonic solid, cut set, and circle.
- :설명 불분명 <-Amazon에서의 대부분 평가
+:(I believe they present topics such as set theory, elementary number theory, discrete probability, combinatorics, graph theory etc. as though you won't ever take another course nor read a book on such topics. If that's you, then you may like Rosen or Epp.)
+: I find it very easy and straightforward. However i also supplement with youtube videos like MIT's free ones
Book Review: This book covers various topics related to Discrete Mathematics which include algorithmic thinking, combinatorial analysis, mathematical reasoning and discrete structures. The book presents various concepts of discrete mathematics in a practical manner. The book also presents the immediate applications of discrete mathematics in various fields pertaining to engineering and medicine.
Other Good Textbook on Discrete Mathematics
1.oncrete Mathematics: A Foundation for Computer Science, By Donald Knuth
(Need prerequisite to this book is a background in the basic concepts of discrete math)
(You will only need it if you for doing advanced proofs in DS/Algorithms.)
(Discrete Math knowledge is needed to become adept in proving the correctness and deriving the complexity of algorithms and data structures)
2.“Discrete Mathematics” by Norman L Biggs
3. “Discrete Mathematics for Computer Science” by Kenneth Bogart and Robert L Drysdale
4. “Discrete Mathematics with Applications” by Thomas Koshy
Goals of a Discrete Mathematics Course
1. Mathematical Reasoning:
Students must understand mathematical reasoning in order to
read, comprehend, and construct mathematical arguments. This text starts with a discussion
of mathematical logic, which serves as the foundation for the subsequent discussions of
methods of proof. Both the science and the art of constructing proofs are addressed. The
technique of mathematical induction is stressed through many different types of examples
of such proofs and a careful explanation of why mathematical induction is a valid proof
technique.
2. Combinatorial Analysis:
An important problem-solving skill is the ability to count or enumerate
objects. The discussion of enumeration in this book begins with the basic techniques
of counting. The stress is on performing combinatorial analysis to solve counting problems
and analyze algorithms, not on applying formulae.
3. Discrete Structures:
A course in discrete mathematics should teach students how to work
with discrete structures, which are the abstract mathematical structures used to represent
discrete objects and relationships between these objects. These discrete structures include
sets, permutations, relations, graphs, trees, and finite-state machines.
4. Algorithmic Thinking:
Certain classes of problems are solved by the specification of an
algorithm. After an algorithm has been described, a computer program can be constructed
implementing it. The mathematical portions of this activity, which include the specification
of the algorithm, the verification that it works properly, and the analysis of the computer
memory and time required to perform it, are all covered in this text. Algorithms are described
using both English and an easily understood form of pseudocode.
5. Applications and Modeling:
Discrete mathematics has applications to almost every conceivable
area of study. There are many applications to computer science and data networking
in this text, as well as applications to such diverse areas as chemistry, biology, linguistics,
geography, business, and the Internet. These applications are natural and important uses of
discrete mathematics and are not contrived. Modeling with discrete mathematics is an extremely
important problem-solving skill, which students have the opportunity to develop by
constructing their own models in some of the exercises.
Features of the Book
ACCESSIBILITY This text has proved to be easily read and understood by beginning
students. There are no mathematical prerequisites beyond college algebra for almost all the
content of the text. Students needing extra help will find tools on the companion website for
bringing their mathematical maturity up to the level of the text. The few places in the book
where calculus is referred to are explicitly noted. Most students should easily understand the
pseudocode used in the text to express algorithms, regardless of whether they have formally
studied programming languages. There is no formal computer science prerequisite.
Each chapter begins at an easily understood and accessible level. Once basic mathematical
concepts have been carefully developed, more difficult material and applications to other areas
of study are presented.
FLEXIBILITY This text has been carefully designed for flexible use. The dependence
of chapters on previous material has been minimized. Each chapter is divided into sections of
approximately the same length, and each section is divided into subsections that form natural
blocks of material for teaching. Instructors can easily pace their lectures using these blocks.
WRITING STYLE The writing style in this book is direct and pragmatic. Precise mathematical
language is used without excessive formalism and abstraction. Care has been taken to
balance the mix of notation and words in mathematical statements.
MATHEMATICAL RIGORAND PRECISION All definitions and theorems in this text
are stated extremely carefully so that students will appreciate the precision of language and
rigor needed in mathematics. Proofs are motivated and developed slowly; their steps are all
carefully justified. The axioms used in proofs and the basic properties that follow from them
are explicitly described in an appendix, giving students a clear idea of what they can assume in
a proof. Recursive definitions are explained and used extensively.
WORKEDEXAMPLES Over 800 examples are used to illustrate concepts, relate different
topics, and introduce applications. In most examples, a question is first posed, then its solution
is presented with the appropriate amount of detail.
APPLICATIONS The applications included in this text demonstrate the utility of discrete
mathematics in the solution of real-world problems. This text includes applications to a wide variety
of areas, including computer science, data networking, psychology, chemistry, engineering,
linguistics, biology, business, and the Internet.
ALGORITHMS Results in discrete mathematics are often expressed in terms of algorithms;
hence, key algorithms are introduced in each chapter of the book. These algorithms
are expressed in words and in an easily understood form of structured pseudocode, which is
described and specified in Appendix 3. The computational complexity of the algorithms in the
text is also analyzed at an elementary level.
HISTORICAL INFORMATION The background of many topics is succinctly described
in the text. Brief biographies of 83 mathematicians and computer scientists are included as footnotes.
These biographies include information about the lives, careers, and accomplishments of
these important contributors to discrete mathematics and images, when available, are displayed.
In addition, numerous historical footnotes are included that supplement the historical information
in the main body of the text. Efforts have been made to keep the book up-to-date by
reflecting the latest discoveries.
KEY TERMS AND RESULTS A list of key terms and results follows each chapter. The
key terms include only the most important that students should learn, and not every term defined
in the chapter.
EXERCISES There are over 4000 exercises in the text, with many different types of
questions posed. There is an ample supply of straightforward exercises that develop basic skills,
a large number of intermediate exercises, and many challenging exercises. Exercises are stated
clearly and unambiguously, and all are carefully graded for level of difficulty. Exercise sets
contain special discussions that develop new concepts not covered in the text, enabling students
to discover new ideas through their own work.
Exercises that are somewhat more difficult than average are marked with a single star ∗;
those that are much more challenging are marked with two stars ∗∗. Exercises whose solutions
require calculus are explicitly noted. Exercises that develop results used in the text are clearly
identified with the right pointing hand symbol . Answers or outlined solutions to all odd
numbered exercises are provided at the back of the text. The solutions include proofs in which
most of the steps are clearly spelled out.
REVIEW QUESTIONS A set of review questions is provided at the end of each chapter.
These questions are designed to help students focus their study on the most important concepts
and techniques of that chapter. To answer these questions students need to write long answers,
rather than just perform calculations or give short replies.
SUPPLEMENTARY EXERCISE SETS Each chapter is followed by a rich and varied
set of supplementary exercises. These exercises are generally more difficult than those in the
exercise sets following the sections. The supplementary exercises reinforce the concepts of the
chapter and integrate different topics more effectively.
COMPUTER PROJECTS Each chapter is followed by a set of computer projects. The
approximately 150 computer projects tie together what students may have learned in computing
and in discrete mathematics. Computer projects that are more difficult than average, from both
a mathematical and a programming point of view, are marked with a star, and those that are
extremely challenging are marked with two stars.
COMPUTATIONS AND EXPLORATIONS A set of computations and explorations is
included at the conclusion of each chapter. These exercises (approximately 120 in total) are designed
to be completed using existing software tools, such as programs that students or instructors
have written or mathematical computation packages such as MapleTM or MathematicaTM.
Many of these exercises give students the opportunity to uncover new facts and ideas through
computation. (Some of these exercises are discussed in the Exploring Discrete Mathematics
companion workbooks available online.)
WRITING PROJECTS Each chapter is followed by a set of writing projects. To do these
projects students need to consult the mathematical literature. Some of these projects are historical
in nature and may involve looking up original sources. Others are designed to serve as gateways
to new topics and ideas. All are designed to expose students to ideas not covered in depth in
the text. These projects tie mathematical concepts together with the writing process and help
expose students to possible areas for future study. (Suggested references for these projects can
be found online or in the printed Student’s Solutions Guide.)
APPENDIXES There are three appendixes to the text. The first introduces axioms for real
numbers and the positive integers, and illustrates howfacts are proved directly from these axioms.
The second covers exponential and logarithmic functions, reviewing some basic material used
heavily in the course. The third specifies the pseudocode used to describe algorithms in this text.
SUGGESTED READINGS A list of suggested readings for the overall book and for each
chapter is provided after the appendices. These suggested readings include books at or below
the level of this text, more difficult books, expository articles, and articles in which discoveries
in discrete mathematics were originally published. Some of these publications are classics,
published many years ago, while others have been published in the last few years.
Key to the Exercises
no marking A routine exercise
∗ A difficult exercise
∗∗ An extremely challenging exercise
An exercise containing a result used in the book (Table 1 on the
following page shows where these exercises are used.)
(Requires calculus ) An exercise whose solution requires the use of limits or concepts
from differential or integral calculus
The best approach is to try exercises yourself before you consult the answer section at the end of this book.
Note that the odd-numbered exercise answers provided in the text are answers
only and not full solutions; in particular, the reasoning required to obtain answers is omitted in these answers. The Student’s Solutions Guide, available separately, provides complete, worked
solutions to all odd-numbered exercises in this text. When you hit an impasse trying to solve an odd-numbered exercise, I suggest you consult the Student’s Solutions Guide and look for some guidance as to how to solve the problem. The more work you do yourself rather than passively
reading or copying solutions, the more you will learn.
The answers and solutions to the evennumbered exercises are intentionally not available from the publisher; ask your instructor if you
have trouble with these.
Point In Each Chapter Related To The Five Important Themes
C H A P T E R 1. The Foundations: Logic and Proofs
In this chapter, we will explain what makes up a correct mathematical argument and introduce
tools to construct these arguments.We will develop an arsenal of different proof methods
that will enable us to prove many different types of results. After introducing many different
methods of proof, we will introduce several strategies for constructing proofs. We will introduce
the notion of a conjecture and explain the process of developing mathematics by studying
conjectures.
The rules of logic specify the meaning of mathematical statements. For instance, these rules
help us understand and reason with statements such as “There exists an integer that is
not the sum of two squares” and “For every positive integer n, the sum of the positive integers
not exceeding n is n(n + 1)/2.” Logic is the basis of all mathematical reasoning, and of all
automated reasoning. It has practical applications to the design of computing machines, to the
specification of systems, to artificial intelligence, to computer programming, to programming
languages, and to other areas of computer science, as well as to many other fields of study.
|
1.1 Propositional Logic |
To understand mathematics, we must understand what makes up a correct mathematical argument, that is, a proof. Once we prove a mathematical statement is true, we call it a theorem. A collection of theorems on a topic organize what we knowabout this topic.To learn a mathematical topic, a person needs to actively construct mathematical arguments on this topic, and not just read exposition. Moreover, knowing the proof of a theorem often makes it possible to modify |