述語、述語の同値性

サイトのTOP→理系インデックス
集合論のTOP→集合論インデックス





定義 ( 述語 )

変数 x の値を定めることで真偽を判定することができる主張を 『 述語 』 という。

とくに、変数 x を 『 自由変数 』 という。

自由変数 x をもつ述語を P(x)と表す。

P(x)に値 a を代入したものを P(a)と表す。

述語は 『 条件 』 と呼ばれることもある。

既に前のページでも紹介したが、例えば、次の P(x)、Q(x)は述語である。

P(x) : x+3=5

Q(x) : x は偶数である。

これらの主張は変数 x を定めることで真偽の判定が可能になる。

例えば、P(2)は真だが、P(3) は偽である。

また、Q(3)は偽だが、Q(4)は真である。

定義 ( 変域 )

述語に含まれる変数に代入できる値全体を 『 変域 』 という。

変域は明示されないことも多いが、述語に対して変域は必ず定まっているとする。

定義 ( 真理集合 )

P(x)を述語とする。

X を x の変域とする。

X の元で、P(x) に代入してできる命題が真であるもの全体を考える。

このような集合を 『 述語P(x)の真理集合 』 といい、{ x | P(x)}と表す。

いま、ここで集合の話と述語の話がつながった。

見方を変えれば、{ x | P(x)}は 『 条件P(x)を満たす x∈X の全体 』 である。

述語P(x)を 『 条件 』 と呼ぶことがあるのはそのためである。

例えば、x=2 という述語を考えてみよう。

自由変数 x の変域を とすると、この述語の真理集合は、



自由変数 x の変域を とすると、この述語の真理集合は、



とくに、x の変域を として考えている場合、これは方程式を解く作業と全く同じである。

つまり、「 方程式を解く作業 」 は 「 等式で表された述語の真理集合を求めること 」 を意味する。

定義 ( 述語の同値性 )

P(x)、Q(x)を述語とする。

P(x)とQ(x)の真理集合が一致するとする。

このとき、「 P(x)とQ(x)は同値である 」 といい、P(x)⇔Q(x)と表す。

定義

命題と同じように、述語についても∧、∨、→、¬ を定義する。

例えば、述語 P(x)、Q(x)に対して、新しい述語 P(x)∧Q(x)を構成できる。

Z5 ( 述語の演算 )

P(x)、Q(x)、R(x)を述語とする。

このとき、次が成り立つ。



(1)、(2)を交換則、(3)、(4)を結合則、(5)、(6)を分配則という。

(8)、(9)を ド・モルガンの法則 という。

証明

明らかである。(※Z2)

参考

変数 x の変域を とする。次の(1)、(2)、(3)を考える。

(1) x>3

(2) 任意の x∈ に対し、x>3 である。

(3) ある x∈ が存在して、x>3 となるようにできる。

このとき、(1)、(2)、(3)はそれぞれ命題であろうか?述語であろうか?

これは非常に間違えられやすい問題である。

答えはすぐ下に書くので、まずは自ら考えるのがよいであろう。

定義 ( 全称命題、存在命題 )

変数 x の変域を とする。次の(1)、(2)、(3)を考える。

(1) x>3

(2) 任意の x∈ に対し、x>3 である。

(3) ある x∈ が存在して、x>3 となるようにできる。

いま、(1)は x の値が定まっていないと真偽の判定ができないので、述語である。

一方、(2)、(3)は真偽の判定ができる主張なので、命題である。

実際、(2)は偽であり、(3)は真である。

(2)のような形の命題を 『 全称命題 』 という。

(3)のような形の命題を 『 存在命題 』 という。

いま説明したように、全称命題や存在命題に書かれている x には値を代入できない。

このような変数 x を 『 束縛変数 』 という。

定義 ( 量化子 )

全称命題 「 任意の x に対してP(x)である 」 を ∀x P(x) と表す。

存在命題 「 ある x が存在してP(x)となるようにできる 」 を ∃x P(x) と表す。

∀ を 『 全称量化子 』 という。

