The hallway light and the phone tree

Two everyday machines, both made of yes/no questions.

The hallway light on two switches: flip either switch and the light toggles, no matter what the other one is doing. State the rule as questions: "Is switch A up? Is switch B up?" — the light is on exactly when the answers differ. Four combinations, and no shortcut: you always need both answers. (Logicians call this two-question stubbornness exclusive or.)

The phone tree: "Press 1 for sales, 2 for support… is your issue billing? are you a business customer?" — a chain of questions ending in a verdict (which queue you land in). Same species as a doctor's diagnostic flowchart, an airport security checklist, a tax form's eligibility box: ask, branch, conclude.

Chapter one taught you the space these machines walk: $n$ yes/no questions span $2^n$ combinations. This chapter is about the walk itself — and about a fact almost nobody designing a phone tree notices: the same verdicts can cost wildly different trees, depending only on what you ask first.

A question that never mattered

Walk this little support tree. It routes correctly — every caller lands in the right queue. Walk it more than once, taking different answers, and try to catch what's wasteful about it before the next section names it.

Caught it? The VIP question's yes-branch and no-branch are identical futures: the same follow-up question leading to the same verdicts. Whatever the caller answers, nothing downstream differs. The question costs a node, an interaction, a maintenance burden — and decides nothing.

Two mechanical deletions clean up any such tree, and they are the entire technology of this chapter:

1. Merge rule: if two subtrees are identical — same questions, same structure, same verdicts — keep one and point both parents at it. (You met this move in the memory chapter as subterm sharing: name a future by what it is, and identical futures collapse. There, it saved space; here it will also expose waste.)
2. Skip rule: if a question's yes-arrow and no-arrow now lead to the same place, the question decides nothing — delete it and wire its parents straight through.

Run them until nothing changes. On the phone tree: the two "billing?" subtrees merge (rule 1), the VIP question's two arrows then point at the same node, so it vanishes (rule 2). Three questions become one. The tree — now a directed acyclic graph, since merged futures are shared — asks each caller exactly what their routing actually depends on: is it billing?

Order is destiny

The VIP question was pure waste. The subtler phenomenon — the one Bryant's "further restrictions on the ordering" points at — is that even among useful questions, the order you ask them in changes the diagram's size. Sometimes catastrophically.

Consider a rule set over three customers attributes: "route to the priority queue if (business AND contract) OR (NOT business AND trial)." Ask business? first, and each side needs only one more question: contract on one branch, trial on the other — five nodes. Ask contract? first, and both branches still need the business question, and one of them still needs trial: the business test gets duplicated. Same function, bigger diagram — and this toy penalty compounds: for some families of functions, the best order gives a diagram linear in the number of questions while a bad order forces one exponential in it. Not a slower algorithm — a bigger object.

The multiplication island from chapter one shows the stakes: the raw space is always $2^n$; the diagram is your compressed walk through it, and the order decides how compressible the walk is.

Commit before the reveal:

The canonicity theorem: equality becomes a glance

Now the payoff that turned a data structure into an industry. Fix a question order once and for all. Reduce until neither rule applies. Bryant's 1986 result: the outcome is unique — every way of writing the same Boolean function, however different the original rule text, lands on the identical diagram.

Sit with what that buys. Two firewall configs written by different teams in different years; a refactored eligibility rule and its gnarly ancestor; a compiler's output and its specification. Build both diagrams under one order (sharing subterms as you go, so identical futures are literally the same node in memory — the memory chapter's hash-consing, doing verification work now): if the two roots are the same node, the policies are the same policy, for all $2^n$ inputs, with no enumeration. If not, walking the first differing node hands you a concrete input on which they disagree — a counterexample, free of charge.

The check for "this question decides nothing" is the same glance: a node whose two children are the same node. The VIP question didn't need a code review to be caught; the structure confessed.

Now run the theorem on rules of your own. The evaluator below builds the reduced, ordered diagram of two Boolean rules under one shared variable order, counts the nodes, searches every order for the smallest diagram, and answers the canonical question — same policy? — exactly the way this chapter promised: equal diagrams prove equality on every assignment without enumerating them, and unequal ones hand you the disagreeing assignment for free. The sample pair is the refactoring scenario: prove the short rule really is the long one.

A representation owes two round trips

A canonical diagram is a representation of a Boolean function. Any representation boundary has two directions: encode a value into the representation, and decode the representation back into a value. “It round-trips” is incomplete until the direction is named.

For every value $v$, losslessness requires

$$decode(encode(v)) = v.$$

For every accepted representation $r$, canonicity requires

$$encode(decode(r)) = canonicalize(r).$$

