Applied Discrete Structures

About this book

Alan Doerr and Kenneth Levasseur’s Applied Discrete Structures connects the mathematical language of computing with counting, graphs, recurrences, and algebraic systems. The complete author-hosted PDF is dated July 16, 2026 and contains sixteen main chapters. This guide follows that textbook, replacing the imported link to the separate activity-slide collection. Definitions, proofs, algorithms, and examples are treated as complementary ways to understand a discrete structure.

Chapter and section guide

1. Set Theory

Sets provide a language for describing collections and relationships. Membership differs from inclusion, and set operations should be understood through their definitions. Diagrams help with small examples, while symbolic arguments extend beyond what can be drawn. Students should identify the universal set when taking complements and distinguish an element from a singleton containing it. This foundation supports later relations, functions, graphs, and algebra.

Study application: Prove one elementary set identity by showing both inclusions. Use a diagram to check intuition, then explain why the argument applies beyond the pictured example.

2. Combinatorics

Counting requires a precise description of the objects being counted. Product and sum rules, permutations, and combinations address different constructions. Order, repetition, and distinguishability affect the result. Students should explain why a construction counts each object once rather than choose a familiar formula from surface wording. A small enumerated example can reveal overcounting before a general expression is accepted.

Study application: Count a simple selection problem both directly and through a construction. Change whether order matters and explain why the answer changes.

3. Logic

Propositions, truth tables, implication, quantifiers, and proof support valid mathematical reasoning. An implication is not the same as its converse, and negating a quantified statement changes both the quantifier and predicate. The chapter connects formal statements with arguments students can audit. A truth table checks a propositional form, while a proof about objects must also use the relevant definitions and hypotheses.

Study application: Write a quantified claim, negate it correctly, and give a counterexample to its converse when possible. Explain which part of the logic the example tests.

4. More on Sets

Further set reasoning connects logical operations with identities and constructions. The chapter extends the tools needed to organize mathematical objects and compare descriptions. Students should move between membership statements and logical conditions carefully. A named identity becomes more useful when its proof can be reconstructed from definitions. This also prepares the interpretation of structures built from sets rather than treating every later chapter as a new notation system.

Study application: Translate an expression involving union, intersection, and complement into a logical statement about one arbitrary element. Use the translation to verify a claimed equivalence.

5. Matrix Algebra

Matrices offer compact representations and operations useful in discrete problems. Addition and multiplication have different dimension requirements, and multiplication generally depends on order. Students should explain what an entry in a product represents instead of performing arithmetic mechanically. The meaning of the representation may vary with the application. A dimension check can identify an impossible operation before calculation begins.

Study application: Multiply two small compatible matrices and explain one resulting entry as a sum of products. State the sizes of all objects and why reversing the factors may fail or change the result.

6. Relations

A relation is a set of ordered pairs with properties that can be tested precisely. Reflexivity, symmetry, antisymmetry, and transitivity describe different conditions. Matrix and graph representations make finite relations easier to inspect, but proofs must cover all required cases. Equivalence relations and orders organize elements in different ways. Students should avoid assuming that a familiar visual pattern establishes a property without checking its definition.

Study application: Construct a relation that is symmetric but not transitive, then explain exactly which required pair is missing. Contrast it with an equivalence relation.

7. Functions and Probability

Functions impose a unique-output condition on a relation and can be studied through injectivity, surjectivity, and composition. Probability applications connect finite constructions with quantified uncertainty. Students should distinguish a function’s codomain from its actual range and state the sample space underlying a probability calculation. Counting outcomes without examining whether they are equally likely can produce an incorrect probability even when the count is right.

Study application: Define a finite function with a codomain larger than its range. Then build a probability example and explain the assumption required to use favorable outcomes divided by total outcomes.

8. Recursion and Recurrences

Recursive definitions specify an object through earlier cases, while recurrences describe relationships among sequence values. Initial conditions are essential to a unique sequence. The chapter develops methods for solving and checking recurrence relations and connects them with generating functions and algorithmic patterns. Students should distinguish deriving a candidate formula from proving that it satisfies both the recurrence and starting values.

Study application: Solve a small recurrence with stated initial conditions and verify the first few terms. Explain why omitting an initial condition leaves a family of possibilities.

9. Graph Theory

Vertices and edges model relationships while retaining only the features relevant to a problem. Paths, connectivity, graph representations, and structural properties support different questions. The appropriate model may be directed, undirected, weighted, or unweighted. Students should state those choices before applying a theorem or traversal. A drawing is one representation of a graph, not the graph’s unique identity.

Study application: Model a small route or dependency problem, explaining what vertices and edges mean. Identify which information was deliberately omitted and how that limits the model’s use.

10. Trees

