Regarding construction of Reed-Muller normal form from ZDD

Question

In the current exercise sheet 3, task 2 we have a given ZDD. For this I constructed the representation set and then tried to do the Reed-Muller Form. Going through the steps I thought I was right, but after checking it I wasn't.

Here my calculation step by step. Am I missing a point somewhere?

Answer 1

The steps taken are correct, but in the distributive law step there is a missing part:

(a&b&c) ⊕ (a&b&c) ⊕ (a&c) ⊕ (a&b&c) ⊕ (a&b) ⊕ (a&c) ⊕ a ⊕ (a&b&c) ⊕ (a&b) ⊕ (a&c) ⊕ (b&c) ⊕ a ⊕ b ⊕ c ⊕ 1.

From the last bracket ((a ⊕ 1) & (b ⊕ 1) & (c ⊕ 1)) you get (a&b&c) ⊕ (a&b) ⊕ (a&c) ⊕ (b&c) ⊕ a ⊕ b ⊕ c ⊕ 1

On the next step of deleting doubles entries, I think there is misunderstanding. If you have double entries that term will be deleted based on:

a ⊕ a = 0

0 ⊕ a = a

Based on the syntactic sugar above and if we rearrange the term a bit,  we will have:

(a&b&c) ⊕ (a&b&c) ⊕ (a&b&c) ⊕ (a&b&c) ⊕ (a&c) ⊕ (a&c) ⊕ (a&c) ⊕ (a&b) ⊕ (a&b) ⊕ (b&c) ⊕ a ⊕ a ⊕ b ⊕ c ⊕ 1

= 0 ⊕ (a&c) ⊕ 0 ⊕ (b&c) ⊕ 0 ⊕ b ⊕ c ⊕ 1 = (a&c) ⊕ (b&c) ⊕ b ⊕ c ⊕ 1.

Answer 2

This is beautifully written, and well documented! Great work!

There are two slight typos that I spot.

1. The line where you applied the distributive law, should end in xor 1, as the (a xor 1) & (b xor 1) & (c xor 1), also yields 1 & 1 & 1.
2. You wrote deleting double entries but you actually just reduced all multiply occurring entries to a single entry. This isn't how the semantics of xor work. xor tells us whether and odd number of operands is satisfied. For example, a xor b xor a. Here, having both variables true satisfies the formula. This isn't the case for a xor b. The reason is that deleting an odd number of occurrences changes their parity. Deleting (or adding, haha) an even number of occurrences doesn't change the semantics of the formula: a xor b xor a = b = a xor b xor a xor a xor b xor b xor a xor c xor c (it's funny cuz it's true). In your example: (a & b & c) occurs four times → delete, a&c three times → keep once, (a & b) twice → delete, a twice → delete, b&c once → keep, b once → keep, c once → keep