A graph-based technique for representing Boolean functions as directed acyclic graphs (binary decision diagrams, BDDs) together with reduction rules (merge isomorphic subgraphs and eliminate redundant tests) that can produce a canonical, reduced ordered BDD (ROBDD) for a fixed variable ordering, enabling efficient equivalence and satisfiability checks.

Principle

Represent the function as a decision graph and apply two core reduction rules: (1) merge isomorphic subgraphs (unique table/sharing) and (2) eliminate nodes whose children are identical; with a fixed variable order these reductions yield a canonical form for the Boolean function.

Demonstration

Given Boolean function f over variables x1 < x2 < x3, construct its full decision DAG then apply reduction: identical subgraphs are merged and nodes with identical low/high successors are removed, yielding a compact ROBDD that can be compared by pointer equality to test equivalence with another function under the same order.

Misapplication

Assuming BDD reduction always yields a compact representation independent of variable ordering — in fact poor variable orders can cause exponential blow-up; also misusing BDDs for functions naturally requiring different decomposition strategies (e.g., arithmetic carry chains) without considering alternative representations.

Consequence

When variable ordering is well-chosen, reduction produces a canonical form that permits polynomial-time equivalence testing and enables many symbolic Boolean operations to be implemented efficiently; it also underlies model checking and symbolic manipulation tools.

Reversal

Contrasted with CNF-SAT or explicit truth-table enumeration: those techniques enumerate assignments or clauses, while reduced BDDs provide a shared structural representation; reversing the approach suggests choosing enumeration-based algorithms when BDD size becomes intractable.

Boundary

Applies to Boolean functions and depends crucially on a fixed variable ordering; it does not avoid worst-case exponential size for some functions and is not directly a good representation for non-Boolean or high-arity arithmetic without decomposition.

Semantic Tension

Tension between OBDD (ordered, reduced) and other representations like FBDD (free BDDs), SDDs, or CNF encodings: trade-offs involve canonicity, variable-order sensitivity, and the class of functions each represents compactly.

Synthesis

BDD reduction converts a decision process for a Boolean function into a canonical shared graph by merging isomorphic subgraphs and removing redundancies under a fixed variable order; the resulting ROBDD, when small, supports efficient equivalence checking and symbolic operations.