目次
はじめに：述語論理について
みなさん、述語論理という言葉を聞いたことはあるでしょうか。
述語論理とは、文の述語に注目するタイプの論理学です。
最近はPythonをはじめとしたプログラミング言語でも用いられているので、この機会に基礎を押さえておきましょう！
論理学とは
述語論理について詳しく解説する前に、「そもそも論理学とは何か？」という問題に触れておきます。
以下の記事にも同じ内容が書かれてあるので、興味のある方はご参照ください。
論理学は、基本的に「命題論理」と「述語論理」に分けられます。命題論理が「原子文」を単位とする論理学なのに対して、述語論理は「原子文」の中身である「個体定項」と「述語」を単位とする論理学です。
……「いきなり何やら難し気な単語が爆誕したぞ」と思われたかもしれませんが、心配はご無用です。単語は堅っ苦しいですが、それほど難しい内容ではありません。
原子文とは、文としてそれ以上切り分けられない文（命題）のことです。ちなみに、切り分ける余地のある文は「複合文」と言います。
例えば、以下の2つの文を読んでみてください。どちらが原子文かわかりますか？
- 明日は新宿で雨が降るだろう。
- 明日新宿で雨が降ったら、私たちは池袋へショッピングに行く予定だ。
1つ目が “Tomorrow it will rain in Shinjuku.” というSV型の1つの文のみで構成されているに対して、2つ目は “If tomorrow it rains in Shinjuku, I’m going to go shopping in Ikebukuro.” なので、文としてはifから始まる従属節とカンマより後の主節に分けられますね。
従って、1つ目の文が原子文、2つ目の文が複合文になります。
「明日は新宿で雨が降るだろう」などの原子文をp, qなどと表して、原子文p,q同士の関係を「かつ」「または」「ならば」などの接続詞で表現して論理を作るのが命題論理です。
これに対して、原子文p,qを更に細かく分割して論理を作るのが述語論理です。
「私はショッピングに行く」という原子文について考えてみましょう。
述語論理において最初に注目されるのは述語です。この場合は「ショッピングに行く」ですね。この述語を「F」とおきます。
次に注目するのは主語（述語論理では「個体定項」と呼ばれます）。この原子文では「私」ですね。この個体定項（主語）を「c」とおきます。
ゆえに、「私はショッピングに行く」という原子文は、述語論理ではFcと表記されることになります。述語Fと個体定項cを基本要素として文を作り、「かつ」「または」「ならば」などの接続詞で文同士を繋いで論理を作るのが述語論理です。
命題論理よりも細かい単位で論理を構築するので、述語論理は命題論理の発展版と考えられますね。
以下の記事で命題論理について説明したので、この記事では述語論理について扱います。命題論理と併せて、論理学の基礎をマスターしましょう！
述語論理で用いる記号
はじめに、述語論理で用いる記号について紹介します。述語論理は、ここに登場する記号だけを使って表現されます。それほど量は多くないので、最後まで目を通してみてください。
述語論理で用いる記号①：語彙の定義
述語論理で用いる語彙（≒単語）は以下の通りです。
- ¬：でない（否定）
- ∧：かつ（連言）
- ∨：または（選言）
- →：ならば（条件法）
- ⇔：同値（双条件法）
- ( )：記号の作用域
- 例：（p→q）⊦ ¬p ∨ q
- [ ]：仮定
- { }：集合
- ∈：要素
- 例：A ∈ {A, B}：意味「Aは集合{A,B}の要素である」
- < >：順序対（順番に意味のある集合）
- ⊦ ：推論
- 例：{p} ⊦ p∨q
- 意味：pを前提にして、p∨qを推論する。
- 構文論の証明で用いる。⊦ の前が前提、後が結論になる。前提には{ }をつける。前提が複数個ある場合は{p,q}のように , で繋ぐ。）
- ⊧：論理式の充足
- 詳しくは「述語論理の意味論」を参照
- ⊨：論理的帰結
- 例：φ ⊨ ψ
- 意味：φを前提にして、ψを帰結する。
- 意味論の証明で用いる。⊦ （推論）と違って、前提に{ }を必要としない。なお、⊧（論理式の充足）とは無関係である。この記事では横棒の長さで両者を区別するので、注意して見てほしい。横棒が長ければ論理的帰結、短ければ論理式の充足を意味する。
- p, q ：命題
- 述語論理では使わないが、公理の説明で利用する。
- F, G：一項述語
- 例：「ソクラテスは人間である」という文は、1つの項（ソクラテス）と1つの述語（人間である）で成立している。このような文に登場する述語を「一項述語」と呼ぶ。
- R：二項述語
- 例：「太郎は花子を愛している」という文は、2つの項（太郎・花子）と1つの述語（愛している）で成立している。このような文に登場する述語を「二項述語」と呼ぶ。
- c：個体定項
- 例：「ソクラテスは人間である」という文をFcと表すと、c（＝ソクラテス）が個体定項に当たる。
- a, b ：自由変項
- 例：「ソクラテスは人間である」という文の「ソクラテス」という個体定項が不明である場合、「aは人間である」と表記される。「aは人間である」は文ではなく（意味が決まっていないから文にならない）、「論理式」と呼ばれ、aは「自由変項」と呼ばれる。cが定数、a・bが変数と考えれば良い。
- ∀：すべての（全称）
- 例：「全てのxに対して『xは人間である』が成立する」＝∀xFx
- ∃：ある（存在）
- 例：「『xは人間である』を満たすxが存在する」＝∃xFx
- x, y：束縛変項
- 「aは人間である」という論理式をFaと表す。この論理式を存在量化すると「『xは人間である』を満たすxが存在する」となり、この論理式は「∃xFx」と表される。∀・∃を使う場合、論理式の項である自由変項aが束縛変項xになることに注意。
- φ, ψ：文と論理式を表すメタ変項
- メタ変項とは、文法について説明する際にのみ用いられるメタ言語（言語を説明するのに使う言語）である。大文字のΦ、Ψも同義。文法説明以外では用いないので注意。
- α：個体定項を表すメタ変項
述語論理で用いる記号②：文と論理式の定義
述語論理の語彙について説明する際、特に注釈なく「文」と「論理式」という言葉を使っていましたが、ここで改めて文・論理式を定義しておきます。先ほど定義した語彙を使っていくので、語彙の部分を参照しつつ読んでみてください。
- Fcは原始文である
- Rc1c2は原始文である（※c1, c2はcと同じく個体定項。二項述語は個体定項を2つ必要とするので、添字を使って2つの個体定項を区別している。）
- 原始文は文である
- Faは原始論理式である
- Rabは原始論理式である
- 原始論理式は論理式である
- φが文ならば、¬φも文である
- φが論理式ならば、¬φも論理式である
- φとψがともに文ならば、φ∧ψ、φ∨ψ、φ→ψも文である
- φとψのどちらか一方でも論理式ならば、φ∧ψφ∨ψ、φ→ψも論理式である
要するに、一つでも自由変項が含まれていれば論理式になり、全ての項が個体定項ならば文になる、ということです。
述語論理の構文論
述語論理の構文論①：述語論理で用いる公理
ここまで、述語論理で用いる記号を解説してきました。ここからは、いよいよ本格的に論理の文法の説明に入ります。
記号論理では、いくつかの公理（証明不要な推論）から、派生的にどんどん推論を作っていきます。推論の起点になる公理は以下の12個です（うち、命題論理でも使う公理が8つあります）。
命題論理の公理
- 連言導入則：{p, q} ⊦ p∧q
- 連言除去則：{p∧q} ⊦ p, {p∧q} ⊦ q
- 選言導入則：{p} ⊦ p∨q, {q} ⊦ p∨q
- 選言除去則：{p∨q, [p]…r, [q]…r} ⊦ r
- [p]…rは、「pを仮定することでrが導出される」という意味。「…」は、途中の推論過程を省略する記号。以下同様。
- 条件法導入則：{[p]…q} ⊦ p→q
- 条件法除去則：{p, p→q} ⊦ q
- 否定導入則：{[p]…q∧¬q} ⊦ ¬p
- 否定除去則：{¬¬p} ⊦ p
述語論理の公理
- 全称汎化：{Φα} ⊦ ∀xΦx
- 以下の条件を満たす場合に成立する
- ∀xΦxにαが含まれない
- Φαが依存する前提と仮定にαが含まれない
- （※全称汎化の例は以下の【補足】を参照）
- 全称例化：{∀xΦx} ⊦ Φα
- 例：「全てのxについて『xは人間である』が成立する」という前提から、「ソクラテスは人間である」を結論づける。
- 存在汎化：{Φα} ⊦ ∃xΦx
- 例：「ソクラテスは人間である」という前提から、「あるxについて『xは人間である』」を結論づける
- 存在例化：{∃xΦx, [Φα]…ψ} ⊦ ψ
- 以下の条件を満たす場合に成立する
- ψと∃xΦxにαが現れない
- ψが依存する前提にαが現れない
- ψが依存する仮定にαが現れない（ただしΦαは除く）
- 例：「あるxについて『xは人間である』」という前提と、「『ソクラテスは人間である』を仮定したとき、『全ての人間は死ぬ』を導出できる」という前提から、「全ての人間は死ぬ」を導出する
【全称汎化についての補足】
全称汎化は、例えば「ソクラテスは人間である」という前提から「全てのxについて『xは人間である』が成立する」という結論を導く推論である。
この公理のポイントは、Φαだけでは∀xΦxを導けない点にある。例えば以下の推論は不成立である。
{Fa} ⊦ ∀xFx
「依存する前提・仮定」とは、推論の起点となる論理式・文を指すのだが（例えば{Ga ⊦ Fa} ⊦ ¬Ga ∨ Fa ならば、GaはFaが依存する仮定になる）、Faが依存する前提はこの場合Fa自身になる。Faにaが含まれているので、全称汎化は成立しない。
一方で、以下の推論は＿＿何の意味もない推論だが＿＿成立する。
{∀xFx ⊦ Fa} ⊦ ∀xFx
「全てのxに対して『xは人間である』」という前提から「ソクラテスは人間である」を導き、「ソクラテスは人間である」という前提から「全てのxに対して『xは人間である」という結論を導き直している。全く意味のない推論（前提と結論が一致する）だが、全称汎化について有益な示唆を与える推論である。
∀xFx ⊦ Faという推論は「全称例化」と呼ばれる公理（後述）に基づいている。この場合、Faが依存する前提は∀xFxである。Faの前提となる∀xFxにaが含まれておらず、結論となる∀xFxにもaが含まれていないので、全称汎化が成立する。
以上からわかる通り、全称汎化を用いる場合には、Φα（例えばFa）の前提・仮定として何か別の文・論理式が必要になる。ぜひ注意して使ってもらいたい。
【補足おわり】
述語論理の構文論②：述語論理の公理を使った証明
12個公理を紹介しましたが、「暗記しろ！」というつもりはありません。公理は証明で使っていくうちに覚えるものですから。
というわけで、早速以下の推論を証明に挑戦してみましょう。
{∃x(Fx∨Gx)} ⊦ ∃xFx ∨ ∃xGx
Fxを「xは人間である」、Gxを「xは高校生である」とすると、「『人間であるか、または高校生である』ような人が存在する」という前提から「人間である人が存在するか、または高校生である人が存在する」という結論を導く推論になります。早速証明しましょう。
- Faを仮定する
- Gaを仮定する
- ①の仮定Faに存在汎化を適用すると、∃xFxが導出できる
- ③で導出した∃xFxに選言導入則を適用すると、∃xFx ∨ ∃xGx が導出できる
- ②の仮定Gaに存在汎化を適用すると、∃xGxが導出できる
- ⑤で導出した∃xGxに選言導入則を適用すると、∃xFx ∨ ∃xGx が導出できる
- Fa∨Gaを仮定する
- ⑦の仮定Fa∨Ga、及び①の仮定Faからの導出結果∃xFx ∨ ∃xGx、②の仮定Gaからの導出結果∃xFx ∨ ∃xGx。以上3つを前提として選言除去則を適用すると、∃xFx ∨ ∃xGxを導出できる
- 前提∃x(Fx∨Gx)と、⑦の仮定Fa∨Gaからの導出結果∃xFx ∨ ∃xGx。以上2つを前提として存在例化を適用すると、∃xFx ∨ ∃xGxが導出できる
この証明だけを見ても理解はできないと思うので、自分で手を動かしながら証明してみてください。
述語論理の意味論
構文論では、一つの文が正しいかどうか（例：Fc = 「ソクラテスは人間である」の真偽）は考えてきませんでした。構文論での推論は、文の真偽に関係なく実行可能だからです。
しかし現実には、文の真偽によって推論結果が変わることの方が多いはずです。そんな場合には、どのように推論すれば良いのでしょうか。
そこで使うのが意味論です。述語論理における意味論は「モデル論的意味論」とも呼ばれます。ぜひ最後まで読んでみてくださいね。
述語論理の意味論①：モデルと付値関数による論理式の充足
先ほど「文の真偽」という表現を使いましたが、述語論理の意味論のスタート地点は、文ではなく論理式になります。論理式の条件によって、文の真偽が決まるからです。
例えば、「太郎は殺人犯である」という文の真偽を考えたいとしましょう。この文の真偽は、「太郎は殺人犯であり得るかどうか」ということを軸に判断されるはずです。
これを述語論理風に言い直すと、
論理式Fa（ = 「aは殺人犯である」）の自由変項aに、個体定項「太郎」が入りうるか？
になります。
自由変項aに個体定項c (=太郎）が入ることによって、FaがFc (= 「太郎は殺人犯である」）になり、意味（＝真偽）が決まります。この意味の決定を「充足」と呼び、厳密には
論理式Faが、対象「太郎」によって充足される
と表現されます。述語論理の意味論では、文の意味を論理式の充足によって検討していきます。
※ここでいう「対象」とは、言語a（自由変項）を表現するメタ言語（「太郎」）を指しています。
この充足の理論を、もう少し汎用性のある形に整形したのが「モデル論」です。
モデル論において、論理式の充足は以下のように表現されます。
Mi ⊧ ηj Fa
意味：モデルMi（=<Di, Ii>）の下で、論理式Faは、付値関数ηj（読み：エータ・ジェイ）の値となる対象γ （=ηj(a)）によって充足される（※i, jは添字で、1以上の自然数になる）
モデルMiは、対象領域Diと解釈関数Iiによって規定された順序対です……と言っても意味不明だと思うので、Diから順番に説明します。
対象領域Diとは、簡単に言うと「登場人物」です。今から扱う論理式・文に登場する対象は〇〇と△△ですよーーと宣言するのがDiの役割です。
例えばこんな感じですね。
D1 = {太郎、花子}
対象を列挙するので、集合として表現できます。
続いて解釈関数Iiを解説します。実例をみてもらったほうが早いので、D1= {太郎、花子}を使いつつ例を示します。
I1(F) = {太郎、花子} = {X | Xは人間である}
I1(R) = {<太郎、花子>} = {<X,Y> | XはYを愛している}
I1(c1) = 太郎、I1(c2) = 花子
解釈関数は、一項述語と二項述語と個体定項を解釈します。
I1(F)の場合、「Xは人間である」のXに入ることができる項は「太郎」と「花子」である、と解釈しています。I1(R)の場合（二項述語）の場合も同様です。
I1(c1), I1(c2)は、個体定項c1, c2の値になるのが、それぞれ「太郎」と「花子」である、と解釈しています。今回は対象が2つなので個体定項も2つですが、対象領域Diによって規定される対象の数に応じて、Iiが解釈すべき個体定項の数も変わってきます。
以上を整理すると、M1 =<D1, I1>は
D1 = {太郎、花子}
I1(F) = {太郎、花子} = {X | Xは人間である}
I1(R) = {<太郎、花子>} = {<X,Y> | XはYを愛している}
I1(c1) = 太郎、I1(c2) = 花子
と整理できます。モデルMiは、常に
- 対象領域Di
- 一項述語の解釈Ii(F)
- 二項述語の解釈Ii(R)
- 個体定項の解釈Ii(c)
の4要素によって成立していることを覚えておいてください。
さて、M1に基づくと、
「太郎は人間である」という文は真になります。論理式Fa「aは人間である」が、c1=太郎によって充足されるからです。
M1の下では、Fa「aは人間である」を充足させられる対象は「太郎」と「花子」の2つです。
Faの自由変項aに、「太郎」と「花子」が入りうる。このことを、述語論理では以下のように示します。
η1(a) = 太郎、η2(a) = 花子
ηは付値関数と呼ばれます。自由変項aに定まった値を付与する関数、という意味です。
論理式の自由変項がとる値はDiによって決まるので、モデルMiが決まった後で初めて付値関数のとる値も決まります。
「論理式の自由変項に何の値を与えると充足するのか」を付値関数で明確にすることで、
Mi ⊧ ηj Fa
：モデルMiの下で、論理式Faは、付値関数ηjの値となる対象γによって充足される
という充足の理論が使いやすくなります。モデルMiの中の解釈に似た作業をもう一度やることになるので、最初は面倒かもしれませんが、以下で紹介する充足条件を踏まえるとその良さが実感できるはずです。
述語論理の意味論②：充足条件
充足条件には、その名の通り「論理式がどんな条件で充足するのか」が示されています。9種類あるので、1つずつご紹介します。
- Mi ⊧ ηj Fa ⇔ ηj(a) ∈ Ii(F)
- Mi ⊧ ηj Fc ⇔ Mi ⊧ Fc ⇔ Ii(c) ∈ Ii(F)
- Mi ⊧ ηj Rc1c2 ⇔ Mi ⊧ Rc1c2 ⇔ <Ii(c1), li(c2)> ∈ Ii(R)
- Mi ⊧ ηj ¬φ ⇔ Mi ⊭ ηj φ
- Mi ⊧ ηj φ∧ψ ⇔ Mi ⊧ ηj φ かつ Mi ⊧ ηj ψ
- Mi ⊧ ηj φ∨ψ ⇔ Mi ⊧ ηj φ または Mi ⊧ ηj ψ
- Mi ⊧ ηj φ→ψ ⇔ Mi ⊭ ηj φ または Mi ⊧ ηj ψ
- Mi ⊧ ηj ∀xΦx ⇔ 任意のηkにより、Mi ⊧ ηk Φα
- Mi ⊧ ηj ∃xΦx ⇔ あるηkにより、Mi ⊧ ηk Φα
改めて見てみると、論理学の文法って本当に呪文ですね。大丈夫です。こんなもの、覚える必要はありません。証明で必要になるときに、適宜使えるようになっていれば良いのです。
述語論理の意味論③：モデル論的意味論による証明
呪文のような充足条件に少しでも慣れるために、一つ証明に挑戦してみましょう。お題はこちらです。
M1 =<D1, I1>が
D1 = {太郎、花子}
I1(F) = {太郎、花子} = {X | Xは人間である}
I1(R) = {<太郎、花子>} = {<X,Y> | XはYを愛している}
I1(c1) = 太郎、I1(c2) = 花子
であるとき、
M1 ⊨ ηj Fc1 ∧ ¬Fc2
が成立しないことを示せ。
（証明）
M1 ⊨ ηj Fc1 ∧ ¬Fc2
⇔ M1 ⊨ ηj Fc1 かつ M1 ⊨ ηj ¬Fc2（条件⑤）
⇔ M1 ⊨ ηj Fc1 かつ M1 ⊭ ηj Fc2（条件④）
⇔ M1 ⊨ Fc1 かつ M1 ⊭ Fc2（条件②）
⇔ I1(c1) ∈ I1(F) かつ I1(c2) ∉ I1(F)（条件②）
⇔ 太郎 ∈ {太郎、花子} かつ 花子 ∉ {太郎、花子}（モデルM1）
「花子 ∉ {太郎、花子}」が偽なので、不成立。
証明のコツは、元の式を条件④〜⑨を使ってシンプルにして、最終的に条件①〜③を使って成立/不成立を示すことです。慣れれば簡単なので、ぜひチャレンジしてみてくださいね。
おわりに：述語論理のまとめ
いかがでしたか？
この記事では、述語論理で用いる記号から、構文論の証明・意味論の証明まで説明してきました。
読んでいるだけでは理解できなかった箇所がたくさんあったと思います。論理学は、数学と同じで問題を解くことで徐々に本質を理解できる類の学問です。
以下に、練習問題がたくさん付いている論理学の参考書を紹介しますので、述語論理の理解を深めたい方はぜひ読んでみてくださいね。
- 金子祐介『論理と分析——文系のための記号論理入門』、2019年、晃洋書房（Amazonリンクはこちら）
- 金子祐介『文系のための記号論理入門——命題論理から不完全性定理まで』、2021年、朝倉書店（Amazonリンクはこちら）
- 藤村龍雄『よくわかる記号論理』、2005年、勁草書房（Amazonリンクはこちら）
それでは！！！
