述語論理

執筆日時：

すべての、任意の

全称記号（ぜんしょうきごう、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)) \}]

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

次は導出図やなぁ……