Editing Binary decision diagram (section)

=== Example ===
The left figure below shows a binary [[decision tree|decision ''tree'']] (the reduction rules are not applied), and a [[truth table]], each representing the function <math>f(x_1, x_2, x_3)</math>. In the tree on the left, the value of the function can be determined for a given variable assignment by following a path down the graph to a terminal. In the figures below, dotted lines represent edges to a low child, while solid lines represent edges to a high child. Therefore, to find <math>f(0, 1, 1)</math>, begin at x<sub>1</sub>, traverse down the dotted line to x<sub>2</sub> (since x<sub>1</sub> has an assignment to 0), then down two solid lines (since x<sub>2</sub> and x<sub>3</sub> each have an assignment to one). This leads to the terminal 1, which is the value of <math>f(0, 1, 1)</math>.

The binary decision ''tree'' of the left figure can be transformed into a binary decision ''diagram'' by maximally reducing it according to the two reduction rules. The resulting '''BDD''' is shown in the right figure.

{| align="center"
|-
| [[File:BDD.png|thumb|546px|Binary decision tree and [[truth table]] for the function <math>f(x_1, x_2, x_3)=(\neg x_1 \wedge \neg x_2 \wedge \neg x_3) \vee (x_1 \wedge x_2) \vee (x_2 \wedge x_3)</math>, described in notation for [[Boolean algebra#Basic operations|Boolean operators]].]]
| [[File:BDD simple.svg|thumb|189px|BDD for the function ''f'']]
|}

Another notation for writing this Boolean function is <math>\overline{x}_1 \overline{x}_2 \overline{x}_3 + x_1 x_2 + x_2 x_3</math>.