述語論理と ( 全称 ) ( 存在 ) 回の講義の概観 : 命題論理 ( 真理値 ) 2 述語論理 ( モデルと解釈 ) 意味論 semantics 命題論理 ( 公理と推論規則 ) 述語論理 ( 公理と推論規則 ) syntax 構文論 preview 述語論理は命題論理よりも複雑 例題 : 次の文は真か偽か? ( 曖昧な文です ) すべての自然数 x に対して x < y を満たすような自然数 y が存在する ( 小野先生の例題 ). 解釈 ( その一 ) すべての x に対して x < y を満たすような y が存在する : x y (x < y) 2. 解釈 ( その二 ) すべての x に対して x < y を満たす ような y が存在する : y x (x < y) 曖昧 2 復習 述語と対象変数 命題とは真理値 ( 真偽 ) が確定している文のこと真偽のいずれかの値 { t, f} をとる : 命題変数 対象変数を含む文の真理値は確定しない例 : x 200 y は素数であるこのような文を扱うために命題関数 P を考える P : D T, ここに T = { t, f } 例 : 対象領域 D として自然数の集合を考える P : D D T, 2 変数 ( 引数 ) の述語 対象変数 individual variable, object variable 命題関数 propositional function 述語 predicate 述語 : 命題関数の具体的な表現例 : Le, Prime Le (x, 200): (x 200 ), 2 変数 ( 引数 ) 述語記号 Prime (y) : y は素数である 対象領域 D の要素を対象 object, individual という対象領域 D の上を動く変数を対象変数 D の定数を対象定数 object (individual) constant という 全称記号, と存在記号 x P(x): すべての x D に対して P(x) が真になる y Q(y): ある y D が存在して Q(y) が真になる 正確な記法を次に述べる と が多重になるときに注意 4 述語論理の項 term 今までに登場したもの : 対象変数 対象定数 さらに必要なもの : 対象領域の上の関数記号関数記号の例 : 自然数の上の +, 項 term の定義 :. 個々の対象定数 対象変数は項である 2. f が n 変数 ( 引数 ) の関数記号で, t, t2,, tn が項であるならば f (t, t2,, tn) は項である 項の例 : 200, x, y, (+x), 6 (x+y). +(,x), (6, +(x, y)) とも書く 5 論理式 formula, wff 述語記号 : 述語を表す記号. P が n 変数 ( 引数 ) の述語記号で t, t2,, tn が項ならば P(t, t2,, tn) は論理式である 2. A, B が論理式ならば A B, A B, A B, Aは いずれも論理式である復習 : は省略してよい. A が論理式で x が対象変数ならば ( x A), ( x A) は論理式である注 : の形の論理式を原子(atomic) 論理式という 例 : x( y( q( r(x=q y+r)))), = は述語記号 6
, quantifier 限定記号, 量化記号, 限量子 すべての x に対して R(x, y) を満たす y が存在する という文は曖昧である前出. x y (x < y) すべての自然数 x に対して,x よりも大きな自然数 y ( 例えば x+ ) が存在する ( 真 ) 2. y x (x < y) ある自然数 y が存在して,y は如何なる ( すべての ) 自然数 x よりも大きい ( 偽 ) 7 自由変数と束縛変数 free and bound variables x y (x < y) の変数 x, y は 変数と呼ばれているが 代入の対象にならない z y (z < y) と書いても意味が変わらない 変数には2 種類ある 自由変数と束縛変数 ここで注意するべき事は 同じ変数が自由であり 同時に束縛されることがある例 : y (x = y+y ) z ( y = z+z+ ) x は偶数である y は奇数である 自由変数と束縛変数を出現 occurrence という単位で区別しなければならない 8 出現 occurrence. A が原子論理式であるとき A に含まれる変数 x の出現は すべて自由な出現である 2. A が B C, B C, B C, B のいずれかであるとする もし x が B または C における自由な出現であるならば その x は A において自由である もし x が B または C における束縛された出現であるならば その x は A において束縛されている. A が ( z B) または ( z B) であるとする もし z が x であるときは Aにおける x の出現は束縛されている z が x と異なる場合には もし x が B における自由な出現であるならば その x の出現は A において自由である もし x が B における束縛された出現であるならば その x の出現は A において束縛されている 9 自由変数と束縛変数 ( 例 ) 例 : y (x = y+y ) z( y = z+z+ ) 論理式が自由変数を一つも含まない時閉論理式 closed formula という 論理式 A に含まれる自由変数 x に項 t を代入して得られる論理式を A[t/x] と表す 代入をめぐる珍現象 : ( 小野先生の例題 ) z(x=y z) : x は y の倍数である z(x=00 z) : x は 00 の倍数である z(x=z z) : x は平方数である これを避けるために自由変数と束縛変数の記号の種類を分ける流儀の教科書もある 0 代入の方法 A は zb または zb の形の論理式とする A[t/x] は z が x のとき A[t/x] は A 自身 ( 束縛変数に代入不可 ) z が x とは異なる変数のとき t に z が出現しなければ A[t/x] は za[t/x] または za[t/x] t に z が出現する場合は A[t/x] は w((a[w/z])[t/x]) または w((a[w/z])[t/x] ) ただし w は A にも t にも現れない新しい対象変数 i.e. 項 t に変数 w が現れることがない 代入に関する補足説明 前のスライドの変数 w は新しい変数である これは対象変数の集合が無限集合であることを意味する つまり必要があれば いつでも 新しい変数 を選ぶことができる 前のスライドの面倒な操作を一言で表現すれば 束縛変数が項 t に出現する場合には 束縛変数を新しい変数に あらかじめ書き換えておく ということである 2 2
論理式の意味 述語論理の論理式の意味を考えるには 対象領域 domain を定める必要がある ( 解釈 interpretation, モデル model, 構造 structure) 空でない集合 D を定める 対象定数に D の要素 ( 元 ) を対応づける対象変数は D の上を動く関数記号に D の上の関数を対応づける述語記号に D の上の述語を対応づける 単なる記号に具体的な要素 関数 述語を対応 ただし述語記号 = ( 等号 ) の解釈は通常の等号とする 解釈 閉論理式 M A 解釈 M において論理式 A が真 M A 解釈 M において論理式 A が偽. A が原子論理式のとき M P(t, t2,, tn) となるのは Pの解釈が項 t, t2,, tn の解釈において真になる場合である. 2. M A B となるのは (M A かつ M B ),. M A B となるのは (M A または M B), 4. M A B となるのは (M A ならば M B), 5. M A となるのは M A の時である. M: Lucida Calligraph : MSゴシック (UTF) 4 ( 続 ) 解釈 閉論理式 6. M x A となるのは すべての D の要素 u に対して M A[u/x] となるとき, 7. M x A となるのは D のある要素 u が存在して M A[u/x] となるときである. 論理式 B に対して B に含まれる自由変数が x, x2,, xm であるとき x x2 xm B を B の閉包 universal closure という. B C と書く 8. M B となるのは M B C となるときである. 恒真な (valid) 論理式 いかなる解釈 ( モデル ) に対しても真になる論理式を恒真な valid 論理式という 述語論理におけるトートロジー ということもある どのような解釈をしても真になるということは 個別の対象要素 関数記号 述語記号の解釈に依存しないという意味であるすなわち論理式の形 ( 構造 ) により 恒真であるか否かが定まる M: Lucida Calligraph : MS ゴシック (UTF) 5 6 恒真な論理式の例 ( その一 ) A は x を自由変数として含まない. x A A, x A A 2. x B y(b[y/x]), x B y (B[y/x]) ここに y は B に含まれていない新しい変数. A x B x (A B), A x B x (A B) 4. A x B x (A B), A x B x (A B) 5. xb x C x (B C), x B x C x (B C) 6. ( xb x C) x (B C), x(b C) ( x B x C) 7 恒真な論理式の例 ( その二 ) 7. x y B y x B, x y B y x B 8. x y B y x B ( 関連の話題が前出 ) 9. x B x B 0. x B x B, x B x B ド モルガンの法則. (A x B) x(a B), (A x B) x(a B) 2. ( x B A) x(b A), ( x B A) x(b A). x(b C) ( x B x C) 4. x(b C) ( x B x C) 5. x(b C) ( x B x C) 8
恒真な論理式の説明 ( x B A) x(b A) 2の下 この論理式に含まれる自由変数が y,, ym のとき 任意の解釈 M について次をいえばよい M y ym{( x B A) x(b A)} 上は閉論理式であるから次をいう ( 解釈 4, 6) すべての u,,um D に対して M ( x B A)[u/y,,um/ym] M x(b A) [u/y,,um/ym] 以下の説明では 既に上のような項の代入が済んでいると仮定する 恒真な論理式の説明 (2) M ( x B A) であると仮定する. 解釈 4から (M x B ) ならば (M A) である ということになる 解釈 7から ( ある v D が存在して M B[v/x]) ならば (M A) である ということになる 上は (M B[v/x] を満たすような v D は存在しない ) または (M A) である となる さらに ( すべての v D に対して M B[v/x] ) または (M A) である となる 9 20 恒真な論理式の説明 () 論理式 A は x を自由変数として含まない すべての v D に対して (M B[v/x] または M A[v/x]) である すべての v D に対して (M B[v/x] または M A[v/x]) である ( すべての v D に対して (M B[v/x] A[v/x]) である ( すべての v D に対して (M B[v/x] A[v/x]) である M x(b A) 半分終り 2 恒真な論理式の説明 (4) M x(b A) であると仮定する. 解釈 6と4から すべての v D に対して (M B[v/x] ならば M A[v/x]) である になる 論理式 A は x を自由変数として含まない すべての v D に対して (M B[v/x] または M A ) ( すべての v D に対してM B[v/x]) または (M A) である ), さらに (M B[v/x] を満たす v D は存在しない ) または (M A) である (M B[v/x] を満たすv D が存在する ) ならば (M A) である 終 22 充足可能な論理式 ある解釈 ( モデル ) に対して真になる論理式を充足可能な satisfiable 論理式という 充足可能でない論理式を充足不可能 unsatisfiable という 論理式 A が充足不可能であることは A が恒真であることの必要十分条件である 2 冠頭標準形 prenex normal form 全称記号 と存在記号 が 他の論理記号の外側にあるとき 冠頭論理式という QxQyQz A, Q は あるいは 記号 A は全称記号も存在記号も含まない論理式 論理式 A と同値な冠頭論理式が存在するこれを冠頭標準形という ( 小野先生の説明 ) 恒真な論理式の, 4, 0,, 2 を使って同値変形する ただし A が自由変数 x を含むときは まず 2. により x を新しい変数で置き換えておく 24 4
冠頭標準形への同値変形 yp(x,y) y{ zq(x,y,z) R(x,y)} yp(x,y) w{ zq(x,w,z) R(x,w)} y P(x,y) w{ zq(x,w,z) R(x,w)} y w{ P(x,y) ( zq(x,w,z) R(x,w))} y w{ P(x,y) z(q(x,w,z) R(x,w))} { ( ( ( ) ( ))} y w z{ P(x,y) (Q(x,w,z) R(x,w))} さらに y w z{ P(x,y) ( Q(x,w,z) R(x,w))} y w z{( P(x,y) Q(x,w,z)) 分配法則 ( P(x,y) R(x,w))} 訂正 : 廣瀬先生の p.24, z は z です 25 冠頭標準形 ( 廣瀬先生の説明 ) 与えられた述語の中の別の変数が同じ変数の記号で表されているとき すべて異なる変数に書き換える例 : x P(x,y) y Q(y,z) は x P(x,y) w Q(w,z) x P(x) x Q(x, y) は x P(x) z Q(z, y) ド モルガンの法則を用いて否定記号 を内側に移動する (0) 全称記号 と存在記号 を外側に移動する (, 4,, 2) さらに 冠頭標準形と論理和標準形 冠頭標準形と論理積標準形を組合せることができる 26 5