I realized that many students are not friends with the Reed-Muller normal form, so maybe the hints given here can help to change this.
As a generalization of the Reed-Muller normal form, one can also consider so-called mixed-polarity Reed-Muller forms. In contrast to Reed-Muller normal forms, the mixed-polarity Reed-Muller forms allow us to use negative literals as the DNFs do.
Any DNF can be easily converted to such a mixed-polarity Reed-Muller form: If we can make sure that the cubes of the DNF do not overlap (i.e., do not share satisfying variable assignments), then we can safely replace their disjunctions by xor operators. In particular, this allows us to read a mixed-polarity Reed-Muller form directly from the truth tables (which is done as in case of DNFs), and also in Shannon decompositions, the disjunction can be made an xor.
Converting a mixed-polarity Reed-Muller form to a Reed-Muller normal form is simple: We just have to eliminate the negative literals which is done by applying the following valid equivalences:
- ¬φ = true⊕φ
- (α⊕β)∧γ = α∧γ ⊕ β∧γ
- φ⊕φ = false
Example: From a truth table, we may read the following DNF/mixed-polarity Reed-Muller form and translate it to Reed-Muller normal form:
- ¬x∧y∧z ∨ x∧¬y∧z ∨ x∧y∧¬z ∨ x∧y∧z
- = ¬x∧y∧z ⊕ x∧¬y∧z ⊕ x∧y∧¬z ⊕ x∧y∧z
- = (true⊕x)∧y∧z ⊕ x∧(true⊕y)∧z ⊕ x∧y∧(true⊕z) ⊕ x∧y∧z
- = true∧y∧z ⊕ x∧y∧z ⊕ x∧true∧z ⊕ x∧y∧z ⊕ x∧y∧true ⊕ x∧y∧z ⊕ x∧y∧z
- = y∧z ⊕ x∧y∧z ⊕ x∧z ⊕ x∧y∧z ⊕ x∧y ⊕ x∧y∧z ⊕ x∧y∧z
- = y∧z ⊕ x∧z ⊕ x∧y ⊕ (x∧y∧z ⊕ x∧y∧z) ⊕ (x∧y∧z ⊕ x∧y∧z)
- = y∧z ⊕ x∧z ⊕ x∧y
Of course, the same technique can be applied to DNFs read from BDDs as long as the cubes of the DNF do not overlap. If cubes should overlap, you have to change this. For example, you have to expand x∧y ∨ x∧z to x∧¬y∧z ∨ x∧y∧z ∨ x∧y∧¬z first.
I have updated the chapter on propositional logic by adding slides 26,28,75 that you may wish to read. At the same time, I want to emphasize that this is not required and does in particular not mean that this is an important point for the exam next week. It is just to let you know about this technique.
Try to apply that technique to the following formula x∧¬y ∨ ¬x∧z, what is its Reed-Muller normal form?
