Applied Discrete Structures PDF Download – Doerr & Levasseur (3rd Edition) BSCS/BS Math

Applied Discrete Structures covers the Discrete Structures course taken by BS Computer Science and BS Mathematics students, built from set theory, logic, combinatorics and graph theory through to groups, rings and fields. Written by Alan Doerr and Kenneth Levasseur of the University of Massachusetts Lowell, it is part of the official syllabus wherever a Discrete Structures or Discrete Mathematics course runs across two semesters rather than one.

For students preparing for mid-terms and finals, the value here is in the parts most textbooks skip: worked proofs instead of results stated without justification, real chapter summaries instead of a table of contents, and roughly 750 practice problems with solutions provided for most odd-numbered exercises. Whether your course covers only Part 1 (Chapters 1–10) or continues into the full two-semester sequence, this edition gives you the complete text, chapter by chapter, at no cost.

Book Overview

Chapter List

Chapter 1: Set Theory

Difficulty: Easy · Key topics: sets, subset, cardinality, intersection, union, complement, Cartesian product, power set, binary representation

This chapter builds the set-theory vocabulary the rest of the book depends on. It opens with enumeration and set-builder notation, the standard number sets ℕ, ℤ, ℚ, ℝ, and the difference between a subset and set equality. From there it defines the core operations — intersection, union, complement and symmetric difference — and introduces Venn diagrams to picture them, alongside disjoint sets and the universal set U. The chapter then covers Cartesian products and power sets, the binary representation of positive integers, and finally summation notation, extending it to indexed intersections, unions and Cartesian products of several sets.

Key Points:

• A set A is a subset of B (A ⊆ B) iff every element of A is in B; equality means A ⊆ B and B ⊆ A both hold.
• Cardinality of a finite set A is written |A|; a set that is not finite is infinite.
• A ∩ B, A ∪ B, and the complement Aᶜ = U − A are the three basic set operations; disjoint sets have A ∩ B = ∅.
• Symmetric difference A ⊕ B = (A ∪ B) − (A ∩ B) — the elements in exactly one of A or B.
• The Cartesian product A × B has |A| × |B| ordered pairs; the power set P(A) is the set of all subsets of A.
• Positive integers are grouped by powers of two in binary representation — the same idea decimal notation uses with powers of ten.

Memory Tip: Picture ∩ as the narrow waist of an hourglass — only what is shared falls through — and ∪ as a wide cup that collects everything from either side.

Common Mistake: Writing A ⊆ B when the relationship meant is really A ∈ B (or the reverse) — subset is a relationship between two sets, element-of is between an element and a set.

Important Questions:

• What is the difference between a subset and an equal set? A ⊆ B only requires every element of A to be in B; A = B additionally requires every element of B to be in A as well.
• If A = {1, 3, 8} and B = {−9, 22, 3}, what is A ∩ B? {3} — the only element common to both sets.

Chapter 2: Combinatorics

Difficulty: Easy · Key topics: rule of products, permutations, partitions, law of addition, combinations, binomial theorem

Combinatorics is introduced as the art of counting without listing every possibility. The chapter starts with the rule of products — a tree diagram of a snack-bar order shows why multiplying choice counts works — then specializes it to permutations, ordered selections counted by P(n,k) = n!/(n−k)!. It moves to partitions, splitting a set into disjoint, exhaustive subsets, which underlies the law of addition for counting by cases. It closes with combinations, unordered selections counted by the binomial coefficient C(n,k), and their role in the binomial theorem.

Key Points:

• Rule of products: if a first choice has m outcomes and a second has n outcomes independent of the first, there are m × n total outcomes.
• n! (n factorial) is the product of the first n positive integers; 0! = 1 by definition.
• A permutation of k objects from n is an ordered arrangement with no repeats: P(n,k) = n!/(n−k)!.
• A partition splits a set into nonempty subsets that are pairwise disjoint and cover the whole set — the basis of the law of addition.
• Order matters in permutations, not in combinations; C(n,k) = n!/(k!(n−k)!), read “n choose k”.

Memory Tip: Permutation has an order hiding in it if you look closely — P for Position matters; C for Combination Cares nothing for order.

Common Mistake: Using the permutation formula for a problem that is actually asking for an unordered selection, or the reverse — always check first whether swapping two chosen items changes the outcome.

Important Questions:

• A snack bar offers 5 sandwiches and 3 beverages. How many different lunches are possible? 15, by the rule of products (5 × 3).
• How many ways can the 3 letters of {a, b, c} be ordered? 6, since 3! = 3 × 2 × 1 = 6.

Chapter 3: Logic

Difficulty: Medium · Key topics: propositions, truth tables, tautology, equivalence, mathematical systems, induction, quantifiers, proof methods

Logic opens by defining a proposition as a sentence with exactly one truth value, then builds the connectives — conjunction, disjunction, negation, the conditional and its converse — through truth tables. It defines tautology, contradiction, logical equivalence and implication, and catalogs the standard laws of logic that mirror ordinary algebra. A section on mathematical systems formalizes what a definition, axiom, theorem and proof actually are. The chapter then extends propositions to predicates over a universe with truth sets, introduces mathematical induction for proving statements about all positive integers, defines the existential and universal quantifiers, and closes with a review of proof methods.

