この記事は現在、プロジェクトメンバーによる査読中のものです。草稿段階ですので、内容・表現の正確さについて責任を負いかねます。 リンクを正しく張れていないところが存在しますのでご注意ください。 正式公開まで、いましばらくお待ちください。
数学のレシピ (09) --述語論理の記号と文法 (1)--

この記事は数学のレシピ (08) の続きです.まだ数学のレシピ (08) をお読みでない方は,そちらを先にお読み下さい.

述語論理の記号と文法

前回までで,命題論理に関する記号,文法,基礎的な定理の証明,そして命題論理の意味論に関する勉強をしてきました.今回からは,一階の述語論理 (first order predicate logic) に関するお話しになります.

命題論理と (一階の) 述語論理との違い

命題論理と (一階の) 述語論理との違いを説明する為に,「 A 子さんはテニスをする」という命題を考えてみましょう.命題論理では,この命題は,即ち,論理式で,例えば P などの命題変項で表しました.しかし,述語論理では,この命題を主語,即ち「 A 子さん」と述語「テニスをする」に分けて表します.そして,主語である「 A 子さん」を「固体記号」 (例えば「 A 子」) で表し,述語である「テニスをする」を「述語記号」 (例えば「テニス ( \ast ) 」) で記号化します.ここで, ( \ast ) の \ast には固体記号が入ります.すると,この「 A 子さんはテニスをする」という命題は,「テニス (A 子)」と表す事が出来ます.そうすれば,命題「 B 太郎君はテニスをする」は「テニス (B 太郎)」と記号化する事が出来ますね.

