Binary decision diagram (BDD)

A binary decision diagram is a compact, canonical way to represent a Boolean function as a branching graph: each node asks 'what is the value of variable x?' and sends you down a 0-branch or a 1-branch toward two terminal leaves, TRUE or FALSE. Picture a flowchart of yes/no questions collapsed so that identical sub-decisions are shared instead of repeated. Where a truth table for n variables needs 2ⁿ rows, a reduced ordered BDD can shrink that to a handful of nodes — turning functions with hundreds of inputs into something a computer can store and compare.

Its superpower is canonicity: once you fix a variable ordering and apply two reduction rules (merge identical subgraphs, skip nodes whose branches lead to the same place), every Boolean function has exactly ONE reduced ordered BDD. So two circuits are logically equivalent if and only if their BDDs are the identical graph — a one-line equivalence check that powered a generation of formal verification, combinational equivalence checking, and symbolic model checking. The catch: the variable ordering matters enormously, and some functions (notably multipliers) blow up to exponential size no matter the order.