ヒルベルトシステム-自動化証

Question

ようにしている証明書に~(a->~b)=>a ヒルベルト スタイルシステム。残念ながらうことはできなく一般的なアルゴリズムによる証明が、私力タイプの戦略です。そのアイデアをどう攻撃のことを歓迎する。

Answer 1

の場合のように"プログラミング"を combinatoryロジック, その

• で自動的に"翻訳"の一部ロジックの問題を他の分野:証明等のcombinatoryロジック。
• 良いプログラミング実習、解決できる
• およびその後、できる翻訳の答えをヒルベルトスタイル証明のオリジナルのロジックの問題です。

の目的への適合性その他一切の翻訳を確保 カレー-ハワード対応.

残念ながら、事態はそう簡単に限のサブセット(命題)論理制を条件分岐.否定は複雑化、知らない。従って私のせにはお答えできませんのでこのコンクリートの質問:

¬ (α ⊃ ¬β)   ⊢   α

がある場合否定ではないという問いを持って、これまでに述べた自動翻訳や翻訳でき、また既に実践プログラミングやcombinatoryトです。

---

もちろん、その他の助けもできるは内側の領域の論理:

• 証明になる問題をより直感的演繹システムなど 自然控除)
• およびその後の使用 metatheoremsを提供する"コンパイラ"の可能性：翻訳の高レベルの"証明書自然を控除し、"機械-コード"のヒルベルト-スタイルを控除します。だって、たとえば、metalogical定理という控除定理".

---

しのための定理証システムの調査を実施しているのは、同じく知られているように機能の一部が拡張できるようハーネス人案内もあります。E.g. コック である。

---

---

付録

見てみましょう。検証方法 α ⊃ α?

ヒルベルトシステム

• ガex quolibet_α,β は想定していaxiomのスキームを記載する文 α ⊃ β ⊃ α 予定演繹で,インスタンスを生成のための他のsubsentences α,β
• チェーン規則_α,β,γ は想定していaxiomのスキームは、この文の(α ⊃ β ⊃ γ) ⊃ (α ⊃ β) ⊃ α ⊃ γ 予定演繹で,インスタンスを生成のための他のsubsentences α,β
• 手ponens は原則として推測理論:提供する α ⊃ β は演繹できま α は演繹で、その期待を正当化されると推測されるも α ⊃ β は演繹可能.

ましょう定理を証明する: α ⊃ α は演繹可能の他 α する必要があります。

を紹介し、以下の表記および略語の展開"証明微分積分学":

証明微分積分学

• VEQ_α,β:   ⊢   α ⊃ β ⊃ α
• CR_α,β,γ:   ⊢   (α ⊃ β ⊃ γ) ⊃ (α ⊃ β) ⊃ α⊃ γ
• MP:ま⊢ α ⊃ β と⊢ α, その⊢ β

樹形図に表記：

Axiomのスキーム—ガex quolibet:

    ━━━━━━━━━━━━━━━━━ [VEQ_α,β]
          ⊢   α ⊃ β ⊃ α

Axiomのスキーム—チェーン規則:

    ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ [CR_α,β,γ]
          ⊢   (α ⊃ β ⊃ γ) ⊃ (α ⊃ β) ⊃ α⊃ γ

原則推測理論—手ponens:

     ⊢   α ⊃ β           ⊢   α
    ━━━━━━━━━━━━━━━━━━━ [MP]
                     ⊢   β

証明樹

見てみましょうツリー図表現の証明:

━━━━━━━━━━━━━━━━━━━━━━━━━━━━ [CR_{α, α⊃α, α}]    ━━━━━━━━━━━━━━━ [VEQ_{α, α⊃α}]
⊢   [α⊃(α⊃α)⊃α]⊃(α⊃α⊃α)⊃α⊃α                         ⊢   α ⊃ (α ⊃ α) ⊃ α
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ [MP]      ━━━━━━━━━━━ [VEQ_α,α]
                                          ⊢   (α ⊃ α ⊃ α) ⊃ α ⊃ α                                              ⊢   α ⊃ α ⊃ α
                                          ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ [MP]
                                                                                     ⊢   α ⊃ α

