Write $(p↔q)$ in DNF 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?
 A: 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.
A: 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).
