DNF ex.4 ws17

Question

Hello,

I don't understand why the DNF of the function is (!a & !b)|(a & b)|(!a&c). I get (!a & !b)|(!a & b & c)|(a & b), I do it the same way as I do for CNF. Why is the b omitted, what am I doing wrong?

Answer 1

I think both is correct, note the the DNF is not a canonical normal form without further restrictions. You can verify the following equivalences:

• ((a->b) ∧ (c∨a∨¬b)) <-> (¬a∧¬b ∨ a∧b ∨ ¬a∧c)
• ((a->b) ∧ (c∨a∨¬b)) <-> (¬a∧¬b ∨ ¬a∧b∧c ∨ a∧b)

It is a matter of logic minimization. The function has even two minimal DNFs which are

• !a&!b|a&b|b&c
• !a&!b|a&b|!a&c

Comments

So if I write it that way on the exam, it would still be acceptable and correct?

---

Sure! The task was to compute a DNF and a CNF and every one that is equivalent to the given formula is a correct solution. The example solution already lists four versions for the DNF and two for the CNF.

---

Thanks! What about ex. 6 where minimization is needed?

---

There is it different, of course, since you have to determine a minimal DNF or CNF. Still, there might be different solutions and anyone of the minimal DNFs or CNFs would be correct. Other non-minimal DNFs/CNFs would however not be accepted.