ホーン節（Horn clause）とは：定義・種類・Prologと計算理論での役割

ホーン節の定義・種類を基礎から解説し、Prolog実装や定理証明、計算理論での役割や応用例を図解でわかりやすく紹介。

ホーン節とは、リテラルの論理的論理和で、リテラルのうちせいぜい1つが正で、他はすべて負である節（クローズドな論理式）を指します。これは1951年にこの形の節を研究した Alfred Horn にちなむ名称です。直感的には「結論（正のリテラル）が最大1つしかなく、残りはすべて条件（否定されたリテラル）」という形の論理式です。

種類と記法

ホーン節には主に次の3種類があります。

• 確定節（definite clause）：正のリテラルがちょうど1つあるホーン節。規則（rule）とも呼ばれ、論理プログラムの基本単位です。
• 事実（fact）：確定節のうち、負のリテラルが一つもないもの。単純な断言で、例：u.
• ゴール節（goal clause）（あるいは問合せ、query）：正のリテラルがないホーン節。問いや否定として扱われることが多いです。

例えば命題論理の形で書くと、以下はホーン節の典型的な形です：

♪♪¬ p ∨ ¬ q ∨ ⋯ ∨ ∨ ¬ t ∨ u

この形式は含意の形で書き直すと分かりやすくなります：

( p ∧ q ∧ ⋯ ∧ t ) → u {\display style (p\wedge q\wedge \cdots \wedge t)\rightarrow u}

一階述語論理の場合、節内のすべての変数は暗黙に普遍量化されます。たとえば次は等価な表現です：

∀ X ( human ( X ) → mortal ( X ) ) .

あるいは同じ節を否定リテラルの論理和として書くと：

♪♪¬ p ∨ ¬ q ∨ ⋯ ∨ ¬ t

論理的性質と解決（resolution）

ホーン節は解消（resolution）の下で特別な性質を持ちます。2つのホーン節の解消子（resolvent）は再びホーン節になるため、ホーン節系は閉じています。特に、確定節とゴール節の解消によって常にゴール節が得られることから、1次解消（first-order resolution）を用いた自動定理証明や問合せの検索で扱いやすくなっています。

論理プログラミングにおける代表的な推論戦略は、後ろ向き推論（backward chaining）で、これは実装上 SLD 解決（SLD resolution）として知られています。確定節（規則）を用いて現在のゴールを分解し、事実に突き当たるまで繰り返すことで問合せを解きます。

to show u … といった手続き的な読み方をすると、上の節は「uを示すために p, q, …, t を示せ」と解釈できます。後ろ向きの記法で書くと次のようになります：

u ← ( p ∧ q ∧ ⋯ ∧ t )

論理プログラミングとProlog

ホーン句は論理プログラミングの基礎をなしており、規則や事実は一般に暗黙的な含意の形で記述されます。Prolog では上の規則は次のように書かれます：

u :- p, q, ..., t.

Prolog の表記や「ゴール節」という用語には文脈によって曖昧さが残ります。例えばゴール節の変数は普遍量化と存在量化のどちらで読むか、またゴール（問合せ）を解いて "false" を導くことが矛盾の検出を意味するのか、単に問合せが成功したことを示すのかは、扱う論理的意味論によって異なります。

意味論（モデル理論と意味付け）

Van Emden と Kowalski (1976) は、論理プログラム（特に確定節の集合）に対するモデル理論的性質を研究しました。彼らは、確定節の集合 D に対して一意の最小モデル M（Herbrand の最小モデル）が存在することを示し、原子式 A がその最小モデル M で真であるならば、論理的に D により帰結される（暗黙の了解として導かれる）と定義できます。これは宣言的意味論と演算的意味論（解決による帰結）の一致を支える基本的事実です。

また、定義的意味（declarative semantics）に加え、演算的にはTP演算子（即ちプログラムの即達点を与える単調関数）による到達可能性の反復で最小モデルに達するという視点（fixpoint semantics）も重要です。

