CNF（合取標準形）とは何か：定義・変換・実務での応用と注意点

2025年12月12日 最終更新日時 : 2025年12月12日 エバープレイ編集部

概要：CNF（合取標準形）とは

CNF（Conjunctive Normal Form、合取標準形）はブール論理式の表現の一つで、複数の節（clause）を論理積（AND）で結んだ形を指します。各節はリテラル（変数またはその否定）の論理和（OR）で構成されます。コンピュータサイエンスやソフトウェア検証、SATソルバーでの問題定式化など、広範な分野で基本的かつ重要な役割を持ちます。

形式的定義と簡単な例

形式的には、CNFは次のように表されます。

  • 一つのCNF式は複数の節の論理積：C1 ∧ C2 ∧ ... ∧ Cn
  • 各節 Ci はリテラルの論理和： (l1 ∨ l2 ∨ ... ∨ lk)
  • リテラルは変数 x またはその否定 ¬x のいずれか

例： (x1 ∨ ¬x2 ∨ x3) ∧ (¬x1 ∨ x4) は CNF の典型的な式です。

CNF に変換する手順

任意のブール式は等価な CNF に変換可能ですが、直接分配則を適用すると式のサイズが爆発することがあります。一般的な変換手順は次の通りです。

  • 含意（→）や同値（↔）を基本演算（∧, ∨, ¬）に置き換える。
  • ド・モルガンの法則を用いて否定を変数の前に移動し、否定正規形（NNF）にする。
  • 分配法則（∨を∧に分配）を用いて CNF に変換する。ただしこの方法は指数的に膨らむ可能性がある。

実務的にはサイズ増加を抑えるために Tseitin 変換（導入命題を用いる線形サイズ変換）が広く使われます。Tseitin 変換では元の部分式ごとに新しい補助変数を導入し、各補助変数と部分式との同値性を節で表現します。これにより元式と同値ではなく充足不能性に関して等価な CNF を線形サイズで得られます（SAT 問題を扱う上では十分）。

代表的な特殊形：k-CNF、Horn、2-SAT

  • k-CNF：各節が高々 k 個のリテラルからなる CNF。特に 3-CNF は 3-SAT 問題の基礎。
  • Horn CNF：各節に含まれる正リテラルが高々 1 個の CNF。Horn SAT は線形時間で解ける。
  • 2-SAT：各節のリテラル数が最大 2 の場合、強連結成分を使うことで多項式時間（線形）で解ける。

CNF と SAT（充足可能性問題）

CNF は SAT ソルバーが扱う標準的な入力形式です。SAT（CNF-SAT）は、与えられた CNF 式を真にする変数の割り当てが存在するかを問う問題で、NP完全であることで知られます（特に 3-SAT）。しかし実務的な SAT ソルバーは高度に最適化され、現実の大規模問題を効率良く解けることが多いです。

SAT ソルバーの基本技術

主要なアルゴリズムや最適化技術は以下です。

  • DPLL：分割とバックトラックを行う古典的な探索法。単位伝播（unit propagation）を用いる。
  • CDCL（Conflict-Driven Clause Learning）：衝突解析で学習節（学習クローズ）を生成し、バックジャンプを行う。現在の主要ソルバーはこれを採用。
  • ウォッチリテラル：効率的な単位伝播を実現するデータ構造。
  • 前処理（簡約）・後処理：単位節削除、純リテラル除去、節の縮退除去、変数削除など。

CNF への実務的エンコーディング技法

多くの実世界問題は直接 CNF に落とすと効率が悪くなるため、様々なエンコーディング技法が使われます。

  • 基礎的なエンコーディング：論理表現をそのまま Tseitin で変換
  • 順序回路や加算器を使うカーディナリティ制約のエンコーディング（逐次加算器、ソートネットワークなど）
  • Pseudo-Boolean（擬似ブーリアン）や XOR 制約を特別処理するハイブリッド手法
  • 対称性除去や問題固有の簡約を行ってサイズを削減

形式検証・計画・AI における応用例

CNF/SAT は多様な分野で応用されています。

  • ハードウェア・ソフトウェアの形式検証（モデル検査で生成される条件を SAT に帰着）
  • 自動計画（Planning as SAT）：計画問題を時間ステップごとに CNF にエンコードして SAT ソルバーで解く
  • 制約充足問題、テスト生成、最適化（MaxSAT）、暗号解析（暗号の特性を SAT に落とす）
  • 知識表現や定理証明補助（自動定理証明器で SAT/SMT を利用）

実運用で注意すべき点

  • 直接的な CNF 化は式の指数的膨張を招くことがあるため、Tseitin などの補助変数導入法を用いること。
  • エンコーディング次第で SAT ソルバーの性能が大きく変わる。節のサイズ分布や対称性が重要。
  • DIMACS 形式など入出力規約を守ること（ソルバー間の互換性確保）。
  • 最適化問題（MaxSAT 等）や数え上げ問題（#SAT）など、CNF を用いた派生問題では異なるアルゴリズムが必要。

代表的なツール・フォーマット

  • DIMACS CNF 形式：多くの SAT ソルバーが入力として採用する簡易テキスト形式。
  • MiniSAT、Glucose、Lingeling、Cadical などの CDCL ベースソルバー。
  • Z3 や CVC4 などの SMT ソルバーは SMT-LIB を通じて内部で CNF 化（または内部論理変換）を行う。

具体例（概念説明）

例えば式 (a → b) ∧ (b → c) を CNF に直すと、含意を置換して (¬a ∨ b) ∧ (¬b ∨ c) という CNF になります。より複雑な式は Tseitin 変換で補助変数を導入するのが実務的です。

まとめと今後の展望

CNF は理論的な基礎と豊富な実用技術の両方を持ち、SAT ソルバーの進化とともに応用領域が拡大しています。近年はSATと機械学習の融合、分散 SAT、QBF（量化ブール式）やハイブリッド解法など新しい研究領域が活発です。実務では適切なエンコーディングと前処理が性能を左右するため、問題ごとの工夫が重要です。

参考文献

合取標準形 (Wikipedia 日本語)

Conjunctive normal form (Wikipedia)

Tseitin transformation (Wikipedia)

SAT Competition / DIMACS 形式 等 (SAT関連情報)

MiniSat（代表的な SAT ソルバー）

Handbook of Satisfiability（概説、英語）

カテゴリー
IT
前の記事
MANOとは何か：NFV時代の管理とオーケストレーションを徹底解説New!!
2025年12月12日
次の記事
ETSI NFVの全貌：歴史・アーキテクチャ・実装・課題と今後の展望New!!
2025年12月12日