証方式

見てみましょうもconciser(代数?微分積分学?) 表記の証明:

(CR_{α,α⊃α,α} VEQ_{α,α ⊃ α}) VEQ_α,α:   ⊢   α⊃ α

いまを表現することができる証明木一式

• の分岐のツリー（手ponens）によって描画される単純な連結(括弧),
• の葉の木が描画される略語に対応するaxiomます。

での思い出として残したりしたいのコンクリートインスタンス化とはtypesetこsubindexicalパラメータ。

していますからシリーズの以下の例につけることができますし、 証明微分積分学, は、公理はnotatedという ベースcombinators, は、手ponensはnotatedな の応用 その"前提"subproofs:

例1

VEQ_α,β:   ⊢   α ⊃ β ⊃ α

していることを意味

ガex quolibet axiomスキームのインスタンス化 α,β ス証明書には、 α ⊃ β ⊃ α は演繹可能.

例2

VEQ_α,α:   ⊢   α ⊃ α ⊃ α

ガex quolibet axiomスキームのインスタンス化 α,α ス証明書には、 α ⊃ α ⊃ α は演繹可能.

例3

VEQ_{α, α⊃α}:   ⊢   α ⊃ (α ⊃ α) ⊃ α

していることを意味

ガex quolibet axiomスキームのインスタンス化 α, α⊃α ス証明書には、 α ⊃ (α ⊃ α) ⊃ α は演繹可能.

例4

CR_α,β,γ:   ⊢   (α ⊃ β ⊃ γ) ⊃ (α ⊃ β) ⊃ α⊃ γ

していることを意味

チェーン規則 axiomスキームのインスタンス化 α,β,γ ス証明書には、(α ⊃ β ⊃ γ) ⊃ (α ⊃ β) ⊃ α⊃ γ は演繹可能.

例5

CR_{α,α⊃α,α}:   ⊢   [α ⊃ (α⊃α) ⊃ α] ⊃ (α ⊃ α⊃α) ⊃ α⊃ α

していることを意味

チェーン規則 axiomスキームのインスタンス化 α,α⊃α,α ス証明書には、[α ⊃ (α⊃α) ⊃ α] ⊃ (α ⊃ α⊃α) ⊃ α⊃ α は演繹可能.

例6

CR_{α,α⊃α,α} VEQ_{α,α ⊃ α}:   ⊢   (α ⊃ α⊃α) ⊃ α⊃ α

していることを意味

した場合せ CR_{α,α⊃α,α} や VEQ_{α,α ⊃ α} という方でも 手ponens, をしてい証明することを証明する以下の声明を発表した。(α ⊃ α⊃α) ⊃ α⊃ α は演繹可能.

例7

(CR_{α,α⊃α,α} VEQ_{α,α ⊃ α}) VEQ_α,α:   ⊢   α⊃ α

