Rewrite a 15-operator expression as the same function with at most 4 operators.
For a fixed variable order, every Boolean function has exactly one ROBDD, up to the names of its nodes. Two expressions that compute the same function therefore give the same diagram, however many operators each uses. Reading a diagram back gives an expression: a node on x with else child l and then child h computes x ? h : l.
x
l
h
x ? h : l
Take k = p & q & r | p & q & ~r | ~p & q & r, which uses 10 operators, under the order p q r.
k = p & q & r | p & q & ~r | ~p & q & r
p q r
With p = 1, the first two terms leave q & r | q & ~r, which is q, and the third term is 0. With p = 0, only the third term remains: q & r.
p = 1
q & r | q & ~r
q
p = 0
q & r
So the root on p has then child q and else child q & r, and k is p ? q : q & r, which uses 2 operators.
p
k
p ? q : q & r
Check one row: at p = 0, q = 1, r = 0, every term of the long form has a factor that is 0, so it is 0, and p ? q : q & r gives q & r, which is also 0.
p = 0, q = 1, r = 0
Given: order: a b c;
order: a b c;
The program g = a & b & c | a & ~b & c | a & ~b & ~c | ~a & b & c; defines a function of a, b and c with 15 operators. Its truth table is below.
g = a & b & c | a & ~b & c | a & ~b & ~c | ~a & b & c;
a
b
c
Write the same function with at most 4 operators. Its ROBDD is the same, whichever way you write it.
One definition, g = expression;, in the variables a, b and c. Each use of &, |, ^, ~ or the conditional p ? q : r counts as one operator; constants are free. For example, a function of other variables might read m = s & (t | ~u);, with 3 operators.
g = expression;
&
|
^
~
p ? q : r
m = s & (t | ~u);
g is the function the program above defines.
At most 4 operators. Each use of an operator counts once: a & b & c uses 2, ~a uses 1, c ? x : y uses 1; constants are free.
Watch the conditions: they count your operators as the constraint does, as you type.
Under the diagram, the truth table of your g appears: compare it row by row with the table in the task.
g
Where the tables differ on a row, evaluate your g by hand on that row to find the part that gives the wrong value.
Kata 2.3 of Binary Decision Diagrams with CUDD on formal.org. The site checks the answer when you press Check answer; sign in to keep your progress.