Microsoft PowerPoint - fol.ppt

Transcription

1 認知システム論知識と推論 (4) 知識と論理でを組み合わせて問題を解決する 一階述語論理 (first-order predicate logic) 一階述語論理入門 構文論 ( 論理式の文法 ) 意味論 ( 論理式の解釈 ) 前回までは, 命題論理 の構文と意味, および推論規則について学んだ. 今回からは, 命題論理よりも表現力の高い を学ぶ. 今回はその導入部分であり, 最初に, 命題論理では表現力が不十分であることを理解した後, 一階述語論理の構文 ( 論理式の文法 ) と意味 ( 論理式の解釈 ) について学ぶ. 一階述語論理 (first-order predicate logic) は, 文献によっては単に, (predicate logic) あるいは (first-order logic; FOL) と呼ばれることもある. 1

2 一階述語論理入門 (1/9): 命題論理の世界 P true true Q false 命題論理の世界 ( 原始命題の世界 ) 原始命題より細かな情報は表現されない 原始命題の真偽しか表現されない 原始命題を論理記号 ( ) でつないで複雑な命題を表現 まず, すでに学んだ命題論理の世界の概略を復習しておこう. 命題論理を構成する基本的な要素は原始命題である. これは,P, Q などの1つの命題記号で表現されるものである. 命題記号をそれ以上細かな要素に分解することはできない. そして, 原始命題について興味のある情報は, 真偽のみであり, それ以外の知識を表現することはできない. 原始命題を論理記号で結合することによって, より複雑な命題が表現される. 2

3 一階述語論理入門 (2/9) 命題論理の表現力の限界 これは OK P P Q Q 命題論理がうまくはたらく例を見ておこう. このスライドの例では, 雨が降っていることを P, 道路が濡れていることを Q で表し,P および P ならば Q という 2 つの知識から,Q であることを論理的帰結として導いている. いったん,P,Q に置き換えると, もとの意味を知らなくても, 機械的にこの推論が可能であることが重要である. 3

4 一階述語論理入門 (3/9) 命題論理の表現力の限界 これは? P Q (Socrates is a human.) (Every human is mortal.) R (Socrates is mortal.) ところが, このスライドの例では, 命題論理ではうまくいかない. ソクラテスは人間である は原始命題なのでPで表す. すべての人間は死ぬ運命である は, 結構複雑なことを言っている文だが, 命題論理の理論体系ではこの文をそれより細かな命題に分解できないので, やはりこれも原始命題なので,Qで表す. 人間なら, この2つの命題から ソクラテスは死ぬ運命である という結論を導くことができる. しかし, コンピュータは機械的にこれを導けるだろうか? 答えは否である. もとの意味を失って,PとQだけにしてしまったので, この2つからは有益な知識は何も導かれない. たとえば, いま議論している ソクラテスは死ぬ運命である も原始命題なのでRと表すとして, 明らかに,RはP Qの論理的帰結ではない.(PとQが真で,Rが偽である解釈が存在する.) これが命題論理の表現力の限界である. 今回学ぶ一階述語論理はこの限界を克服する表現力をもつ. 4

5 一階述語論理入門 (4/9) Aibo Human Mortal Mickey Human Mortal Jack Socrates 一階述語論理の世界 ( オブジェクトの世界 ) Human Will Elizabeth 名前のない要素も OK オブジェクト ( 個体 ) を表現できるオブジェクトの性質 (property) を命題として表現できるオブジェクト間の関係 (relation) を命題として表現できるオブジェクト間の関数 (function) を表現できる 一階述語論理の世界を構成する基本的な要素は である. オブジェクトは命題ではない. このスライドでは, オブジェクトとして人やアニメキャラクターやロボットを示しているが, 応用目的に応じて, オブジェクトは何でも良い. ここでいう オブジェクト とは, オブジェクト指向プログラミング でいう オブジェクト とは関係なく, 単に モノ という意味である. オブジェクトは有限個であっても無限個であってもよい. この世界に関する知識として, 一階述語論理は, つぎのようなことを表現できる. - オブジェクトの. たとえば,Socrates やWill というオブジェクトはHumanという性質 ( プロパティ ) をもつことを表現できる. - オブジェクト間の. たとえば,JackとWillは友人関係にあることを表現できる. - オブジェクト間の. 関数とは, 任意にオブジェクト x が与えられると, それに対応したただ1つのオブジェクト y に対応づける写像である. たとえば,Elizabeth をその父親 ( 図では名前はない ) に対応づけることができる. 5

