第1页 / 共986页
第2页 / 共986页
第3页 / 共986页
第4页 / 共986页
第5页 / 共986页
第6页 / 共986页
第7页 / 共986页
第8页 / 共986页
discrete mathematics with applications 4th edition susanna epp.pdf
Cover Page
Half-title Page
Title Page
Copyright Page
Dedication Page
Contents
PREFACE
Themes of a Discrete Mathematics Course
Special Features of This Book
Highlights of the Fourth Edition
Companion Website
Student Solutions Manual and Study Guide
Organization
Acknowledgments
Chapter 1:
Speaking Mathematically
1.1:
Variables
1.2:
The Language of Sets
1.3:
The Language of Relations and Functions
Chapter 2:
The Logic of Compound Statements
2.1:
Logical Form and Logical Equivalence
2.2: Conditional Statements
2.3:
Valid and Invalid Arguments
2.4:
Application: Digital Logic Circuits
2.5:
Application: Number Systems and Circuits for Addition
Chapter 3:
The Logic of Quantified Statements
3.1:
Predicates and Quantified Statements I
3.2:
Predicates and Quantified Statements II
3.3:
Statements with Multiple Quantifiers
3.4:
Arguments with Quantified Statements
Chapter 4: Elementary Number Theory
and Methods of Proof
4.1: Direct Proof and Counterexample I: Introduction
4.2:
Direct Proof and Counterexample II: Rational Numbers
4.3:
Direct Proof and Counterexample III: Divisibility
4.4: Direct Proof and Counterexample IV: Division into Cases and the Quotient-Remainder Theorem
4.5:
Direct Proof and Counterexample V: Floor and Ceiling
4.6:
Indirect Argument: Contradiction and Contraposition
4.7:
Indirect Argument: Two Classical Theorems
4.8:
Application: Algorithms
Chapter 5: Sequences, Mathematical Induction,
and Recursion
5.1:
Sequences
5.2:
Mathematical Induction I
5.3:
Mathematical Induction II
5.4: Strong Mathematical Induction and the Well-Ordering Principle for the Integers
5.5:
Application: Correctness of Algorithms
5.6:
Defining Sequences Recursively
5.7:
Solving Recurrence Relations by Iteration
5.8: Second-Order Linear Homogenous Recurrence Relations with Constant Coefficients
5.9:
General Recursive Definitions and Structural Induction
Chapter 6:
Set Theory
6.1:
Set Theory: Definitions and the Element Method of Proof
6.2:
Properties of Sets
6.3:
Disproofs, Algebraic Proofs, and Boolean Algebras
6.4:
Boolean Algebras, Russell’s Paradox, and the Halting Problem
Chapter 7:
Functions
7.1:
Functions Defined on General Sets
7.2:
One-to-One and Onto, Inverse Functions
7.3:
Composition of Functions
7.4:
Cardinality with Applications to Computability
Chapter 8:
Relations
8.1:
Relations on Sets
8.2:
Reflexivity, Symmetry, and Transitivity
8.3:
Equivalence Relations
8.4:
Modular Arithmetic with Applications to Cryptography
8.5:
Partial Order Relations
Chapter 9:
Counting and Probability
9.1:
Introduction
9.2:
Possibility Trees and the Multiplication Rule
9.3:
Counting Elements of Disjoint Sets: The Addition Rule
9.4:
The Pigeonhole Principle
9.5:
Counting Subsets of a Set: Combinations
9.6:
r-Combinations with Repetition Allowed
9.7:
Pascal’s Formula and the Binomial Theorem
9.8:
Probability Axioms and Expected Value
9.9:
Conditional Probability, Bayes’ Formula, and Independent Events
Chapter 10:
Graphs and Trees
10.1:
Graphs: Definitions and Basic Properties
10.2:
Trails, Paths, and Circuits
10.3:
Matrix Representations of Graphs
10.4:
Isomorphisms of Graphs
10.5:
Trees
10.6:
Rooted Trees
10.7:
Spanning Trees and Shortest Paths
Chapter 11:
Analysis of Algorithm Efficiency
11.1:
Real-Valued Functions of a Real Variable and Their Graphs
11.2: O-, Ω-, and Θ-Notations
11.3:
Application: Analysis of Algorithm Efficiency I
11.4:
Exponential and Logarithmic Functions:Graphs and Order
11.5:
Application: Analysis of Algorithm Efficiency II
Chapter 12:
Regular Expressions and Finite-State Automata
12.1:
Formal Languages and Regular Expressions
12.2:
Finite-State Automata
12.3:
Simplifying Finite-State Automata
Appendix A:
Properties of the Real Numbers
Appendix B:
Solutions and Hints to Selected Exercises
Index
DISCRETE MATHEMATICS
WITH APPLICATIONS
FOURTH EDITION
SUSANNA S. EPP
DePaul University
Australia · Brazil · Japan · Korea · Mexico · Singapore · Spain · United Kingdom · United States
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
Subject
Logic
Applications
of Logic
Number
Theory and
Applications
List of Symbols
Symbol
∼p
p ∧ q
p ∨ q
p ⊕ q or p XOR q
P ≡ Q
p → q
p ↔ q
∴
P(x)
P(x) ⇒ Q(x)
P(x) ⇔ Q(x)
∀
∃
Meaning
not p
p and q
p or q
p or q but not both p and q
P is logically equivalent to Q
if p then q
p if and only if q
therefore
predicate in x
every element in the truth set for P(x) is in
the truth set for Q(x)
P(x) and Q(x) have identical truth sets
for all
there exists
NOT
NOT-gate
AND
OR
AND-gate
OR-gate
NAND
NAND-gate
NOR
NOR-gate
|
↓
n2
n10
n16
d | n
d |/ n
n div d
n mod d
x
x
|x|
gcd(a, b)
x := e
Sheffer stroke
Peirce arrow
number written in binary notation
number written in decimal notation
number written in hexadecimal notation
d divides n
d does not divide n
the integer quotient of n divided by d
the integer remainder of n divided by d
the floor of x
the ceiling of x
the absolute value of x
the greatest common divisor of a and b
x is assigned the value e
Page
25
25
25
28
30
40
45
51
97
104
104
101
103
67
67
67
75
75
74
74
78
78
91
170
172
181
181
191
191
187
220
214
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
Subject
Sequences
Set
Theory
Symbol
Meaning
and so forth
. . .
n
n
k=m
ak
the summation from k equals m to n of ak
ak
k=m
n!
a ∈ A
a /∈ A
{a1, a2, . . . , an}
{x ∈ D | P(x)}
R, R−, R+, Rnonneg
Z, Z−, Z+, Znonneg
Q, Q−, Q+, Qnonneg
N
A ⊆ B
A ⊆ B
A = B
A ∪ B
A ∩ B
B − A
Ac
(x, y)
(x1, x2, . . . , xn)
A × B
A1 × A2 × ··· × An
∅
P(A)
the product from k equals m to n of ak
n factorial
a is an element of A
a is not an element of A
the set with elements a1, a2, . . . , an
the set of all x in D for which P(x) is true
the sets of all real numbers, negative real
numbers, positive real numbers, and
nonnegative real numbers
the sets of all integers, negative integers,
positive integers, and nonnegative integers
the sets of all rational numbers, negative
rational numbers, positive rational numbers,
and nonnegative rational numbers
the set of natural numbers
A is a subset of B
A is not a subset of B
A equals B
A union B
A intersect B
the difference of B minus A
the complement of A
ordered pair
ordered n-tuple
the Cartesian product of A and B
the Cartesian product of A1, A2, . . . , An
the empty set
the power set of A
Page
227
230
223
237
7
7
7
8
7, 8
7, 8
7, 8
8
9
9
339
341
341
341
341
11
346
12
347
361
346
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
Subject
Counting and
Probability
Functions
Algorithm
Efficiency
Relations
List of Symbols
Symbol
Meaning
N (A)
P(A)
P(n, r )
n
r
]
, . . . , xir
[xi1
, xi2
P(A | B)
f : X → Y
f (x)
x f→y
f (A)
−1(C)
f
Ix
bx
expb(x)
logb(x)
−1
F
f ◦ g
x ∼= y
O( f (x))
( f (x))
( f (x))
x R y
−1
R
m ≡ n (mod d)
[a]
x y
the number of elements in set A
the probability of a set A
the number of r-permutations of a set of
n elements
n choose r, the number of r-combinations
of a set of n elements, the number of
r-element subsets of a set of n elements
multiset of size r
the probability of A given B
f is a function from X to Y
the value of f at x
f sends x to y
the image of A
the inverse image of C
the identity function on X
b raised to the power x
b raised to the power x
logarithm with base b of x
the inverse function of F
the composition of g and f
x is approximately equal to y
big-O of f of x
big-Omega of f of x
big-Theta of f of x
x is related to y by R
the inverse relation of R
m is congruent to n modulo d
the equivalence class of a
x is related to y by a partial order relation
Page
518
518
553
566
584
612
384
384
384
397
397
387
405, 406
405, 406
388
411
417
237
727
727
727
14
444
473
465
502
Continued on first page of back endpapers.
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
CONTENTS
Chapter 1 Speaking Mathematically
1
1.1 Variables
1
Using Variables in Mathematical Discourse; Introduction to Universal, Existential,
and Conditional Statements
1.2 The Language of Sets
6
The Set-Roster and Set-Builder Notations; Subsets; Cartesian Products
1.3 The Language of Relations and Functions
13
Definition of a Relation from One Set to Another; Arrow Diagram of a Relation;
Definition of Function; Function Machines; Equality of Functions
Chapter 2 The Logic of Compound Statements
23
2.1 Logical Form and Logical Equivalence
23
Statements; Compound Statements; Truth Values; Evaluating the Truth of More Gen-
eral Compound Statements; Logical Equivalence; Tautologies and Contradictions;
Summary of Logical Equivalences
2.2 Conditional Statements
39
Logical Equivalences Involving →; Representation of If-Then As Or; The Nega-
tion of a Conditional Statement; The Contrapositive of a Conditional Statement; The
Converse and Inverse of a Conditional Statement; Only If and the Biconditional;
Necessary and Sufficient Conditions; Remarks
2.3 Valid and Invalid Arguments
51
Modus Ponens and Modus Tollens; Additional Valid Argument Forms: Rules of
Inference; Fallacies; Contradictions and Valid Arguments; Summary of Rules of
Inference
2.4 Application: Digital Logic Circuits
64
Black Boxes and Gates; The Input/Output Table for a Circuit; The Boolean Expres-
sion Corresponding to a Circuit; The Circuit Corresponding to a Boolean Expres-
sion; Finding a Circuit That Corresponds to a Given Input/Output Table; Simplifying
Combinational Circuits; NAND and NOR Gates
2.5 Application: Number Systems and Circuits for Addition
78
Binary Representation of Numbers; Binary Addition and Subtraction; Circuits for
Computer Addition; Two’s Complements and the Computer Representation of
vi
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
Negative Integers; 8-Bit Representation of a Number; Computer Addition with
Negative Integers; Hexadecimal Notation
Contents
vii
Chapter 3 The Logic of Quantified Statements
96
3.1 Predicates and Quantified Statements I
96
The Universal Quantifier: ∀; The Existential Quantifier: ∃; Formal Versus Informal
Language; Universal Conditional Statements; Equivalent Forms of Universal and
Existential Statements; Implicit Quantification; Tarski’s World
3.2 Predicates and Quantified Statements II
108
Negations of Quantified Statements; Negations of Universal Conditional Statements;
The Relation among ∀, ∃, ∧, and ∨; Vacuous Truth of Universal Statements; Variants
of Universal Conditional Statements; Necessary and Sufficient Conditions, Only If
3.3 Statements with Multiple Quantifiers
117
Translating from Informal to Formal Language; Ambiguous Language; Negations
of Multiply-Quantified Statements; Order of Quantifiers; Formal Logical Notation;
Prolog
3.4 Arguments with Quantified Statements
132
Universal Modus Ponens; Use of Universal Modus Ponens in a Proof; Universal
Modus Tollens; Proving Validity of Arguments with Quantified Statements; Using
Diagrams to Test for Validity; Creating Additional Forms of Argument; Remark on
the Converse and Inverse Errors
Chapter 4 Elementary Number Theory
and Methods of Proof
145
4.1 Direct Proof and Counterexample I: Introduction
146
Definitions; Proving Existential Statements; Disproving Universal Statements by
Counterexample; Proving Universal Statements; Directions for Writing Proofs of
Universal Statements; Variations among Proofs; Common Mistakes; Getting Proofs
Started; Showing That an Existential Statement Is False; Conjecture, Proof, and
Disproof
4.2 Direct Proof and Counterexample II: Rational Numbers
163
More on Generalizing from the Generic Particular; Proving Properties of Rational
Numbers; Deriving New Mathematics from Old
4.3 Direct Proof and Counterexample III: Divisibility
170
Proving Properties of Divisibility; Counterexamples and Divisibility; The Unique
Factorization of Integers Theorem
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
viii Contents
4.4 Direct Proof and Counterexample IV: Division into Cases
and the Quotient-Remainder Theorem
Discussion of the Quotient-Remainder Theorem and Examples; div and mod; Alter-
native Representations of Integers and Applications to Number Theory; Absolute
Value and the Triangle Inequality
180
4.5 Direct Proof and Counterexample V: Floor and Ceiling
191
Definition and Basic Properties; The Floor of n/2
4.6 Indirect Argument: Contradiction and Contraposition
198
Proof by Contradiction; Argument by Contraposition; Relation between Proof by
Contradiction and Proof by Contraposition; Proof as a Problem-Solving Tool
4.7 Indirect Argument: Two Classical Theorems
√
2; Are There Infinitely Many Prime Numbers?; When to Use
207
The Irrationality of
Indirect Proof; Open Questions in Number Theory
4.8 Application: Algorithms
214
An Algorithmic Language; A Notation for Algorithms; Trace Tables; The Division
Algorithm; The Euclidean Algorithm
Chapter 5 Sequences, Mathematical Induction,
and Recursion
227
5.1 Sequences
227
Explicit Formulas for Sequences; Summation Notation; Product Notation; Properties
of Summations and Products; Change of Variable; Factorial and n Choose r Notation;
Sequences in Computer Programming; Application: Algorithm to Convert from Base
10 to Base 2 Using Repeated Division by 2
5.2 Mathematical Induction I
244
Principle of Mathematical Induction; Sum of the First n Integers; Proving an Equal-
ity; Deducing Additional Formulas; Sum of a Geometric Sequence
5.3 Mathematical Induction II
258
Comparison of Mathematical Induction and Inductive Reasoning; Proving Divisibil-
ity Properties; Proving Inequalities; A Problem with Trominoes
5.4 Strong Mathematical Induction
and the Well-Ordering Principle for the Integers
Strong Mathematical Induction;Binary Representation of Integers;The Well-Ordering
Principle for the Integers
268
5.5 Application: Correctness of Algorithms
279
Assertions; Loop Invariants; Correctness of the Division Algorithm; Correctness of
the Euclidean Theorem
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
Contents
ix
5.6 Defining Sequences Recursively
290
Definition of Recurrence Relation; Examples of Recursively Defined Sequences;
Recursive Definitions of Sum and Product
5.7 Solving Recurrence Relations by Iteration
304
The Method of Iteration; Using Formulas to Simplify Solutions Obtained by Itera-
tion; Checking the Correctness of a Formula by Mathematical Induction; Discovering
That an Explicit Formula Is Incorrect
5.8 Second-Order Linear Homogenous Recurrence Relations
with Constant Coefficients
Derivation of a Technique for Solving These Relations; The Distinct-Roots Case;
The Single-Root Case
317
5.9 General Recursive Definitions and Structural Induction
328
Recursively Defined Sets; Using Structural Induction to Prove Properties about
Recursively Defined Sets; Recursive Functions
Chapter 6 Set Theory
336
6.1 Set Theory: Definitions and the Element Method of Proof
336
Subsets; Proof and Disproof; Set Equality; Venn Diagrams; Operations on Sets; The
Empty Set; Partitions of Sets; Power Sets; Cartesian Products; An Algorithm to
Check Whether One Set Is a Subset of Another (Optional)
6.2 Properties of Sets
352
Set Identities; Proving Set Identities; Proving That a Set Is the Empty Set
6.3 Disproofs, Algebraic Proofs, and Boolean Algebras
367
Disproving an Alleged Set Property; Problem-Solving Strategy; The Number of Sub-
sets of a Set; “Algebraic” Proofs of Set Identities
6.4 Boolean Algebras, Russell’s Paradox, and the Halting Problem
Boolean Algebras; Description of Russell’s Paradox; The Halting Problem
374
Chapter 7 Functions
383
7.1 Functions Defined on General Sets
383
Additional Function Terminology; More Examples of Functions; Boolean Functions;
Checking Whether a Function Is Well Defined; Functions Acting on Sets
Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
