# How to convert formula to disjunctive normal form?

Formula is: $((p \wedge q) → r) \wedge (¬(p \wedge q) → r)$

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.

-
It's really great you got as far as you did; thanks for showing what you've done. – amWhy Nov 4 '12 at 17:10

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$

-
Sorry for asking, but how did you use distributivity law to get the third line? All I can think of is to use this identity: a∧(b∨c)=(a∧b)∨(a∧c) to get this: ((¬p∨¬q∨r)∧(p∧q))∨((¬p∨¬q∨r)∧r) – user1242967 Nov 6 '12 at 18:39
Here you use: (a∨b∨c)∧(d∨e)=(a∧d)∨(b∧d)∨(c∧d)∨(a∧e)∨(b∧e)∨(c∧e) – user48415 Nov 6 '12 at 18:59
The above can be seen as follows: (a∨b∨c)∧(d∨e) = ((a∨b∨c)∧d) ∨ ((a∨b∨c)∧e) = (a∧d)∨(b∧d)∨(c∧d)∨(a∧e)∨(b∧e)∨(c∧e) – user48415 Nov 6 '12 at 19:06

((p∧q)\to r)∧(¬(p∧q)\to r) ⇔(¬(p∧q)∨r)∧((p∧q)∨r) using distributive law: ⇔r∨(¬(p∧q)∧(p∧q)) ⇔r∨F (because s∧¬s equals false)

-