数理論理学

出典: フリー百科事典『ウィキペディア（Wikipedia）』
移動先: 案内、 検索

数理論理学（すうりろんりがく、英語：mathematical logic）または記号論理学（きごうろんりがく、英語：symbolic logic）とは、数学的関係を表すのに用いられる形式的ことばとそれによる推論を、普通のことばとして表されることに由来する不明瞭さを避けて記述し推論するために、論理学の上の語とそれによる論理計算として表現できるように拡張された論理学のことである[1]。

数理論理学の発祥

言葉を、代数学におけると同様に文字や記号の列で表して、その変換について研究するいわゆる記号論理学、数理論理学の発祥は、19世紀のジョージ・ブールによる「論理代数」、ゴットロープ・フレーゲの書『概念記法』に見ることができる。前者は命題論理、後者は述語論理の原型である。

二値論理（古典論理）

数理論理学においてまず第一に必要なのはいわゆる命題論理である。ただし、一般に命題論理は命題自身の論理的構造には立ち入る事ができない。そのため命題論理だけでは数理論理学の目的に対して一般的に不十分である。命題自身の論理的構造、すなわち命題を構成する主語と述語の関係を分析するためには述語論理が必要となる。

すべての命題の意味が真(true)か偽(false)のどちらかである、すなわち2値論理は古典論理(classical logic)の特徴のひとつである。

命題論理(propositional logic)

テンプレート:Details 命題論理(propositional logic)とは、命題(proposition)と呼ばれるその内容が真(true)か偽(false)かいずれかであるものの間の論理的関係を精確に表すための論理である。ただし、命題そのものはそれ以上分析できないもののとして扱われる。

いくつかの命題は、一定の方法で新しい命題に結合される。たとえば、「2は3より小さい」及び「雪は黒い」という二つの命題から、以下のように新しい命題を導く事ができる：

「2は3より小さく、かつ雪は黒い」(and)
「2は3より小さいか、または雪は黒い」(or)
「2が3より小さいときは、雪は黒い」(if ... then)
「2は3より小さくない」(not)

これら命題の間の結合を適当な記号で表すことを考える。命題を表すためにX、Y、Z、Uなどの記号を用い、命題の論理的基本結合を表すにあたって以下の5つの記号を用いる事とする。

¬X(not X)
X という命題の否定的命題を表す。
X ∧ Y(X and Y)
X と Y が同時に真であるとき、かつそのときに限り真である命題を表す。
X ∨ Y(X or Y)
X と Y のうち、いずれか一方が真であるとき、真である命題を表す。
X → Y(if X, then Y)
X が真で、Y が偽であるときにのみ、偽となる命題を表す。
X = Y(X equivalent to Y)
X と Y とが共に真であるか、もしくは偽であるときのみ真である命題を表す。X = Y であるとき X と Y の真理値は一致する。

これら命題の基本結合を組み合わせることによってより複雑な命題を構成することができる。また、逆に論理計算としてその複雑な命題を恣意的な判断を排した形で簡単化することも可能となる。命題論理の基本的な興味の範疇はその複雑な命題の構成及び簡約に係る論理計算の性質である。

述語論理(predicate logic)

テンプレート:Details 命題論理は命題と命題の間の論理的関係を表現するだけで、命題自身はそれ以上分析することができない。そのため、伝統的なアリストテレスの論理における簡単な推論ですら命題論理では表現する事ができない。例えば、

すべての人間は必ず死ぬ;
カーユス(Cajus)は人間である;
ゆえにカーユスは必ず死ぬ.

という三段論法は個々の命題における主語と述語の関係を用いて推論を行っているため、主語と述語を扱う事ができない命題論理ではこの推論を形式的に表現する事ができない。

各命題を個物である主語とその性質である述語(predicate)に分けたものを述語論理(predicate logic)と呼ぶ。主語としては、数字の5など特定の対象を表す固有名詞(proper noun)及び特定の対象を表すものではない変項(variable)が導入される[2]。対して述語は記号的には、引数をとる関数記号を流用して表現される。例えば変項を x とするとき、 P(x) は「x は素数である」という述語[3]を表すものとすれば、変項 x に特定の固有名詞 5 を代入した P(5) は「5は素数である」という命題を表すことになる[4]。変項に代入される特定の対象を変項の値(variable value)と呼ぶ。

伝統的なアリストテレス三段論法を系統的に導きだすには、

  1. すべての x は A である（全称肯定判断）
  2. ある x は A である（特称肯定判断）
  3. すべての x は A ではない（全称否定判断）
  4. ある x は A ではない（特称否定判断）

の4つの形の命題を表す必要がある。そのため、この4つの形の命題を表すために全称記号(universal quantifier) ∀ 及び存在記号(existential quantifier) ∃ と呼ばれる前置記号が導入される。前置記号を導入する事で上記の4命題は以下のように形式的に書き表される。

  1. ∀ x . A(x)
  2. ∃ x . A(x)
  3. ∀ x . ¬A(x)
  4. ∃ x . ¬A(x)

なお、∀ x や ∃ x のように前置記号のすぐ後におかれる変項（全称または存在記号に属する変項）を束縛変項(bound variable)と呼ぶ。束縛変項ではない変項を自由変項(free variable)と呼ぶ[5]。

このように、変項及び前置記号（全称記号、存在記号）を導入した述語論理においては、伝統的なアリストテレス三段論法などを論理計算として扱う事ができるようになる。

述語の階数による区分けと型理論

テンプレート:Details

機能拡張した第一階述語論理としての公理的集合論

テンプレート:Details 抽象的な集合論は、述語論理と密接な関係をもっている。その骨子は

述語(predicate)を集合(set)とみなす

ことにある[6]。つまりは、述語の外延(extension)を集合として扱うのである。

