# Constructing FDD from formula

+1 vote
Dear Prof. and Team,

I am hoping that this question is somehow related. Attached are the 2 images. How is it simplified with the xor's. Can you please help ?

These problems are somewhat related, but also different. The cited thread is about converting DNF to Reed-Muller normal form while the images ask for the construction of FDDs. FDDs and Reed-Muller normal forms are closely related, so having one helps a lot to get the other one. Still a bit work has to be done to do that.

The example solutions construct the FDDs by performing the Davio decomposition using the cofactors. That is not the worst you can do for such problems.

An alternative would be to work with the relationship between RMF and FDDs .Let's consider 2016-Feb-2e: The task is to construct a FDD for the formula x1⊕x2. This formula is already in Reed-Muller normal form, but still we have to generate the FDD. Having the Reed-Muller normal form helps, since we just have to sort the monomials into those having x2 and others:

x1⊕x2 = (x1)⊕x2⋀(1) = (0⊕x1⋀1)⊕x2⋀(1)

For the other problem, it helps a bit more, since we can first rewrite x1x2 to its Reed-Muller normal form from a DNF:

```x1➞x2 = ¬x1⋁x2 = ¬x1⋀¬x2 ⋁ x1⋀x2 ⋁ ¬x1⋀x2
= ¬x1⋀¬x2 ⊕ x1⋀x2 ⊕ ¬x1⋀x2
= (1⊕x1)⋀(1⊕x2) ⊕ x1⋀x2 ⊕ (1⊕x1)⋀x2
= 1 ⊕ x1 ⊕ x2 ⊕ x1⋀x2 ⊕ x1⋀x2 ⊕ x2 ⊕ x1⋀x2
= 1 ⊕ x1 ⊕ x1⋀x2
```

Again, from the above Reed-Muller normal form, we can get the FDD by sorting the monomials:

```= (1 ⊕ x1) ⊕ x2 ⋀ (x1)
= (1 ⊕ x1 ⋀ 1) ⊕ x2 ⋀ (0 ⊕ x1 ⋀ 1)
```

But as you see, that was more work than performing the Davio decomposition as given in the example solution. Still, you can solve these problems this way.

by (166k points)
selected by
Thanks Professor !

x1➞x2 = ¬x1⋁x2 = ¬x1⋀¬x2 ⋁ x1⋀x2 ⋁ ¬x1⋀x2

But how is this ¬x1⋁x2 written as ¬x1⋀¬x2 ⋁ x1⋀x2 ⋁ ¬x1⋀x2  ? I was thinking that it was the missing terms, but here there are 3 terms, so not comprehending.
In the DNF ¬x1⋁x2, we have two cubes ¬x1 and x2 that share a minterm (both can become true in one variable assignment). We therefore have to expand the cubes to other variables: ¬x1 is expanded to ¬x1⋀¬x2 ⋁ ¬x1⋀x2 and x2 is expanded to x1⋀x2 ⋁ ¬x1⋀x2. Putting these together, we only get three minterms, since ¬x1⋀x2 is shared by the two expansions.
Thanks Again ! :)