読者です 読者をやめる 読者になる 読者になる

だるろぐ

とてもだるだるした日記です http://about.daruyanagi.jp/

お知らせ

述語論理

論理学

すべての、任意の

全称記号(ぜんしょうきごう、universal quantifier)とは、数理論理学において「全ての」(全称量化)を表す記号である。通常「∀」と表記され、全称量化子(ぜんしょうりょうかし)、全称限量子(ぜんしょうげんりょうし)、全称限定子(ぜんしょうげんていし)、普遍量化子(ふへんりょうかし)、普通限定子(ふつうげんていし)などとも呼ばれる。

\forall x(すべての x について、任意の x について)

TeX 記法

[tex:\forall x]

ある、適当な

存在記号(そんざいきごう、existential quantifier)とは、数理論理学(特に述語論理)において、少なくとも1つのメンバーが述語の特性や関係を満たすことを表す記号である。通常「∃」と表記され、存在量化子(そんざいりょうかし)、存在限量子(そんざいげんりょうし)、存在限定子(そんざいげんていし)などとも呼ばれる。

\exists x(ある x について、適当な x について)

\exists x(P(x)) で、「P という条件に当てはまる x が存在する」ってな感じかな。

TeX 記法

[tex:\exists x]

\forall\exists で指示されている変数のことを束縛変数(bound variable)と呼び、そうでないものを自由変数(free variable)と呼ぶ。

述語

そもそも述語とは、形式論理学における命題のB(Aについて語る事柄)に当たるものを、アリストテレスがギリシア語でκατεγορωυμενον katēgoroumenonと表現したことにさかのぼるという。これが、その後ラテン語でpraedictumと表現され、論理学及び文法の用語として次第に定着、今日のヨーロッパ諸言語でも継承され(例えば英語predicate)、また他の言語でも用いられる様になり、日本でも述語と訳してきたものである(形式論理学では賓辞とも、文法では述部とも訳す)。

P(x) (たとえば、「~は素数である」「~は3歳だ」など)

TeX 記法

[tex:P(x)]

述語はその引数(?)の数に応じて、性質が決まる。

  • 0:命題
  • 1:性質
  • n:関係

述語論理は、命題論理を含んでいる。

述語論理

以上の記号と、 論理演算子 - だるろぐ で出てきた \vee \wedge \neg \to \bot を組み合わせて組み立てる。

例:ゴールドバッハ予想

「4以上のすべての偶数は、2つの素数の和で表せる」

ここでは以下の述語を仮定する。

  • G_4(x):x は4以上である
  • E(x):x は偶数である
  • P(x):x は素数である

\forall n \exists x \exists y \{(G_4(n) \wedge E(n))\to(P(x) \wedge P(y) \wedge (n=x+y)) \}

[tex:\forall n \exists x \exists y \{(G_4(n) \wedge E(n))\to(P(x) \wedge P(y) \wedge (n=x+y)) \}]

このように、述語論理さえ使えば通常の数学はすべて表現できる。

次は導出図やなぁ……