第3章：述語論理 (1)

第 3 章述語論理 (1)
3.1
3.1.1
命題関数
何を行うか
今まで、ひとつの文章全体としての命題の真偽を扱ってきたが、文章をさらに細かく見ると、「· · · は ∼ である」とい
う形で、主語が何かによって真偽が定まるものが多い。例えば、「x は大学生である」という文章は、x に誰が入るかに
よって、真偽が定まる。このような主張は、「x をどうとったときになりたつことなのか」、「x の範囲をどう定めるか」
に注意する必要がある。例えば、
「コミュニケーション能力がある人は志望する職業につくことができる」という主張が、
「コミュニケーション能力があって志望の職業についた人がいる」ということを意味しているのか、「コミュニケーショ
ン能力がある人の全てが志望の職業につける」ということを意味しているのかは大きな違いである1 。
3.1.2
定義
主語 x によって真偽が定まる主張を、
主語 x を「変数」とし、値として T または F をとる関数のようなもの
と考えることにする。
定義 3.1 x を定めると命題になる文 P (x) を命題関数または述語という。x を（命題）変数または述語変数という。
例 : P (x) を「x が素数である」という命題関数とすると、
P (1) ≡ F,
P (2) ≡ T,
P (3) ≡ T,
P (4) ≡ F, · · ·
となる。（例終）
例 : P (x) を「x は x2 − 2x − 3 > 0 を満たす」という命題関数とすると、
P (1) ≡ F,
P (2) ≡ F,
P (3) ≡ F,
P (4) ≡ T, · · ·
となる。（例終）
例 : P (x) を「x は
a
（a、b は整数）の形で書ける数である」とすると、
b
( )
2
P (4) ≡ T, P
≡ T, P (π) ≡ F, · · ·
3
である。（例終）
形式的には、x の範囲を決めないで議論をするが、普通は、その考え方を適用する変数の範囲は決まっているので、それ
1 でも、その辺をアイマイにして声高に自分の考えを主張している人は多い（笑）
17
を前提に考える場合が多い。変数の範囲を変域ということにする。その辺のことは、集合の記法を使えばある程度明確
になるが、集合について考えるときに、少しだけこれから行う議論を使うので、きちんと定式化するのはその後にする。
問 : 主語 x によって、真偽が異なるような命題関数の例を考えよ。
3.1.3
命題関数の否定、組合せ
命題と同じように、「x は · · · である」という命題関数から、「x は · · · でない」という命題関数を作ることができる。
定義 3.2 x を変数とする命題関数 P (x) に対し、変数の要素を x = x0 と定めると ¬P (x0 ) となる命題関数を P (x) の
否定といい、¬P (x) と表す。
例 : x の変域を自然数とする。P (x) を「x は素数である」としたとき、¬P (x) は、「x は素数ではない」すなわち、「x
は 1 か合成数である。」ということである。（例終）
例 : x の変域を実数とする。P (x) を「x > 0 である」とすると、¬P (x) は「x < 0 ではない」、すなわち、「x ≥ 0 であ
る」ということである。（例終）
「x は · · · である」、「x は ∼ である」という命題関数をもちいて、「x は · · · または ∼ である」、「x は · · · かつ ∼ で
ある」という命題関数を作ることができる。
定義 3.3 x を変数とする命題関数 P (x)、Q(x) について、
(i) x = x0 と変数を定めると命題 P (x0 ) ∨ Q(x0 ) となる命題関数を P (x) ∨ Q(x) と定める。
(ii) x = x0 と変数を定めると命題 P (x0 ) ∧ Q(x0 ) となる命題関数を P (x) ∧ Q(x0 ) と定める。
例 : x の変域を整数とする。P (x) を「x は 4 の倍数である」、Q(x) を「x は 6 の倍数である」とするとき、P (x) ∨ Q(x)
は、「x は 4 の倍数または 6 の倍数である」すなわち、「x は偶数である」という命題関数である。P (x) ∧ Q(x) は「x
は 4 の倍数かつ 6 の倍数である」すなわち、「x は 12 の倍数である」という命題関数である。（例終）
3.2
3.2.1
量化子
すべての（全称命題）
定義 3.4 P (x) を命題関数とするとき、「すべての x について P (x) 」、「任意の x について P (x)」は命題である。こ
れを ∀x(P (x)) と書く。∀ を用いて表される命題を全称命題という。
ちなみに、∀ は “all” の “A” を逆さにした記号。
例 : x の変域を実数とする。
(i) P (x) を「x は x2 + 1 > 0 を満たす」という命題関数とするとき、 ∀x(P (x)) は真の命題である。
(ii) P (x) を「x は x2 > 1 を満たす」という命題関数とするとき、∀x(P (x)) は偽の命題である。実際、x = 0 とすると
き、x2 = 0 なので、すべての実数に対して、x2 > 1 がなりたつわけではない。（例終）
18
ある（存在命題）
3.2.2
定義 3.5 P (x) を命題関数とするとき、「ある x について P (x)」、すなわち、「P (x) が真となる x が存在する」は命題
である。これを ∃x(P (x)) と書く。∃ を用いて表される命題を存在命題という。
ちなみに、∃ は “exist” の “E” を逆さにした記号。
例 : x の変域を実数とする。
(i) P (x) を「x は x2 − 3x + 2 < 0 を満たす」という命題関数とするとき、P (3/2) は真だから、∃x(P (x)) は真の命題
である。
(ii) P (x) を「x は x2 < 0 を満たす」という命題関数とするとき、∃x(P (x)) は偽の命題である。
(iii) P (x) を「x は x2 ≤ 0 を満たす」という命題関数とするとき、P (0) は真だから、∃x(P (x)) は真の命題である。
（例終）
定義 3.6 ∀、∃ のことを量化子と呼ぶ。
量化子を含む推論をを厳密に構成するには、与えられた記号について、例えば、
「a を変域のある対象とした時、P (a) ⇒ ∃x(P (x))」、
「a を変域のある対象とした時、∀x(P (x)) ⇒ P (a)」、
「P (x) の x を取り除いた P ( ) が x にも a にもよらないとき、P (a) ⇒ ∀x(P (x)) 」、
のような、「あたりまえ」と感じる操作を基本的な推論として認め、それらの組合せによって命題を得るという方法が取
られる。
3.3
3.3.1
量化子を含む変換
否定
「すべての文教大生は埼玉県に住んでいる」を否定するには、埼玉県以外に住んでいる人をひとりでもよいから見つけれ
ばよいことになる。すなわち、「埼玉県以外に住んでいる文教大生が（ひとりでも）いる」が、上の命題の否定になる。
また、「数学基礎の試験で 100 点をとった人がいる」を否定する1 には、受験者全員に得点を聞いて回って、全員の得点
が 100 点ではないことを確かめればよい。すなわち、「数学基礎の試験で、すべての人の得点が 100 点ではない」が上
の主張の否定になる。このように、否定すると、全称命題と存在命題が入れ違う。実際、次がなりたつ。
命題 3.7 (i) ¬(∀x(P (x))) ⇔ ∃x(¬P (x))
(ii) ¬(∃x(P (x))) ⇔ ∀x(¬P (x)).
実は、このような主張は命題として前節で説明した意味において証明できるが、少々ややこしい。よって、以後、結果だ
けを認めることにする2 が、例として、(i) が証明されることを見ておく。ちなみに、「¬¬P ⇔ P 」、「(P ⇒ F ) ⇒ ¬P 」
のような、命題論理で示した推論は断りなしに用いる。
（(i) の証明） ⇒) ¬(∀xP (x)) を仮定したとき、¬(∃x(¬P (x))) として矛盾を導く。a を任意の変数とするとき、¬P (a) と
すれば、∃x¬P (x) となる。これは、¬(∃x(¬P (x))) に矛盾するから、¬¬P (a)、すなわち、P (a) がいえる。ここで、a は
任意だから、∀x(P (x)) がいえるが、これは、¬(∀x(P (x))) に矛盾する。ゆえに、¬¬(∃x(¬P (x)))、すなわち、∃x(¬P (x))
1 否定したくないが
2 興味のある人は、例えば、島倉剛一「数学の基礎」
（日本評論社）などを参照してほしい。
19
がいえる。
⇐) ∃x(¬P (x)) と仮定する。つまり、¬P (a) となる a が存在する。このとき、∀x(P (x)) と仮定すると、P (a) が得られ、
¬P (a) と矛盾する。よって、¬(∀x(P (x))) がいえる。（証明終）
3.3.2
連言・選言
例えば、
「このクラス全員が数論と数学基礎を受講している」という命題は、
「このクラス全員が数論を受講している」か
つ「このクラス全員が数学基礎を受講している」ということと同じである。このように、
「すべての x が · · · かつ ∼ であ
る」は、
「すべての x が · · · である」かつ、
「すべての x が ∼ である」ことと同じになる。これは、次のように定式化される。
命題 3.8 ∀x(P (x) ∧ Q(x)) ⇔ (∀x(P (x))) ∧ (∀(Q(x)))
このとき、∧ を ∨ に置き換えた
∀x(P (x) ∨ Q(x)) ⇔ ∀x(P (x))) ∨ (∀x(Q(x)))
は成り立たないことに注意する。例えば、「このクラス全員が数論か数学基礎を受講している」ことと、「このクラス全
員が数論を受講しているか、または、このクラス全員が数学基礎を受講している」ことは違う。
例えば、「数論か数学基礎を落とした人がいる」1 という命題は、「数論を落とした人がいる」または、「数学基礎を落と
した人がいる」ということと同じである。つまり、
「· · · または ∼ である x が存在する」は、
「· · · である x が存在する」
または、「∼ である x が存在する」ということと同じになるので、次のように定式化される。
命題 3.9 ∃x(P (x) ∨ Q(x)) ⇔ (∃P (x)) ∨ (∃Q(x))
このときも、
∃x(P (x) ∧ Q(x)) ⇔ (∃xP (x)) ∧ (∃xQ(x))
は、成り立たないことに注意する。
問題 : このことが成り立たない P (x) と Q(x) の例をあげよ。
3.4
3.4.1
多変数の述語論理
多変数の命題関数
今まで、変数がひとつだけの命題関数を考えてきたが、
「x は y より大きい」のように、２つの変数が確定すれば命題に
なるような文もある。これを、２変数の命題関数として P (x, y) のように表すことにする。例えば、この命題関数
def.
P (x, y) := 「x は y より大きい」
について、
P (3, 2) ≡ T,
P (1, 4) ≡ F,
P (2, 2) ≡ F
などがなりたつ。
また、変数のうちのひとつを y = 2 のように確定させると、
「x は 2 より大きい」となる。これは、x を変数とする１
変数の命題関数とみなすことができる。つまり、P (x, 2) は x を変数とする１変数の命題関数である。同様に、P (3, y)
1 そういう方がいないことを祈っていますが
20
は、「3 は y より大きい」となり、y を変数とする１変数の命題関数とみなすことができる。
同様に、n 個の変数 x1 、x2 、· · · 、xn を持つ命題関数 P (x1 , x2 , · · · , xn ) を定めることができ、このうちのひとつの変
数が定まると、n − 1 変数の命題関数になる。
3.4.2
全称命題と存在命題
x、y の変域を実数とする。２変数の命題 P (x, y) を「x は y より大きい」としたとき、∃x(P (x, y)) は、「y より大きい
実数が存在する」∀x(P (x, y)) は、「全ての実数は y より大きい」という１変数の命題関数になる。さらに、量化子を付
け加えることで、量化子が複数入った命題を作ることができる。このとき、全称や存在をとる順番を注意する必要があ
る。例えば、x の変域を教育学部の学生全体、y の変域を教育学部の科目全体として、P (x, y) を「x は y を履修して
いる」としたとき、∀y(∃x(P (x, y))) は、「教育学部の全ての科目は、学部学生の誰かが履修している」ということだが、
∃x(∀yP (x, y)) は、「教育学部の全ての科目を履修している学部学生がいる」ということになる。
例 : 変数の変域を実数とする。このとき、P (x, y) を「x > y を満たす」とする。
(i) ∀x(∀y(P (x, y))) は、「すべての x に対し、『すべての y に対し x > y 』が成り立つ」ということである。例えば、
x = 1、y = 2 のとき、P (1, 2) は偽なので、すべての x、y に対し、これは成り立たない。すなわち、∀x(∀y(P (x, y)))
も偽である。
(ii) ∀y(∀x(P (x, y))) も、(i) と同様に偽であることがいえる。
(iii) ∃x(∃y(P (x, y))) は、「『x > y を満たす y が存在する』を満たす x が存在する」ということである。例えば、x = 3
としたとき、y = 2 とすれば、P (3, 2) は真であるので、このような x と y は存在する。すなわち、∃x(∃y(P (x, y))) は
真である。
(iv) ∃y(∃x(P (x, y))) も (iii) と同様に偽であることがいえる。
(v) ∀x(∃y(P (x, y))) は、「すべての x に対し、『x > y を満たす y が存在する』ことがいえる」ことである。これは、任
意の実数 x = x0 に対し、y を y = x0 − 1 とすると常に x > y がいえるので、真である。
(vi) ∃y(∀x(P (x, y))) は、「『すべての x に対し x > y 』を満たす y が存在する」ことである。これは、もし、そのよう
な実数 y が存在したとして、それを y0 としたとき、x = y0 − 1 とすると x < y となってしまい、矛盾するので、偽で
ある。
(vii) ∃x(∀yP (x, y)) は、(v) と同様に、偽であることが示せる。
(viii) ∀y(∃xP (x, y)) は、(vi) と同様に、真であることが示せる。（例終）
問 : 変数 x、y の変域を実数とする。
(1) P (x, y) を「x2 −2xy+y 2 > 0 を満たす」とする。このとき、(i) ∀x(∀yP (x, y))、(ii) ∃x(∃yP (x, y))、(iii) ∀x(∃yP (x, y))、
(iv) ∃y(∀xP (x, y)) の真偽を答えよ。
(1) Q(x, y) を「x2 −2xy+y 2 ≥ 0 を満たす」とする。このとき、(i) ∀x(∀yQ(x, y))、(ii) ∃x(∃yQ(x, y))、(iii) ∀x(∃yQ(x, y))、
(iv) ∃y(∀xQ(x, y)) の真偽を答えよ。
21
3.4.3
複数の量化子の否定
２変数の命題変数に関し、量化子が入っている場合、ひとつずつの量化子ごとに、否定の操作を行うことができる。
例 : P (x, y) を命題関数とするとき、例えば、
(i) ¬(∀x(∀y(P (x, y)))) ⇔ ∃x(¬(∀y(P (x, y)))) ⇔ ∃x(∃y(¬P (x, y)))
(ii) ¬(∃x(∃y(P (x, y)))) ⇔ ∀x(¬(∃y(P (x, y)))) ⇔ ∀x(∀y(¬P (x, y)))
(iii) ¬(∀x(∃y(P (x, y)))) ⇔ ∃x(¬(∃y(P (x, y)))) ⇔ ∃x(∀y(¬P (x, y)))
(iii) ¬(∃x(∀y(P (x, y)))) ⇔ ∀x(¬(∃y(P (x, y)))) ⇔ ∀x(∃y(¬P (x, y)))
となる。（例終）
例えば、x の変域を「教育学部の学生全体」、y の変域を「教育学部の授業全体」とし、P (x, y) を「x は y を受講す
る」としたとき、∀x(∃yP (x, y)) は「全ての学生は、何かひとつは講義を受講している」ということだった。この否定は、
∃x(∀y(¬P (x, y)))、すなわち、「何の講義も受講していない学生がいる」ということになる。
変数を増やした n 変数の命題関数に関しても、同様に考えることができる。
例 : 変数 x、y 、z を持つ命題関数 P (x, y, z) に対し、
¬(∀x(∃y(∀z(P (x, y, z))))) ⇔ ∃x(∀y(∃z(¬P (x, y, z))))
となる。（例終）
問題 : 上の例が成り立つことを確かめよ。
22

Download Report