|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 除去 ： [じょきょ] 1. (n,vs) removal 2. getting rid of ・ 定理 ： [ていり] 【名詞】 1. theorem 2. proposition ・ 理 ： [り] 【名詞】 1. reason
カット除去定理（カットじょきょていり、）は、シークエント計算の手法の重要性を示す、数理論理学の主要な結果のひとつである。（数理論理学の）基本定理と呼ぶこともある。ゲルハルト・ゲンツェンが1934年に書いた記念碑的論文 "Investigations in Logical Deduction" で、古典論理と直観論理の体系をそれぞれ形式化したシークエント計算の形式的体系 LK 及び LJ において、最初に証明が与えられた。カット除去定理は、シークエント計算の推論規則であるカット規則を用いて証明可能な式には、カット規則を用いない証明図もまた必ず存在することを示したものである。 == シークエント == シークエントは複数の文からなる論理表現であり、 という形式をとる。これは、直観的には「A かつ B かつ C かつ… を仮定すれば、P または Q または R または… が証明可能である」という意味に理解することができる（ここで左辺が論理積で、右辺は論理和であることに注意されたい）。前提である左辺は任意個の論理式からなり、左辺が空のシークエントが証明できた場合、その右辺は無前提に主張可能なトートロジーだということになる。逆に、結論である右辺が空となるなら、左辺は矛盾していると言える。LK（古典論理）では、右辺もまた任意個の論理式からなるが、LJ（直観論理）では、右辺には多くとも一つの文しか置くことが許されない。右辺に複数の論理式を置けることと、右縮約規則があるときに排中律が成り立つこととは等価である。ただし、シークエント計算は非常に表現能力が高く、右辺に多数の論理式のある直観論理のシークエント計算も存在する。Jean-Yves Girard の論理体系 LC においては、右辺に高々一個の論理式しか持たない古典論理の自然な定式化も容易に得られている。ここで鍵となるのは、論理的な推論規則と構造に関する推論規則との相互作用である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「カット除去定理」の詳細全文を読む スポンサード リンク
|