Conjunctive Normal Form

definitionlogic

Definition

A formula is in conjunctive normal form (CNF) if and only if it has the form,

$$({\ell }_{0,0}\vee {\ell }_{0,1}\vee \dots \vee {\ell }_{0,i_0})\wedge ({\ell }_{1,0}\vee \dots \vee {\ell }_{1,i_1})\wedge \dots \wedge ({\ell }_{k,0}\vee \dots \vee {\ell }_{k,i_k}).$$

Where each ${\ell }_{a,b}$ is a literal.

Examples