6 一階述語論理入門 (5/9) オブジェクト ( 個体 ) を表現 Mortal A A A オブジェクトの性質 (property) を命題として表現 B A is mortal. オブジェクト間の関係 (relation) を命題として表現 A is a friend of B. A 個体記号 Mortal( A) 述語記号 (1 変数 ) 述語記号 (2 変数 ) Friend( A, B) オブジェクト間の関数 (function) を表現 関数記号 A father of A 名前のない要素 father( A) このスライドの右端にある表現が, 一階述語論理による具体的な表現である. 1つめは, を用いて, を表現している.( オブジェクトは命題ではない.) 2つめは, を用いて, オブジェクトの を命題として表現している. 3つめは, を用いて, オブジェクト間の を命題として表現している. 4つめは, を用いて, オブジェクト間の を表現している.( 関数の表現は命題ではない.) 6

7 一階述語論理入門 (6/9) 原始命題は,1 つの述語記号とその引数 ( 項 ) から構成される A B A is a friend of the father of B. Friend( A, father( B)) 原子式 (atom) 項 (term) 一階述語論理では, 原子式が原始命題を表現する. 以上を組み合わせて, さらに複雑な知識を表現できる. たとえば, このスライドの表現は, AはBの父の友人である ことを表す命題である. Bの父 の名前に言及することなく, その人物とAとの友人関係が表現されている. ここで,Aやfather(B) は, オブジェクトを表す表現である. このような表現を (term) という. また, 命題はFriend(A, father(b)) は, これ以上分解すると項になり, 命題ではなくなる. これは原始命題に相当するもので, 一階述語論理では と呼んでいる. 7

8 一階述語論理入門 (7/9) (Every human is mortal.) 変数記号 全称記号 x Human( x) Mortal( x) Every human is mortal. = Everything is mortal if it is human. = For all object, if it is human, then it is mortal. と の組合せは, 相性が良い. さらに, 一階述語論理では, と を用いて, すべてのオブジェクトが満たしている命題をまとめて表現することができる. このスライドの例では,, もしxが人間ならば,xは死ぬ運命にある という一般的な知識が表現されている. この例のように, 全称記号 ( ) と含意記号 ( ) は相性が良く, 組み合わせて知識が表現されることが多い. まず, ( x) で すべてのx について と言っておき, その後, 実際にはある種の限定された範囲のxであることを含意 ( ) の前提で規定するのである. 8

9 一階述語論理入門 (8/9) (Every human is mortal.) (Socrates is a human.) x Human( x) Mortal( x) Human( Socrates) (Socrates is mortal.) Mortal( Socrates) これは機械的に導出可能! ( x = Socrates ) 詳しくは次回以降に学ぶが, 一階述語論理によって, さきほど命題論理では不可能だった推論が可能となる. 実際, この例では, すべての人間は死ぬ運命である と ソクラテスは人間である を一階述語論理で記号化すると, あとは機械的に ソクラテスは死ぬ運命である という結論を導くことができる. そのキモは, 変数 xに自動的にsocratesを代入することによって, 命題論理の ( あるいは ) の推論規則 Human(Socrates) Human(Socrates) Mortal(Socrates) Mortal(Socrates) が適用できるように論理式を変形することにある. 9

10 一階述語論理入門 (9/9) 存在記号 (Mickey has a human friend.) x Human( x) Friend( x, Mickey) Mickey has a human friend. = Mickey has something which is human and his friend. = There exists something which is human and which is a friend of Mickey. と の組合せは, 相性が良い. また, 一階述語論理では, と変数を用いて, 指定された条件を満たすあるオブジェクトが少なくとも1つ存在することを表現することができる. このスライドの例では, そのxは人間であり, かつ,xはミッキーの友人である という知識が表現されている. この例のように, 存在記号 ( ) とAND 記号 ( ) は相性が良く, 組み合わせて知識が表現されることが多い. まず, ( x) で あるxが存在して と言っておき, その後に, そのxが満たすべき条件を AND で結合することによって,xの存在範囲を限定していくのである. 10

11 述語論理の構文論 論理式の文法 11

