ホーン条項: 基礎と応用

By Fouad Sabry

ホーン節とは

数理論理学と論理プログラミングの分野では、ホーン節として知られる論理式は、独特のルールのような形式を持ち、 論理プログラミング、形式仕様、モデル理論に適用できる有用な性質を備えています。 論理学者のアルフレッド ホーンは、1951 年にホーン条項の重要性に最初に注目を集めた人物であるとされています。

どのようなメリットがあるか

(I) 以下のトピックに関する洞察と検証:

第 1 章: ホーン節

第 2 章: 直観主義的論理

第 3 章: 計算論理

第 4 章: 自動定理証明

第 5 章: ロジックでの解決

第 6 章: ホーン充足可能性

第 7 章: ルールベースのシステム

第 8 章: 制約処理ルール

第 9 章: 一次論理

第 10 章: ブール充足可能性問題

(II) ホーン条項に関する一般のよくある質問に回答します。

(III) 多くの分野でのホーン条項の実際の使用例。

(IV) 266 を簡単に説明する 17 の付録 各業界の新興テクノロジーを取り上げ、ホーン クロースのテクノロジーを 360 度完全に理解することができます。

本書の対象者

専門家、大学生、大学院生 、愛好家、愛好家、そしてあらゆる種類のホーン節に関する基本的な知識や情報を超えたいと考えている人。

 

• Language: 日本語
• Publisher: 10億人の知識があります [Japanese]
• Release date: Jun 29, 2023

Book preview

第1章:ホーン条項

数理論理学および論理プログラミングの分野では、ホーン節は特定の規則のような形をとる論理式です。このルールのような形式は、論理プログラミング、形式仕様、およびモデル理論に使用できる有用な品質を式に与えます。論理学者のアルフレッドホーンは、1951年にホーン条項の関連性に最初に注意を向けた人物であると信じられています。

最大で1つの正の、または否定されていないリテラルを含む文は、ホーン句として知られています。この種のフレーズはリテラルの選言です。

一方、デュアルホーン句は、否定されるリテラルが1つしかないリテラルの選言として言われます。

厳格なホーン句としても知られる明確なホーン句は、正確に1つの肯定的なリテラルを含むホーン節です。目標句は、正のリテラルが含まれていない場合の Horn 句です。goal 句は空の句であり、リテラルが含まれていないため、値 false を表すことに注意してください。命題形式の次の例は、これら3種類のHorn節の図を示しています。

文の変数はすべて暗黙の普遍的な量化を受け取り、この定量化の範囲は句全体です。これは、たとえば次のことを意味します。

¬ 人間(X) ∨ 致命的(X)

の略:

∀X( ¬  人間(X) ∨ 人間(X) )

これは(論理的な意味で)と同じことです:

∀X(人間(X) → 致命的(X) )

構成論理と計算論理として知られる論理の枝は、どちらもホーン節に大きく依存しています。

これらは、主に2つのホーン節の解決もホーン節であり、目標節は、定節と目標節を溶媒として組み合わせたときに得られるものであるという事実により、一次解決として知られる自動定理証明プロセスにおいて重要な役割を果たします。

ホーン節のこれらの特性は、定理を証明するプロセスにおいてより良い程度の効率をもたらすかもしれません:目的節はこの定理の否定です。そのすぐ上にある表の Goal 句を参照してください。

直感的に、φ証明したい場合は、¬φ(目標)を仮定し、そのような仮定が矛盾につながるかどうかを確認します。

もしそうなら、φ保持しなければなりません。

このように、2つの別々のグループ、(サブ)目標と仮定を持つのではなく、機械的証明機器(仮定)で最新の状態に保つ必要がある式のセットは1つだけです。

コンピュータの複雑さの研究では、命題ホーン節は別の研究分野です。「HORNSAT」という用語は、組み合わせると命題のホーン節の結合を真にする可能性のある真理値の割り当てを発見するという課題を指します。この問題は線形時間で解くことができ、P完全構造を持っています。制約のないブール充足可能性の問題はNP完全問題であることに留意することが重要です。

論理プログラミングでは、明確な句を含意の形で表現することが通常慣例であり、ホーン節はフィールドの基本的な構成要素として機能します。

(p   ∧ q ∧ ..

∧トン) → u

実際、論理プログラミング言語Prologの開発に採用されているSLD解決推論規則の基礎は、新しい目標句を生成するために、明確な句を持つ目標節の解決です。

定節は、論理プログラミングに関する目標削減手法と同じように機能します。例として、上に書かれたホーン句は、プロセスと同様に動作します。

Uを実証し、Pを実証し、Qを実証し、そして...そしてtを実証する。

この節の逆方向の適用に注意を引くために、それはしばしば逆の形式で書かれています:

u ← (p   ∧ q ∧ ..

∧ トン)

