Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers

1.6k comments

543 users

+1 vote

Hello,

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

Thank you,

Patrick

in * TF "Emb. Sys. and Rob." by (220 points)

1 Answer

+1 vote

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
by (25.6k points)
edited by
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.

Related questions

0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
asked Aug 10, 2020 in * TF "Vis. and Sci. Comp." by Anshu (870 points)
+1 vote
2 answers
asked Apr 27, 2020 in * TF "Intelligent Systems" by RS (770 points)
0 votes
1 answer
Imprint | Privacy Policy
...