DNF to RMNF

Question

Hello,

Is it sufficient to write out formula A or do I need to reduce it to B?

Thank you,

Patrick

Answer 1

A formula in Reed Muller normal form consists of conjunctions of variables. These conjunctions are connected by xor. Hence, the first formula does not meet that syntactic requirement, the second one does.

My solution looks like this:

(c ∧ ¬b) ∨ (¬c ∧ a)

// note that there is no assignment that satisfies both (c ∧ ¬b) and (¬c ∧ a) at the same time, so ∨ and ⊕ make no difference here.

= (c ∧ ¬b) ⊕ (¬c ∧ a)

// now we express negation by ⊕ 1

= (c ∧ (1 ⊕ b)) ⊕ ((1 ⊕ c) ∧ a)

// now we multiply out

= c ⊕ b ∧ c ⊕ a ⊕ c ∧ a

Comments

how many points would I get for the the first formula?

---

Wild guess: Maybe a point or one and a half.

---

thank you! Is there an easy way to go from A to B?

---

Multiplying out. And replacing ∨ by ⊕ everywhere where never more than one clause can become true at the same time.

---

You mean replacing ∨ by ⊕, of course whenever the subformula of these operands can never be both true.

---

Holy guacamole. Yes, I did mean that. Excuse the typo! I fixed it.