数理論理学第2回

数理論理学第9回
茨城大学工学部情報工学科
佐々木稔
前回までのあらすじ
 述語論理
 述語と変数
 高階述語
 配布資料は以下からダウンロードできます
http://sas.cis.ibaraki.ac.jp/logic/
今週のお題
 述語論理
 関数
 定義域
 量記号
関数
 引数として固体定数を渡すと固体を返す




年齢（x） : xの年齢を返す関数
父親（x） : xの父親を返す関数
沈む方向（太陽） = 西
最小（素数） = 2
 関数は関数記号 f, g などを用いて表現
 年齢（x）の年齢を f、父親（x）の父親を g
 f(x), g(x)
関数
 述語論理では関数の値は出さない
 例1
 大きい（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） : x は 0 または正の数である
 負（x） : x は負の数である
 正（x）∨負（x）
 x = {x| x は整数} であれば、真
 x = {x| x は実数} であれば、真
 x = {x| x は複素数} であれば、偽
量記号
 全称記号（全称限量子、全称量化子）
 ∀xP(x)
 「すべての x について、 P となる」
 定義域にあるすべての固体に対して成立
 存在記号（存在限量子、存在量化子）
 ∃xP(x)
 「ある x について、P となるものが存在する」
 P が真となる固体の集合が定義域に含まれる
量記号
 「すべての 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 つの頭を持った変な人」は存在しないので偽
存在量化子
 記号化
 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 がサメならば、x は肉食である」
 ∀x（P（x）∧Q（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））
 「すべての 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)を愛するような人(x)が存在する」
 ∃y∀xP（x, y）
 「すべての人(x)から愛される人(y)が存在する」
 ∀x∃yP（x, y）
 「すべての人(x)が少なくとも一人の人(y)を愛する」
 ∀y∃xP（x, y）
 「すべての人(y)は少なくとも一人の人(x)から愛される」

Download Report