The first law says encoding loses no meaning. The second says decoding and re-encoding chooses the one official spelling. If the decoder accepts redundant diagrams, the right side cannot always be the original bytes; it must be their reduced ordered form.

This distinction appears everywhere. Parsing and pretty-printing an abstract syntax tree should preserve the tree, while reprinting accepted source may normalize whitespace. Serializing a set should preserve its members, while reserialization should sort them into the canonical byte order. A BDD should evaluate to the same truth function, while reduction should erase all noncanonical branching.

The same diagram, three famous times

Hardware verification. Bryant's paper landed where $2^n$ hurt most: a 64-bit circuit has more input combinations than atoms in a teaspoon of iron, and BDDs made "does the silicon match the spec?" answerable by construction and comparison instead of simulation. Symbolic model checking — verifying protocol state spaces of $10^{20}$ states and beyond — was built directly on this representation, and BDD packages remain workhorses in electronic design automation.

Packet classification. A firewall ruleset is a Boolean function of packet fields. nftables compiles rule sets into decision structures rather than checking rules one by one, and access-control and routing engines industry-wide use BDD-family representations to deduplicate overlapping rules and answer "does any packet match rule 7 that rule 3 doesn't already handle?" — a question which is exactly a diagram comparison.

Config and policy analysis. "Are these two IAM policies equivalent?" "Which feature-flag combinations enable the broken path?" — chapter one framed these as regions of a Boolean space; the BDD is the data structure that makes the regions manipulable: intersect two policies, subtract one from another, test emptiness, count satisfying configurations — each an efficient graph operation on canonical diagrams.

Where the diagram runs out

• Some functions are big under every order. Multiplication is the famous offender: the middle bits of a binary multiplier have exponentially large BDDs regardless of variable order — no cleverness rescues them. Canonical never promised small.
• Finding the best order is itself hard. Optimal variable ordering is NP-hard; real packages use heuristics and dynamic reordering (sifting), which usually work and sometimes thrash. "Choose a good order" is honest advice, not an algorithm.
• Yes/no only. Fields with big domains must be encoded into bits first, and the encoding choice changes the diagram as much as the order does. Cousins in the diagram family (multi-terminal and zero-suppressed variants) trade away simplicity for domain fit.
• The modern rival. For one-shot "is it satisfiable?" questions, SAT solvers (a later chapter) usually beat building a whole canonical object. BDDs pay off when you'll reuse the structure — many queries, incremental edits, equivalence checks — not when you need one verdict once.

Lessons

• Any yes/no rule set is a tree of questions; merging identical futures and deleting decide-nothing questions squeezes it into a reduced DAG.
• Question order is destiny: it decides how much structure later questions must duplicate, from linear to exponential size for the very same function.
• Under a fixed order, the reduced diagram is canonical — policy equality becomes reference equality, and every inequality yields a concrete counterexample input.
• A representation owes two round trips: values survive decode-after-encode, and accepted spellings converge under encode-after-decode.
• The structure earns its keep under reuse (verification, packet classification, policy algebra); for one-shot satisfiability, other tools win.
• Canonical ≠ small: some functions are irreducibly large, and finding good orders is itself a hard problem.

Practice

The next structure starts with two sets

A canonical diagram classifies every Boolean assignment into accepted or rejected. Reverse the viewpoint: each accepted object carries a set of properties, and each property is shared by a set of objects. Ask which properties determine exactly which objects, then ask back which objects determine exactly which properties.

The two answers chase one another until both stop changing. The next chapter shows that categories can compute themselves from that mutual closure.

References

1. Bryant. “Graph-Based Algorithms for Boolean Function Manipulation.” IEEE Trans. Computers, 1986. — the epigraph's source: the reduction rules, canonicity proof, and the apply algorithm, all in readable 1986 prose
2. “Binary decision diagram.” — the reference overview, including the variable-ordering examples and the multiplier lower bound
3. Knuth. “The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms.” Addison-Wesley, 2011. — §7.1.4 is the deepest single treatment of BDDs in print — read when the appetite is serious
4. McMillan. “Symbolic Model Checking.” Kluwer, 1993. — how BDDs turned protocol verification from simulation into algebra — the 10^20-states story
5. “nftables wiki: main page.” netfilter.org. — packet classification as compiled decision structures, in the production system's own docs
6. Seshia & Bryant et al.. “Handbook of Model Checking, ch. 7: Binary Decision Diagrams.” Springer, 2018. — the modern survey — BDD variants, ordering heuristics, and the honest comparison with SAT
7. Andersen. “An Introduction to Binary Decision Diagrams.” Lecture notes, ITU Copenhagen, 1999. — the classic free lecture notes — the gentlest rigorous next step after this chapter