Skip to main content
Applied Discrete Structures
Al Doerr, Ken Levasseur
Contents
Index
Search Book
close
Search Results:
No results.
Prev
Up
Next
Scratch ActiveCode
Profile
Course Home
Assignments
Practice
Peer Instruction (Instructor)
Peer Instruction (Student)
Change Course
Instructor's Page
Progress Page
Edit Profile
Change Password
Log Out
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} \)
Front Matter
Colophon
Dedication
Acknowledgements
Preface
1
Set Theory
1.1
Set Notation and Relations
1.1.1
The notion of a set
1.1.2
Subsets
1.1.3
Exercises for Section 1.1
1.2
Basic Set Operations
1.2.1
Definitions
1.2.2
Set Operations and their Venn Diagrams
1.2.3
SageMath Note: Sets
1.2.4
Exercises
1.3
Cartesian Products and Power Sets
1.3.1
Cartesian Products
1.3.2
Power Sets
1.3.3
SageMath Note: Cartesian Products and Power Sets
1.3.4
Exercises
1.4
Binary Representation of Positive Integers
1.4.1
Grouping by Twos
1.4.2
A Conversion Algorithm
1.4.3
Exercises
1.5
Summation Notation and Generalizations
1.5.1
Sums
1.5.2
Generalizations
1.5.3
Exercises
2
Combinatorics
2.1
Basic Counting Techniques - The Rule of Products
2.1.1
What is Combinatorics?
2.1.2
The Rule Of Products
2.1.3
Exercises
2.2
Permutations
2.2.1
Ordering Things
2.2.2
Exercises
2.3
Partitions of Sets and the Law of Addition
2.3.1
Partitions
2.3.2
Addition Laws
2.3.3
Exercises
2.4
Combinations and the Binomial Theorem
2.4.1
Combinations
2.4.2
The Binomial Theorem
2.4.3
SageMath Note
2.4.4
Exercises
3
Logic
3.1
Propositions and Logical Operators
3.1.1
Propositions
3.1.2
Logical Operations
3.1.3
Exercises
3.2
Truth Tables and Propositions Generated by a Set
3.2.1
Truth Tables
3.2.2
Propositions Generated by a Set
3.2.3
Exercises
3.3
Equivalence and Implication
3.3.1
Tautologies and Contradictions
3.3.2
Equivalence
3.3.3
Implication
3.3.4
A Universal Operation
3.3.5
Exercises
3.4
The Laws of Logic
3.4.1
3.4.2
Exercises
3.5
Mathematical Systems and Proofs
3.5.1
Mathematical Systems
3.5.2
Direct Proof
3.5.3
Indirect Proof
3.5.4
Exercises
3.6
Propositions over a Universe
3.6.1
Propositions over a Universe
3.6.2
Truth Sets
3.6.3
Exercises
3.7
Mathematical Induction
3.7.1
Introduction, First Example
3.7.2
More Examples
3.7.3
Course of Values Induction
3.7.4
Exercises
3.8
Quantifiers
3.8.1
The Existential Quantifier
3.8.2
The Universal Quantifier
3.8.3
The Negation of Quantified Propositions
3.8.4
Multiple Quantifiers
3.8.5
Exercises
3.9
A Review of Methods of Proof
3.9.1
Key Concepts in Proof
3.9.2
The Art of Proving
\(P \Rightarrow C\)
3.9.3
Exercises
4
More on Sets
4.1
Methods of Proof for Sets
4.1.1
Examples and Counterexamples
4.1.2
Proof Using Venn Diagrams
4.1.3
Proof using Set-membership Tables
4.1.4
Proof Using Definitions
4.1.5
Exercises
4.2
Laws of Set Theory
4.2.1
Tables of Laws
4.2.2
Proof Using Previously Proven Theorems
4.2.3
Proof Using the Indirect Method/Contradiction
4.2.4
Exercises
4.3
Minsets
4.3.1
Definition of Minsets
4.3.2
Properties of Minsets
4.3.3
Exercises
4.4
The Duality Principle
4.4.1
4.4.2
Exercises
5
Introduction to Matrix Algebra
5.1
Basic Definitions and Operations
5.1.1
Matrix Order and Equality
5.1.2
Matrix Addition and Scalar Multiplication
5.1.3
Matrix Multiplication
5.1.4
Exercises
5.2
Special Types of Matrices
5.2.1
Diagonal Matrices
5.2.2
The Identity Matrix and Matrix Inverses
5.2.3
Exercises
5.3
Laws of Matrix Algebra
5.3.1
The Laws
5.3.2
Commentary
5.3.3
Exercises
5.4
Matrix Oddities
5.4.1
Dissimilarities with elementary algebra
5.4.2
Exercises
6
Relations
6.1
Basic Definitions
6.1.1
Relations between two sets
6.1.2
Relations on a Set
6.1.3
Composition of Relations
6.1.4
Exercises
6.2
Graphs of Relations on a Set
6.2.1
Digraphs
6.2.2
Exercises
6.3
Properties of Relations
6.3.1
Individual Properties
6.3.2
Partial Orderings
6.3.3
Equivalence Relations
6.3.4
Exercises
6.4
Matrices of Relations
6.4.1
Representing a Relation with a Matrix
6.4.2
Composition as Matrix Multiplication
6.4.3
Exercises
6.5
Closure Operations on Relations
6.5.1
Transitive Closure
6.5.2
Algorithms for computing transitive closure
6.5.3
Exercises
7
Functions
7.1
Definition and Notation
7.1.1
Fundamentals
7.1.2
Functions of Two Variables
7.1.3
SageMath Note
7.1.4
Non-Functions
7.1.5
Exercises
7.2
Properties of Functions
7.2.1
Properties
7.2.2
Counting
7.2.3
Exercises
7.3
Function Composition
7.3.1
Function Equality
7.3.2
Function Composition
7.3.3
Inverse Functions
7.3.4
Exercises
8
Recursion and Recurrence Relations
8.1
The Many Faces of Recursion
8.1.1
Binomial Coefficients
8.1.2
Polynomials and Their Evaluation
8.1.3
Recursive Searching - The Binary Search
8.1.4
Recursively Defined Sequences
8.1.5
Recursion
8.1.6
Iteration
8.1.7
Induction and Recursion
8.1.8
Exercises
8.2
Sequences
8.2.1
Sequences and Ways They Are Defined
8.2.2
A Fundamental Problem
8.2.3
Exercises
8.3
Recurrence Relations
8.3.1
Definition and Terminology
8.3.2
Solving Recurrence Relations
8.3.3
Recurrence Relations Obtained from “Solutions”
8.3.4
Solution of Nonhomogeneous Finite Order Linear Relations
8.3.5
Exercises
8.4
Some Common Recurrence Relations
8.4.1
A First Basic Example
8.4.2
An Analysis of the Binary Search Algorithm
8.4.2.1
8.4.2.2
Review of Logarithms
8.4.2.3
8.4.3
Analysis of Bubble Sort and Merge Sort
8.4.4
Derangements
8.4.5
Exercises
8.5
Generating Functions
8.5.1
Definition
8.5.2
Solution of a Recurrence Relation Using Generating Functions
8.5.3
Operations on Sequences
8.5.4
Operations on Generating Functions
8.5.5
Closed Form Expressions for Generating Functions
8.5.6
Extra for Experts
8.5.7
Exercises
9
Graph Theory
9.1
Graphs - General Introduction
9.1.1
Definitions
9.1.2
Subgraphs
9.1.3
Graph Isomorphisms
9.1.4
Next Steps
9.1.5
Exercises
9.2
Data Structures for Graphs
9.2.1
Basic Data Structures
9.2.2
Sage Graphs
9.2.3
Exercises
9.3
Connectivity
9.3.1
Preliminaries
9.3.2
Adjacency Matrix Method
9.3.3
Breadth-First Search
9.3.4
Graph Measurements
9.3.5
SageMath Note - Graph Searching
9.3.6
Exercises
9.4
Traversals: Eulerian and Hamiltonian Graphs
9.4.1
Eulerian Graphs
9.4.2
Hamiltonian Graphs
9.4.3
Exercises
9.5
Graph Optimization
9.5.1
Weighted Graphs
9.5.2
The Traveling Salesman Problem
9.5.3
Networks and the Maximum Flow Problem
9.5.4
Other Graph Optimization Problems
9.5.5
Exercises
9.6
Planarity and Colorings
9.6.1
Planar Graphs
9.6.2
Graph Coloring
9.6.3
Exercises
9.6.4
Further Reading
10
Trees
10.1
What Is a Tree?
10.1.1
Definition
10.1.2
Conditions for a Graph to be a Tree
10.1.3
Exercises
10.2
Spanning Trees
10.2.1
Motivation
10.2.2
Definition
10.2.3
Prim’s Algorithm
10.2.4
Exercises
10.3
Rooted Trees
10.3.1
Definition and Terminology
10.3.2
Kruskal’s Algorithm
10.3.3
SageMath Note - Implementation of Kruskal’s Algorithm
10.3.4
Exercises
10.4
Binary Trees
10.4.1
Definition of a Binary Tree
10.4.2
Traversals of Binary Trees
10.4.3
Expression Trees
10.4.4
Counting Binary Trees
10.4.5
SageMath Note - Power Series
10.4.6
Exercises
11
Algebraic Structures
11.1
Operations
11.1.1
What is an Operation?
11.1.2
Properties of Operations
11.1.3
Operation Tables
11.1.4
Exercises
11.2
Algebraic Systems
11.2.1
Monoids at Two Levels
11.2.2
Levels of Abstraction
11.2.2.1
The Concrete Level
11.2.2.2
The Axiomatic Level
11.2.2.3
The Universal Level
11.2.3
Groups
11.2.4
Exercises
11.3
Some General Properties of Groups
11.3.1
First Theorems
11.3.2
Exponents
11.3.3
Exercises
11.4
Greatest Common Divisors and the Integers Modulo
\(n\)
11.4.1
Greatest Common Divisors
11.4.2
The Euclidean Algorithm
11.4.3
Modular Arithmetic
11.4.4
Properties of Modular Arithmetic
11.4.5
SageMath Note - Modular Arithmetic
11.4.6
Exercises
11.5
Subsystems
11.5.1
Definition
11.5.2
Subgroups
11.5.3
Sage Note - Applying the condition for a subgroup of a finite group
11.5.4
Cyclic Subgroups
11.5.5
Exercises
11.6
Direct Products
11.6.1
Definition
11.6.2
Direct Products of Groups
11.6.3
Exercises
11.7
Isomorphisms
11.7.1
Group Isomorphisms
11.7.2
The order sequence of a finite group
11.7.3
Conditions for groups to not be isomorphic
11.7.4
Exercises
12
More Matrix Algebra
12.1
Systems of Linear Equations
12.1.1
Solutions
12.1.2
Elementary Operations on Equations
12.1.3
Transition to Matrices
12.1.4
Elementary Row Operations
12.1.5
The Gauss-Jordan Algorithm
12.1.6
SageMath Note - Matrix Reduction
12.1.7
Exercises
12.2
Matrix Inversion
12.2.1
Developing the Process
12.2.2
The General Method for Computing Inverses
12.2.3
Exercises
12.3
An Introduction to Vector Spaces
12.3.1
Motivation for the study of vector spaces
12.3.2
Vector Spaces
12.3.3
Exercises
12.4
The Diagonalization Process
12.4.1
Eigenvalues and Eigenvectors
12.4.2
Diagonalization
12.4.3
SageMath Note - Diagonalization
12.4.4
Exercises
12.5
Some Applications
12.5.1
Diagonalization
12.5.2
Path Counting
12.5.3
Matrix Calculus
12.5.4
SageMath Note - Matrix Exponential
12.5.5
Exercises
12.6
Linear Equations over the Integers Mod 2
12.6.1
Row reduction mod 2
12.6.2
Exercises
13
Boolean Algebra
13.1
Posets Revisited
13.1
Exercises
13.2
Lattices
13.2
Exercises
13.3
Boolean Algebras
13.3
Exercises
13.4
Atoms of a Boolean Algebra
13.4
Exercises
13.5
Finite Boolean Algebras as
\(n\)
-tuples of 0’s and 1’s
13.5
Exercises
13.6
Boolean Expressions
13.6
Exercises
13.7
A Brief Introduction to Switching Theory and Logic Design
13.7
Exercises
14
Monoids and Automata
14.1
Monoids
14.1
Exercises
14.2
Free Monoids and Languages
14.2
Exercises
14.3
Automata, Finite-State Machines
14.3
Exercises
14.4
The Monoid of a Finite-State Machine
14.4
Exercises
14.5
The Machine of a Monoid
14.5
Exercises
15
Group Theory and Applications
15.1
Cyclic Groups
15.1
Exercises
15.2
Cosets and Factor Groups
15.2
Exercises
15.3
Permutation Groups
15.3.1
The Symmetric Groups
15.3.2
Cycle Notation
15.3.3
Parity of Permutations and the Alternating Group
15.3.4
Dihedral Groups
15.3.5
Exercises
15.4
Normal Subgroups and Group Homomorphisms
15.4.1
Normal Subgroups
15.4.2
Homomorphisms
15.4.3
Exercises
15.5
Coding Theory, Linear Codes
15.5.1
Introduction
15.5.2
Error Detection
15.5.3
Error Correction
15.5.4
Exercises
16
An Introduction to Rings and Fields
16.1
Rings, Basic Definitions and Concepts
16.1.1
Basic Definitions
16.1.2
Direct Products of Rings
16.1.3
Multiplicative Inverses in Rings
16.1.4
More universal concepts, isomorphisms and subrings
16.1.5
Integral Domains and Zero Divisors
16.1.6
Exercises
16.2
Fields
16.2
Exercises
16.3
Polynomial Rings
16.3
Exercises
16.4
Field Extensions
16.4
Exercises
16.5
Power Series
16.5.1
Definition
16.5.2
Properties, Units
16.5.3
Exercises
Back Matter
A
Algorithms
A.1
An Introduction to Algorithms
A.1.1
Assignments
A.1.2
Conditional steps
A.1.3
Loops
A.1.4
Exercises
A.2
The Invariant Relation Theorem
A.2.1
Two Exponentiation Algorithms
A.2.2
Proving the correctness of the fast algorithm
A.2.3
Exercises
B
Python and SageMath
B.1
Python Iterators
B.1.1
Counting Subsets
B.2
Dictionaries
B.2.1
Colors of Fruits
C
Determinants
C.1
Definition
C.2
Computation
D
Hints and Solutions to Selected Exercises
E
Notation
F
Glossary
F
An Informal Glossary of Terms
References
Index
Dedication
Dedication
To our families
Donna, Christopher, Melissa, and Patrick Doerr
Karen, Joseph, Kathryn, and Matthew Levasseur
