Discrete Mathematics and Applications, Second Edition is intended for a one-semester course in discrete mathematics. Such a course is typically taken by mathematics, mathematics education, and computer science majors, usually in their sophomore year. Calculus is not a prerequisite to use this book.
Part one focuses on how to write proofs, then moves on to topics in number theory, employing set theory in the process. Part two focuses on computations, combinatorics, graph theory, trees, and algorithms.
Emphasizes proofs, which will appeal to a subset of this course market
Links examples to exercise sets
Offers edition that has been heavily reviewed and developed
Focuses on graph theory
Covers trees and algorithms
Author(s): Ferland, Kevin
Edition: 2
Publisher: CRC Press LLC
Year: 2017
Cover
Half Title
Title
Copyright
Dedication
Contents
Preface
Acknowledgments
Introduction: Representing Numbers
I: Proofs
1: Logic and Sets
1.1: Statement forms and logical equivalences
1.1.1: Statement forms
1.1.2: Logical equivalences
1.1.3: Digital circuits
1.2: Set notation
1.2.1: Paradoxes
1.2.2: Software implementation of sets
1.3: Quantifiers
1.3.1: Negating quantified statements
1.4: Set operations and identities
1.4.1: Software implementation of set operations
1.5: Valid arguments
1.5.1: Arguments involving quantifiers
1.6: Review problems
2: Basic Proof Writing
2.1: Direct demonstration
2.1.1: Existential statements
2.1.2: Counterexamples
2.1.3: Universal statements for small universes
2.2: General demonstration (Part 1)
2.2.1: If-then statements
2.2.2: Subsets
2.2.3: Set equalities
2.3: General demonstration (Part 2)
2.3.1: If and only if statements
2.3.2: Set equalities revisited
2.3.3: Sets with particular forms
2.4: Indirect arguments
2.4.1: Proofs by contradiction
2.4.2: Proving the contrapositive
2.5: Splitting into cases
2.6: Review problems
3: Elementary Number Theory
3.1: Divisors
3.1.1: Parity
3.1.2: Divisibility
3.1.3: Primes
3.1.4: GCD’s
3.2: Well-ordering, division, and codes
3.2.1: Computer searches for large primes
3.2.2: Integer division
3.2.3: Rounding numbers
3.2.4: Applications of mod
3.3: Euclid’s Algorithm and Lemma
3.3.1: Euclid’s Algorithm
3.3.2: Lemmas on factoring
3.4: Rational and irrational numbers
3.4.1: Rational numbers
3.4.2: Irrational numbers
3.5: Modular arithmetic and encryption
3.5.1: Linear ciphers
3.5.2: RSA encryption
3.5.3: Primality conditions
3.5.4: The additive group of integers modulo n
3.6: Review problems
4: Indexed by Integers
4.1: Sequences, indexing, and recursion
4.1.1: Factorials and binomial coefficients
4.1.2: Sequences
4.1.3: Two special kinds of sequences
4.1.4: Reindexing a sequence
4.1.5: Recursion
4.1.6: Software implementation of recursion
4.2: Sigma notation
4.2.1: Product notation
4.2.2: General summation formulas
4.3: Mathematical induction: An introduction
4.4: Induction and summations
4.5: Strong induction
4.5.1: Standard factorization
4.5.2: The Fibonacci numbers
4.6: The Binomial Theorem
4.7: Review problems
5: Relations
5.1: General relations
5.1.1: Databases
5.1.2: Representing relations
5.1.3: Properties of relations on sets
5.2: Special relations on sets
5.2.1: Order relations
5.2.2: Equivalence relations
5.2.3: Partitions
5.3: Basics of functions
5.3.1: Composing functions
5.3.2: Focusing on real functions
5.4: Special functions
5.4.1: One-to-one and onto functions
5.4.2: Inverse functions
5.4.3: Logarithms
5.5: General set constructions
5.5.1: Images and inverse images
5.5.2: Indexed set operations
5.6: Cardinality
5.7: Review problems
II: Combinatorics
6: Basic Counting
6.1: The multiplication principle
6.2: Permutations and combinations
6.2.1: Permutations
6.2.2: Combinations
6.2.3: Permutations vs. combinations
6.2.4: The proof of Theorem 6.4
6.3: Addition and subtraction
6.3.1: Disjoint events
6.3.2: Complements
6.3.3: Basic inclusion and exclusion
6.4: Probability
6.4.1: Conditional probability
6.5: Applications of combinations
6.5.1: Paths in a grid
6.5.2: Poker
6.5.3: Choices with repetition
6.6: Correcting for overcounting
6.7: Review problems
7: More Counting
7.1: Inclusion–exclusion
7.1.1: Derangements
7.2: Multinomial coefficients
7.3: Generating functions
7.3.1: The algebra
7.3.2: The combinatorics
7.3.3: More algebra
7.3.4: More combinatorics
7.4: Counting orbits
7.4.1: The delayed proofs
7.5: Combinatorial arguments
7.6: Review problems
8: Basic Graph Theory
8.1: Motivation and introduction
8.1.1: Motivation
8.1.2: Introduction
8.1.3: Parts of a graph
8.2: Special graphs
8.3: Matrices
8.4: Isomorphisms
8.5: Invariants
8.5.1: Graph operations
8.6: Directed graphs and Markov chains
8.6.1: Markov chains
8.7: Review problems
9: Graph Properties
9.1: Connectivity
9.1.1: Edge connectivity
9.2: Euler circuits
9.3: Hamiltonian cycles
9.4: Planar graphs
9.4.1: Crossing number
9.5: Chromatic number
9.5.1: Coloring maps
9.6: Review problems
10: Trees and Algorithms
10.1: Trees
10.2: Search trees
10.2.1: Breadth-first search trees
10.2.2: Depth-first search trees
10.2.3: Applications
10.3: Weighted trees
10.3.1: Minimum spanning trees
10.3.2: Shortest path trees
10.4: Analysis of algorithms (Part 1)
10.4.1: Search algorithms
10.4.2: Complexity of algorithms
10.4.3: Growth of functions
10.4.4: Order of algorithms
10.5: Analysis of algorithms (Part 2)
10.5.1: Decision trees
10.5.2: Sorting algorithms
10.6: Review problems
Appendix A: Assumed Properties of ℤ and ℝ
Appendix B: Pseudocode
Appendix C: Answers to Selected Exercises
Bibliography
Index
