Solving a Complex Logical Equivalence in CNF Form

[Yankel]

Hello all,

I am trying to bring this:

(p \iff q ) \implies r

into a CNF form. I have started with the logical equivalences:

(p \implies q) = \lnot p\lor q
(p \iff q) = (p \land q)\lor (\lnot p \land \lnot q)

and then I have applied De Morgan's rules and the distribution rules, but unsuccessfully. I do know that every statement has a CNF. Can you please assist me with finding it?

Thank you in advance.

 

[Evgeny.Makarov]

and then I have applied De Morgan's rules and the distribution rules, but unsuccessfully.

Did your paper burst into flames? :D Sorry, I'll show myself out.

In working with big Boolean formulas I find the following notations useful: conjunction is dropped and $$\neg p$$ is written as $$\bar{p}$$. Note that
\[
\overline{p\leftrightarrow q}=\overline{pq\lor\bar{p}\bar{q}}=\overline{pq}\overline{\bar{p}\bar{q}}=(\bar{p}\lor\bar{q})(p\lor q)=p\bar{q}\lor\bar{p}q
\]
In the last equality I used distributivity and the facts that $p\bar{p}=0$ and $p\lor0=p$. For the future you may note that $p\bar{q}\lor\bar{p}q$ is called "exclusive OR" or XOR. It is the negation of $\leftrightarrow$ and is often denoted by $\oplus$. It is a very nice connective because together with $\land$ it behaves exactly as addition and multiplication modulo 2. Also, every function is represented using only $\oplus$, $\land$ and 1; this is called the algebraic normal form.

So,
\[
(p\leftrightarrow q)\to r=\overline{p\leftrightarrow q}\lor r=(\bar{p}\lor\bar{q})(p\lor q)\lor r=(\bar{p}\lor\bar{q}\lor r)(p\lor q\lor r).
\]
The last equality uses distributivity of $\lor$ over $\land$: $pq\lor r=(p\lor r)(q\lor r)$.

 

[Yankel]

Thank you.

I managed to do the first part of your calculation. The problem remains in the second part.

You (and I) got that the negation of p \iff q is in DNF form. But when you went back and put the result together with \lor r, you put it differently. This is the part I miss here, can you please explain?

 

[Evgeny.Makarov]

But when you went back and put the result together with \lor r, you put it differently. This is the part I miss here, can you please explain?

I replaced $$\overline{p\leftrightarrow q}$$ with $$(\bar{p}\lor\bar{q})(p\lor q)$$, which is the second last expression in the first line of formulas in my previous post.