Microsoft PowerPoint - logic ppt [互換モード]

Size: px

Start display at page:

Download "Microsoft PowerPoint - logic ppt [互換モード]"

のぶあきかむら
5 years ago
Views:

1 述語論理と ( 全称 ) ( 存在 ) 回の講義の概観 : 命題論理 ( 真理値 ) 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

2 , 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

3 論理式の意味述語論理の論理式の意味を考えるには対象領域 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

4 恒真な論理式の説明 ( 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

5 冠頭標準形への同値変形 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

Microsoft PowerPoint - logic ppt [互換モード]

Microsoft PowerPoint - logic ppt [互換モード] 寄せられた質問 : 演習問題についてこの講義の範囲に含まれる適切な演習問題が載っている参考書がありますか? できれば解答や解説が付いているものがあると良いのですが第回の授業の中で演習問題に取り組む方法を説明しますこの授業は回だけ行うもので書籍の1 冊分に比べると少ない分量しかカバーしていません回の講義の概観 : 1 完全性と不完全性命題論理命題論理 ( 真理値 ) ( 公理と推論規則