結合標準形の条件を書く

Question

結合標準形（CNF）は、命題式の標準化された表記法であり、すべての式を論理和の論理積として記述するよう指示します。すべてのブール式をCNFに変換できます。ですから、例えば：

(A | B) & (A | C)

はCNFに条件文を書くためのプログラミングにおけるベストプラクティスです：

A | (B & C)

は、このようなCNFで表現していますか？

Answer 1

いいえ、これはお勧めできません。 Conjunctive normal formは、主に理論上のコンピュータサイエンスで使用されます。 CNFで数式を解くアルゴリズムと、時間の複雑さとNP硬度についての証明があります。

実用的な観点からは、ロジックを最も自然に表すブール演算子を使用してコードを記述する必要があります。これは、入れ子式、XOR、否定などの演算子を最大限に活用することを意味します。あなたが例示したように、表現がより長く、しばしば部分表現を繰り返すので、CNFはしばしば「自然さ」のこの目標と矛盾します。理論的な注意点として

は、最悪の場合、N演算子を含む無制限のブール式は、その長さNに指数関数的であるCNF式に変換することができます。だからCNFは潜在的に非常に大量に式を爆破する可能性があります。この動作を説明する一連の例：

• （A & B） （A | C）&（A | D）&（B | C）&（B | D）である。
• （A & B）| （C & D）| （E & F）==
  （A | C | E）&（A | C | F）&（A | D | E）&（A | D | F）&（B | C | E）&（ B | D | E）&（B | D | F）
• （A & B）| （C & D）| （E &F）| （G & H）==
  （A | C | E | G）&（A | C | E | H）&（A | C | F | G）&（A | C | F | H）&（ D | E | G）&（A | D | E | H）&（A | D | F | G）&（A | D | F | H）&（B | C | E | G）& D | E | H）&（B | C | F | H）&（B | C | F | G）&（B | C | F | H）& B | D | F | G）&（B | D | F | H）