これはプロローグで表現される方法です::

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

論理プログラミングでは、計算とクエリ評価は、ターゲット句として対処する必要がある問題の否定を提供することによって実行されます。これにより、問題をより迅速に解決できます。たとえば、正のリテラルの存在的に定量化された結合を解く問題の解決策を見つけるという課題を考えてみましょう。

∃X (p   ∧ q ∧ ..

∧ トン)

は、問題に解決策があることを否定し、問題を否定するのと同じであり、論理的に同一の形式である目標句の形式で表現することによって表現されます。

∀X (偽← p   ∧ q ∧ ..

∧ トン)

これはプロローグで表現される方法です::

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

問題の解決策を見つけることは、それ自体と互換性のない結論に到達することを意味し、それは空のフレーズ(または「false」)によって象徴されます。矛盾の証明は、問題を解決するための鍵を提供し、それを使用して、目標句の変数に置き換えるべき項を導き出すことができます。このように使用すると、目標句はリレーショナルデータベースの接続クエリに匹敵し、ホーン句ロジックの計算能力はユニバーサルチューリングコンピューターに匹敵します。

Prologに使用される表記法は実際にはやや曖昧であり、「目標句」という用語も曖昧に使用されることがあります。

目標句の変数を解釈するには、普遍的または存在的量化子の2つの方法があり、「false」を導出することは、矛盾を導出するか、解決すべき問題の成功した解決策を導き出すものとして解釈できます。

論理プログラミングの枠組みの中で、Van EmdenとKowalski(1976)はホーン節のモデル理論的特徴を調べました。彼らは、定節Dの任意のセットが一意の最小モデルMを持つことを示しました。これは彼らの研究を通して示されました。原子式AがMで有効である場合に限り、Dは論理的に原子式Aを暗示する。 論理的には、Pが正のリテラルの存在的に定量化された接続詞で表される問題である問題Pの解は、PがMで真である場合にのみDによって提案されます。これは、前のステートメントに従います。ロジックプログラムの安定したモデルセマンティクスは、Horn句の単純なモデルセマンティクスによって提供される基盤の上に構築されています。

{第 1 章終了}

第2章 直観主義的論理

構成的証明の概念をより厳密に模倣するという点で古典論理に使用されるものとは異なる記号論理のシステムは、直観主義論理と呼ばれます。時には、より広く、この種の論理は建設的論理と呼ばれます。特に、古典論理学における重要な推論規則である除外中間否定と二重否定消去の法則は、直観論理のシステムでは想定されていません。

Arend Heytingは、形式化された直観主義論理を確立した最初の人物であり、Lの正式な基盤を提供するためにそれを行いました。

E.

J.

ブラウワーのプログラムの下で実践されている直観主義。

証明理論の観点から見ると、ヘイティングの計算は、除外された中間および二重否定の除去の法則が削除された古典論理の制限です。

命題ごとに、除外された中間消去と二重否定消去は、特定の場合には真であることが示される場合がありますが、従来の論理と同じようにすべての状況で当てはまるわけではありません。

BHK解釈は、一般的に直観主義的論理を説明する最良の方法と見なされています。

伝統的な論理の意味論に関しては、命題の公式には、 \{\top, \bot\} それぞれの場合に直接証明がある場合とない場合があるという事実に関係なく、2つの要素セット(それぞれ「true」と「false」)から真理値が割り当てられます。

これは、人々が「除外された中間のルール」について話すときの意味であり、主に「真」と「偽」以外の他の真理値の存在を排除するという事実によるものです。

対照的に、直観主義的論理では、命題定式化には決定的な真理値が与えられず、むしろ、それらを裏付ける直接的な証拠、したがって証拠がある場合にのみ「真」と判断されます。

