連言標準形
任意の論理式は等価な CNF に変換することができる。これを行うには、二重否定の除去、ド・モルガンの法則、分配法則といった論理的に等価な変換を使う。全ての論理式は CNF に変換できるため、証明に際して全ての論理式が CNF であることを前提とすることが多い。しかし、元の論理式によっては、CNF への変換によって論理式が極めて長大になることもある。例えば、論理式
( X 1 ∧ Y 1 ) ∨ ( X 2 ∧ Y 2 ) ∨ ⋯ ∨ ( X n ∧ Y n ) {\displaystyle (X_{1}\wedge Y_{1})\vee (X_{2}\wedge Y_{2})\vee \dots \vee (X_{n}\wedge Y_{n})}
を CNF に変換すると、 2 n {\displaystyle 2^{n}} 個の節を書き連ねることになる。実際、対応する CNF は
( X 1 ∨ X 2 ∨ ⋯ ∨ X n ) ∧ ( Y 1 ∨ X 2 ∨ ⋯ ∨ X n ) ∧ ( X 1 ∨ Y 2 ∨ ⋯ ∨ X n ) ∧ ( Y 1 ∨ Y 2 ∨ ⋯ ∨ X n ) ∧ ⋯ ∧ ( Y 1 ∨ Y 2 ∨ ⋯ ∨ Y n ) {\displaystyle (X_{1}\vee X_{2}\vee \cdots \vee X_{n})\wedge (Y_{1}\vee X_{2}\vee \cdots \vee X_{n})\wedge (X_{1}\vee Y_{2}\vee \cdots \vee X_{n})\wedge (Y_{1}\vee Y_{2}\vee \cdots \vee X_{n})\wedge \cdots \wedge (Y_{1}\vee Y_{2}\vee \cdots \vee Y_{n})}