連言標準形
となる。この式は 2 n {\displaystyle 2^{n}} 個の節があり、それぞれの節は各 i {\displaystyle i} について X i {\displaystyle X_{i}} または Y i {\displaystyle Y_{i}} を含んでいる。
等価性よりも充足可能性を満たすよう CNF に変換することで、論理式のサイズの指数関数的増加を招かない変換方式もある。このような変換方式でのサイズ増加は線形であることが保証されるが、新たな変数を導入する必要がある。たとえば、上の論理式は新たな変数 Z 1 , ... , Z n {\displaystyle Z_{1},\ldots ,Z_{n}} を導入することにより CNF
A ∧ ( B ∨ D ) ∧ ( B ∨ E ) . {\displaystyle A\wedge (B\vee D)\wedge (B\vee E).}
リテラル(英: literal)は、変項(命題)か変項の否定であり、否定演算子はこの形でのみ出現する。全ての変項(またはその否定)を含む論理式を標準項と呼び、特に全ての変項(またはその否定)の論理和の形式になっている項を最大項と呼ぶ。従って、最大項の論理積の形式になっている論理式は、CNF である。この形式は、真理値表で出力が「偽」となる行を最大項として取り出したものを論理積で繋いだものであり、その真理値表に対応する論理式となっている。つまり、真理値表で表されるものは全て連言標準形の論理式で表せ、組合せ回路も連言標準形で表せる。
連言標準形から節標準形を作ることができ、節標準形は導出に使われる。
計算複雑性理論における重要な問題の一種として、連言標準形の論理式を「真」にする各変項の真偽の組合せを問う問題がある。これを充足可能性問題(SAT)という。変項が3種類の 3-SAT はNP完全問題(3変項以上のSATは全てNP完全)だが、2-SAT は多項式時間で解く事が出来る。
連言標準形を論理式として見ると、充足可能性問題などの解法の一つとなる。左記の論理式の全ての充足解を求める手法として、二分決定グラフで表現し、これを圧縮することで実用的に解を導くことができる場合がある。二分決定グラフには幾つかの種類があるが、充足可能性問題や最適化問題の解法として実用的に取り扱う手法が知られている。
連言標準形では、1つ以上のリテラルの論理和を1つ以上含む論理積の形式となる。選言標準形(DNF)と同様、CNF における演算子は論理積、論理和、否定だけである。
以下の論理式は CNF の一種である。
A ∧ B {\displaystyle A\wedge B}
¬ A ∧ ( B ∨ C ) {\displaystyle \neg A\wedge (B\vee C)}
( A ∨ B ) ∧ ( ¬ B ∨ C ∨ ¬ D ) ∧ ( D ∨ ¬ E ) {\displaystyle (A\vee B)\wedge (\neg B\vee C\vee \neg D)\wedge (D\vee \neg E)}
( ¬ B ∨ C ) . {\displaystyle (\neg B\vee C).}
しかし、以下の論理式は CNF ではない。
¬ ( B ∨ C ) {\displaystyle \neg (B\vee C)}
( A ∧ B ) ∨ C {\displaystyle (A\wedge B)\vee C}
A ∧ ( B ∨ ( D ∧ E ) ) . {\displaystyle A\wedge (B\vee (D\wedge E)).}
上記の3つの論理式はそれぞれ下記の3つの連言標準形の論理式と等価である。
¬ B ∧ ¬ C {\displaystyle \neg B\wedge \neg C}
( A ∨ C ) ∧ ( B ∨ C ) {\displaystyle (A\vee C)\wedge (B\vee C)}