# How can I write a DNF to CNF form?

How can I have write (p∧q) ∨ (¬p ∧ ¬q), which is the equivalent for (p<->q), in conjunctive normal form (CNF)?

In general, am I allowed to do (p ∨ (¬p ∧ ¬q)) ∧ (q ∨ (¬p ∧ ¬q)) ??

• No, what you have is not CNF. If you have $(a \wedge b) \vee (c)$ then you can "distribute" as $(a\vee c) \wedge (b \vee c)$. In your case you have $(a\wedge b) \vee (c \wedge d)$ which then becomes $\big(a \vee (c\wedge d)\big) \wedge \big(b \vee (c \wedge d)\big)$, which then can become $\big((a \vee c) \wedge (a \vee d)\big) \wedge \big((b \vee c) \wedge (b \vee d)\big)$, from here we should be able to show that this is equivalent to $(a \vee c) \wedge (a \vee d) \wedge (b \vee c) \wedge (b \vee d)$ (I believe). Your's will simplify since you will get things like $p \vee \neg p$. Commented May 4, 2016 at 0:39
• So if I continue (p ∨ (¬p ∧ ¬q)) ∧ (q ∨ (¬p ∧ ¬q)) as ( (p ∨ ¬p) ∧ (p ∨ ¬q) ) ∧ ( (q ∨ ¬p) ∧ (q ∨ ¬q) ) then (p ∨ ¬p) ∧ (p ∨ ¬q) ∧ (q ∨ ¬p) ∧ (q ∨ ¬q) is the final form? Commented May 4, 2016 at 0:44
• And how does p∨¬p simplify? :D Commented May 4, 2016 at 0:45

In general, am I allowed to do $(p ∨ (¬p ∧ ¬q)) ∧ (q ∨ (¬p ∧ ¬q))$

Yes, we can.   That is an application of distribution.   Only we don't stop here: were not CNF yet.

We can do it again on the first factor: $((p ∨ ¬p) ∧ (p ∨ ¬q)) ∧ (q ∨ (¬p ∧ ¬q))$

But wait: there's a tautology: $(p∨\neg p)$, which can be absorbed (by conjunctive identity).

So we have: $(p∨\neg q)\wedge(q\vee(\neg p\wedge \neg q))$

Keep going until you have conjunctions of disjunctions of atomic propositions.

You are on the right track, just keep going:

\begin{align} (p\wedge q) \vee (\neg p \wedge \neg q) =&\ \big(p \vee (\neg p \wedge \neg q)\big) \wedge \big(q \vee (\neg p \wedge \neg q\big) \\ =&\ \big((p \vee \neg p) \wedge (p \vee \neg q)\big) \wedge \big((q \vee \neg p) \wedge (q \vee \neg q)\big) \\ =&\ (p \vee \neg p) \wedge (p \vee \neg q) \wedge (q \vee \neg p) \wedge (q \vee \neg q) \end{align}

If you are uneasy about that last step, taking away the parentheses, then I believe it can be shown to be true through the associative property of the $\wedge$ operator. That is $(a \wedge b) \wedge c \equiv a \wedge (b \wedge c)$.

However $\zeta \vee \neg \zeta$ is a tautology...every boolean value is either true or false, therefore $p \vee \neg p$ and $q \vee \neg q$ are trivially true and can be dropped out of the CNF form leaving only:

$$(p \vee \neg q) \wedge (\neg p \vee q)$$

This makes sense if you think about it. If $p$ is true then $\neg p$ is false, therefore, to be true $q$ must be true to satisfy this property. Thus $p \rightarrow q$. Also if $\neg p$ is true, then $\neg q$ must be true to satisfy the above, thus $\neg p \rightarrow \neg q$. Together, these are the double implication.

• Thank you a lot! Do you mind also checking this one? How can I simplify it? (the answer on wolframalpha is p ^ q ^ -r ) ¬((p∧q) -> (q ∧ r)) = ¬(¬(p∧q) ∨ (q ∧ r)) = ((p∧q) ∧ (¬q ∨ ¬r)) How should i continue? Commented May 4, 2016 at 19:02