Key Points:

• A proposition takes exactly one of true/false; p ∧ q, p ∨ q, ¬p and p → q are defined by truth tables, not by wording alone.
• A tautology is true in every case; a contradiction is false in every case.
• Propositions r, s are equivalent (r ⇔ s) iff r ↔ s is a tautology; r implies s iff r → s is a tautology.
• A mathematical system = a universe + definitions + axioms + theorems; a theorem is a true proposition derived from the axioms, and a proof is the finite chain of valid steps that gets there.
• The truth set of a predicate p(n) over universe U is Tᷯ = {a ∈ U : p(a) is true}; p is a tautology over U iff Tᷯ = U.
• Mathematical induction proves a statement for all positive integers by verifying a base case and showing each case forces the next — like a row of dominoes.
• ∃ is the existential quantifier (“there exists”), ∀ is the universal quantifier (“for all”).

Memory Tip: Read induction as toppling dominoes — knock over domino 1 (base case), then show every standing domino knocks over the next (inductive step); that alone guarantees the whole row falls.

Common Mistake: Confusing a conditional’s converse (q → p) with the original (p → q) — the two do not have the same truth value in general.

Important Questions:

• What must be true about a sentence for it to count as a proposition? It must have a definite truth value — exactly one of true or false can be meaningfully applied to it.
• What are the two steps of a proof by mathematical induction? Prove the base case, then prove the inductive step — that the statement being true for k forces it to be true for k+1.

Chapter 4: More on Sets

Difficulty: Medium · Key topics: proof methods for sets, counterexample, laws of set theory, minsets, duality principle

This chapter asks how to actually prove a set identity like A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), starting from a common non-proof — plugging in one numerical example — and showing why that fails. A single counterexample disproves an identity, but no number of examples proves one. It then catalogs the laws of set theory, structurally identical to the laws of logic from Chapter 3. Minsets are introduced as the finest partition generated by a collection of sets, giving any set built from B₁,...,Bₙ a canonical normal form. The chapter closes with the duality principle, which turns every true set identity into another true one by swapping ∪↔∩ and ∅↔U.

Key Points:

• Plugging in specific sets can disprove an identity (one counterexample is enough) but can never prove one true for all sets.
• The laws of set theory mirror the laws of logic (Chapter 3) and ordinary algebra — De Morgan’s, distributive, associative, and more.
• A minset generated by B₁,...,Bₙ is an intersection D₁ ∩ D₂ ∩ ... ∩ Dₙ where each Dᵢ is Bᵢ or its complement; there are 2ₙ minsets for n sets.
• A set is in minset normal form when written as a union of distinct nonempty minsets.
• The dual of an identity swaps ∪ ↔ ∩ and ∅ ↔ U; if the original is true, so is its dual.

Memory Tip: To find a dual fast, mechanically flip the four symbols — ∪→∩, ∩→∪, ∅→U, U→∅ — complement never changes.

Common Mistake: Treating one worked numerical example as a valid proof of a general set identity — it can only ever disprove, never prove.

Important Questions:

• Why doesn’t plugging in one example of A, B, C prove a set identity for all sets? It only shows the identity holds for that one choice, not for every possible set — a general proof needs the Definition or Laws approach.
• How many minsets are generated by 2 sets B₁ and B₂? 4 (2²), since each of the two sets contributes either itself or its complement.

Chapter 5: Introduction to Matrix Algebra

Difficulty: Medium · Key topics: matrix order, matrix addition, matrix multiplication, diagonal matrix, identity matrix, inverse, determinant

Matrix algebra is introduced as a third algebra alongside sets and logic, with entries indexed by row and column and an m×n matrix having order m×n. The chapter defines matrix equality, addition, scalar multiplication and matrix multiplication, then covers special matrices — the zero matrix, diagonal matrices, the identity matrix I, inverses, and the 2×2 determinant formula ad − bc. It lists the standard laws of matrix algebra, carefully noting which orders make each operation defined, and closes with “oddities” — ways matrix algebra breaks the intuitions built from ordinary algebra, especially that multiplication is not commutative.

Key Points:

• An m×n matrix has m rows and n columns; two matrices are equal only if same order and every corresponding entry matches.
• Matrix addition is entrywise: (A+B)ᵢᵡ = aᵢᵡ + bᵢᵡ, and is only defined for matrices of the same order.
• Matrix multiplication requires the number of columns of A to equal the number of rows of B.
• A diagonal matrix has dᵢᵡ = 0 whenever i ≠ j; the identity matrix I is the diagonal matrix of all 1’s.
• The determinant of a 2×2 matrix [[a,b],[c,d]] is ad − bc.
• Matrix multiplication is not commutative in general — AB ≠ BA — so XA = B solves to X = BA⁻¹, not A⁻¹B.

Memory Tip: Whenever a matrix step feels like ordinary algebra, stop and ask “does order matter here?” — addition and scalar multiplication behave like numbers, multiplication does not.

Common Mistake: Writing the solution of XA = B as X = A⁻¹B out of habit from scalar algebra — since matrix multiplication is not commutative, the correct solution is X = BA⁻¹.

Important Questions:

