Discrete Mathematics
MTH 288-001N
Course Outline & Homework
Annandale Campus
Northern Virginia Community College
Dr. Don Goral
Course Description: Presents
topics in sets, counting, graphs, logic, proofs,
functions, relations, mathematical induction, Boolean
Algebra, and recurrence relations.
The page
numbers will be given in the form 3 (8),
where the
first number is what is entered for digital navigation
and the
second number is the printed page number.
Kwong
1.1 An Overview . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . 10 (1)
1.2 Suggestions to Students . . . . .
. . . . . . . . . . . . . . . . . . . . . 11 (2)
1.3
How to Read and Write Mathematics . . . . . . . . . . .
. . . . . 12
(3)
2.1 Propositions
Page 22 (13):
1, 3, 7
2.2 Conjunctions and Disjunctions
Page 22 (16): 1, 3, 5, 7
2.3 Implications
Page 32 (23): 1, 3, 5, 7, 9
2.4 Biconditional
Page 36 (27): 1, 3, 5, 7
2.5 Logical Equivalences
Page 44 (35): 1, 3, 5, 7,11
4.1 Introduction
4.2 Propositions and Compound
Statements
Page 86: 4.20, 4.21, 4.22
4.9 Arguments
Page 86: 4.23
Levin
3.1 Propositional Logic
Truth Tables
Deductions
Page 147 (138): 1, 7
_________________________________________
Kwong
2.6 Logical Quantifiers
Page
50 (41): 1, 3, 5
Levin
0.2 Predicates and
Quantifiers
Page 38 (22): 16, 18
Lipschutz
1.3 Venn Diagrams
Page 19: 1.34 b, 1.34c, 1.35a, 1.36
__________________________________________________
Logic – Proof
Doer
3.5 Mathematical Systems and Proofs
Page 71 (57): 1, 3a, 5a
3.6 Propositions over a Universe
Page 74 (60): 1
3.7 Mathematical Induction
Page 80 (66): 1
3.9 A Review of Methods of Proof
Page 88 (74): 1
1.4
Proving Identities
Page 17 (8): 1
3.1 An
Introduction to Proof Techniques
Page 55 (46): 3, 5
3.2
Direct Proofs
Page 60 (51): 1, 3
3.3
Indirect Proofs
Page 66 (57): 1, 3, 9
3.4
Mathematical Induction: An Introduction
Page 74 (65): 1,
5
3.5 More
on Mathematical Induction 3.6 Mathematical Induction: The
Strong Form
Page 81 (72): 1, 3, 9
Levin
3.2 Proofs
Page 239 (233): 1, 7
_________________________________________________
Doer
1.1 Set Notation and Relations
Page 17 (3): 1, 3, 5
1.2 Basic Set Operations
Page 23 (9): 1a, 1g, 1e, 3c, 3f
1.3 Cartesian Products and Power
Sets
Page 26 (12): 1a, 1b, 1h, 3, 9
4.1 Methods of Proof for Sets
Page 93 (79): 1a, 1d, 3c
4.2 Laws of Set Theory
Page 96 (82): 1, 3c
Kwong
4.1 An
Introduction
Page 97 (88): 3a, 3b, 7a, 7b, 7c, 7d, 13a, 13b
4.2
Subsets and Power Sets
Page 105 (96): 3, 5, 9
4.3
Unions and Intersections
Page 111 (102): 1,
3
4.4
Cartesian Products
Page 117 (108): 1a,
3
Functions and
Relations
Kwong
Page 168 (159): 2, 3
6.2 Definition of Functions
Page 173 (164): 1,3
6.3 One-to-One Functions
Page 179 (170): 1, 3, 5
6.4 Onto Functions
Page 184 (175): 1, 3, 7
7.1 Definition of Relations
Page 209 (200): 1, 2, 9
7.2 Properties of Relations
Page 216 (207): 1, 7, 9
7.3 Equivalence Relations
Page 224 (215): 1, 3, 5
7.4 Partial and Total Ordering
Page 227 (218): 1, 3, 7
Counting Theory
Kwong
8.2 Addition and Multiplication
Principles
Page 237 (228): 1, 3, 5, 7
8.3 Permutations
Page 243 (234): 1, 3, 7
8.4 Combinations
Page 251 (242): 1, 3,7, 11
8.5 The Binomial Theorem
Page 258 (249): 1a, 3a, 7
1.4 Combinatorial Proofs
Page 115 (99): 1, 3, 9
5.6
Pigeonhole Principle
Page
105: 5.69, 5.71
Doer
9.1 Graphs - General Introduction
9.4.1 Eulerian Graphs
Page 228 (214): 5, 6, 8
10.1 What Is a Tree?
Page 256 (242): 1, 3, 5a
10.2 Spanning Trees
Page 261 (247): 1, 3, 4
Levin
4 Graph
Theory
4.1 Basics
Page 185 (176): 5, 7a
Lipschutz
8.2 Graphs and Multigraphs
8.3 Subgraphs, Isomorphic and
Homeomorphic Graphs
8.4 Paths, Connectivity
8.5 Traversable and Eulerian Graphs,
Bridges of Königsberg
8.8 Tree Graphs
Page 191: 8.34a, 8.34b, 8.34c, 8.35a, 8.35b, 8.35c,
8.39, 8.42
Doer
13.1 Posets Revisited
Page 352 (338): 3 (for graphs a, b, c), 5
13.2 Lattices
Page 355 (341): 1, 6
13.3 Boolean Algebras
Page 358 (344): 1, 4
14.2 Ordered Sets
14.8 Lattices
14.9 Bounded Lattices
14.10 Distributive Lattices
14.11 Complements, Complemented
Lattices
Page 360: 14.31, 14.33, 14.39
15.1 Introduction
15.2 Basic Definitions
15.5 Boolean Algebras as Lattices
Page 403: 15.47
___________________________________________________________________________
Doer
8.2 Sequences
Page 165 (151): 1, 2a
8.3 Recurrence Relations
Page 175 (161): 1, 3, 13a, 15
2
Sequences
2.1
Describing Sequences
Page 160 (144): 1a, 1b, 3, 7
2.2
Arithmetic and Geometric
Sequences
Page 172 (156): 1, 7
2.4
Solving Recurrence Relations
The Characteristic Root
Technique
Page 191 (175): 1, 3, 5
3.6
Recursively Defined Functions
6.6
Recurrence Relations
6.7
Linear Recurrence Relations with Constant Coefficients
6.8
Solving Second-Order Homogeneous Recurrence Relations
Page 121: 6.31a, 6.33a, 6.34a