この両者を併せてみるとcompund証(CR_{α,α⊃α,α} とともに VEQ_{α,α ⊃ α} （ 手ponensしかもcompund証明することにあります。この証明以下の声明を発表した。 α⊃ α は演繹可能.

Combinatoryロジック

はすべてこの上もって証明を理うですが、非常にunintuitive.目に見えない方法で"見出し"の証明することにあります。

見てみましょう別の分野では、同様の問題を調査しています。

Untyped combinatoryロジック

Combinatoryロジック 視して考えることができるのでとしても非常に余白のプログラミング言語です。ものは違うという意味で、完全にコンピュータの完全なevenmore、あまり書けなかなか直感的で複雑なプログラムでもこの一見obfuscated言語モジュールおよび再利用可能な、一部の実践から得られた"通常の"プログラミングおよび一部の代数的-知.

追加タイピング規則

Combinatoryロジックにも入力しに変更されることもあります。書式は拡張として、evenmoreのほか、削減規則、またタイピング規則が追加されます。

ベースcombinators:

• K_α,β が選ばれていることがありますが基本的なcombinator 息タイプ α → β → α
• S_α,β,γ が選ばれていることがありますが基本的なcombinator息するタイプ(α → β → γ) → (α → β) → α → γ.

タイピング規則の適用:

• の場合 X 生息タイプ α → β や Y 生息タイプ α, その X Y 生息タイプ β.

表記および略語

• K_α,β: α → β → α
• S_α,β,γ: (α → β → γ) → (α → β)* → α → γ.
• の場合 X: α → β や Y: α, その X Y: β.

カレー-ハワード対応

この"パターン"は同型の証明計算本文combinatoryトです。

• の ガex quolibet axiomの証明の微分積分に対応する K ベースcombinatorのcombinatoryロジック
• の チェーン規則 axiomの証明の微分積分に対応する S ベースcombinatorのcombinatoryロジック
• の 手ponens 原則推測理論の証明微分積分に対応した操作アプリ"にcombinatoryトです。
• の"条件"結合⊃のロジックに対応するタイプのコンストラクタ→型の理論および入力combinatory論理）

プログラミング

それでは。なぜすべての翻訳の問題にcombinatory論理によるものか。私は、とっても便利で機能的なプログラミングも大きい文に用いられます。人に慣れていき、強制的に利用でerverydayプログラミング作業も対応済みans pracice.あな技術のヒントプログラミングの実践で活用できる非常にcombinatoryロジック低減を図ります。した場合には"転送"の実践をcombinatoryロジックにそのまま残ってしまった活用されるものを探すの証明にヒルベルトシステム。

外部リンク

リンクの方法種類のプログラミング(lambda微分積分学、combinatory論理付けることができる論理証明および定理:

• Wadler、フィリップ(1989). 定理のための無料！.

リンク(書籍)を身につけるための方法と実践プログラムを直接combinatory論理

• Madore、David(2003)を参照のこと。 のUnlambdaプログラミング言語.Unlambda:機能性プログラミング言語の夢が叶.
• カレー、B.&Feys、ロバート&クレイグ-ウィリアム-(1958年)。 Combinatoryロジック. Vol.I.アムステルダム:北オランダの出版社。
• Tromp、ジョン-(1999). バイナリのラムダ計算とCombinatoryロジック.ダウンロードPDF、Postscriptの著者 ジョンのラムダ計算とCombinatoryロジックの遊び場.

Answer 2

ヒルベルト・システムは、通常、自動化された定理証明に使用されていません。自然の控除を使用して証明を行うためのコンピュータプログラムを書くためにはるかに簡単です。もちろんのCSの材料から：

  

いくつかのよくある質問のヒルベルトシステムについて：   Q：どのように1 knowがどの公理   使用するスキーマ、およびその   置換は作るには？あるので、   それは無限に多くの可能性、   でも中に、それらすべてを試してみてくださいすることはできません   princple。 A：何のアルゴリズムはありません。に   少なくとも単純な1ありません。むしろ、一つは持っています   賢いことにします。純粋数学では、   これは、以来、問題視されていません   1が最も懸念しています   証拠の存在。しかし、中   コンピュータサイエンスのアプリケーションで、1は、   控除を自動化することに興味   このプロセスは、これは致命的な欠陥です。ザ・   ヒルベルトシステムは、通常では使用されません   自動化された定理証明。 Q：それでは、なぜ   ヒルベルトについて人々のケアを行います   システム？ A：そのようモーダスポネンス付き   単一演繹ルールは、それがAを提供します   どのように人間の口に合うモデル工夫   証明。後で述べるように、   に、より適している方法   コンピュータ実装プロデュースプルーフ   以下「のような人間。」である。

Answer 3

ヒルベルト計算で証明を見つけることは非常に困難である。

あなたはヒルベルト微積分へのシークエント計算や自然演繹で証明を翻訳しようとすることができます。

を

Answer 4

できるアプローチにも問題設定によるα=α→⊥.その上で、いまを採用、ヒルベルトスタイルシステムとしては、別紙に回答し、古典の追加で、以下の二つの公理をそれぞれ定数:

Ex Falso Quodlibet:E_α : ⊥ → α
Consequentia Mirabilis:M_α : (¬ α → α) → α

A sequentの証明(α→β)→αを読み込みとおり

1. α⊢α（アイデンティティ)
2. ⊥⊢β→⊥(Ex Falso Quodlibet)
3. α→⊥、α⊢β→⊥(Impl巻頭左1&2)
4. α→⊥⊢α→β→⊥)(Impl紹介右3)
5. ⊥⊢α(Ex Falso Quodlibet)
6. （α→β→⊥))→⊥、α→⊥⊢α(Impl巻頭左4&5)
7. （α→β→⊥))→⊥⊢α(Consequentia Mirabilis6)
8. ⊢((α→β→⊥))→⊥)→α(Impl紹介右7)

