Skip to main content
\(\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}{&} \)
Applied Discrete Structures
Al Doerr, Ken Levasseur
COT 2000 Lecture Notes: Abridged Version
Read the
Online Textbook
for the full content.
Contents
Index
Prev
Up
Next
Contents
Prev
Up
Next
Front Matter
Colophon
Dedication
Acknowledgements
Preface
1
Set Theory
Set Notation and Relations
Basic Set Operations
Cartesian Products and Power Sets
Binary Representation of Positive Integers
Summation Notation and Generalizations
2
Combinatorics
Basic Counting Techniques - The Rule of Products
Permutations
Partitions of Sets and the Law of Addition
Combinations and the Binomial Theorem
3
Logic
Propositions and Logical Operators
Truth Tables and Propositions Generated by a Set
Equivalence and Implication
The Laws of Logic
Mathematical Systems and Proofs
Propositions over a Universe
Mathematical Induction
Quantifiers
A Review of Methods of Proof
4
More on Sets
Methods of Proof for Sets
Laws of Set Theory
Minsets
The Duality Principle
5
Introduction to Matrix Algebra
Basic Definitions and Operations
Special Types of Matrices
Laws of Matrix Algebra
Matrix Oddities
6
Relations
Basic Definitions
Graphs of Relations on a Set
Properties of Relations
Matrices of Relations
Closure Operations on Relations
7
Functions
Definition and Notation
Properties of Functions
Function Composition
8
Recursion and Recurrence Relations
The Many Faces of Recursion
Sequences
Recurrence Relations
Some Common Recurrence Relations
Generating Functions
9
Graph Theory
Graphs - General Introduction
Data Structures for Graphs
Connectivity
Traversals: Eulerian and Hamiltonian Graphs
Graph Optimization
Planarity and Colorings
10
Trees
What Is a Tree?
Spanning Trees
Rooted Trees
Binary Trees
11
Algebraic Structures
Operations
Algebraic Systems
Some General Properties of Groups
Greatest Common Divisors and the Integers Modulo
\(n\)
Subsystems
Direct Products
Isomorphisms
12
More Matrix Algebra
Systems of Linear Equations
Matrix Inversion
An Introduction to Vector Spaces
The Diagonalization Process
Some Applications
Linear Equations over the Integers Mod 2
13
Boolean Algebra
Posets Revisited
Lattices
Boolean Algebras
Atoms of a Boolean Algebra
Finite Boolean Algebras as
\(n\)
-tuples of 0's and 1's
Boolean Expressions
A Brief Introduction to Switching Theory and Logic Design
14
Monoids and Automata
Monoids
Free Monoids and Languages
Automata, Finite-State Machines
The Monoid of a Finite-State Machine
The Machine of a Monoid
15
Group Theory and Applications
Cyclic Groups
Cosets and Factor Groups
Permutation Groups
Normal Subgroups and Group Homomorphisms
Coding Theory, Linear Codes
16
An Introduction to Rings and Fields
Rings, Basic Definitions and Concepts
Fields
Polynomial Rings
Field Extensions
Power Series
Back Matter
A
Algorithms
An Introduction to Algorithms
The Invariant Relation Theorem
B
Python and SageMath
Python Iterators
Dictionaries
C
Determinants
Definition
Computation
D
Hints and Solutions to Selected Exercises
E
Notation
References
Index
Authored in PreTeXt
Textbook: Applied Discrete Structures
Al Doerr
Department of Mathematical Sciences
University of Massachusetts Lowell
Ken Levasseur
Department of Mathematical Sciences
University of Massachusetts Lowell
kenneth_levasseur@uml.edu
May 23, 2022
Colophon
Dedication
Acknowledgements
Preface