Further Reading: Partial Orders, Lattices, and Boolean Algebra

Annotated pointers for going deeper. Start with the textbook sections that re-cover this chapter at a different pace, then branch toward whichever thread pulls you — order theory, topological sort and DAGs, or Boolean algebra and its hardware payoff.

Core textbook treatments

Rosen, Discrete Mathematics and Its Applications (8th ed.), §9.6 and Chapter 12 The market-standard treatment. §9.6 covers partial orders, Hasse diagrams, lattices, and topological sort with a large graded exercise bank; Chapter 12 ("Boolean Algebra") covers Boolean functions, the laws, and logic gates — including Karnaugh maps and Quine–McCluskey minimization, the next step beyond the §13.6 simplifier. The single best companion for more drill on this exact material.

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042), the "Partial Orders and Equivalence Relations" chapter Freely available. The most CS-flavored presentation: partial orders are developed alongside DAGs, scheduling, and the "parallel time = longest chain" idea that drove Case Study 1, with the same algorithmic spirit as this chapter. Highly recommended for the topological-sort and chain/antichain material.

Levin, Discrete Mathematics: An Open Introduction (3rd ed.), the relations/order sections Freely available. A gentle, well-illustrated open textbook. Good if you want a second, slower pass over partial orders and Hasse diagrams before attempting the harder exercises here.

Epp, Discrete Mathematics with Applications (5th ed.), the partial-order and Boolean-algebra sections Careful, example-rich, and especially strong on the definitions (comparable vs. incomparable, maximal vs. greatest) that trip students up. A good reference if Exercise 13.18's maximal-vs-greatest distinction still feels slippery.

On topological sort, DAGs, and scheduling

Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms (4th ed.), §20.4 (topological sort) and §20.3 (DFS) The canonical algorithmic reference. §20.4 gives the depth-first-search topological sort that Chapter 28 of this book re-derives; reading it now shows the other standard algorithm (besides Kahn's) and proves its correctness. The critical-path material connects directly to Case Study 1.

Knuth, The Art of Computer Programming, Vol. 1 (3rd ed.), §2.2.3 Knuth's original, meticulous treatment of topological sorting (he calls it "topological ordering"), including the historical Kahn-style algorithm you implemented as topo_sort. Dense but definitive, and a nice glimpse of how foundational this little algorithm is.

On Boolean algebra and logic gates

Rosen, Discrete Mathematics and Its Applications (8th ed.), Chapter 12 (Boolean Algebra), §12.4 Beyond the laws, this section covers circuit minimization (Karnaugh maps and the Quine–McCluskey method) — the systematic, complete techniques that the hand-built simplifier in Case Study 2 only approximates. Read it if Case Study 2's "sound but not complete" gap bothered you; this is how real tools close it.

Lehman, Leighton & Meyer, Mathematics for Computer Science, the Boolean-algebra / propositional-logic material Freely available. Reinforces the §13.5 threshold concept that propositional logic, set algebra, and the two-element Boolean algebra are the same structure — the unifying idea the chapter built toward.

Deeper dives (optional)

Dilworth's and Mirsky's theorems — Rosen §9.6 supplementary exercises, or any combinatorics text The two duality theorems stated (not proved) in §13.2. Mirsky's theorem is the easier induction and underwrites the "layered schedule is optimal" claim in Case Study 1; Dilworth's is deeper and a classic of combinatorics. Worth proving Mirsky's yourself as a §13.2 capstone.

Order theory and lattices — Davey & Priestley, Introduction to Lattices and Order (2nd ed.) The standard graduate-friendly introduction to order theory, for readers who found lattices the most interesting part. It develops the lattice/Boolean-algebra connection rigorously and reaches results like "every finite Boolean algebra has size a power of two" (Exercise 13.33) in full. Far beyond what this chapter needs, but the right next book if order theory grabbed you.

Suggested order

  1. Re-read §§13.1–13.4 here, then do Rosen §9.6 exercises for drill on posets, Hasse diagrams, and lattices.
  2. Read the MIT 6.042 partial-orders chapter for the CS framing (scheduling, longest chain), alongside Case Study 1.
  3. Read CLRS §20.4 to see the DFS-based topological sort (the alternative to your Kahn's-algorithm topo_sort) — but save the deep DFS details for Chapter 28, which builds on them.
  4. Read Rosen Chapter 12 for Boolean algebra and circuit minimization, alongside Case Study 2; this is the natural sequel to §§13.5–13.6.
  5. Save Davey & Priestley for after the course, if order theory and lattices are a direction you want to pursue.