Web教材一覧ハードウェアとソフトウェア

数理論理学

キーワード

命題論理、論理計算、述語論理、∀、∃、様相論理、意味論


「ソクラテスは人間である」「すべての人間は死ぬ」という命題から「ソクラテスは死ぬ」という命題を導くような推進法則を研究することを論理学といいます。このような論理を記号を用いて研究することを記号論理学といいます。記号論理学では、数学的な方法を利用するので、数理論理学ともいいます。
 数理論理学は、取り扱う範囲の観点から命題論理述語論理様相論理に区分できます。

命題論理
「1時間以上勉強する」という命題をA、「眠くなる」という命題をBというように、命題を記号で表現します。
このとき、「1時間以上勉強する」ことと、「眠くなる」ことが共に成立する(真である)ことを A∧B(論理積)、「1時間以上勉強すると、眠くなる」ことを A⇒B(含意)と表わします。これを論理式といい、論理式の真・偽を計算したり、複雑な論理式を単純な論理式にすることを論理計算といいます。
¬A  否定  (Aでない)
A∧B 論理積 (AかつB)
A∨B 論理和 (AまたはB)
A→B(A⇒B、A IMP ) 含意・内包 (AならばB)
A⇔B(A EQV B)同値 (AとBは同値)
述語論理
述語論理は、命題論理の拡張と考えられます。
  • 例えば、x={1、2、…、n}という値を表すと、それを2倍するという述語記号fを導入して f(X) とすれば、「Xが自然数である」が真であるとき、「f(x) は偶数である」は真であるというような論理を扱います。
  • そして、「yが偶数である」ことを真とする述語記号をpとして、「p(f(x)) が真である」と表現します。
  • さらに、「すべての自然数xについて、p(f(x)) が真である」という命題を、全体を表す論理記号∀を用いて「∀x,p(f(x)) (xは自然数)」と表記します。
  • 存在を表すには論理記号∃があります。「すべての自然数xのなかには、少なくとも1個以上の偶数が存在する」という命題は「∃x,p(x) (xは自然数)」と表記します。
様相論理
様相論理では、論理式から論理式を導き出す推論規則を展開したものです。含意(→)や同値(⇔)が主要な記号になります。
  • 「ソクラテス」をP、「人間である」をQ、「死ぬ」をRとすれば、「ソクラテスは人間である」はP→Q、「すべての人間は死ぬ」は、Q→Rと表記します。
  • 「ソクラテスは死ぬ」という三段論法の結論を導くのは、P→Q、Q→RからP→Rを計算することだといえます。
  • 一般化して厳密に表記するならば、「どんなxを取っても、P→Q、かつ、Q→Rが成り立つとき、P→Rが成立する」ことは、
       ∀x {(P(x) → Q(x)) ∧ (Q(x) → R(x))} ⇒ P(x) → R(x)
    となります。
    様相論理では、記号化した命題を、このような推論規則の公式を用いて論理を進めます。

また、数理論理学は研究する分野から意味論証明論に区分されます。

意味論
論理式で記述される命題の「意味」を、何らかの数学的対象に変換することを重視した研究する分野です。
証明論
記号化された命題をいかに解くかを重視した研究分野です。

補足

「同値」について
二つの命題が同値であるとは、例えば「P:数学ができる」⇔「Q:頭が良い」は、「数学ができる人は頭が良い」という命題と同じだという意味です(実社会でこれが真か偽か不明ですが真としておきます)。
「同値」のときは、PとQを入れ替えても同じです。
   P Q P⇔Q
 1 真 真  真(数学ができる人は頭が良い、頭が良い人は数学ができる)
 2 真 偽  偽(数学ができる人は頭が悪い、頭が悪い人は数学ができる)
 3 偽 真  偽(数学ができない人は頭が良い、頭の良い人は数学ができる)
 4 偽 偽  真(数学ができない人は頭が悪い、頭の悪い人は数学ができない-1の対偶)

「含意」について
「PならばQである」を「P→Q」と表現します。そして、Pを前提、Qを結論といいます。
同値と異なるのは、前提→結論の順序であり、結論→前提にはならないという点にあります。
例えば、Pを「あの人は数学ができる(P)。だから、あの人は頭が良い(Q)」の命題が真であるとします。
   P Q P→Q
 1 真 真  真(あの人は数学ができる。だから、あの人は頭が良い)
 2 真 偽  偽(あの人は数学ができる。だから、あの人は頭が悪い)
 3 偽 真  真(あの人は数学ができない。だから、あの人は頭が良い)
 4 偽 偽  真(あの人は数学ができない。だから、あの人は頭が悪い)

ここで3が気になります。しかし、含意の場合は、「数学ができれば頭が良い」といっているだけで、「頭が良いのは数学ができることだ」とはいっていない(結論→前提ではない)のです。数学ができなくても頭の良い人がいることもあります。「前提が崩れている場合は、どのような結論も正しいといえる」ので、3と4が真になるのです。
論理演算の演算記号
論理演算は確率論でも重要な分野で、論理積や論理和など数理論理学と同じような概念をもっています。集合論でも和集合や積集合の概念があります。学問の分野により、用いる記号が異なります。
        数理論理学 確率論  集合論
   否定    ¬A        Ac
   論理和   A∨B  A+B  A∪B
   論理積   A∧B  A×B  A∩B
しかし、ベン図や真理値表など、計算方法はどれも同じですので、あまり気にしなくてもよいでしょう。
確率論での記号に関しては「論理演算」(stat-ronri-enzan)、 集合論での記号については「集合の基礎」(hs-syugou)を参照してください。