このことからsequent証明できるエキス、ラムダを表現。の可能性 ラムダ式のsequent証明を読み込みとおり

λy.(M λz.(E y λx.(E(z x)))))

このラムダ仕様の表現に変換することができるスキー場。の可能性 スキー期のラムダ仕様の表現を読み込みとおり

S(K M))(L2（L1(K(L2（L1(K I))))))
場L1=(S(S(K S))((S(K))っ)))
およびL2=(S(K(S K E))))

このヒルベルトスタイル証明:

補題1:形市のチェーン規則:
1:（A→B)→(C→A)→(C→B)))→(((A→B→C→A)→((A→B→C→B)[チェーン]
2:（A→B)→(C→(A→B)→(C→A)→(C→B))))→(((A→B→C→(A→B)))→((A→B)→(C→A)→(C→B))))[チェーン]
3:((C→(A→B)→(C→A)→(C→B)))→((A→B)→(C→(A→B)→(C→A)→(C→B))))[ガEx】
4:(C→(A→B)→(C→A)→(C→B)[チェーン]
5:(A→B)→(C→(A→B)→(C→A)→(C→B)[MP3,4]
6:（A→B→C→(A→B)))→((A→B)→(C→A)→(C→B)[MP2,5]
7:（A→B)→((A→B→C→(A→B))))→(((A→B)→(A→B)→((A→B→C→(A→B))))[チェーン]
8:（A→B→C→(A→B)))→((A→B)→((A→B→C→(A→B))))[ガEx】
9:(A→B→C→(A→B)[ガEx】
10:(A→B)→((A→B→C→(A→B)[MP8,9]
11:（A→B)→(A→B)→((A→B→C→(A→B)[MP7,10]
12:(A→B)→(A→B)[人]
13:(A→B→C→(A→B)[MP11,12]
14:(A→B)→(C→A)→(C→B)[MP6日13]
15:（A→B→C→A)→((A→B→C→B)[MP1,14]

補題2:形市のFalso:
1:(A→（Ｂ→⊥)→(B→C)))→((A→B→⊥))→(A→B→C)))[チェーン]
2:（Ｂ→⊥)→(B→C)→(A→（Ｂ→⊥)→(B→C)))[ガEx】
3:（B→(⊥→C)→(B→⊥)→(B→C)[チェーン]
4:(⊥→C)→(B→(⊥→C)[ガEx】
5:⊥→C[Ex Falso]
6:B→(⊥→C)[MP4,5]
7:（B→⊥)→(B→C)[MP3,6]
8:A→（Ｂ→⊥)→(B→C)[MP2,7]
9:(A→B→⊥))→(A→B→C)[MP1日8]