次に,「 A 子さんは B 太郎君を愛している」という命題は,固体記号「 A 子」と「 B 太郎」,そして,述語記号「愛する ( \ast , #)」 (ここで, \ast 及び # には固体記号が入ります) を用いて,「愛する (A 子, B 太郎)」と記号化する事が出来ます.すると,この命題は, A 子さんと B 太郎君との関係を表しています.

これらの例では,述語記号には固体記号を一つもしくは二つ取る場合を考えましたが,もっと一般的に,有限個の固体記号を取る述語記号を考える事が出来ます. n 個の固体記号を取る述語記号の事を一般的に n 項述語記号と呼びます.

更に,述語論理では,「全ての人はテニスをする」という命題や,「テニスをする人が存在する」という命題を扱う事が出来ます [*] .これらの命題は,まず,「 x はテニスをする」という命題を考え,述語記号「テニス ( \ast )」と固体変項 x を用いて「テニス ( x )」と表し,更に,「全ての」を表す量化記号 {}^{\forall} を用いて,「 {}^{\forall}x テニス ( x )」と表します.また,「存在する」を表す量化記号 {}^{\exists} を用いて,「 {}^{\exists}x テニス ( x )」で「テニスをする人が存在する」という命題を表します.

[*]ここで,何を以て「全て」とするかやどこに「存在する」のかは,一旦措いておいて下さい.これらの問いが問題になってくるのは述語論理の意味論からです.それまでは形式的世界での話ですから,何を意味しているのか,それは考えてはいけないのです.それに,テニスをするとはどういう事か,愛するとはどういう事か,その意味も形式的世界では考える必要はないのです.ただ単に記号列として見て下さい.勿論,このような形式的世界と現実世界との橋渡しが必要になるでしょう.それは述語論理の意味論で扱います.

さて,次節で,一階の述語論理に於ける記号を定義しましょう.この一階の述語論理体系の事を「体系 \rm{M_{1}} 」と呼ぶ事にしましょう.

一階の述語論理の記号

体系 \rm{M_{1}} において使う事の出来る記号は以下の通りです [†]

(定義 09-01)

  1. 論理記号: \neg ,\, \longrightarrow ,\, {}^{\forall} ,\, {}^{\exists}
  2. 固体変項: x,\, y,\, z,\, \ldots ,\, x_{1},\, x_{2},\, \ldots
  3. 固体定項: c ,\,  c_{1},\, c_{2},\, \ldots 及び有限個の任意の固有名詞
  4. 述語記号: P(\ast ),\, Q({\ast}_{1} ,\, {\ast}_{2} ),\, R({\ast}_{1}, \, {\ast}_{2} ,\, {\ast}_{3} ,\, \ldots ,\, {\ast}_{n} ),\, \ldots
  5. 括  弧: (,\, )

固体変項と固体定項とを併せて項と呼びます.

[†]論理記号のうち, {}^{\forall}{}^{\exists} との事を特に量化記号とも呼びます.また, {}^{\exists} は, {}^{\forall} を用いて表す事が出来るので,これを補助論理記号であると定義する事もあります.本レシピでは, {}^{\exists} も論理記号の中に入れておきます.

文法

次に体系 \rm{M_{1}} における文法を考えてみます.体系 \rm{M_{1}} における論理式を以下のように定義します.

(定義 09-02)

  1. P({\ast}_{1}, \, {\ast}_{2} ,\, {\ast}_{3} ,\, \ldots ,\, {\ast}_{n} )n 項述語記号で, t_{1},\, t_{2},\, t_{3},\, \ldots ,\, t_{n} が項であれば, P(t_{1}, \, t_{2} ,\, t_{3} ,\, \ldots ,\, t_{n} ) は論理式である.特にこの形の論理式の事を原子論理式と呼ぶ.
  2. A が論理式であれば (\neg A) は論理式である.
  3. AB が両方とも論理式であれば (A \longrightarrow B) は論理式である.
  4. A が論理式であれば,任意の固体変項 x に対して, ({}^{\forall}xA) 及び ({}^{\exists}xA) は論理式である.
  5. 以上の定義から論理式と判断できる物だけが論理式である.

なお,一般に論理式の事を P, \; Q, \; P_{1}, \; P_{2}, \; P_{n} 等と書く事があります.また,ある論理式が個体変項 x を含む事を明示する場合には,「論理式 P(x) 」と,個体変項 x_{1}, \; x_{2}, \; \ldots ,\; x_{n} を含む場合には,「論理式 P(x_{1}, \; x_{2}, \; \ldots ,\; x_{n}) 」と書く事があります.

補助記号

以下に示す補助記号を用いる事にします.これは命題論理,即ち,体系 \rm{M_{0}} での補助記号と同じです.

  1. 補助論理記号: \vee ,\, \wedge ,\, \longleftrightarrow
  2. 括    弧: [,\, ],\, \{ ,\, \}

これらの補助記号は,体系 \rm{M_{1}} での文章が長くなりすぎるのを防ぐ為や体系 \rm{M_{1}} での文章を分かり易くする為に用いる記号です.ですから,これらの補助記号は,本質的にはなくても問題のない物です.

これらの補助記号は以下のように定義されます.ただし, A 及び B はどちらも論理式であるとします.

Def-Or: \vee
論理式 ((\neg A) \longrightarrow B) のことを (A \vee B) と記す.
Def-And: \wedge
論理式 (\neg ((\neg A) \vee (\neg B))) のことを (A \wedge B) と記す.
Def-Equ: \longleftrightarrow
論理式 ((A \longrightarrow B) \wedge (B \longrightarrow A)) のことを (A \longleftrightarrow B) と記す. この AB の関係の事を同値 (equivalent) と言います.

また,括弧 ( [,\, ],\, \{ ,\, \} ) は通常の括弧 ( ( \, ) ) が連続して使われている時等,見づらいときに使う事にします.これも見やすくする為の記号ですので,本質的にはなくても問題のない物です.

括弧の省略規則

この規則も命題論理,即ち体系 \rm{M_{0}} の括弧の省略規則と同じであります.ただし,量化記号 {}^{\forall} ,\, {}^{\exists}\neg と同じ結びつきの強さであるとします.

復習の為に,括弧の省略規則を書いておきます.論理式が冗長になる事を防ぐ為に,誤解の虞がない場合に限り,かっこを省略しても良い事にします.まず,一番外側の括弧は省略しても良い事にします.次に,論理記号同士の結びつきの強さ [‡] を以下のように定義し,結びつきの関係が明らかな括弧は省略しても良い事にします.

  • (\longrightarrow ,\, \longleftrightarrow ) \, < (\vee ,\, \wedge ) \, < \left( \neg ,\, {}^{\forall} ,\, {}^{\exists} \right)

これも命題論理,即ち体系 \rm{M_{0}} でも触れましたが,この括弧の省略規則は,「省略しても良い」という規則であって,「必ず省略しなければならない」という規則ではありません [§] .ですから,混乱しないように,必要に応じて省略しても良いかっこを省略せずに書く事もあります.

[‡]もう一度,四則演算及び冪の結びつきの強さを復習しておきましょう. (+ ,\, -) \, < (\times ,\, \div ) \, < 累乗 (冪) つまり, 2 + 3 \times 5^{7} という数式は, 2 + (3 \times (5^{7})) を表しています. ((2 + 3) \times 5)^{7} と表す場合との違いに注意して下さい. それと同様に, \neg A \longrightarrow B \vee C という論理式は ((\neg A) \longrightarrow (B \vee C)) を表しています. (\neg ((A \longrightarrow B) \vee C)) 等との違いに注意して下さい.
[§]省略する事の出来る括弧を全て省略した論理式というものも後々出てきます.省略する事の出来る括弧を全て省略した論理式の事を正規論理式と呼びます.