= Solution
Choose the <variable ordering of a binary decision diagram> $y<x<z$. The <Boolean cofactor> with $y=1$ is the constant one, while the <Boolean cofactor> with $y=0$ is $x\land z$. Consequently the right panel in part (d) has the following arrows:
$$
\boxed{y:\ (0\to x,\ 1\to1),\qquad
x:\ (0\to0,\ 1\to z),\qquad
z:\ (0\to0,\ 1\to1).}
$$
Here an entry such as $0\to x$ denotes the zero arrow to the $x$ <decision node>. There are $\boxed{3+2=5}$ <vertices>: three <decision nodes> and two <terminal nodes>, saving one <decision node> relative to either of the previous orderings. Testing $y$ first is effective because its one branch settles the entire <Boolean function> immediately. The ordering $y<z<x$ works equally well.
This is also minimal among ordinary <binary decision diagrams> for this <Boolean function>. Each <Boolean variable> is essential: setting $y=0,z=1$ leaves $f=x$; setting $y=0,x=1$ leaves $f=z$; and setting $x=z=0$ leaves $f=y$. If a <Boolean variable> were never tested, the represented <Boolean function> could not depend on it. Thus at least three <decision nodes> are necessary, and the construction attains that bound.
Back to article page
