How to convert formula to disjunctive normal form?

53.9k Views Asked by At

Convert

$$((p \wedge q) → r) \wedge (¬(p \wedge q) → r)$$

to DNF.

This is what I've already done:

$$((p \wedge q) → r) \wedge (¬(p \wedge q) → r)$$

$$(¬(p \wedge q) \vee r) \wedge ((p \wedge q) \vee r)$$

$$((¬p \vee ¬q) \vee r) \wedge ((p \wedge q) \vee r)$$

And from this point I'm not sure how to proceed. Help would be appreciated.

Sorry, but the last line was written badly (I think). It's fixed now.

1

There are 1 best solutions below

4
On BEST ANSWER

You can continue by using Distributivity of the boolean algebra:

$((¬p \vee ¬q) \vee r) \wedge ((p \wedge q) \vee r)$

$ \Leftrightarrow (¬p \vee ¬q \vee r) \wedge ((p \wedge q) \vee r)$

Here we apply distributivity:

$ \Leftrightarrow (¬p \wedge p \wedge q) \vee (¬q \wedge p \wedge q) \vee (r \wedge p \wedge q) \vee (¬p \wedge r) \vee (¬q \wedge r) \vee (r \wedge r)$

Formally, this is in disjunctive normal form now. We could further simplify:

$ \Leftrightarrow (r \wedge p \wedge q) \vee (¬p \wedge r) \vee (¬q \wedge r) \vee r$