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

前回までの確認から

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

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

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

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

Prenex Conjunctive Normal Form

Prenex Conjunctive Normal Form Clause Prenex Matrix

PCNFの例

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

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

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

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

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

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

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

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

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

Skolem Standard Form

Skolem Standard Form Clause Prenex Matrix

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

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

真理値が保存されない例

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

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

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

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

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

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

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

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

例

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

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