Write $(p↔q)$ in DNF

Question

I have the following formula:

$(p↔q)$

and I have to write in DNF (disjunctive normal form) This is where I got so far:

$(p↔q) = ((p→q)∧(q→p)) = ((¬p∨q)∧(¬q∨p))$

but here I got stuck. How can I write the last formula in DNF? Any ideas?

Answer 1

You can make use of Distributivity: \begin{align} (\neg p\vee q) \wedge (\neg q\vee p) & = ((\neg p \vee q)\wedge \neg q) \vee ((\neg p \vee q) \wedge p) \\ & = (\neg p \wedge \neg q) \vee (q\wedge \neg q) \vee (\neg p \wedge p) \vee (q\wedge p) \end{align} Of course, you can eliminate some of the terms in here, like $\neg p\wedge p=0$ and $\neg q\wedge q=0$ and using the fact that $0$ is an identity for $\vee$ to give $$(\neg p \wedge \neg q) \vee (q\wedge p)$$ For sanity check, we can let $p=q=1$ to see that we get $0\vee 1=1$, and when $p=q=0$ we get $1\vee 0=1$. Finally, if $p\neq q$, then both $\neg p \wedge \neg q$ and $q\wedge p$ are false, so we get $0$, as expected.

It's also worth noting that this same technique can be used to convert any formula in CNF to DNF, and vice-a-versa (but as above, the formula will get larger, if things don't cancel).

Answer 2

From the truth table

\begin{align} p && q && p \leftrightarrow q \\ 0 && 0 && 1\\ 0 && 1 && 0\\ 1 && 0 && 0\\ 1 && 1 && 1 \end{align}

pick those lines where the $p \leftrightarrow q$ is true and connect them with disjunctions:

$$(\neg p \wedge \neg q) \vee (p \wedge q) =:F $$

This is our DNF. We can verify

\begin{align} p && q && p \leftrightarrow q && (\neg p \wedge \neg q) && (p \wedge q) \\ 0 && 0 && 1 &&1 &&0\\ 0 && 1 && 1 &&0 &&0\\ 1 && 0 && 0 &&0 &&0\\ 1 && 1 && 1 &&0 &&1 \end{align}

So

\begin{align} p && q && p \leftrightarrow q && F \\ 0 && 0 && 1 &&1 \\ 0 && 1 && 0 &&0 \\ 1 && 0 && 0 &&0 \\ 1 && 1 && 1 &&1 \end{align}

You can always create a DNF from a formula that way.