# Transform formula to conjunctive normal form.

I need help with conjunctive normal form. Can you give me some tips?

I have following formula. I did the first few steps.

$$[(p \implies q) \land (r \implies q)] \implies [( \neg q \vee \neg q) \implies ( \neg p \vee \neg r)]$$

1. Step one - Deleting arrows by swap $\ p \implies q$ to $\ \neg (p \vee q)$

$$[ \neg(\neg(p \vee q) \land \neg(r \vee q)) ] \vee [ \neg(\neg q \vee \neg q)) \vee (\neg p \vee \neg r)]$$

1. Step two - Deleting double negations: $$[\neg((\neg p \land \neg q) \land (\neg r \land \neg q))] \vee [\neg ((q \land q) \vee \neg (p \land r))]$$

2. Step three - Using De Morgan's Laws, so now I have following formula: $$[(p \vee q) \land (\neg r \land \neg q)] \vee [(q∨¬q)∨(¬p∨¬r)]$$

At this moment I don't know what to do next. Can You help me?

• Step 2 is wrong : you can delete double negs only in case $\lnot \lnot p \equiv p$. For $¬(¬q∨¬q)$ you must have $(q∧q)$. – Mauro ALLEGRANZA Dec 2 '16 at 12:36
• You mentioned about $\ \neg (A ∨ B) = \neg A ∧ \neg B$ rule? For $\ ¬(¬q∨¬q)$ I have $\ (\neg \neg q ∧ \neg \neg q)$. Now I can delete double negs, yes? $\ (q ∧ q )$. But $\ (q ∧ q)$ is it same that $\ q$?? – Damian U Dec 2 '16 at 12:43
• Yes: $q \land q \equiv q$. – Mauro ALLEGRANZA Dec 2 '16 at 12:47
• Using SymPy, p, q, r = symbols('p q r'); Phi = ((p >> q) & (r >> q)) >> ((Not(q) & Not(q)) >> (Not(p) & Not(r))); print to_cnf(Phi) produces the formula in CNF And(Or(Not(p), Not(q), p, q), Or(Not(p), Not(q), q), Or(Not(p), Not(q), q, r), Or(Not(p), p, q, r), Or(Not(q), Not(r), p, q), Or(Not(q), Not(r), q), Or(Not(q), Not(r), q, r), Or(Not(r), p, q, r)). This formula can be greatly simplified, however. – Rodrigo de Azevedo Dec 2 '16 at 12:50
• Step 1 looks wrong: $p \implies q$ is equivalent to $(\lnot p)\lor q$, not to $\lnot(p \lor q)$. – chi Dec 2 '16 at 12:59

First, I would use $\rightarrow$ instead of $\implies$; $p \rightarrow q$ is a logic statement that may or may not be true, depending on the truth-values of $p$ and $q$, but $p \implies q$ is typically understood as a meta-logical statement that says that $p$ logically implies $q$ ... which it does not ... and hence that statement is definitely false.

$$[(p \rightarrow q) \land (r \rightarrow q)] \rightarrow [( \neg q \vee \neg q) \rightarrow ( \neg p \vee \neg r)]$$

As you said, we can rewrite any conditional $p \rightarrow q$, but note that the correct equivalence is that $p \rightarrow q \Leftrightarrow \neg p \vee q$, rather than $p \rightarrow q \Leftrightarrow \neg (p \vee q)$, which is what you had: the latter is not true!

OK, so let's use the correct equivalence, so we get:

$$\neg [(\neg p \vee q) \land (\neg r \vee q)] \vee [\neg ( \neg q \vee \neg q) \vee ( \neg p \vee \neg r)]$$

Now we can do some DeMorgan's:

$$\neg (\neg p \vee q) \vee \neg (\neg r \vee q) \vee (\neg \neg q \land \neg \neg q) \vee \neg p \vee \neg r$$

(note we can drop the square brackets, since everything is disjuncted together, and by associativity of disjunction, the order in which you disjunct things together doesn't matter. Likewise, we can drop the parentheses from the $( \neg p \vee \neg r)$ at the end)

Some more Demorgan's:

$$(\neg \neg p \land \neg q) \vee (\neg \neg r \land \neg q) \vee (\neg \neg q \land \neg \neg q) \vee \neg p \vee \neg r$$

And some Double Negations:

$$(p \land \neg q) \vee (r \land \neg q) \vee (q \land q) \vee \neg p \vee \neg r$$

Idempotence says that $p \land p \Leftrightarrow p$, so:

$$(p \land \neg q) \vee (r \land \neg q) \vee q \vee \neg p \vee \neg r$$

Reduction says that $p \vee (\neg p \land q) \Leftrightarrow p \vee q$, so:

$$p \vee r \vee q \vee \neg p \vee \neg r$$

$p \vee \neg p \Leftrightarrow \top$, so:

$$q \vee \top \vee \top$$

And finally, $p \vee \top \Leftrightarrow \top$, so we get:

$$\top$$

• I don't understand that "Reduction says that $\ p∧(¬p∨q)⇔p∧q$ ". Where did you use it? – Damian U Dec 2 '16 at 21:04
• I reduced the first term $(p \land \neg q)$ to $p$ given the third term $q$. I also reduced the second term $(r \land \neg q)$ to $r$ given the same third term $q$ – Bram28 Dec 2 '16 at 21:09
• Oh wait, I see your confusion! Remember the duality of $\land$ and $\vee$: whenever something works for $\land$, something analogous works for $\vee$. For example, we have $\neg(A \land B) \Leftrightarrow \neg A \vee \neg B$, but if we systematically switch the $\land$ and $\lor$, then that gives us $\neg(A \vee B) \Leftrightarrow \neg A \land \neg B$. The Duality Theorem says that this always works: you can systematically switch any operator with its dual and any equivalence will result in a new equivalence. So, given $p \land (\neg p \vee q)$, we also have $p \vee (\neg p \land q)$. – Bram28 Dec 2 '16 at 21:12
• But in this case $\ (p \land \neg q) \vee (r \land \neg q)$ I would use Distributive Rule. And this gives me $\ \neg q \land ( \neg p\vee r)$. – Damian U Dec 2 '16 at 21:22
• @DamianU Yes, you can do that as well. So then you get $(\neg q \land (p \vee r)) \vee q \vee \neg p \vee r$. But then you can do Reduction on that (so $(\neg q \land (p \vee r)) \vee q$ becomes $p \vee r$), and that means you get $p \vee r \vee q \vee \neg p \vee r$, so it will be the same again as what I get by doing Reduction immediately. – Bram28 Dec 2 '16 at 21:37