(また、命題の公式が具体的な証拠の結果として「真」であるのではなく、それが議論によって占められていることを(カリー・ハワードの意味で)実証すると言うこともできます。その結果、直観主義的論理の操作は、真実の評価ではなく、事実とそれを証明する能力に照らして正当化を維持します。

数学への構成主義的アプローチを確立する過程で、直観主義的論理はしばしば使用される技術です。一般に構成主義論理の使用は、数学者と哲学者の間で論争の的となっている問題でした(たとえば、ブラウワーとヒルベルトの間の議論)。上記のように、古典論理の2つの基本法則、除外された中間の法則と二重否定の除去がないことは、それらの使用に対して頻繁に提起される議論です。デイヴィッド・ヒルベルトは、これらを数学の応用にとって非常に重要であると見なし、それらについて次のように書いた:「数学者が除外中間の原理を適用することを妨げられた場合、それは天文学者が望遠鏡を使用することを妨げたり、ボクサーが拳を使わないようにすることに似ています。存在の主張や排除された中間の概念が違法となれば、数学全体を科学分野として諦めるのと同じだ」

除外された中間および二重否定の除去の有用な原則を利用できないことによってもたらされる重大な障害にもかかわらず、直観主義的論理は現実の世界で特定の用途を持っています。このため、この理由の1つは、それが課す制限が存在特性を持つ証明をもたらし、他のタイプの数学的構成主義での使用も許容されることです。非公式には、これは、オブジェクトが存在するという構成的証明がある場合、その構成的証明をそのオブジェクトの例を生成するためのアルゴリズムとして使用できることを意味します。この原理は、証明とアルゴリズムの間のカリー・ハワード対応として知られています。オブジェクトが存在するという建設的な証明がない場合、これはオブジェクトが存在するという建設的な証明がないことを意味します。直観主義的論理のこの特定の側面が非常に有益である多くの理由の1つは、実務家が一緒に証明アシスタントと呼ばれるさまざまなコンピューター化されたツールを利用できるためです。これらのツールは、大規模な証明を検証(および生成)するプロセスでユーザーを支援しますが、そのサイズは、数学的証明の公開と評価に必要な典型的な人間ベースのチェックを除外することがよくあります。したがって、証明アシスタント(AgdaやCoqなど)の雇用により、現代の数学者や論理学者は、完全に手作業で作成および検証できる実用的なシステムを超えて、非常に複雑なシステムを設計および証明することが可能になっています。4色定理のよく知られた証明は、正式な検証に頼らなければ満足のいく方法で検証できない証明の例です。この定理は、可能な反例の大規模なクラスを除外する証明が開発されるまで、100年以上にわたって数学者を困惑させましたが、それでも証明を完了するためにコンピュータープログラムが必要になるのに十分な可能性を残しました。その時点まで、定理は証明できないと考えられていました。この証明はしばらくの間争われましたが、最終的にはCoqを使用して検証されました。

直観主義論理で使用される公式の構造は、命題論理や一階論理の構造と多少似ています。

しかし、古典論理で使用される接続詞とは対照的に、直観的な接続詞は互いに定義できないため、選択するオプションが重要です。

直観主義命題論理(IPL)では、基本的な接続詞として→、∧、∨、⊥を使用し、¬Aを(A → ⊥)の略語として扱うのが通例です。

直観的な一階論理では、両方の量化子∃、∀が必要です。

直観主義論理を見る1つの方法は、単純化された一種の古典論理としてであり、推論者が引き出すことを可能にする結論に関してより抑制されている一方で、以前は従来の推論を使用して引き出すことが不可能であった新しい結論の形成を防ぎます。

直観的論理を使用して証明できるすべての定理は、古典論理を使用して証明することもできますが、他の方向では証明できません。

古典論理学では、多くのトートロジーは定理と見なされます。しかし、直観主義論理学では、これらのトートロジーの多くは、前述のように定理とは見なされず、直観主義論理の主な目標の1つは、建設的でない矛盾によって証明の価値を損なうために、除外された中間の規則を肯定することを避けることであり、存在すると主張するものの特定のインスタンスを与えることなく、物事の存在を示すために使用される場合があります。

「肯定しない」というフレーズを使用するのは、法律が特定の状況で維持されるとは限らない場合でも、反例を提供する方法は、法律が特定の命題に適用されないことを暗示することによって古典論理の規則に違反する推論を構成するためです。この種の推論は、直観主義論理などの論理の厳密な弱体化では許されません。

実際、システムのトートロジーとして、法の二重否定は維持されます。 これは、 {\displaystyle \neg {\big (}\neg (P\vee \neg P){\big )}} 命題に関係なく、 という定理である P ことを意味します。

したがって、命題計算は本質的に伝統的な論理と一致しています。

定量化された式が相殺されると、述語論理の定式化の状況はより複雑になります。

ゲルハルト・ゲンツェンは、古典論理学の連続計算である彼のシステムLKが、直観主義論理の観点から健全で完全なシステムを生成するために、簡単な方法で制限される可能性があることを発見しました。このシステムは彼によってLJという名前を与えられました。シーケンスの結論側では、LKは任意の数の数式の発生を許可します。対照的に、LJはこの場所で複数の式を許可しません。

他のLK導関数は直観的導出に限定されていますが、それでも多くの結論を順番に導き出すことができます。そのようなインスタンスの 1 つが LJ です。

ヒルベルトのような次の微積分は、直観主義論理として知られているものを定義するために使用することができます。これは、従来の命題論理で使用される公理化手法に匹敵します。

手口の規則は、命題論理の推論規則として機能します。

MP: から \phi 推測する \phi \to \psi \psi

公理は次のとおりです。

その後-1: \phi \to (\chi \to \phi )

その後-2:

(\phi \to (\chi \to \psi )) \to ((\phi \to \chi ) \to (\phi \to \psi ))

そして-1: