14
$\begingroup$

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.

  • 0
    It's really great you got as far as you did; thanks for showing what you've done.2012-11-04

2 Answers 2

11

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$

  • 0
    brother, how did you simplified further the last statement using disjunctive normal form2016-06-23
1

$((p \land q) \to r) \land (\neg(p \land q)\to r) \equiv (\neg(p \land q) \lor r) \land ((p \land q) \lor r)$

using the distributive law

$r \lor (\neg (p \land q) \land (p \land q)) \equiv r \lor \text{False} \equiv r$

because $s \land \neg s \equiv \text{False}$.