Trees combine connectedness with the absence of cycles and support many structural and computational applications. Rooted and binary trees add conventions that change the questions one asks about levels, parents, and traversal. Students should distinguish a general tree from one particular drawing or rooting. Proofs often exploit the structure recursively. A spanning tree preserves reachability among vertices while discarding some edges of a larger graph.

Study application: Find a spanning tree of a small connected graph and explain which edges were removed. Verify connectedness and the absence of cycles rather than relying only on an edge count.

11. Algebraic Structures

A set together with operations can satisfy different systems of algebraic properties. Closure, associativity, identities, and inverses need separate examination. Familiar arithmetic supplies examples, but notation alone does not guarantee the same laws. The chapter builds a vocabulary for comparing structures by what their operations do. Students should test the defined operation on the stated set rather than import unproved assumptions.

Study application: Define a small binary operation using a table and test closure, identity, and commutativity. Identify which additional property would need proof for a stronger classification.

12. More Matrix Algebra

Further matrix methods connect systems, inverses, and structural properties with the earlier algebraic viewpoint. A computational procedure needs conditions under which its steps are valid. Students should distinguish row operations that preserve a system’s solutions from an assertion that every matrix is invertible. The chapter connects calculations with broader questions about how operations compose and which equations can be solved.

Study application: Use row operations to investigate a small matrix equation. Explain whether the result establishes existence, uniqueness, or both, and verify the conclusion in the original system.

13. Boolean Algebra

Boolean algebra abstracts operations associated with logical and set-theoretic patterns. Laws can support simplification and the comparison of different expressions. The chapter’s applications show why an equivalent expression may be useful in a different implementation. Students should distinguish logical equivalence from syntactic resemblance and identify the meaning of the operations in the chosen interpretation.

Study application: Simplify a small Boolean expression and verify it with a truth table. Explain how two different-looking expressions can implement the same input-output behavior.

14. Monoids and Automata

Monoids organize associative operations with an identity, while automata connect states and transitions with processing input. The chapter links algebraic composition with computational behavior. A transition description should specify the alphabet, states, starting condition, and acceptance convention. Students should trace short inputs before making a general claim about the recognized language. The algebraic and machine descriptions illuminate different aspects of the same structure.

Study application: Trace several strings through a small automaton and describe the accepted pattern. Explain what information the current state retains about the input already read.

15. Groups and Applications

Groups add invertibility to a structured operation and support analysis of symmetry and transformations. Subgroups, cosets, and permutation examples require attention to the operation, not only the underlying elements. Applications such as coding connect algebraic properties with concrete questions. Students should identify the invariant or structure preserved by a transformation and justify the group properties used in an argument.

Study application: Construct a small symmetry group and compose two actions in both orders. Explain whether the results agree and why group structure does not require commutativity.

16. Rings and Fields

Rings and fields combine operations with specified compatibility laws. The availability of division distinguishes important structures and affects which algebraic manipulations are justified. Modular examples help make zero divisors and invertibility concrete. Students should check the hypotheses before canceling or dividing, especially when a familiar arithmetic step is moved into a different system. The chapter broadens the earlier structures while keeping the definitions central.

Study application: Compare arithmetic modulo a prime with arithmetic modulo a composite number. Find a nonzero element lacking an inverse in the latter and explain the consequence for solving an equation.

Appendices and Supporting Tools

The appendices support algorithms, computation, and further study. These resources should be connected with the main text’s definitions and proof goals rather than treated as shortcuts around them. An algorithmic experiment can suggest a pattern, while a mathematical argument explains why it holds under stated conditions. Students should record inputs, outputs, and limitations when using a computational tool.

Study application: Use a small calculation or program to test a conjecture from one chapter, then identify the additional argument needed to establish it for all permitted inputs.

Study instructions

1. Build a glossary containing each structure, its defining properties, an example, and a nonexample.
2. Before counting or calculating, state the objects, operations, and assumptions precisely.
3. Use small cases to discover errors, then prove the general statement from definitions.
4. Connect algorithms with invariants, initial conditions, and the mathematical reason they work.
5. Keep the complete textbook separate from the author’s activity-slide supplement when following chapter references.

Practice and review task

Create a small discrete-model portfolio: one counting argument, one relation classification, one recurrence, one graph model, and one algebraic example. For each, include a test case and a proof or justification appropriate to the claim.

Questions for reflection

Why can a successful computational test fail to prove a general statement? What changes when an algebraic operation is defined on a different underlying set?

Sources and coverage

This original study guide follows Complete author-hosted textbook PDF dated July 16, 2026. It draws on the source contents, chapter introductions, selected explanations and examples, and review material. It condenses the resource rather than replacing the full text; study applications are original exercises. The complete PDF was located from the authors’ official site. The previous PDF link led to the separate 128-page active-learning slide collection. The catalog cover identifies an earlier printing of the same textbook.

Reviewed source text; Book and cover catalog record.