数理論理学　第9回 茨城大学工学部情報工学科 佐々木　稔

前回までのあらすじ 配布資料は以下からダウンロードできます http://sas.cis.ibaraki.ac.jp/logic/ 述語論理 述語と変数 高階述語 配布資料は以下からダウンロードできます http://sas.cis.ibaraki.ac.jp/logic/

前回の問題 次の文を述語を用いて論理式で表現しなさい。 x が y 以下で、y が z 以下ならば、x は z 以下である。 (「x が y 以下である」を P(x, y) とする) 花子と桃子は姉妹ではない。 (「x と y は姉妹である」を Q(x, y) とする) Bob は情報工学科の所属であれば、機械工学科の所属ではない。(「x は y の所属である」を R(x, y) とする)

x が y 以下で、y が z 以下ならば、x は z 以下である。 　P(x, y)∧P(y, z) ⇒ P(x, z) 花子と桃子は姉妹ではない。 　～Q(花子, 桃子) Bob は情報工学科の所属であれば、機械工学科の所属ではない。 　R(Bob, 情報工学科) ⇒ ～R(Bob, 機械工学科)

今週のお題 述語論理 関数 定義域 量記号

関数 引数として固体定数を渡すと固体を返す 関数は関数記号 f, g などを用いて表現 年齢（x） : xの年齢を返す関数 沈む方向（太陽） = 西 最小（素数） = 2 関数は関数記号 f, g などを用いて表現 年齢（x）の年齢を f、父親（x）の父親を g f(x), g(x)

述語論理と関数の違い 述語論理は真偽を返す 例1 例2 関数のように値は返さない 大きい（x, y） : xがyより大きい 年齢（x） : xの年齢を返す関数 大きい（年齢（Alice）, 年齢（Bob）） 例2 知っている（Alice, 父親（Bob））

関数の引数 関数の引数に関数を渡してもよい 例 父親（x） : x の父親を返す関数 母親（x） : x の母親を返す関数 父親（母親（太郎）） : 太郎の母方の祖父 母親（父親（花子）） : 花子の父方の祖母

述語 述語は返り値として真理値を返す 関数との違いに注意 大きい（x, y） : xがyより大きいことを表す述語 推薦する（x, y, z） : x が y に z を推薦する 交換する（x, y, z, u） : x が y に z を u に交換する 関数との違いに注意 関数は固体を返す 述語は真理値を返す

定義域 定義域 例 第1階述語論理で扱う個体の集合 素数（x） 年齢（x） 固体変数 x の定義域は「自然数」

定義域 正（x） : x は 0 または正の数である 負（x） : x は負の数である 正（x）∨負（x）

量記号 全称記号（全称限量子、全称量化子） 存在記号（存在限量子、存在量化子） ∀xP(x) 「すべての x について、 P となる」 定義域にあるすべての固体に対して成立 存在記号（存在限量子、存在量化子） ∃xP(x) 「ある x について、P となるものが存在する」 P が真となる固体の集合が定義域に含まれる

量記号 「すべての P は Q である」 「すべての P は Q でない」 「ある P は Q である」 「ある P は Q でない」 ∀x（P（x）⇒Q（x）） 「すべての P は Q でない」 ∀x（P（x）⇒~Q（x）） 「ある P は Q である」 ∃x（P（x）∧Q（x）） 「ある P は Q でない」 ∃x（P（x）∧~Q（x））

存在量化子 「ある P は Q である」 例 ∃x（P（x）∧Q（x）） であって、 ∃x（P（x）⇒Q（x）） でないのか？ 「ある x が 7 つの頭を持つ人ならば、x は変な人である」 （ ∃x（P（x）⇒Q（x）） ） 「7 つの頭を持った変な人である x が存在する」 （ ∃x（P（x）∧Q（x）） ） 「7 つの頭を持った変な人」は存在しないので偽

存在量化子 記号化 「x = 人」 とすると、 P（人） ⇒ Q（人） = 真 P（人） ∧ Q（人） = 偽 P（x） : 7 つの頭を持つ Q（x） : 変である 「x = 人」 とすると、 P（人） = 偽 Q（人） =　真 （ほとんどの人は偽ですが…） P（人） ⇒ Q（人） = 真 P（人） ∧ Q（人） = 偽

全称量化子 「すべての P は Q である」 例 ∀x（P（x）⇒Q（x）） であって、 ∀x（P（x）∧Q（x）） でないのか？ 「すべてのサメは肉食である」 記号化 P（x） : x はサメである Q（x） : x は肉食である

全称量化子 ∀x（P（x）⇒Q（x）） ∀x（P（x）∧Q（x）） 意味の違いに注意！ 「すべての x がサメならば、x は肉食である」

量化子の作用域（スコープ） 作用域（スコープ） 束縛変数の変更は可能 ∀x（･･･）,∃y（･･･）の束縛変数 x,y の影響範囲 ∀y（∃xP（x, y）⇒∃zQ（z, f（y））） x の作用域は P（x, y） y の作用域は ∃xP（x, y）⇒∃zQ（z, f（y）） z の作用域は Q（z, f（y）） 束縛変数の変更は可能 ∀xP（x） の x を y に変更しても同じ論理式

複数の量化子が存在する場合 同じ量記号の場合、 束縛変数の順序が変わっても同じ意味 ∀x∀y∀z, ∀x∀z∀y, ∀y∀x∀z, ∀y∀z∀x, ∀z∀x∀y, ∀z∀y∀x ∃x∃y∃z, ∃x∃z∃y, ∃y∃x∃z, ∃y∃z∃z, ∃z∃x∃y, ∃z∃y∃x

複数の量化子が存在する場合 異なる量記号の場合は注意が必要 P(x, y) : x は y に P である ∃x∀yP（x, y） = ∃x（∀yP（x, y）） 「ある x に対して、x がすべての y に P であるものが存在する」 ∃y∀xP（x, y） = ∃y（∀xP（x, y）） 「ある y に対して、すべての x が y に P であるようなものが存在する」

複数の量化子が存在する場合 ∀x∃yP（x, y） = ∀x（∃yP（x, y）） ∀y∃xP（x, y） = ∀y（∃xP（x, y）） 「すべての x で、x はある y に P である」 ∀y∃xP（x, y） = ∀y（∃xP（x, y）） 「すべての y について、ある x は y に P である」

例 P(x, y) : x は y を愛する ∃x∀yP（x, y） ∃y∀xP（x, y） ∀x∃yP（x, y） ∀y∃xP（x, y）

練習問題 F(x)を「xはカエルである」 、G(x)を「xは緑色である」 、H(x) 「xは跳ねている」 、I(x) 「xは虹色である」 して、以下の各文を形式化せよ。 すべてのカエルは緑色である。 あるカエルは緑色でない。 緑色のカエルが存在する。 あるものは緑色でも虹色でもある。 ある緑色のカエルは跳ねていない。