2013年8月6日火曜日

∀と∃ メモ

(∀x) Fx や、(∃x)Fx は簡単にわかるとして、∀x ∃y Fxy など、入れ子になるとわかりにくくなる。

∀と∃は「全称」「存在」と訳されているが、思い切って、

∀ ・・・ 偽をみつけたら偽を返す量化子
∃ ・・・ 真をみつけたら真を返す量化子

と考えるのもよさそうだ。

∀x Fx というのは、議論領域のxについて走査していき、Fxが偽になれば偽を返せということ
∃x Fx というのは、議論領域のxについて走査していき、Fxが真になれば真を返せということ

若干、プログラミングちっくにかけば…

■∀x Fx
while(未調査の要素xが存在する){
 if (Fx == False) return False;
}
return Ture

■∃x Fx
while(未調査の要素xが存在する){
 if(Fx == True) return True;
}
return False;


このことからも、
「すべての人間はいずれ死ぬ」を ∀x { Hx ⇒ Dx}
「ある人間はいずれ死ぬ」を ∃x { Hx ∧ Dx}
と書き分ける理由がわかる。

∀xのxは議論領域が定まっていなければ、万物を指す。
∀x ~の命題は、偽がひとつでも出ればFalseを返して終了してしまうので、
∀x {Hx ∧ Dx}とは書けない。これは当然とも言える。
ほとんどすべての場合で、∀x {Hx ∧ Dx}はFalseを返してしまうだろう。
一方で、∀x { Hx ⇒ Dx}は適切である。
これは、非人間なxについてはHxがFalseとなることで「Hx⇒Dx」がTrueであり続けるからだ。
平たくいえば、非人間なxへのフィルターがかかるので、きちんと働く。

∃xのxも議論領域が定まっていなければ、万物を指す。
∃x~の命題は、真がひとつでも出ればTrueを返して終了してしまうので、
∃x {Hx ⇒ Dx} とは書けない。これは⇒の性質による。
すなわち、Hx ⇒ Dx は、HxがFalseであれば真となってしまうため、
そこで∃x~の命題がTrueを返してしまうからである。これは言いたいこととは異なる。
ほとんどすべての場合で、∃x {Hx ⇒ Dx}はTrueを返してしまうはずである。
一方で、∃x { Hx ∧ Dx}は適切である。
これは、非人間なxについてはHxがFalseとなることで「Hx ∧ Dx」がFalseとなり続けるため。
平たく言えば、非人間なxへのフィルターがかかるので、きちんと働く。

結局、∀と∃で違う表現をとらなければならないのは、その性質、すなわち「偽をみつける」のか「真をみつける」のかの違いに起因するともとれる。


入れ子量化子も「偽をみつける」「真をみつける」という視点でみれば、そこそこ見やすいかも。

∀x ∃y (x loves y)
これは、xを走査していき、∃y (x loves y)が偽となるものがあればFalseを返す命題。
∃y (x loves y) の真偽をみるためには、(一時的に固定された)xの元で、
yを走査していき、x loves y が真となるものがあるかどうかをみればよい。(なければ偽)

∃y ∀x (x loves y)
これは、yを走査していき、∀x (x loves y)が真となるものがあればTrueを返す命題。
∀x (x loves y)の真偽をみるためには、(一時的に固定された)yの元で、
xを走査していき、x loves y が偽となるものがあるかどうかをみればよい。(なければ真)


なお、∀が「偽をみつける」量化子であるのは、
∀x Fx と¬(∃x ¬Fx)が同値であることからも明らか。
すなわち、FxがFalseとなるxが存在すれば、∀x Fxは偽となるのである。

0 件のコメント:

コメントを投稿