このブログは、旧・はてなダイアリー「檜山正幸のキマイラ飼育記 メモ編」(http://d.hatena.ne.jp/m-hiyama-memo/)のデータを移行・保存したものであり、今後(2019年1月以降)更新の予定はありません。

今後の更新は、新しいブログ http://m-hiyama-memo.hatenablog.com/ で行います。

法則としてのシーケント

記号的には、

  • [x1:t1, ..., xk:tk | A1, ..., An |- B]
  • 最初はk個の変数型宣言。型理論で言う型環境。
  • 次にn個の前提(仮説)論理式。
  • 1個の結論論理式。
  • 出現するすべての変数は型環境で型付けされている。

自然言語風の記述は:


for
x1:t1, ..., xk:tk
given
A1
and
...
...
and
An
shows
B

この意味を単一の論理式で書くなら、

  • ∀x1:t1, ..., xk:tk.(A1∧ ... ∧An)⇒B

αが法則(公理、定理)としてのシーケンのとき、

  • apply α to β1, ..., βp

の形で適用できる。

β1, ..., βp を A1, ..., An とマッチングして、ユニフィケーションの結果であるユニファイヤをΘとする。マッチングで残った前提を A'1, ..., A'q として、適用(apply)の結果は、

  • [x'1:t'1, ..., x'l:t'l | A'1[Θ], ..., A'q[Θ] |- B[Θ] ]

適用結果はシーケントなので、適当に論理式にして結果とする。

アルゴリズム的にはユニフィケーションがキモ。