最終証明:
1:(((A→B→ ⊥)) → ⊥) → (((A→⊥)→A)→A)→((((A→B→ ⊥)) → ⊥) → ((A→⊥)→A)→(((A→B→⊥))→⊥)→A)[チェーン]
2:(((A→⊥)→A)→A)→(((A→B→ ⊥)) → ⊥) → (((A→⊥)→A)→A)[ガEx】
3:（A→⊥)→A)→A[Mirabilis]
4:（A→B→ ⊥)) → ⊥) → (((A→⊥)→A)→A)[MP2,3]
5:(((A→B→ ⊥)) → ⊥) → ((A→⊥)→A)→(((A→B→⊥))→⊥)→A)[MP1,4]
6:(((A→B→ ⊥)) → ⊥) → ((A→ ⊥) → ⊥)) → (((A→B→ ⊥)) → ⊥) → ((A→⊥)→A)[補題2]
7:(((A→B→ ⊥)) → ⊥) → ((A→⊥)→(A→B→ ⊥)))) → (((A→B→ ⊥)) → ⊥) → ((A→⊥)→⊥))[補題1]
8:（A→⊥)→(A→B→⊥)))→(((A→B→ ⊥)) → ⊥) → ((A→⊥)→(A→B→⊥))))[ガEx】
9:（A→⊥)→(A→⊥))→((A→⊥)→(A→B→⊥)))[補題2]
10:（A→⊥)→(A→A)→((A→⊥)→(A→⊥))[補題1]
11:(A→A)→((A→⊥)→(A→A)[ガEx】
12:A→A[人]
13:(A→⊥)→(A→A)[MP11,12]
14:(A→⊥)→(A→⊥)[MP10日13]
15:(A→⊥)→(A→B→⊥))[MP9,14]
16:（A→B→ ⊥)) → ⊥) → ((A→⊥)→(A→B→⊥)))[MP8,15]
17:（A→B→ ⊥)) → ⊥) → ((A→⊥)→⊥)[MP7,16]
18:（A→B→ ⊥)) → ⊥) → ((A→⊥)→A)[MP6,17]
19:（A→B→⊥))→⊥)→A[MP5日18]

かなりの長の証なのです！

Bye

Answer 5

1. ある特定のヒルベルトシステム?がトンにもなります。
2. その最良の方法で証明でsequent微分積分変換するヒルベルトシステム。

Answer 6

使ってい ポーランド表記.

か参照される文を引用される場合は、出典が"しょう当社の基

1CpCqp.

2CCpCqrCCpqCpr.

3CCNpNqCqp.

したいことを証明

NCaNb|にした。

私の定理式試験器 Prover9.なので、する必要がありますparenthesizeます。また、変数のProver9（x,y,z u,w v5、v6,...,vn).それ以外の記号はすべて取得しとして解釈される機能や関連の述語.すべての公理を必要と述語の記号が"P"の前におくものを考えることができるという意味では証す---"以上"もしくは"証明".すべての文章にProver9く終わりません。このように公理1、2、3となり、それぞれ:

1P(C(x,C(y,x))).

2P(C C(x,C(y,z))、C(C(x,y)、C(x,z)))).

3P(C C(N(x)N(y)),C(y,x))).

して結合し、ルールの代替および剥離の原則の 凝縮 剥離.にProver9して表現することができること:

-P(C(x,y))|-P(x|P(y).

の"|"を示す論理的に分離し、""は否定.Prover9証による矛盾に満ちているものです。ルールという言葉で解釈されていること"のいずれかではない場合の場合、x、yが証明でない場合がx証、またはyが証明." このように、または保持する場合、x、y証、disjunct失敗します。った場合の開催とが証明、そのdisjunct失敗します。ので、出張不在の為、しばらくx、yの証明がある証明の第三disjunct、ｙが証明で以下の規則です。

今まであるかのように映像化しているに置き換えNCaNbかなtautology.もすること。このように置かれていま

P(N(C,N(b)))).

としては、Prover9すると解釈で"a"または"b"として nullary 機能の効率を定数とまたP(a)として私たちの目標です。

今までも"調整"Prover9様々な定理証明など戦略の重み付け、共振subformula、定率、飽和度（あるいは発明、自社).また利用したいと思い、ヒント戦略は少により、手を加えることで、このような前提条件を含むの支配の推定の目的へのヒント.僕も、最大重量40、5の最大の変数.

