Editing Conjunctive normal form (section)

==First-order logic==
In first order logic, conjunctive normal form can be taken further to yield the clausal normal form of a logical formula, which can be then used to perform [[Resolution (logic)#Resolution in first-order logic|first-order resolution]].
In resolution-based automated theorem-proving, a CNF formula 
{| 
|-
||
|| <math>(</math>
|| <math>l_{11}</math>
|| <math>\lor</math>
|| <math>\ldots</math>
|| <math>\lor</math>
|| <math>l_{1n_1}</math>
|| <math>)</math>
|| <math>\land</math>
|| <math>\ldots</math>
|| <math>\land</math>
|| <math>(</math>
|| <math>l_{m1}</math>
|| <math>\lor</math>
|| <math>\ldots</math>
|| <math>\lor</math>
|| <math>l_{mn_m}</math>
|| <math>)</math>
||
|| ,{{refn|<math>1 \le m \le</math> [[Conjunctive normal form#max disjunctions|maximum number of disjunctions]]<br/><math>1 \le in_i \le</math> [[Conjunctive normal form#max disjunctions|maximum number of literals]]}} is commonly represented as a set of sets
|-
|| <math>\{</math>
|| <math>\{</math>
|| <math>l_{11}</math>
|| <math>,</math>
|| <math>\ldots</math>
|| <math>,</math>
|| <math>l_{1n_1}</math>
|| <math>\}</math>
|| <math>,</math>
|| <math>\ldots</math>
|| <math>,</math>
|| <math>\{</math>
|| <math>l_{m1}</math>
|| <math>,</math>
|| <math>\ldots</math>
|| <math>,</math>
|| <math>l_{mn_m}</math>
|| <math>\}</math>
|| <math>\}</math>
|| .
|}
See below for an example.

===Converting from first-order logic===
To convert [[first-order logic]] to CNF:{{sfn|Russel|Norvig|2010|pages=345-347|loc=9.5.1 Conjunctive normal form for first-order logic}}
#Convert to [[negation normal form]].
## Eliminate implications and equivalences: repeatedly replace <math>P \rightarrow Q</math> with <math>\lnot P \lor Q</math>; replace <math>P \leftrightarrow Q</math> with <math>(P \lor \lnot Q) \land (\lnot P \lor Q)</math>. Eventually, this will eliminate all occurrences of <math>\rightarrow</math> and <math>\leftrightarrow</math>.
##Move NOTs inwards by repeatedly applying [[De Morgan's Law|De Morgan's law]]. Specifically, replace <math>\lnot (P \lor Q)</math> with <math>(\lnot P) \land (\lnot Q)</math>; replace <math>\lnot (P \land Q)</math> with <math>(\lnot P) \lor (\lnot Q)</math>; and replace <math>\lnot\lnot P</math> with <math>P</math>; replace <math>\lnot (\forall x P(x))</math> with <math>\exists x \lnot P(x)</math>; <math>\lnot (\exists x P(x))</math> with <math>\forall x \lnot P(x)</math>. After that, a <math>\lnot</math> may occur only immediately before a predicate symbol.
#Standardize variables
##For sentences like <math>(\forall x P(x)) \lor (\exists x Q(x))</math> which use the same variable name twice, change the name of one of the variables. This avoids confusion later when dropping quantifiers. For example, <math>\forall x [\exists y \mathrm{Animal}(y) \land \lnot \mathrm{Loves}(x, y)] \lor [\exists y \mathrm{Loves}(y, x)]</math> is renamed to <math>\forall x [\exists y \mathrm{Animal}(y) \land \lnot \mathrm{Loves}(x, y)] \lor [\exists z \mathrm{Loves}(z,x)]</math>.
#[[Skolem normal form|Skolemize]] the statement
##Move quantifiers outwards: repeatedly replace <math>P \land (\forall x Q(x))</math> with <math>\forall x (P \land Q(x))</math>; replace <math>P \lor (\forall x Q(x))</math> with <math>\forall x (P \lor Q(x))</math>; replace <math>P \land (\exists x Q(x))</math> with <math>\exists x (P \land Q(x))</math>; replace <math>P \lor (\exists x Q(x))</math> with <math>\exists x (P \lor Q(x))</math>. These replacements preserve equivalence, since the previous variable standardization step ensured that <math>x</math> doesn't occur in <math>P</math>. After these replacements, a quantifier may occur only in the initial prefix of the formula, but never inside a <math>\lnot</math>, <math>\land</math>, or <math>\lor</math>. 
##Repeatedly replace <math>\forall x_1 \ldots \forall x_n \; \exists y \; P(y)</math> with <math>\forall x_1 \ldots \forall x_n \; P(f(x_1,\ldots,x_n))</math>, where <math>f</math> is a new <math>n</math>-ary function symbol, a so-called "[[Skolem normal form|Skolem function]]". This is the only step that preserves only satisfiability rather than equivalence. It eliminates all existential quantifiers.
#Drop all universal quantifiers.
#Distribute ORs inwards over ANDs: repeatedly replace <math>P \lor (Q \land R)</math> with <math>(P \lor Q) \land (P \lor R)</math>.

'''Example'''

As an example, the formula saying ''"Anyone who loves all animals, is in turn loved by someone"'' is converted into CNF (and subsequently into [[clause (logic)|clause]] form in the last line) as follows (highlighting replacement rule [[redex]]es in <math>{\color{red}{\text{red}}}</math>):

{|
|-
||<math>\forall x</math>
||
||
||
||<math>(</math>
||<math>\forall y</math>
||
||
||
||
||<math>\mathrm{Animal}(</math>
||<math>y</math>
||<math>)</math>
||<math>\color{red}\rightarrow</math>
||
||<math>\mathrm{Loves}(x,</math>
||<math>y</math>
||<math>)</math>
||
||<math>)</math>
||<math>\rightarrow</math>
||<math>(</math>
||<math>\exists</math>
||<math>y</math>
||<math>\mathrm{Loves}(</math>
||<math>y</math>
||<math>,x)</math>
||<math>)</math>
||
||
||
||
||
||
||
||
||

|-
||<math>\forall x</math>
||
||
||
||<math>(</math>
||<math>\forall y</math>
||
||
||
||<math>\lnot</math>
||<math>\mathrm{Animal}(</math>
||<math>y</math>
||<math>)</math>
||<math>\lor</math>
||
||<math>\mathrm{Loves}(x,</math>
||<math>y</math>
||<math>)</math>
||
||<math>)</math>
||<math>\color{red}\rightarrow</math>
||<math>(</math>
||<math>\exists</math>
||<math>y</math>
||<math>\mathrm{Loves}(</math>
||<math>y</math>
||<math>,x)</math>
||<math>)</math>
||
||
||
||
||
||
||
||
||by 1.1

|-
||<math>\forall x</math>
||<math>\color{red}\lnot</math>
||
||
||<math>(</math>
||<math>{\color{red}{\forall y}}</math>
||
||
||
||<math>\lnot</math>
||<math>\mathrm{Animal}(</math>
||<math>y</math>
||<math>)</math>
||<math>\lor</math>
||
||<math>\mathrm{Loves}(x,</math>
||<math>y</math>
||<math>)</math>
||
||<math>)</math>
||<math>\lor</math>
||<math>(</math>
||<math>\exists</math>
||<math>y</math>
||<math>\mathrm{Loves}(</math>
||<math>y</math>
||<math>,x)</math>
||<math>)</math>
||
||
||
||
||
||
||
||
||by 1.1

|-
||<math>\forall x</math>
||
||
||
||<math>(</math>
||<math>\exists y</math>
||<math>\color{red}\lnot</math>
||<math>(</math>
||
||<math>\lnot</math>
||<math>\mathrm{Animal}(</math>
||<math>y</math>
||<math>)</math>
||<math>\color{red}\lor</math>
||
||<math>\mathrm{Loves}(x,</math>
||<math>y</math>
||<math>)</math>
||<math>)</math>
||<math>)</math>
||<math>\lor</math>
||<math>(</math>
||<math>\exists</math>
||<math>y</math>
||<math>\mathrm{Loves}(</math>
||<math>y</math>
||<math>,x)</math>
||<math>)</math>
||
||
||
||
||
||
||
||
||by 1.2

|-
||<math>\forall x</math>
||
||
||
||<math>(</math>
||<math>\exists y</math>
||
||
||<math>\color{red}\lnot</math>
||<math>\color{red}\lnot</math>
||<math>\mathrm{Animal}(</math>
||<math>y</math>
||<math>)</math>
||<math>\land</math>
||<math>\lnot</math>
||<math>\mathrm{Loves}(x,</math>
||<math>y</math>
||<math>)</math>
||
||<math>)</math>
||<math>\lor</math>
||<math>(</math>
||<math>\exists</math>
||<math>y</math>
||<math>\mathrm{Loves}(</math>
||<math>y</math>
||<math>,x)</math>
||<math>)</math>
||
||
||
||
||
||
||
||
||by 1.2

|-
||<math>\forall x</math>
||
||
||
||<math>(</math>
||<math>{\color{red}{\exists y}}</math>
||
||
||
||
||<math>\mathrm{Animal}(</math>
||<math>y</math>
||<math>)</math>
||<math>\land</math>
||<math>\lnot</math>
||<math>\mathrm{Loves}(x,</math>
||<math>y</math>
||<math>)</math>
||
||<math>)</math>
||<math>\lor</math>
||<math>(</math>
||<math>\color{red}\exists</math>
||<math>\color{red}y</math>
||<math>\mathrm{Loves}(</math>
||<math>y</math>
||<math>,x)</math>
||<math>)</math>
||
||
||
||
||
||
||
||
||by 1.2

|-
||<math>\forall x</math>
||
||
||
||<math>(</math>
||<math>\exists y</math>
||
||
||
||
||<math>\mathrm{Animal}(</math>
||<math>y</math>
||<math>)</math>
||<math>\land</math>
||<math>\lnot</math>
||<math>\mathrm{Loves}(x,</math>
||<math>y</math>
||<math>)</math>
||
||<math>)</math>
||<math>\color{red}\lor</math>
||<math>(</math>
||<math>\color{red}\exists</math>
||<math>\color{red}z</math>
||<math>\mathrm{Loves}(</math>
||<math>z</math>
||<math>,x)</math>
||<math>)</math>
||
||
||
||
||
||
||
||
||by 2

|-
||<math>\forall x</math>
||<math>\exists z</math>
||
||
||<math>(</math>
||<math>{\color{red}{\exists y}}</math>
||
||
||
||
||<math>\mathrm{Animal}(</math>
||<math>y</math>
||<math>)</math>
||<math>\land</math>
||<math>\lnot</math>
||<math>\mathrm{Loves}(x,</math>
||<math>y</math>
||<math>)</math>
||
||<math>)</math>
||<math>\color{red}\lor</math>
||
||
||
||<math>\mathrm{Loves}(</math>
||<math>z</math>
||<math>,x)</math>
||
||
||
||
||
||
||
||
||
||by 3.1

|-
||<math>\forall x</math>
||<math>{\color{red}{\exists z}}</math>
||
||
||
||<math>\exists y</math>
||
||<math>(</math>
||
||
||<math>\mathrm{Animal}(</math>
||<math>y</math>
||<math>)</math>
||<math>\land</math>
||<math>\lnot</math>
||<math>\mathrm{Loves}(x,</math>
||<math>y</math>
||<math>)</math>
||<math>)</math>
||
||<math>\lor</math>
||
||
||
||<math>\mathrm{Loves}(</math>
||<math>z</math>
||<math>,x)</math>
||
||
||
||
||
||
||
||
||
||by 3.1

|-
||<math>\forall x</math>
||
||
||
||
||<math>{\color{red}{\exists y}}</math>
||
||<math>(</math>
||
||
||<math>\mathrm{Animal}(</math>
||<math>y</math>
||<math>)</math>
||<math>\land</math>
||<math>\lnot</math>
||<math>\mathrm{Loves}(x,</math>
||<math>y</math>
||<math>)</math>
||<math>)</math>
||
||<math>\lor</math>
||
||
||
||<math>\mathrm{Loves}(</math>
||<math>g(x)</math>
||<math>,x)</math>
||
||
||
||
||
||
||
||
||
||by 3.2

|-
||
||
||
||
||
||
||
||<math>(</math>
||
||
||<math>\mathrm{Animal}(</math>
||<math>f(x)</math>
||<math>)</math>
||<math>\color{red}\land</math>
||<math>\lnot</math>
||<math>\mathrm{Loves}(x,</math>
||<math>f(x)</math>
||<math>)</math>
||<math>)</math>
||
||<math>\color{red}\lor</math>
||
||
||
||<math>\mathrm{Loves}(</math>
||<math>g(x)</math>
||<math>,x)</math>
||
||
||
||
||
||
||
||
||
||by 4

|-
||
||
||
||<math>(</math>
||
||
||
||
||
||
||<math>\mathrm{Animal}(</math>
||<math>f(x)</math>
||<math>)</math>
||
||
||
||
||
||
||
||<math>\color{red}\lor</math>
||
||
||
||<math>\mathrm{Loves}(</math>
||<math>g(x)</math>
||<math>,x)</math>
||
||<math>)</math>
||<math>\color{red}\land</math>
||<math>(</math>
||<math>\lnot \mathrm{Loves}(x,f(x))</math>
||<math>\color{red}\lor</math>
||<math>\mathrm{Loves}(g(x),x)</math>
||<math>)</math>
||
||by 5

|-
||
||
||<math>\{</math>
||<math>\{</math>
||
||
||
||
||
||
||<math>\mathrm{Animal}(</math>
||<math>f(x)</math>
||<math>)</math>
||
||
||
||
||
||
||
||<math>,</math>
||
||
||
||<math>\mathrm{Loves}(</math>
||<math>g(x)</math>
||<math>,x)</math>
||
||<math>\}</math>
||<math>,</math>
||<math>\{</math>
||<math>\lnot \mathrm{Loves}(x,f(x))</math>
||<math>,</math>
||<math>\mathrm{Loves}(g(x),x)</math>
||<math>\}</math>
||<math>\}</math>
||([[clause (logic)|clause]] representation)

|}

Informally, the Skolem function <math>g(x)</math> can be thought of as yielding the person by whom <math>x</math> is loved, while <math>f(x)</math> yields the animal (if any) that <math>x</math> doesn't love. The 3rd last line from below then reads as ''"<math>x</math> doesn't love the animal <math>f(x)</math>, or else <math>x</math> is loved by <math>g(x)</math>"''.

The 2nd last line from above, <math>(\mathrm{Animal}(f(x)) \lor \mathrm{Loves}(g(x), x)) \land (\lnot \mathrm{Loves}(x, f(x)) \lor \mathrm{Loves}(g(x), x))</math>, is the CNF.