述語論理 Predicate Logic


|| 数学の言語の述語について

一言で言うと、こいつは数理論理学の「用語」です。

「記号」で表せる「形式体系」共のことを、まとめてこう呼んでます。

範囲は結構広いです。

スポンサーリンク




目次


・数学の言語

   一階述語論理「数学の基礎知識」

   二階述語論理「一階述語論理より幅広い表現ができるやつ」

   高階述語論理「表現の幅が更に拡張されたやつ」


無限論理「無限に長い文を許しちゃう理屈」



量化記号の概要

   全称量化「全ての(もの)は(条件)を満たす」

   存在量化「(条件)を満たす(もの)が存在する」







一階述語論理 First-Order (PL)


|| 数学の基礎そのものと言って良いレベルのもの

個体(変数)」の「量化」だけ許してる、

「命題論理」を拡張した述語論理のことです。



述語論理っていうと、これのことを指す場合もあるくらい代表的です。

述語論理におけるメイントピックは間違いなくこいつ。




なんでこれがメインかというと、

これだけ「完全性」と「健全性」が証明されてるからです。



ちなみに完全性というのは「正しけりゃ証明できちゃうぜ」って感じ。

健全性は「証明できるなら正しいぜ」って感じ。

ややこしいんで完全性だけ覚えましょう。




こいつはまあ「一階」って言ってますが、

「二階」「高階」から削りに削って出来上がったものです。



そんな感じで、これはだめあれもだめをひたすら繰り返して、

色々と性質を確認して、ようやく得られた集大成になります。



一階という字面のせいであれですが、

基本というよりは「成果」と言うべきものになります。




そんなわけなので「数学と論理学の成果」って感じのものになります。

だからこそ「数学の言語」として、これが最も適しているわけです。







二階述語論理 Second-Order (PL)


「個体(変数)」だけじゃなく「関数」と「述語」もOKなやつ。

一階述語論理を拡張したものです。




割と実用的ではあります。

推論は妥当(正→正)なもので、健全性は確かです。

なので、これをベースに推論を行っても基本的には大丈夫です。



ただ、完全性は今のところ保証されていません。

実効性の面で、今後も保証されない可能性が高いです。

なので、なんで正しいのかを「証明」することはできません。



ここで「実効性」(決定可能性)というやつが出てきました。

これについては、詳しくは「再帰理論」でやります。

ざっと言うと「正しいのか確実に確認できる」みたいな性質です。






二階の文法規則(量化して良いやつについて)


t が一階の「項」なら「 t∈S 」も原子論理式で良いよ

要は『個体だらけ(まだ真偽不明)の集合』も、

『二階では』個体扱いしちゃいますってこと。



・項「 t_1,t_2,...,t_n 」で関数記号「 f 」なら、

f(t_1,t_2,...,t_n) 」も原子論理式ってことにしてOK

(関数でもOKってこと)



・関係でも同じ( = とか とか )

「自然数 k 」(なんでも良い)で、「 k 項関係 R 」なら、

R(t_1,t_2,...,t_k) 」も原子論理式ってことで。

(要は述語のことね)




こうするとこんなのもいける。(一階じゃダメ)

∀S∃t\,(t∈S),∀x∃f\,(f(x)=x),∀R∀t\,(R(t))

(ちょっと変なのばっかり書いてみた)







高階述語論理 Higher-Order (PL)


二階述語論理の「拡張のやり方」を延々と繰り返したやつです。

もはやなに言ってるか分からんものでも許しちゃいます。




あれもそれもこれも、なんでも「量化」して良いです。

それをぐちゃっとしたものを更に「量化」したものもOKです。



もうなにを「量化」しても許しちゃうぜ(は?)

そんなわけでいろんなものが表現できちゃいます(真偽はどっか行く)




「階」の高さに関しては「量化」を許せる範囲の広さ、

もしくは「表現」できるものの多さ、とかだと思って大丈夫です。






一階では「個体」の量化まで許されていて、

二階では「個体の集合・ n 項関数・ n 項関係」の量化までOKです。



高階では「個体の集合の集合の集合の…」みたいな感じ。

要は制限を取っ払ってるわけですね。







無限論理 Infinitary Logic


簡単に言うと「無限? ああ、いいよいいよ」って感じのやつです。

1,2,3,... 」みたいなのを許しちゃう論理になります。



「言明(はっきりした主張)」も「証明」でもOKです。

というか、上の二つがメインになります。




なんとなく直観で分かる通り「無限」を許しちゃうので、

それがあってるかどうかの確認ができません。



帰納的に定義したりして「有限」に収めたらいけますが、

そういうのができないやつはお手上げです。

なので完全性の証明も有限の範囲じゃ無理です。




規則の概要


式「 A_α 」なら、

A_0∧A_1∧A_2∧... やら A_0∨A_1∨A_2∨... 」も、

「式」ってことにして OK みたいな感じのものになります。



この辺の詳細は、あらかた書き終わった後に追加します。




とりあえず一旦この辺りで終わりにして、

ちょくちょく出てきていた「量化」について見ていきましょうか。







量化子 Quantifier


|| 量で表すやり方

簡単に言うと、なにかの「量を指定する」こと。




これだけじゃなんだかって感じなので具体例を。



「そこにあれが少なくとも1つある」の「少なくとも~ある」とか。

全てのものには意味がある」の「全て~ある」とか。

ほとんどいけるって」の「ほとんど~」とか。

何個かちょうだい」の「何個~」とか。



こんな感じで、なんか「量を指定する」感じのことを量化と言います。






基本量化子


はい、そんな「量化」ですが、基本的なものが2つ存在します。

その二つについてざっくりと紹介をしていきましょう。



結論から行くと「全称」と「存在」のことです。(?)




説明のために、

なんらかの条件(命題)を「 A 」として(趣味であるみたいな)

その条件を満たすものを「 x 」としましょう。(読書みたいな)






全称量化 All,Any


記号だと「 ∀x\,A,∀x\,A(x),∀x\,(A),∀x\,[A(x)] 」みたいに書きます。



これの意味は、直観的なものとしては、

「 全ての x は、条件(命題) A を満たします」だとか。

「 命題 A を満たす、全ての x 」だとか。



よく見る形式的な言い回しだと、

「全ての x に対して、 A が成立する」だとか。






存在量化 Exist


記号は「 ∃x\,A,∃x\,A(x),∃x\,(A),∃x\,[A(x)] 」と書きます。

全称量化もそうですが、この辺は好みです。

(自分は一番右のが好きですね。分かり易いんで)



直観的に理解しやすい意味としては、

「条件 A を満たす x が存在しますよ」だとか。

「条件 A に合う x はある」だとか。



お堅いやつだと、

A を満たす x は存在する 」だとか。





詳細は「量化子」の別記事にて。