∃ を 『 存在量化子 』 という。

これらを総称して 『 量化子 』 という。

変数 x の変域 X を明示して、次のように表すことも多い。

∀x∈X(P(x)) 「 任意の x∈X に対してP(x)である 」

∃x∈X(P(x)) 「 ある x∈X が存在してP(x)となるようにできる 」

例えば、命題∀x∈(x≧0) は真である。

一方、命題∃x∈(x+7=2) は偽である。

Z6

P(x)を述語とする。

このとき、次が成り立つ。

証明

明らかである。

補足

例えば、「 任意の学生がノートをもっている 」 の否定は、「 ある学生がノートをもっていない 」 である。

補足

Z6 をよく見てみると、量化子が付いた命題の否定には特徴がある。

量化子が付いた命題の否定では、量化子の種類が入れ替わり、¬が括弧の中に入り込む。

このようにして機械的に命題の否定を作り出すことができる。

補足

上の証明では単に 「 明らかである 」 とした。

これに対し、少し異なる角度から説明を試みてみよう。

−−−−−−−−−−−−−−−−−−−−

まず、変域 X が有限集合である場合を考える。

そこで、X={x、・・・、x}とおく。

いま、Z2より、



次に、変域 X が無限集合である場合を考える。

形式的に次のように定義する。



いま、Z2 から類推すると、



−−−−−−−−−−−−−−−−−−−−

上の証明では∧x∈X という記号が登場した。

x∈XP(x)は 「 任意の x∈X に対し、P(x)を考え、それらをすべて∧で結ぶ 」 ということである。

しかし、これは厳密な定義ではない。

だから、上の説明では 「 形式的に 」 と述べた。

ここで、「 厳密ではないとはどういうことか?」 と疑問に思う人がいるかもしれない。

簡単に言えば、

「 何の基礎づけもなしに無限個の命題を∧で結ぶことはできない 」

・・・ということである

Z1により、2つの命題 P(x)、P(x)から P(x)∧P(x)を構成できる。

しかし、これを繰り返しても、無限個の P(x)を∧で結べるわけではない。

この辺りは誤解されやすい。

その原因は、無限の種類が混同されていることにある。

例えば、次の(1)〜(3)が混同されることが多い。

(1) 帰納的な意味での無限

(2) 集合としての無限

(3) 極限としての無限

例えば、任意の自然数は有限だが、自然数全体は無限集合である。

例えば、任意の自然数は有限だが、limn→∞n=∞ である。

例えば、任意の自然数 n に対して 2−n≠0 だが、limn→∞−n=0 である。

『 帰納法(自然数がいくらでも大きくなること)』 と 『 無限集合 』 と 『 極限 』 はすべて異なる。

参考

変数 x の変域を とする。

このとき、(x+1)=x+2x+1 は命題であろうか?述語であろうか?

少しややこしいが、これは述語である。

実際、x に値を代入することができ、値を代入したものは真偽が判定できる命題である。

ただし、(x+1)=x+2x+1 の真理集合は である。

つまり、全称命題∀x∈((x+1)=x+2x+1) は真である。

Z7

P(x)、Q(x)を述語とする。

このとき、次が成り立つ。

証明

Z3 より、P→Q≡¬P∨Q である。

よって、P(x)→Q(x)⇔¬P(x)∨Q(x)である。

さらに、Z6、Z5 より、

Z8

P(x)、Q(x)を述語とする。

X を x の変域とする。

P(x)の真理集合は空集合であるとする。

このとき、次の命題は真である。

証明

Z3 より、P→Q≡¬P∨Q である。

よって、P(x)→Q(x)⇔¬P(x)∨Q(x)である。

いま、P(x)の真理集合は空なので、¬P(x)の真理集合は X である。

よって、¬P(x)∨Q(x)の真理集合は X である。

よって、P(x)→Q(x)の真理集合は X である。

よって、∀x∈X(P(x)→Q(x))は真である。

補足

つまり、P(x)の真理集合が空ならば、Q(x)の内容に関わらず∀x∈X(P(x)→Q(x))は真である。