公理的に建設された集合論、つまり公理的集合論(axiomatic set theory)は第一階述語論理に「x は集合 S の元である」を意味する x ∈ S など集合論特有の公理を付け加えたものに他ならない[7][8]。すなわち、公理的集合論とは機能拡張した第一階述語論理である[9]。

多値論理（非古典論理）

すべての命題の意味が3つ以上あるような論理体系、すなわち多値論理は、非古典論理(non-classical logic)に分類される。

非古典論理の例としては、様相論理(modal logic)、直観主義論理(intuitionistic logic)、ファジィ論理(fuzzy logic)、量子論理(quantum logic)などがある。

多値論理以外にも非古典論理に分類される論理はある。

数理論理学の主たる関心ごと

数理論理学には様々な論理体系があるが、それらに共通の関心ごととは、その論理体系における一つの論理式が普遍妥当（universal valid）[10]であるか否かを決定する真偽決定問題(decision problem)または双対的に論理式が充足不能（unsatisfiable）[11]であるか否かを決定する充足可能性問題（satisfiability problem）である。真偽決定問題は数理論理学における中心問題の一つである。

真偽決定問題と充足性問題

命題論理
命題論理における真偽決定問題とは、与えられた一つの複合命題が恒真命題であるか否かを決定することをいう[12]。
第一階述語論理
第一階述語論理における真偽決定問題とは、与えられた一つの述語論理式が任意の個体領域に対して普遍妥当である（恒真な論理式である）か否かを決定することをいう。
第二階述語論理及びそれ以上の高階述語論理

証明論

テンプレート:See also 証明論とは数学における証明を記号列と見なす立場（つまり syntax の立場）からの研究であり、20世紀初頭にヒルベルトにより数学の基礎付けを目的として創始された。この方面での重要な成果としては、ゲンツェンによる LK の基本定理、すなわち「式 S が LK で provable ならば、S は LK で三段論法なしでも provable である」があげられる。この定理は「対偶や背理法のような間接証明法を用いて証明できる命題は、間接証明法を用いなくても証明できる」というようなことを一般化した、論理について成り立つ非常に美しい法則である。基本定理の応用としては、命題論理・述語論理の無矛盾性、そして命題論理の決定可能性がある。また、この方面の研究としては同じくゲンツェンによる自然数論の無矛盾性の証明があげられる。

意味論

テンプレート:See also 意味論では、論理式で記述される命題の「意味」を、何らかの数学的対象に写像した上で、これらの数学的対象を研究する。述語論理における意味の与え方の一例としては、実在物 (Entity) の全体の集合 E と真偽の集合 {0, 1} との直和を世界と定め、素項の集合から E への写像 f の各々に述語言語から世界への意味写像 f ∗ を対応させる規則を然るべく定め、 意味写像を用いて論理式の真偽の概念を定める等々の方法がある。この方面での重要な成果としてはゲーデルの完全性定理があげられる。これはどのような意味の与え方によっても真となる述語論理の論理式と、述語論理の体系から provable となる論理式は、一致するというものである。

脚注

  1. ↑ ヒルベルト、アッケルマン(1954) p.1 緒言
  2. ↑ 命題論理から述語論理への大きな変更点はこの変項の導入である。変項が導入されたことで全称命題、特称命題が定義可能となる。
  3. ↑ 唯一つの引数を取るものを述語と呼び、二つ以上の引数をとるものを関係(relation)と呼ぶ事もあるが、ここでは二つ以上の引数を取るものも述語と呼ぶこととする。
  4. ↑ 特定の固有名詞が代入されていない P(x) のような表現は命題を意味しない。つまり真偽の判断をすることはできない。
  5. ↑ さらに、全称記号と存在記号の意味から次の命題の等価性が成り立つ。
    ∃ x . A(x) ≡ ¬∀ x . ¬A(x) （ある x は A である ≡ すべての x について A ではない、は成り立たない）
    ∃ x . ¬A(x) ≡ ¬∀ x . A(x) （ある x は A ではない ≡ すべての x について A である、は成り立たない）
    ¬∃ x . A(x) ≡ ∀ x . ¬A(x) （ある x は A である、は成り立たない ≡ すべての x について A ではない）
    ¬∃ x . ¬A(x) ≡ ∀ x . A(x) （ある x は A ではない、は成り立たない ≡ すべての x について A である）
  6. ↑ ヒルベルト、アッケルマン(1954) p.198
  7. ↑ そのため、公理的集合論においては、論理的パラドックス（ラッセルのパラドックスなど）を避ける手法を述語論理からそのまま使い回す事ができる。
  8. ↑ このような公理的集合論は、エルンスト・ツェルメロ、アドルフ・フレンケル、ジョン・フォン・ノイマン 、パウル・ベルナイスらによって大いに発展し、パラドックスに対しても安全であるとされる。
  9. ↑ ヒルベルト、アッケルマン(1954) p.198
  10. ↑ 命題論理においては恒真（tautology）であることを言う。
  11. ↑ 命題論理においては恒偽であることを言う。
  12. ↑ これは完全に解決可能であり、与えられた複合命題を連言標準形に変形し各選言項が恒真であるかどうか（排中律の項を含んでいるかどうか）を確認すればよい。

関連項目

テンプレート:Col-begin テンプレート:Col-break

テンプレート:Col-break

テンプレート:Col-break

テンプレート:Col-end

関連人物

テンプレート:Col-begin テンプレート:Col-break

テンプレート:Col-break

テンプレート:Col-break

テンプレート:Col-break テンプレート:Col-end

参考文献

テンプレート:数学 テンプレート:Logic テンプレート:哲学

「http://wikippe.e-do-match.com/index.php?title=数理論理学&oldid=7437」から取得