を利用したいバージョンのグラフィカルインターフェイスがこの入力：

set(ignore_option_dependencies). % GUI handles dependencies

if(Prover9). % Options for Prover9
assign(max_seconds, -1).
assign(max_weight, 40).
end_if.

if(Mace4).   % Options for Mace4
assign(max_seconds, 60).
end_if.

if(Prover9). % Additional input for Prover9
formulas(hints).
-P(C(x,y))|-P(x)|P(y).
P(C(x,C(y,x))).
P(C(C(x,C(y,z)),C(C(x,y),C(x,z)))).
P(C(C(N(x),N(y)),C(y,x))).
P(N(C(a,N(b)))).
P(a).
end_of_list.
assign(max_vars,5).
end_if.

formulas(assumptions).

-P(C(x,y))|-P(x)|P(y).
P(C(x,C(y,x))).
P(C(C(x,C(y,z)),C(C(x,y),C(x,z)))).
P(C(C(N(x),N(y)),C(y,x))).
P(N(C(a,N(b)))).

end_of_list.

formulas(goals).

P(a).

end_of_list.

この証明ができたことは:

============================== prooftrans ============================
Prover9 (32) version Dec-2007, Dec 2007.
Process 1312 was started by Doug on Machina2,
Mon Jun  9 22:35:37 2014
The command was "/cygdrive/c/Program Files (x86)/Prover9-Mace43/bin-win32/prover9".
============================== end of head ===========================

============================== end of input ==========================

============================== PROOF =================================

% -------- Comments from original proof --------
% Proof 1 at 0.01 (+ 0.01) seconds.
% Length of proof is 23.
% Level of proof is 9.
% Maximum clause weight is 20.
% Given clauses 49.

1 P(a) # label(non_clause) # label(goal).  [goal].
2 -P(C(x,y)) | -P(x) | P(y).  [assumption].
3 P(C(x,C(y,x))).  [assumption].
4 P(C(C(x,C(y,z)),C(C(x,y),C(x,z)))).  [assumption].
5 P(C(C(N(x),N(y)),C(y,x))).  [assumption].
6 P(N(C(a,N(b)))).  [assumption].
7 -P(a).  [deny(1)].
8 P(C(x,C(y,C(z,y)))).  [hyper(2,a,3,a,b,3,a)].
9 P(C(C(C(x,C(y,z)),C(x,y)),C(C(x,C(y,z)),C(x,z)))).  [hyper(2,a,4,a,b,4,a)].
12 P(C(C(C(N(x),N(y)),y),C(C(N(x),N(y)),x))).  [hyper(2,a,4,a,b,5,a)].
13 P(C(x,C(C(N(y),N(z)),C(z,y)))).  [hyper(2,a,3,a,b,5,a)].
14 P(C(x,N(C(a,N(b))))).  [hyper(2,a,3,a,b,6,a)].
23 P(C(C(a,N(b)),x)).  [hyper(2,a,5,a,b,14,a)].
28 P(C(C(x,C(C(y,x),z)),C(x,z))).  [hyper(2,a,9,a,b,8,a)].
30 P(C(x,C(C(a,N(b)),y))).  [hyper(2,a,3,a,b,23,a)].
33 P(C(C(x,C(a,N(b))),C(x,y))).  [hyper(2,a,4,a,b,30,a)].
103 P(C(N(b),x)).  [hyper(2,a,33,a,b,3,a)].
107 P(C(x,b)).  [hyper(2,a,5,a,b,103,a)].
113 P(C(C(N(x),N(b)),x)).  [hyper(2,a,12,a,b,107,a)].
205 P(C(N(x),C(x,y))).  [hyper(2,a,28,a,b,13,a)].
209 P(C(N(a),x)).  [hyper(2,a,33,a,b,205,a)].
213 P(a).  [hyper(2,a,113,a,b,209,a)].
214 $F.  [resolve(213,a,7,a)].

============================== end of proof ==========================