• When is matrix multiplication AB defined? Only when the number of columns of A equals the number of rows of B.
• What is the determinant of a 2×2 matrix [[a,b],[c,d]]? ad − bc.

Chapter 6: Relations

Difficulty: Medium · Key topics: relation, digraph, reflexive, symmetric, antisymmetric, transitive, poset, equivalence relation, transitive closure

A relation from A into B is defined as any subset of the Cartesian product A×B, generalizing an everyday comparison (like matching shirts and slacks) into a formal object. The chapter shows how to draw a relation on a set as a directed graph (digraph) and defines composition of relations. It then isolates the key properties — reflexive, symmetric, antisymmetric and transitive — that combine into a partial ordering (a poset) or an equivalence relation. Relations are also represented as 0-1 matrices using Boolean arithmetic, and the chapter closes with the transitive closure, the smallest transitive relation containing a given one.

Key Points:

• A relation from A into B is any subset of A × B; a relation from A to itself is a relation on A.
• In a digraph of a relation, a directed edge a→b exists exactly when a is related to b.
• Reflexive: a r a for all a. Symmetric: a r b ⇒ b r a. Antisymmetric: a r b and a≠b forces b r a false. Transitive: a r b and b r c ⇒ a r c.
• Reflexive + antisymmetric + transitive = a partial ordering (poset); reflexive + symmetric + transitive = an equivalence relation.
• A relation matrix R has Rᵢᵡ = 1 if aᵢ r bᵡ, else 0; for relations on a set this is also called an adjacency matrix.
• The transitive closure r⁺ is the smallest transitive relation containing r as a subset.

Memory Tip: Test reflexive/symmetric/antisymmetric/transitive on ≤ and = — ≤ is reflexive, antisymmetric and transitive but not symmetric; = is all four at once.

Common Mistake: Assuming “not symmetric” means “antisymmetric” — a relation can be neither, or in rare cases both; they are not opposites.

Important Questions:

• What three properties define a partial ordering? Reflexive, antisymmetric, and transitive.
• What is the transitive closure of a relation r? The smallest transitive relation r⁺ that contains r as a subset.

Chapter 7: Functions and Probability

Difficulty: Medium · Key topics: function, injective, surjective, bijective, composition, sample space, probability distribution, expected value, binomial trial

This chapter first develops functions as relations with two extra restrictions — every domain element maps to exactly one codomain element — defining domain, codomain, image and range, then the injective/surjective/bijective classification and the idea of a countable set. A short section on composition covers function equality, g∘f, function powers, the identity function and invertibility. The chapter then pivots to probability: sample spaces, probability distributions, random variables and expected value, before finishing with binomial (Bernoulli) trials and processes, which model repeated independent yes/no experiments and set up the random-noise models used later in coding theory.

Key Points:

• A function f: A → B is a relation from A to B where every element of A maps to exactly one element of B.
• f is injective if a≠b ⇒ f(a)≠f(b); surjective if its range equals its codomain; bijective if both.
• Two sets have the same cardinality iff a bijection exists between them; a set is countable if finite or the same cardinality as the positive integers.
• Composition: (g∘f)(x) = g(f(x)); an invertible f has a unique inverse f⁻¹ with f⁻¹∘f = f∘f⁻¹ = identity.
• A probability distribution assigns each outcome a nonnegative probability that sums to 1; a random variable maps outcomes to real numbers, with expected value E(X) = Σ X(s)·Pr(s).
• A binomial (Bernoulli) trial has exactly two outcomes with probabilities p and 1−p; a binomial process B(n,p) is n independent repeats of it.

Memory Tip: To check bijective, ask two separate questions — could two inputs share an output? (injective: no) and does every output get hit? (surjective: yes) — both must hold.

Common Mistake: Calling a function “one-to-one” just because it looks like a simple formula — injectivity has to be checked (e.g. f(x)=x² on all integers is not injective, since f(2)=f(−2)).

Important Questions:

• What two conditions make f:A→B a bijection? f must be injective (no two inputs share an output) and surjective (every element of B is hit).
• What is the expected value of a random variable X? E(X) = Σ X(s)·Pr(s), the sum over all outcomes of the outcome’s value weighted by its probability.

Chapter 8: Recursion and Recurrence Relations

Difficulty: Hard · Key topics: recursive definition, sequence, recurrence relation, characteristic equation, homogeneous relation, generating function

Recursion is introduced through parallel examples — binomial coefficients, polynomials, closed-form expressions — to show what a recursive definition actually is: a basis case plus a rule that builds larger cases from smaller ones. A sequence is formalized as a function from the natural numbers, and a recurrence relation as a formula relating each term to earlier ones, illustrated with the two-term Fibonacci relation. The chapter develops finite-order linear recurrence relations with constant coefficients and their characteristic equations, works through common relations outside that class, and ends with generating functions, which turn a sequence into a formal power series so recurrences can be solved by manipulating the series instead.

Key Points:

• A sequence is a function from the natural numbers into a set; S(k) or Sₖ denotes its k-th term.
• A recurrence relation expresses S(k) in terms of earlier terms; the Fibonacci relation Fₖ = Fₖ₂ + Fₖ₁ (indices k−2, k−1) is second-order because it needs the two previous terms.
• An n-th order linear recurrence with constant coefficients has the form S(k) + C₁S(k−1) + ... + CₙS(k−n) = f(k); it is homogeneous when f(k)=0.
• The characteristic equation of a homogeneous linear recurrence is the polynomial built directly from its coefficients.
• A generating function of sequence S is the formal power series G(S;z) = S₀ + S₁z + S₂z² + ...; sequences can be added, scaled, multiplied (convolved) or shifted just like these series.

Memory Tip: Think of a recurrence relation as a recipe that always says “use yesterday’s batch (and maybe the day before’s)” — the order of the relation is how many previous days’ batches it needs.

Common Mistake: Forgetting to state the initial condition(s) alongside a recurrence relation — the relation alone has infinitely many solutions until the starting terms are fixed.

Important Questions:

• Why is the Fibonacci recurrence called second-order? Because each term depends on the two immediately preceding terms.
• What is the generating function of a sequence S with terms S₀, S₁, S₂, …? The formal power series G(S;z) = S₀ + S₁z + S₂z² + ....

Chapter 9: Graph Theory

Difficulty: Hard · Key topics: directed graph, undirected graph, connectivity, Eulerian path, Hamiltonian path, weighted graph, network flow, planarity, coloring

Graph theory formalizes the directed-graph pictures from Chapter 6 into their own object: vertices and edges, with simple, multigraph, complete and subgraph variants, plus connected components. It covers data structures for storing graphs, especially adjacency matrices, then asks when a path exists between two vertices, defining connected and strongly connected graphs. Traversal problems get real history here — Euler’s solution to the Königsberg Bridge Problem motivates Eulerian and Hamiltonian paths/circuits, and the n-cube is introduced as a graph built from binary strings. The chapter covers graph optimization — the Traveling Salesman and Maximum Flow problems on weighted graphs and networks — then closes with planarity and graph colorings, including bipartite graphs.

Key Points:

• A simple directed graph is a vertex set V plus an edge set E ⊆ V×V; an undirected graph’s edges are two-element subsets of V.
• Kₙ denotes the complete graph on n vertices, where every pair of distinct vertices is connected.
• An Eulerian circuit uses every edge exactly once; a Hamiltonian circuit visits every vertex exactly once — named for Euler’s 1735 Königsberg Bridge solution.
• A weighted graph (V,E,w) assigns a weight to each edge; a network adds a source and sink for max-flow problems.
• A graph is planar if it can be drawn with no edge crossings; a bipartite graph is exactly one with a 2-coloring.

Memory Tip: Euler = Edges (an Eulerian path uses every edge once); Hamiltonian = Hits every vertex (a Hamiltonian path visits every vertex once) — the initial letters double as the hook.

Common Mistake: Assuming a graph with an Eulerian circuit also has a Hamiltonian circuit, or the reverse — the two properties are independent; a graph can have one, both, or neither.

Important Questions:

• What made the Königsberg Bridge Problem unsolvable? No walking tour could cross each of the city’s seven bridges exactly once — too many vertices of odd degree for an Eulerian path to exist.
• What is the difference between a connected and a strongly connected directed graph? Connected means for every pair of vertices at least one is reachable from the other; strongly connected means every pair is mutually reachable in both directions.

Chapter 10: Trees

Difficulty: Medium · Key topics: tree, cycle, forest, spanning tree, minimal spanning tree, rooted tree, binary tree

Trees are defined as connected, cycle-free graphs, distinguishing a cycle (a circuit with no repeated edges) from a general circuit. The chapter motivates spanning trees with a network-design problem — connecting university campuses at minimum cost — showing that optimal solutions to that kind of problem are themselves trees, and defines minimal spanning trees for weighted graphs. It introduces rooted trees, where one vertex is distinguished as the root and every other vertex has family-tree language (parent, child) relative to it, and shows how children are conventionally drawn below their parents. It closes with ordered rooted trees and the special case of binary trees, defined recursively from the empty tree and left/right subtrees.

Key Points:

• A tree is an undirected graph that is connected and contains no cycles; a forest is a graph whose components are all trees.
• A cycle Cₙ is a circuit whose edge list has no duplicates.
• A spanning tree of connected graph G is a spanning subgraph of G that is itself a tree; a minimal spanning tree minimizes total edge weight.
• In a rooted tree, the root has no parent, and every other vertex has a unique path back to the root defining its ancestors.
• A binary tree is defined recursively: the empty tree is a binary tree, and a vertex with two subtrees that are each binary trees is a binary tree.

Memory Tip: Say it as one phrase — “connected + no cycles = tree” — drop either half and it stops being a tree (disconnected pieces make a forest, a cycle makes it just a graph).

Common Mistake: Assuming any connected graph with n−1 edges for n vertices must be a tree — that edge count is necessary but the graph must also actually be connected and cycle-free.

Important Questions:

• What two properties define a tree? It must be connected and contain no cycles.
• What is a minimal spanning tree? For a weighted connected graph, a spanning tree whose edges have the smallest possible total weight among all spanning trees of that graph.

Chapter 11: Algebraic Structures

Difficulty: Hard · Key topics: binary operation, algebraic system, group, abelian, integers modulo n, gcd, subsystem, direct product, isomorphism

