第1页 / 共993页
第2页 / 共993页
第3页 / 共993页
第4页 / 共993页
第5页 / 共993页
第6页 / 共993页
第7页 / 共993页
第8页 / 共993页
Discrete Mathematics with Applications, 4th ed, Susanna S. 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
1019763_FM_VOL-I.qxp 9/17/07 4:22 PM Page viii
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
S 50
R 51
1st Pass Pages
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.
DISCRETE MATHEMATICS
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.
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.
1019763_FM_VOL-I.qxp 9/17/07 4:22 PM Page viii
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
S 50
R 51
1st Pass Pages
相关推荐
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