12 構文論 (1/6) 一階述語論理の構成要素 一階述語論理の構文要素個体記号 ( 定数 ): a, b, c, John,30, Socrates 変数 : x, y, z, u, v 関数記号 : f, g, h, father, age, plus 述語記号 : P, Q, R, HUMAN, MORTAL, GREATER DOCTOR( father( John)) GREATER( age( father( John)), plus( a,30)) a+30 一階述語論理の (syntax) とは, を作るために を正しく並べるための 文法 を規定するものである. その並べる記号は, このスライドにある4 種類に分類できる.( そのほかに, など, 事前に組み込まれている論理記号がある.) (individual symbol) は, 定数 (constant) とも呼ばれ, を表す記号である. は, やはり1つのオブジェクトを表す記号なのだが, 特定のオブジェクトではなく, 後に, などの記号とともに, を指すために用いられる.( 変数 といっても, 数 を表すものに限定されない.) は,1つ以上のオブジェクトを引数とし,1つのオブジェクトに対応させる を表現する. は,1 つ以上のオブジェクトを引数とし, 真理値 ( 真または偽 ) に対応させる関数 ( そういう関数を という ) を表現する. 12

13 構文論 (2/6) 項 John x ( 項に, father( John) age( father( John)) plus( a,30) 定数や, 変数, 関数記号を用いて, 別のオブジェクトを表現する (term) を構成することができる. たとえば, father(john) : ジョンの父 age(father(john)) : ジョンの父の年齢 plus(a,30) :a+30 がその例である. 項はオブジェクトを表現するものであり, 真偽を表現するものではない. したがって,4 種類の記号のうち, 項には述語記号が用いられないことに注意しよう. 13

14 構文論 (3/6) 項 項 f n t 1, f ( t1,, t n ), t n 1 つ前のスライドで述べた の正式な文法はこのスライドのとおりである. 14

15 構文論 (4/6) 原子式 原子式 DOCTOR( John) GREATER( age( John),20) P n t 1,, t n (,, ) P t1 t n は, それ以上分解すると命題ではなくなる命題 ( )( と書くこともある ) を表すもので, 述語記号の引数として項を並べたものである. 15

16 構文論 (5/6) 限量子 All ( x) ( x) Exists x (for all x, ) x (there exists x such that ) と ( この両者をあわせて という ) によって, 変数 xのもつ不定性の意味を規定する. x は, x (for all x), xは, x (there exists x such that ) のように読む. 16

17 構文論 (6/6) 論理式 論理式 原子式は論理式である. P, Q が論理式ならば, 以下の5つも論理式である. ( P) ( P Q) ( P Q) ( P Q) ( P Q) P が論理式ならば, 以下の 2 つも論理式である. ( x) P ( x) P 原子式を論理結合子や限量子と組み合わせることによって, 一階述語論理の を作ることができる. このスライドでは, その文法を帰納的に定義している. 17

18 述語論理の意味論 解釈に基づく論理式の真理値の計算 18

19 意味論 (1/7) 解釈 P,Q DOCTOR(John) GREATER( age( John),20) ここから, 一階述語論理の意味論を学ぶ. その中心となる概念が論理式の (interpretation) である. 命題論理の場合, 解釈 とは, 論理式に現れるP,Qなどの命題記号への真理値 (TまたはF) への割り当てのことであった. それに対し, 一階述語論理の場合には,4 種類の記号 ( 個体記号, 変数, 関数記号, 述語記号 ) が含まれるので, それぞれが何を意味するのかを表すものが 解釈 となる. 19

20 意味論 (2/7) 解釈 解釈 G D G D n n D D n n D {T, F} 一階述語論理における 解釈 の定義は, このスライドのとおりである. すなわち, とは, まず, 空でない集合 ( ) を明確にし, それを基礎として, 個体記号, 関数記号, 述語記号の意味を割り当てたものである. 数学的な言葉で説明しているので, みかけは難解に見えるかもしれないが, 言っていることは, これまですでに直観的に述べたとおりの意味を表現しているにすぎない. 20

21 意味論 (3/7) 解釈 GREATER( One, Nine) D={0, 1, 2,. } One 1 Nine 9 GREATER > GREATER( One, Nine) = (1> 9) = F このスライドは, 論理式 GREATER(One,Nine) の一つの例を示している. 定義域 Dを非負整数の全体とする. 定数には, それぞれ,Dの要素を割り当てる必要がある. この解釈では,Oneには1, Nineには9を割り当てている. 述語記号は, ただ1つ,GREATERである. これは2 変数なので, 引数として,2つの非負整数を受け取ったときに, 真または偽を返す関数を割り当てる必要がある. ここでは, 数学でふつうに使われる大小関係 (>) を関数とみなして割り当てている. たとえば, (5>3)=Tである. この解釈によると, 冒頭の論理式の値は GREATER(One,Nine) = (1>9) = F と計算できる. 21

22 意味論 (4/7) 解釈 D={ } GREATER( One, Nine) One Nine 尾根さん仁根さん GREATER(x,y): x y x 尾根さん 尾根さん 仁根さん 仁根さん y 尾根さん 仁根さん 尾根さん 仁根さん GREATER(x,y) = = T F T F F もちろん, 解釈は自由に与えられるので,1つ前のスライドで示したものが, 論理式 GREATER(One,Nine) の唯一の解釈というわけではない. たとえば, このスライドに示した意外な解釈もあり得る. 定義域 Dは,2 人の人物 尾根さん と 仁根さん からなる集合とする. 定数 Oneには 尾根さん,Nineには 仁根さん を割り当てる.( これは, たまたま, 記号をローマ字読みしたものになっているが, 本来, 別にそのような必要もない.) 述語記号 GREATERは, より偉大である という意味なのであろうか. ただし, より偉大である という言葉では数学的に厳格な定義とはならないので, この表のように,2つの引数にDの要素を受け取ったときに,TかFの値を返すような関数として定義している. この解釈によれば, 冒頭の論理式の値は GREATER(One,Nine) = 尾根さんは, 仁根さんより偉大である = T と計算できる. 22

23 意味論 (5/7) 解釈 LOVES( John, father( John)) = T D={ 1, 2, 3, } 定数への割当て 実世界の DB を用いても可 John 人物 5 father( 人物 i) = 人物 (i+1) LOVES( 人物 i, 人物 (i+1)) = T LOVES( 人物 i, 人物 (i+2)) = T それ以外は,LOVES( 人物 i, 人物 j) = F 定義域は無限集合でもよい. たとえば,Dを無限の人の集合とし, 人を区別するために,1,2,3, と番号付けることにする. 定数 Johnには, たとえば, 人物 5を割り当てる. 関数記号 father は, father(x)= xの父親 と解釈する. このスライドの例では, 人物 i の父親は, 番号の1つ多い 人物 i+1 であるという世界を解釈として与えている. 述語記号 LOVESは, LOVE(x,y)= xはyを愛している と解釈する. 数学的に, 厳密にするため, 人物 i は, 番号の1つ多い 人物 i+1 と, 番号の2つ多い 人物 i+2 を愛しているという世界を示している. もちろん, この2つの世界は単なる例であり, 実世界の親子関係や恋愛関係のデータベースがあれば, それによって, 具体的な解釈の内容を定義してよい. 23

24 意味論 (6/7) 論理式の真理値の計算 論理式の真理値原子式の真理値は解釈によって直接定まる. P, Q の真理値が定まっていれば, 以下の論理式の真理値も計算できる. ( P) ( P Q) ( P Q) ( P Q) ( P Q) ( x) P は,P の真理値がD のすべての要素 x についてT ならばT, さもなくば F. ( x) P は,P の真理値がD の少なくとも1つの要素 x についてT ならばT, さもなくば F. 1 つ前のスライドのように, 解釈 を与えて, はじめて論理式の真理値を計算することができる. このスライドは, その計算規則を示している. いずれも, ごく自然な定義になっている. 24

25 意味論 (7/7) 充足不能, 充足可能 恒真どんな解釈のもとでも真充足不能どんな解釈のもとでも偽充足可能ある解釈のもとで真 論理的帰結 P1, P2,, Pn Q が真 のすべてを真とするどんな解釈のもとでも P P P Q 1 2 n が充足不能 命題論理と同様に,,,, という概念を定義することができる. 定義の内容は, 表面的には, 命題論理のときと同じである. しかし, 内容的には, 解釈 の厳格な定義が, 命題論理と一階述語論理とでは異なっていることに注意しよう. また,QがP1,,Pnの論理的帰結であることは,P1 Pn Qが充足不能であることと同値である ( 背理法 ) ということが, 命題論理と同様に成り立つ. 25