計算論理と複雑度

命題ホーン節の充足可能性問題（HORNSAT）は計算複雑度的に重要です。命題ホーン充足性問題は線形時間で解け、P 完全（特に線形時間アルゴリズムがある）です。これは一般のブール充足性問題（SAT）が NP 完全であるのとは対照的です（参考：ブール語の充足性問題はNP完全問題）。

一方、一次（first-order）ホーン節の充足可能性（一般の一階述語論理におけるホーン理論の可満足性）は、関数記号を無制限に許す場合は決定不能となります。関数記号を持たない（あるいは有限深さに制限された）ホーン論理プログラムの特別なケースは、決定可能で効率的に評価できることが多く、データベース理論との関連で重要です（例：Datalog は関数記号を持たないホーン節系で、問合せ評価は決定可能であるが複雑度は文脈依存）。

応用例と利点

• 論理プログラミング言語（Prolog等）：規則と事実による知識表現と問合せ処理。
• 自動定理証明：ホーン節は解消法や単純化された探索空間により扱いやすい。
• 型推論や規則ベースの推論エンジン：ホーン節の単純な推論規則を利用。
• データベース問合せ（Datalog）：関数記号を持たないホーン節系として効率的に評価可能。

まとめ

ホーン節は「最大1つの正リテラル」を持つ節で、論理プログラミングや自動推論、計算複雑度理論において中心的な役割を果たします。モデル理論的には最小モデルを持ち、計算論的には命題版が多項式（線形）時間で解けるなど取り扱いやすい性質をもつため、実務・理論の両面で広く用いられています。

（注）本文中の数式表現や例示の一部は組版上の図像として挿入されています：下記に示した数式図像は元の表記をそのまま保持しています。

♪♪¬ p ∨ ¬ q ∨ ⋯ ∨ ∨ ¬ t ∨ u

fact: u {displaystyle u}.

♪♪¬ p ∨ ¬ q ∨ ⋯ ∨ ¬ t { {\displaystyle ♪ ♪ ♪ p\lor ♪ ♪ ♪ q ♪vee ♪ ♪ ♪cdots ♪ ♪ ♪ vee ♪ ♪ t} ♪

∀ (¬人間( X )∨死人( X ) ) )♪displaystyle ≪pos(310,000)blue≫ ≪pos(310,000)blue≫ ≪pos(310,000)blue≫ ≪pos(310,000)blue≫

∀ X ( human ( X ) → mortal ( X ) ) .♪♪display style ≪(表示スタイル)≫ ♪forall X({pos(100,000)}(X)右矢印 {pos(100,000)}(X).}

( p ∧ q ∧ ∧ ⋯ ∧ t ) → u {\display style (p\wedge q\wedge \cdots \wedge t)\rightarrow u}

to show u , show p and show q and ⋯ and show t .

u ← ( p ∧ q ∧ ⋯ ∧ t )

Prolog では、これは次のように書かれています。

u :- p, q, ..., t.

Van Emden and Kowalski (1976) は、論理プログラムの文脈で Horn 節のモデル理論的性質を研究し、定義節の集合 Dのすべてが一意の最小モデル Mを持つことを示した。原子式 Aは、AがMの中で真である場合に限り、論理的に D によって暗黙の了解を得ることができる。

命題ホーン節は計算複雑度の分野でも注目されています。命題ホーン節の連結を真にするための真理値の代入を見つける問題は、P 完全問題（実際には線形時間で解くことが可能）であり、HORNSAT と呼ばれることもあります（ただし、無制限のブーリアン充足性問題は NP 完全問題です）。(ただし、制限のないブール語の充足性問題はNP完全問題である)。一次ホーン節の充足性は決定不可能である。

質問と回答

Q:ホーン節とは何ですか?

Q:誰が最初に記述したのですか?

Q:定冠詞節とは何ですか?

Q: 事実とは何ですか?

Q: ゴール節とは何ですか?

Q:非命題格の変数はどのように働くのですか?

文字で検索