Write two functions with small BDDs whose AND has a large one.
The computed table lets Apply expand each pair of operand nodes at most once, so the result of f op g has at most |f| × |g| nodes, where |f| is the number of nodes of f. The bound allows a result larger than both operands together. As in Module 2, the result's size is the number of different functions that remain on each level.
f op g
|f| × |g|
|f|
f
Take k = p | r and m = q under the order p q r. With complement edges, k has 3 nodes, one on p, one on r and the terminal, and m has 2.
k = p | r
m = q
p q r
k
p
r
m
Count k & m level by level. Level p has the root. On level q, p = 0 leaves q & r and p = 1 leaves q: two different functions, so 2 nodes.
k & m
q
p = 0
q & r
p = 1
On level r, fixing p and q leaves r, 0 or 1: one node. With the terminal, k & m has 1 + 2 + 1 + 1 = 5 nodes.
The result has 5 nodes, more than either operand, and within the bound of 3 × 2 = 6.
Given: order: a b c d;
order: a b c d;
Write two functions f and g of a, b, c and d whose BDDs each have at most 3 nodes, while the BDD of f & g has at least 8 nodes. Sizes count nodes with complement edges, terminal included, under the order a b c d.
g
a
b
c
d
f & g
a b c d
Two definitions, one per line, each name = expression;: f and g, in the variables a, b, c and d, with any operator of the language. For example, two functions of other variables might read m = s & u; and n = ~t;.
name = expression;
m = s & u;
n = ~t;
f has at most 3 nodes.
g has at most 3 nodes.
f & g has at least 8 nodes.
With complement edges, under the order a b c d.
Watch the conditions: they show the node counts of f, g and f & g with complement edges under the order a b c d, as you type.
Count f & g level by level, as in the example: on each level, list the functions that remain once the variables above are fixed.
Kata 3.4 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.