We have two node for variable b, each of them having up to two co-factors. This yields these formulas:
(a | !a) is a tautology. We often abbreviate that as 1. Let's apply this abbreviation to the formulas above:
- (a | !a) = 1
- ((a | !a) ⊕ a) = 1 ⊕ a
- ( ( a|!a) ⊕ (a|!a)) = 1 ⊕ 1 = 0
- ( ( (a|!a) ⊕(a|!a)) ⊕ (a ⊕ (a|!a))) = ( ( 1 ⊕ 1) ⊕ (a ⊕ 1)) = 0 ⊕ (a ⊕ 1) = 1 ⊕ a
As the first, and third formula don't contain a (in the diagram, thee are just direct edges to the leaves), and the second, and fourth formula are equivalent, we have only one node labelled a that is supposed to represent 1 ⊕ a (also known as ¬a)
(I think so far you understood the context)
Davio-Decomposition of ¬a
The positive Davio decomposition (chapter 3, slide 117) for variable is defined as: (negative co-factor of x) ⊕ (x & (positive co-factor ⊕ negative cofactor)). A formula's positive (negative) co-factor with respect to a variable is the formula that yields after fixing the variable to 1 (0). In case of ¬a, the positive co-factor is 0, the negative one is 1. Hence, the Davio decomposition of ¬a is:
(negative co-factor of a) ⊕ (a & (positive co-factor ⊕ negative co-factor))
= 1 ⊕ (a & (0 ⊕ 1))
(The same as it is in the part of the solution you quoted.)
The term (0 ⊕ 1) is a tautology. One operand is fixed to 0, the other one to 1, hence, XOR is always satisfied. We could write 1 instead of the XOR-term. We get
1 ⊕ a & 1
It may seem a bit odd that we don't simplify a&1 to a. We avoid that as we want to keep the structure of the Davio-Decomposition. The negative co-factor (here, the left 1) is our low-child in the FDD, the XOR of the positive and negative co-factor (here, the right 1) is our high-child in the FDD.
Getting the final Davio-Decomposition
In the previous steps, we got many negative-co-factors, and derivations (that's how we call this negative co-factor XOR positive co-factor). We now have to plug them all in one formula. First, we had decomposed by c:
((a & b) | (a & !b) | (!a & !b) ) ⊕ c & (((a & b) | (a & !b) | (!a & !b) ) ⊕ (( a & b) | (a & !b) | (!a & b) | (!a & !b )))
The part to the first ⊕ was the negative co-factor (low-child), the part after c& is the derivative (high-child). We replace them by step 2.1, and 2.2:
((a | !a) ⊕ b & ((a | !a) ⊕ a)) ⊕ c & (( ( a|!a) ⊕ (a|!a)) ⊕ b & ( ( (a|!a) ⊕(a|!a)) ⊕ (a ⊕ (a|!a))))
Let's abbreviate that a little:
(1 ⊕ b & (1 ⊕ a)) ⊕ c & (( 1 ⊕ 1) ⊕ b & ( ( 1 ⊕ 1) ⊕ (a ⊕ 1)))
Since ( 1 ⊕ 1) = 0, and 0 ⊕ X = X, we can clean that up even more:
(1 ⊕ b & (1 ⊕ a)) ⊕ c & (0 ⊕ b & ( a ⊕ 1))
(Test yourself: Why did we keep specifically the first occurrence of 0? If you don't know the answer, re-read the end of the paragraph on the decomposition of ¬a)
Now, we just need to insert the Davio-Decomposition of a ⊕ 1, which is 1 ⊕ a & 1:
(1 ⊕ b & (1 ⊕ a & 1)) ⊕ c & (0 ⊕ b & ( 1 ⊕ a & 1))
Construct the FDD
You now know the Davio-Decomposition, and its ingredients (negative co-factor, and derivative i.e. negative XOR positive co-factor). Each FDD-node consists of the variable, a high-child pointing to the FDD for the derivative, and a low-child pointing to the FDD for the derivative negative co-factor. Use that, to construct the FDD. Also keep in mind, that FDDs omit nodes wth a high-child pointing to 0.