This chapter opens Part 2 of the book by formalizing what an operation is — a binary operation assigns each ordered pair in S a unique element of S — and the recurring properties (commutative, associative, identity, inverse) that show up throughout algebra. An algebraic system pairs a domain with one or more operations, and the group is introduced as the first fully axiomatic algebraic system: associative, with an identity and inverses. The chapter proves basic group theorems, builds the integers modulo n as a concrete family of groups using the greatest common divisor, and introduces three universal concepts that apply to any algebraic system — subsystems, direct products, and isomorphisms, the idea that two systems can be “the same” under a translation rule even when their elements look completely different.

Key Points:

• A binary operation on S assigns each ordered pair of elements of S a unique element of S — formally, a function from S×S into S.
• A group [G;*] requires * to be associative, have an identity e with a*e=e*a=a, and every element to have an inverse; it is abelian if * is also commutative.
• The integers modulo n, ℤₙ = {0,1,...,n−1} under mod-n addition, form a concrete group for every positive integer n.
• Two integers a, b are relatively prime if gcd(a,b)=1.
• A subsystem W of system V (written W ≤ V) is a subset that is itself an algebraic system of the same kind under the same operations.
• Two systems are isomorphic if a bijection f between them satisfies f(a*b) = f(a)⋄f(b), so every true statement in one translates to a true statement in the other.

Memory Tip: Isomorphism is “same shape, different names” — like doing arithmetic in a different language: the symbols look foreign, but 3+4=7 is still true either way.

Common Mistake: Assuming any set with a binary operation is automatically a group — associativity, an identity, and an inverse for every element all have to be checked; skipping the inverse check is the most common gap.

Important Questions:

• What four conditions make [G;*] a group? * is a binary operation on G that is associative, has an identity element in G, and every element of G has an inverse under *.
• What does it mean for two algebraic systems to be isomorphic? A bijection exists between them that translates the operation correctly, so every true statement in one system corresponds to a true statement in the other.

Chapter 12: More Matrix Algebra

Difficulty: Hard · Key topics: systems of linear equations, row-equivalence, matrix inversion, vector space, basis, dimension, eigenvalue, diagonalization

Returning to matrices, this chapter solves systems of linear equations by reducing them to simpler, row-equivalent systems, then develops a systematic method for finding a matrix inverse via row operations. It introduces vector spaces from scratch — addition and scalar multiplication satisfying a fixed list of axioms — building up linear combination, spanning, linear independence, basis and dimension. These feed into the diagonalization process, defining eigenvalues and eigenvectors and when a matrix A can be written as PDP⁻¹ for diagonal D, which makes computing high powers of A dramatically easier. The chapter closes with linear equations over the integers modulo 2, where arithmetic is finite and the row-reduction techniques from earlier reappear in a context relevant to coding theory.

Key Points:

• Two systems of linear equations are equivalent if they have the same solution set; two matrices are row-equivalent if one is obtained from the other by elementary row operations.
• A vector space requires addition and scalar multiplication to satisfy a fixed list of axioms over the reals.
• A basis is a linearly independent set of vectors that spans the space; the dimension is the number of vectors in a basis.
• λ is an eigenvalue of matrix A if Ax = λx for some nonzero vector x, called the eigenvector for λ.
• A is diagonalizable if there is an invertible P with P⁻¹AP = D diagonal; this makes computing Aᵍ as easy as computing Dᵍ.
• Over the integers mod 2, every unknown can only be 0 or 1, so a system of m equations in n unknowns has at most 2ₙ possible solutions.

Memory Tip: Diagonalizing a matrix is like changing units before doing arithmetic — awkward in the original basis, trivial once you are working in the eigenvector basis where the matrix is just a diagonal of scaling factors.

Common Mistake: Assuming every square matrix is diagonalizable — a matrix needs as many independent eigenvectors as its size for P⁻¹AP=D to exist, and not every matrix has them.

Important Questions:

• What is an eigenvector of a matrix A? A nonzero vector x such that Ax = λx for some scalar λ, called the eigenvalue for x.
• Why does diagonalizing a matrix make computing its powers easier? If A = PDP⁻¹ with D diagonal, then Aᵍ = PDᵍP⁻¹, and raising a diagonal matrix to a power just means raising each diagonal entry.

Chapter 13: Boolean Algebra

Difficulty: Hard · Key topics: poset, lattice, meet, join, bounded lattice, complemented lattice, Boolean algebra, atom, minterm, switching theory

Boolean algebra is built up in careful stages from ideas introduced earlier. Posets are revisited to define lower/upper bounds and greatest/least elements, then lattices are defined as posets where every pair of elements has both a meet and a join. Adding a least and greatest element (0 and 1) and complementation on top of a distributive lattice gives a Boolean algebra. The chapter shows every finite Boolean algebra is generated by a set of atoms and has exactly 2ₙ elements, making it isomorphic to a power-set algebra, and gives an n-tuple representation for computation. It defines Boolean expressions and minterm normal form, then closes with switching theory — how Boolean algebra models the logic gates inside a digital circuit, connecting straight back to Chapter 3’s logic and George Boole’s own 19th-century work.

Key Points:

