Conjunctive Normal Form

logic

Definition

Conjunctive Normal Form

A formula is in conjunctive normal form (CNF) if it is a conjunction of disjunctions of literals. Thus, a formula of the form

$$(L_{1,1}\vee \cdots \vee L_{1,m})\wedge \cdots \wedge (L_{n,1}\vee \cdots \vee L_{n,m})$$

where each $L_{i,j}$ is a literal, is in conjunctive normal form.

Examples:

• $(\neg a\vee b)\wedge (a\vee \neg c\vee d)\wedge \neg b$
• $(\neg a\vee x\vee \neg c\vee d)\wedge (\neg b\vee \neg y)$

Transformation

Let $F$ be a propositional formula, and $A$ and $B$ be subformulas of$F$. Using known mutual entailment rewrite rules, we can rewrite $F$ to a CNF:

$$\begin{array}{rl}A\leftrightarrow B& \equiv (\neg A\vee B)\wedge (\neg B\vee A)\\ A\to B& \equiv \neg A\vee B\\ \neg (A\wedge B)& \equiv \neg A\vee \neg B\\ \neg (A\vee B)& \equiv \neg A\wedge \neg B\\ \neg \neg A& \equiv A\\ (A_1\wedge \cdots \wedge A_m)\vee B_1\vee \cdots \vee B_n& \equiv (A_1\vee B_1\vee \cdots \vee B_n)\wedge \cdots \wedge (A_m\vee B_1\vee \cdots \vee B_n)\end{array}$$

Example

$$\begin{array}{rl}F& =\neg ((p\to q)\wedge (p\wedge q\to r)\to (p\to r))\\ & \equiv \neg (\neg ((p\to q)\wedge (p\wedge q\to r))\vee (p\to r))\\ & \equiv \neg (\neg ((\neg p\vee q)\wedge (p\wedge q\to r))\vee (p\to r))\\ & \equiv \neg (\neg ((\neg p\vee q)\wedge (\neg (p\wedge q)\vee r))\vee (p\to r))\\ & \equiv \neg (\neg ((\neg p\vee q)\wedge (\neg (p\wedge q)\vee r))\vee (\neg p\vee r))\\ & \equiv \neg (\neg ((\neg p\vee q)\wedge (\neg p\vee \neg q\vee r))\vee (\neg p\vee r))\\ & \equiv \neg \neg ((\neg p\vee q)\wedge (\neg p\vee \neg q\vee r))\wedge \neg (\neg p\vee r)\\ & \equiv ((\neg p\vee q)\wedge (\neg p\vee \neg q\vee r))\wedge \neg (\neg p\vee r)\\ & \equiv ((\neg p\vee q)\wedge (\neg p\vee \neg q\vee r))\wedge (p\wedge \neg r)\\ & \equiv (\neg p\vee q)\wedge (\neg p\vee \neg q\vee r)\wedge p\wedge \neg r\end{array}$$

Exponential Blow-up

There are formulas that get exponential in size when transforming them into CNF. Formulas, whose shortest CNF has an exponential size.

Example

$$p_1\leftrightarrow (p_2\leftrightarrow (p_3\leftrightarrow (p_4\leftrightarrow (p_5\leftrightarrow p_6))))$$

This can be addressed by naming.