人工知能特論2011 資料No.6 東京工科大学大学院 担当教員　亀田弘之.

Presentation on theme: "人工知能特論2011 資料No.6 東京工科大学大学院 担当教員　亀田弘之."— Presentation transcript:

1 人工知能特論2011 資料No.6 東京工科大学大学院 担当教員　亀田弘之

2 前回までの確認から

3 Prenex Conjunctive Normal Form
Literal Clause PCNF 前回までこんな話をしました。

4 Leteral Literalの定義： アトムはリテラル (例： P(x), Q(3,5,8) )
上記の１を正リテラル(positive literal)、 ２を負リテラル(negative literal) という。 （例： P(f(x)) は正リテラル, ~P(f(x)) は 負リテラル)

5 Clause Clauseの定義： ゼロ個以上かつ有限個のリテラルからなる選言のこと。 例： P(a) v Q(x,b,f(s))
ゼロ個以上かつ有限個のリテラルからなる選言のこと。 例：　 P(a) v Q(x,b,f(s)) ~Q(x,y) ＜＝１個のリテラルの選言！

6 いろいろな表記法があります。慣れるしかありません。
Clauseの集合による表記法 P(a) v Q(x,b,f(s))　 　{P(a) , Q(x,b,f(s))} ~Q(x,y)  {~Q(x,y) } いろいろな表記法があります。慣れるしかありません。

7 Prenex Conjunctive Normal Form

8 Prenex Conjunctive Normal Form
Clause Prenex Matrix

9 PCNFの例

10 PCNFへの変形 任意の述語論理式はPCNFに変形することができる。その際、その論理式の真理値は保存される。 例：

11 定理 任意の論理式φに対して、φと真理値が等価な論理式ψでかつPCNFのものが１つ存在する。

12 変形の手順（その１） 論理式φの中の→と↔を次の規則を用いて取り除く。 分離された変数がそれぞれ異なるように変数名を書き換える。
（A→B）　を　(~A v B) に置き換える。 (A↔B) を　(~A v B)^(A v ~B) に置き換える。 分離された変数がそれぞれ異なるように変数名を書き換える。

13 変形の手順（その２） すべての～がアトムの直前に来るように次の規則を用いて変形する。 ～∀x ψ を ∃ｘ～ψ に置き換える。
～( φ ∨ ψ ) を ( ~φ ∧ ~ψ ) に置き換える。 ～( φ ∧ ψ ) を ( ~φ ∨ ~ψ ) に置き換える。 ～～φ を φ に置き換える。

14 変形の手順（その３） すべての限量子∀と∃を論理式の先頭部分へ移動させる。 ∃ｘ φ∨ψ ＝＞ ∃ｘ (φ∨ψ)
∃ｘ φ∨ψ 　＝＞　 ∃ｘ (φ∨ψ) φ∨∃x ψ 　＝＞　∃ｘ (φ∨ψ) ∀ｘ φ∨ψ 　＝＞　 ∀ｘ (φ∨ψ) φ∨ ∀x ψ 　＝＞ ∀ｘ (φ∨ψ) ∃ｘ φ∧ψ 　＝＞　 ∃ｘ (φ∧ψ) φ∧∃x ψ 　＝＞　∃ｘ (φ∧ψ) ∀ｘ φ∧ψ 　＝＞　 ∀ｘ (φ∧ψ) φ∧∀x ψ 　＝＞　∀ｘ (φ∧ψ)

15 変形の手順（その4） Matrix部分をCNF形式に変形する。 ((A∧B)∨C) を ((A∨C) ∧(B ∨C)) に

16 PCNF導出の例（練習問題） 何度も練習してみてください。

17 確認問題 次の置き換えは、真理値を保存するか 確かめよ。

18 確認問題 次の置き換えは、真理値を保存することを確かめよ。

19 Skolem Standard Form

20 Skolem Standard Form Clause Prenex Matrix

21 PCNF ＝＞ SSFへの書き換え 限量記号（存在記号）∃を除去しなければならない。そのために、スコーレム定数やスコーレム関数を導入する。
例：

22 大切な注意事項（その１） 任意の論理式はPCNFに変形可能 任意のPCNFはSSFに変形可能

23 真理値が保存されない例

24 大切な注意事項（その２） BUT 充足不可能な論理式は充足不可能なSSFに変形される。

25 Herbrand Models 次に、フランスの論理学者Jacques　Herbrand が考案した解釈(interpretation)を導入する。 この解釈を特に、Herbrand interpretation とよび、この解釈に基づくモデルを Herbrand model と呼ぶ。

26 Herbrand universe U Herbrand base B Herbrand pre-interpretation J Herbrand interpretation I Herbrand model M 以下、例で説明する。

27 例： まず、このような論理式の集合を考える。

28 Herbrand Universe 元の論理式に含まれていた定数と関数に着目し、これからか得られるすべての項を集めたもの。

29 Herbrand　Base 元の論理式に含まれていた述語を、先ほどのUの要素に適用して得られる述語すべてからなる集合。

30 Herbrand pre-interpretation
解釈の領域D：Hebrand Universe U 定数記号の解釈: 自分自身に対応させる。 関数記号の解釈：自分自身に対応させる。

31 Herbrand interpretation
Herbrand pre-interpretation に基づくInterpretation をHerbrand Interpretation と呼ぶ。 なおHIの内、所与の論理式（群）を充足するものを Herbrand Model (HM) と呼ぶ。

32 例

33 注意事項 HMの意義 Σがモデルを持つ　　ΣがHMを持つ。 Σ　｜＝　φ　　SはHMを持たない。 ただし、Sは Σ∪{～φ} のSSF。

34 述語論理における推論 Resolution 代入 論理プログラミング（Prologなど）
帰納論理プログラミング(Progolなど) ＝＞知識分類・知識獲得・知識発見