• A lattice is a poset in which every pair of elements has both a meet a∧b (greatest lower bound) and a join a∨b (least upper bound).
• A bounded lattice has both a least (0) and greatest (1) element; it is complemented if every element a has some b with a∨b=1 and a∧b=0.
• A Boolean algebra is a bounded lattice that is both complemented and distributive.
• Every finite Boolean algebra has 2ₙ elements for some n, generated by exactly n atoms.
• A minterm generated by x₁,...,xₖ is a meet of the variables or their complements; minterm normal form writes any Boolean expression as a join of such minterms.
• Boolean algebra underlies switching theory: computer circuits realize logical operations because circuits and Boolean algebras are isomorphic structures.

Memory Tip: Meet (∧) behaves like AND/intersection; join (∨) behaves like OR/union. Anyone who already knows set operations already knows lattice operations under different names.

Common Mistake: Assuming every lattice is a Boolean algebra — a lattice only becomes Boolean once it is also bounded, complemented, and distributive; many familiar lattices fail distributivity.

Important Questions:

• What extra conditions turn a lattice into a Boolean algebra? It must be bounded (a least element 0 and greatest element 1), complemented, and distributive.
• How many elements does a finite Boolean algebra with n atoms have? Exactly 2ₙ elements.

Chapter 14: Monoids and Automata

Difficulty: Hard · Key topics: monoid, alphabet, string, free monoid, formal language, regular grammar, finite-state machine

The chapter connects two seemingly unrelated ideas: monoid theory (from Chapter 11) and automata theory. A monoid is a set with an associative operation and an identity — weaker than a group since inverses are not required. It defines strings over an alphabet, the free monoid of all strings under concatenation, and formal languages as subsets of that free monoid, including phrase-structure and regular grammars. Finite-state machines are introduced formally as a quintet (states, inputs, outputs, transition and output functions) that read an input tape one symbol at a time. The chapter’s punchline is the two-way correspondence: every finite-state machine has an associated monoid built from its input sequences, and conversely every finite monoid can be represented as a state machine.

Key Points:

• A monoid is a set M with an associative binary operation that has an identity in M — a group without the inverse requirement.
• A string of length n over alphabet A is a sequence of n letters; the null string λ has length 0; A* is the set of all strings over A.
• A formal language over A is any subset of A*; a language is recursive if a recognition algorithm exists for it.
• A regular (right-hand form) grammar has production rules of the form A→t and A→tB only.
• A finite-state machine is a quintet (S,X,Z,w,t): states, inputs, outputs, output function, and next-state function.
• Every finite-state machine has an associated monoid, and every finite monoid can be represented as a machine.

Memory Tip: A monoid is “a group that gave up the promise of undo” — everything a group has except guaranteed inverses; that missing property is exactly what strings-under-concatenation need.

Common Mistake: Assuming every monoid is a group out of habit from Chapter 11 — always check explicitly whether every element has an inverse; string concatenation, for example, has none in general.

Important Questions:

• What is the one property a group has that a monoid does not require? Every element having an inverse — a monoid only requires an associative operation with an identity.
• What does it mean for a formal language to be recursive? There exists an algorithm that can decide, for any string, whether it belongs to the language.

Chapter 15: Group Theory and Applications

Difficulty: Hard · Key topics: cyclic group, coset, factor group, permutation group, normal subgroup, homomorphism, kernel, Hamming distance

Building on Chapter 11’s introduction to groups, this chapter studies group structure in depth. Cyclic groups — generated by a single element, like ℤₙ under addition — have the simplest possible structure. Cosets partition a group into copies of a subgroup, motivating the question of when those cosets themselves form a group (a factor group). Permutation groups treat bijections of a finite set as group elements under composition, illustrated with the symmetric group S₃. The chapter defines normal subgroups (where left and right cosets coincide) and homomorphisms, and closes with a real application: linear coding theory, using the Hamming distance to measure how many bits two transmitted codewords differ in, for detecting and correcting transmission errors.

Key Points:

• A group G is cyclic if some a ∈ G generates all of G; every ℤₙ is cyclic, generated by 1.
• The left coset of subgroup H generated by a is a*H = {a*h : h∈H}; cosets of H partition G into equal-size pieces.
• H is a normal subgroup (H ◁ G) if every left coset of H is also a right coset — the condition needed for the cosets to form a factor group G/H.
• A homomorphism θ: G → G’ satisfies θ(x*y) = θ(x)⋄θ(y); its kernel is the set of elements mapped to the identity.
• The symmetric group Sₙ is the set of all permutations on n elements under composition; the even permutations form the alternating group Aₙ.
• The Hamming distance between two codewords counts the positions where they differ — the basis for detecting and correcting transmission errors.

Memory Tip: A normal subgroup is the one place in algebra where “left equals right” really matters — left cosets = right cosets is exactly what lets a group be divided by a subgroup and still get a group back.

Common Mistake: Confusing a subgroup with a normal subgroup — every normal subgroup is a subgroup, but not every subgroup is normal; the extra condition must be checked separately.

Important Questions:

• What condition makes a subgroup H of G normal? Every left coset of H equals the corresponding right coset for all a in G.
• What does the Hamming distance between two codewords measure? The number of bit positions in which the two codewords differ — the basis for detecting and correcting coding errors.

