MHB Solving a Complex Logical Equivalence in CNF Form

AI Thread Summary
The discussion focuses on converting the logical expression (p ↔ q) → r into conjunctive normal form (CNF). Initial attempts using logical equivalences and De Morgan's rules were unsuccessful. A participant shared a useful transformation involving exclusive OR (XOR) and demonstrated how to express the negation of p ↔ q in terms of conjunctions and disjunctions. The final expression derived was (¬p ∨ ¬q ∨ r)(p ∨ q ∨ r), highlighting the application of distributive properties. The conversation emphasizes the complexity of translating logical statements into CNF while exploring various logical notations and transformations.
Yankel
Messages
390
Reaction score
0
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.
 
Physics news on Phys.org
Yankel said:
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)$.
 
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?
 
Yankel said:
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.
 
Back
Top