述語論理、量化 Predicate Logic and Quantifiers

変数にある特定の要素を代入すると真偽が定まる主張を命題関数(propositional function)または述語(predicate)という。

例：

P(x)＝xは動物である…xに犬や木、本などを代入すると真偽が定まる。

P: 述語「は動物である」、x :変数

P(犬)＝犬は動物である…True

P(本)＝本は動物である…False

変数が複数ある場合、P(x1, x2, ..., xn)はn-place predicateまたはn-ary predicateという。

プログラミングの世界において、プログラムは有効なインプットを与えた時に、恒に望んだアウトプットを表示する。この時のある命令が呼び出される前に必ず満たされていなければならない状態を前提条件(preconditions)、その命令の終了後に保証する状態を帰結条件(postconditions)という。

例：

xとyの値を入れ替えるプログラミングについて、

temp := x

x := y

y := temp

この時、preconditionはP(x, y)＝"x = a and y = b, where a and b are the values of x and y before running the program"

postconditionはQ(x, y)＝"x = b and y = a"

述語と量化を扱う論理分野をpredicate calculusという。この量化(quantification)を使って、命題関数が真になる領域を議論することができる。この領域を定義域(domain/discourse/universe of discourse)という。

量子化の記号として、

全称記号∀(universal quantifier)は英語のall（全ての）、any（任意の）の頭文字を記号化したもの。

存在記号∃(existential quantifier)は英語のexist（存在する）の頭文字を記号化したもの。

存在記号の中でも要素がただ一つに決まる時、uniqueness quantifierと呼び、∃!で表す。

例：

∀xP(x)…全てのxに対してP(x)は真である。

P(x)＝"x＋１＞x、定義域は実数全体"の時、∀xP(x)は真である。

∃xP(x)…ある要素xが存在してP(x)を真として満たしている。

P(x)＝"x＞３、定義域を実数全体"とした時、x＝４はP(x)を満たすがx＝０は満たさない。よって∃xP(x)は真である。

P(x)＝"xー１＝０、定義域は実数全体"の時、xはただ一つ（x＝１）に決まる。∃!P(x)。

優先順位として、量子化記号、論理記号の順に計算する。

ド・モルガンの法則は量化にも使われる。

¬∃xP(x) ≡ ∀x¬P(x)、¬∀xP(x) ≡ ∃x¬P(x)

量化記号は組み合わせることもできる。

順序は外側から内側へ。順序が変わると意味が変わってしまう。

例：

∀y∃y（x＋y＝０）…全てのxに対して、x＋y＝０を満たすyが存在する。

Q(x, y): x＋y＝０の時、

∃x∀xQ(x, y)…あるyに対して全てのxはQ(x, y)を満たす…まずyを選ぶ。y＝１の時、x＝ー１なら命題を満たすが、x≠−１の時命題を満たさない。よって∃x∀xQ(x, y)は偽である。

∀x∃yQ(x, y)…全てのxに対してあるyはQ(x, y)を満たす…xは定義域内ならなんでも良い。x＝１の時、y＝ー１、x＝０の時、y＝０のように、全てのxに対してQ(x, y)を満たすyがそれぞれ存在する。よって∀x∃yQ(x, y)は真である。