Chapter 16: An Introduction to Rings and Fields

Difficulty: Hard · Key topics: ring, commutative ring, unity, unit, zero divisor, field, polynomial ring, field extension, power series

The book’s final chapter generalizes the integers into rings — a set with addition and multiplication where addition forms an abelian group and multiplication distributes over addition — and identifies commutative rings, rings with unity, units and zero divisors along the way. A field strengthens this to a commutative ring with unity where every nonzero element has a multiplicative inverse, finally making equations like ax=b solvable in general. The chapter builds polynomial rings over an arbitrary ring, defining degree and reducible versus irreducible polynomials over a field. Field extensions address what happens when a polynomial’s roots (like √2) do not live in the original field, and the chapter closes with power series, extending polynomials to infinite expressions.

Key Points:

• A ring R has addition and multiplication where [R;+] is an abelian group and multiplication distributes over addition on both sides.
• A commutative ring has commutative multiplication; a ring with unity has a multiplicative identity 1; a unit has a multiplicative inverse within the ring.
• Zero divisors are nonzero a, b in R with a·b = 0 — something that cannot happen in the familiar number systems but can in other rings.
• A field is a commutative ring with unity where every nonzero element has a multiplicative inverse.
• A polynomial over ring R has degree n if its leading coefficient is nonzero; it is irreducible over field F if it cannot be factored into two nonconstant polynomials in F[x].
• A field extension adds a root (like √2) to a field so equations like x²−2=0 become solvable inside the extended field.

Memory Tip: Ring → Field is like integers → rationals: a ring is like ℤ (no guaranteed division), a field is like ℚ (division always works except by zero).

Common Mistake: Assuming multiplicative inverses exist in any ring the way additive inverses do — additive inverses are guaranteed, multiplicative inverses are not, which is exactly what makes a field a field.

Important Questions:

• What single extra property turns a commutative ring with unity into a field? Every nonzero element must have a multiplicative inverse.
• What are zero divisors, and why are they notable? Nonzero ring elements a, b with a·b = 0 — a situation impossible in the integers or reals but possible in other rings.

Appendix: Algorithms

Appendix · Difficulty: Easy · Key topics: algorithm, input, output, steps

This appendix formalizes the everyday idea of a set of instructions — like a recipe or assembly instructions — into the concept of an algorithm: a precise, finite sequence of steps that transforms given input into a defined output. It sets up the vocabulary used informally throughout the rest of the book whenever a procedure, like row reduction or the Euclidean algorithm, is described.

Key Points:

• An algorithm is a finite, precisely specified sequence of steps that produces a defined output from a given input.
• Everyday procedures — recipes, assembly instructions, knitting patterns — share the same structure as computer algorithms: input, steps, output.

Important Questions:

• What three things does every algorithm need to specify? Its input, the sequence of steps to perform, and its output.
• Why do recipes and computer algorithms share the same basic structure? Both are precise, ordered sequences of steps that take some input and reliably produce a defined output.

Appendix: Python and SageMath

Appendix · Difficulty: Easy · Key topics: SageMath, Python, computer algebra system

This appendix highlights how SageMath — a free, open-source computer algebra system built on Python — is used throughout the book’s “SageMath Notes” to let readers experiment with sets, matrices, groups and other structures computationally rather than only on paper. It covers enough Python syntax to read and adapt the book’s embedded Sage cells, since most SageMath code shown is plain Python.

Key Points:

• SageMath (sagemath.org) is free, open-source math software built on top of Python.
• Most code shown in the book’s SageMath cells is ordinary Python and can be evaluated directly in them.
• SageMath replaced the “Pascal Notes” used in the book’s 1980s edition, reflecting how computational tools in math education have changed.

Practice Tip: Open the book’s live Sage Cell pages and re-run a definition’s example by typing it yourself rather than only reading it — seeing the actual output builds intuition faster than the printed page alone.

Important Questions:

• What is SageMath built on top of? Python — most SageMath cell code shown in the book is just ordinary Python.
• What did SageMath replace in the book’s earlier edition? The 1980s edition’s Pascal Notes, replaced throughout with SageMath Notes to match modern computing practice.

Appendix: Determinants

Appendix · Difficulty: Medium · Key topics: determinant, invertibility, n×n matrix

Chapter 5 defines the determinant only for 2×2 matrices, just enough to compute inverses by hand. This appendix completes the picture, defining the determinant of an n×n matrix of any size and summarizing its main properties — most importantly, that a square matrix is invertible if and only if its determinant is nonzero.

Key Points:

• The determinant of a 1×1 matrix is simply its single entry; for a 2×2 matrix it is ad−bc.
• A square matrix has a multiplicative inverse if and only if its determinant is nonzero.
• Determinants are commonly denoted det(A) or |A|.

Memory Tip: “Determinant ≠ 0” is the one-line invertibility test — check it before attempting to invert any square matrix by hand.

Important Questions:

• What does a determinant of zero tell you about a square matrix? The matrix is not invertible — it has no multiplicative inverse.
• What is the determinant of a 1×1 matrix [a]? Simply a, its single entry.

Download Applied Discrete Structures PDF (Free)

Your free PDF is hosted on the authors’ own site — the download link opens the complete 16-chapter edition (about 8 MB) directly from discretemath.org.

How to Study This Book

Applied Discrete Structures is built for a full two-semester sequence, and the book itself makes that split explicit: the free PDF is offered as a complete Chapters 1–16 edition, or as two separate halves — Part 1: Fundamentals (Chapters 1–10) and Part 2: Algebraic Structures (Chapters 11–16). If your course covers only one semester, download the matching half instead of the full 8 MB file.

For a first, one-semester Discrete Structures or Discrete Mathematics course, treat Chapters 1, 3 and 4 (Set Theory, Logic, More on Sets) as the non-negotiable core — nearly everything later in the book leans on set notation, truth tables and proof technique from these three. Chapter 2 (Combinatorics) and Chapter 6 (Relations) usually follow directly. Chapter 5 (Introduction to Matrix Algebra) can be skimmed or skipped if your program has a separate Linear Algebra course — it exists mainly to support the diagonalization work in Chapter 12. Chapter 7 (Functions and Probability) and Chapters 9–10 (Graph Theory, Trees) are shared most directly with a Data Structures and Algorithms course. Chapter 8 (Recursion and Recurrence Relations) is often the hardest on a first pass — its generating-functions section is genuinely optional if your course does not examine it.

If your program continues into a second semester of algebraic structures — sometimes taught as “Discrete Structures II” or folded into an Abstract Algebra course — Chapter 11 (Algebraic Structures) is the anchor everything else in Part 2 depends on; do not skip ahead of it. Chapter 12 (More Matrix Algebra) pairs naturally with a concurrent Linear Algebra course, since it covers vector spaces and diagonalization in more depth than Chapter 5. Chapter 13 (Boolean Algebra) is essential preparation if you are also taking Digital Logic Design, since its final section connects Boolean algebra directly to switching circuits. Chapter 14 (Monoids and Automata) is a useful bridge into a Theory of Automata or Formal Languages course, though it is intentionally brief — treat it as an introduction, not a substitute for a dedicated automata textbook. Chapter 15 (Group Theory and Applications) builds directly on Chapter 11 and closes with an applied section on coding theory. Chapter 16 (Rings and Fields) is usually covered last, and underpins later work in Cryptography or Coding Theory electives.

The three appendices are reference material, not syllabus chapters: read Algorithms and Python and SageMath only if your instructor has you running the book’s embedded SageMath cells, and read Determinants only if Chapter 5 or 12’s brief treatment of 2×2 determinants is not enough for the n×n case your course needs.

What the book does not cover: it stays entirely inside discrete mathematics and never touches calculus, real analysis, or other continuous-math topics — pair it with a separate Calculus text for that. Chapter 14’s automata material is also intentionally short; if your course is a full semester of Theory of Computation, this book is a bridge into that subject, not a replacement for it.

Because roughly half the exercises have hints or solutions in the back of the book, work the odd-numbered problems first in each section, check your answer against the back matter, and only move to the even-numbered problems (which have no printed solution) once you are confident with the technique.

Used In These Programs

This book is used for the Discrete Structures / Discrete Mathematics course in: BS Computer Science · BS Mathematics. Browse all Discrete Structures books or all Mathematics books.

Who Should Read This

This book is written for BSCS and BS Mathematics students taking a Discrete Structures or Discrete Mathematics course, typically in the first or second year, and it works equally well for a one-semester survey or the full two-semester sequence the book itself is designed around. It assumes only high-school algebra going in, so it does not require prior exposure to proofs or formal logic — Chapter 3 builds that from scratch. Because Chapters 11–16 go as far as groups, rings, fields and Boolean algebra, this book also holds up well as pre-reading before a Digital Logic Design, Theory of Automata, or Abstract Algebra course, or as a self-study refresher for someone preparing for a math-heavy graduate entrance test. It is not the right choice for someone who only wants a fast, CS-interview-style pass through counting, logic and graphs — its algebraic-structures half goes considerably deeper into pure mathematics than most single-semester CS discrete-math courses actually examine. Students who want a lighter, more CS-application-focused single-semester text covering similar counting, logic and graph-theory ground should pair this book with Discrete Mathematics: An Open Introduction by Oscar Levin — the two make a genuinely useful contrast rather than a duplicate, since Levin’s book stays CS-focused for one semester while this one continues into the algebraic structures a math-heavy program still needs.

Applicable Universities

This book is useful for students at Pakistani universities offering BSCS and BS Mathematics degrees, including Punjab University, Virtual University, COMSATS, FAST, UET, NUST, and other HEC-recognized institutions.

FAQs

Related Books

• Discrete Mathematics: An Open Introduction – Oscar Levin (4th Edition)
• Calculus Volume 1 – Strang & Herman (OpenStax)
• Active Calculus – Matthew Boelkins (2nd Edition)

Applied Discrete Structures gives BSCS and BS Mathematics students a genuinely complete, two-semester discrete math foundation — from set notation through groups, rings and fields — released for free under a Creative Commons license by its own authors. Browse more free Mathematics books on Freebooks.pk.

Applied Discrete Structures, 3rd Edition (Version 3-14, June 2026), by Alan Doerr & Kenneth Levasseur, University of Massachusetts Lowell. Licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License. Official source: discretemath.org.