融合原理 (resolution) 人工知能 論理と推論（２） 論理的帰結 節形式 融合原理 知識を組み合わせて知識を生み出す

Presentation on theme: "融合原理 (resolution) 人工知能 論理と推論（２） 論理的帰結 節形式 融合原理 知識を組み合わせて知識を生み出す"— Presentation transcript:

1 融合原理 (resolution) 人工知能 論理と推論（２） 論理的帰結 節形式 融合原理 知識を組み合わせて知識を生み出す
人工知能　論理と推論（２） 知識を組み合わせて知識を生み出す 融合原理 (resolution) 　論理的帰結 　節形式 　融合原理 　今回の授業では，命題論理の「節形式」と呼ばれる論理式で記述された複数の知識が与えられたとして，それらを組み合わせて「推論」することによって，既に知られている知識から論理的に帰結される新しい知識を生成する「融合原理」と呼ばれるアルゴリズムを学ぶ．

2 論理的帰結 (logical consequence)
論理的帰結(１)：論理的帰結の定義 論理的帰結 (logical consequence) が真となるどんな解釈によっても が真のとき， の論理的帰結　 は であるといい，つぎのように書く． 　「論理的帰結」の定義については，前回の授業でも触れたが，今回は特にこの概念が重要となるので，その復習からスタートする． 　論理式は，そこに含まれる変数の「解釈」（「真」と考えるか「偽」と考えるか）によって，全体として真であったり偽であったりすることを思い出そう．そこで，論理式PとＱが与えられたとして，Pを真とする解釈をすべて列挙してみる．それらのうちのどの解釈を用いても，必ずＱも真であるとき，「ＱはＰの論理的帰結」であるという．このスライドでは，このようなＰがｎ個与えられるような一般的な状況において，この「論理的帰結」の定義を拡張したものを示している． という前提が成り立つときには， という結論も成り立つことが確実に言えるということ．

3 論理的帰結(２)：真理値表による論理的帰結の判定
例 解釈 前提 結論 P Q P→Q P∨Q T F 　例として，このスライドにある３つの論理式 　　　ＰならばＱ，　ＰまたはＱ，　Ｑ を考え，「Ｑ」が「ＰならばＱ」及び「ＰまたはＱ」の論理的帰結であることを確認しよう． 　変数はＰとＱなので，可能な解釈は，このスライドの真理値表の４つの行に対応するある４通りがある．前回学んだ「ならば」と「または」の意味計算の方法によって計算すると， 「ＰならばＱ」と「ＰまたはＱ」という２つの前提を共に真（Ｔ）とする解釈は，この表のように，１つ目の解釈（Ｐ＝Ｑ＝Ｔ）と３つ目の解釈（Ｐ＝Ｆ，Ｑ＝Ｔ）である．この２つのいずれの解釈のもとでも，結論を表す論理式「Ｑ」は真である．したがって，定義により，「Ｑ」は「ＰならばＱ」及び「ＰまたはＱ」の論理的帰結であることがわかる． 前提が真となるすべての解釈 のもとで結論も真

4 論理的帰結(３)：演習問題 前提１ 暑くて湿度が高ければ，雨が降るだろう． 前提２ 湿度が高いのに暑くないということはあり得ない． 前提３
いま，湿度が高い． 　演習問題：このスライドに書かれた３つの前提が成り立つとすれば，「雨が降るだろう」という命題は，その論理的帰結となることを示そう．まず，記号化をする． 　Ｐ＝「暑い」 　Ｑ＝「湿度が高い」 　Ｒ＝「雨が降るだろう」 という変数を導入すると，３つの前提及び結論を表す命題は，スライドに示した論理式として記号化できる． 　つぎに，「論理的帰結」の定義にしたがって，前提を真とするすべての解釈を求めよう．変数が３つあるので，可能な解釈は最大で８つある．しかし，前提３が「Ｑ」という単純な形であることから，少なくともＱ＝Ｔであるような解釈だけに限ればよいので，最大でも４つにしぼられる．ここから先は宿題である． 論理的帰結 雨が降るだろう． ヒント：解釈は８通りあるが，ＱがＦである解釈は考える必要なし． 　　　　残りの４通りを考察する．

5 論理的帰結(４)：論理的帰結と充足不能の関係
背理法 の論理的帰結　 は 同値 は充足不能（矛盾）　 　「論理的帰結」という概念は，前回学んだ「充足不能（矛盾）」という概念と密接に関係している．それを示したのがこのスライドである．これは，一般に，数学において「背理法」と呼ばれる証明手法の根拠となっている．つまり，「結論Ｑは前提Ｐの論理的帰結である」という定理を証明するために，「前提Ｐが成り立ち，かつ，結論の否定が成り立つ」という命題は決して成り立たない（充足不能），すなわち，この命題は矛盾を含むことを証明するのである．

6 論理的帰結(５)：例 例 同値 は充足不能 解釈 前提 結論の否定 P Q P→Q P∨Q ￢Q T F
　先ほどの例を，いま説明した「背理法」の考え方で解いてみよう． 　前提である「ＰならばＱ」及び「ＰまたはＱ」は成り立つとして，それに加えて，結論「Ｑ」の否定「Ｑでない」が成り立つであろうか？ 　この真理値表からわかるように，可能な４つの解釈のいずれによっても，これら３つの論理式の少なくとも１つが偽（赤く示してある）であることがわかる．つまり，この３つの論理式が同時に成り立つことは絶対ない．したがって，それらの論理積（ＡＮＤ）は必ず偽となる．よって，この３つの論理式の論理積は充足不能である．ゆえに，一つ前に示したスライドの関係によって，「Ｑ」は「ＰならばＱ」及び「ＰまたはＱ」の論理的帰結であると言うことができる．

7 復習 節形式（１）：節形式への変換 節： リテラルの選言． 節形式： 節の連言． 節形式への変換 1 2 3 4 ド・モルガンの法則 5
復習　節形式（１）：節形式への変換 節： リテラルの選言． 節形式： 節の連言． どんな論理式も以下の変換ルール（左辺を右辺に書換え）で 等価な節形式に変換できる． 節形式への変換 1 2 　これは「節形式」の復習． 　「変数」，または，「変数の否定」を「リテラル」という． 　「節」は「リテラル」の論理和である． 　「節形式」は「節」の論理積である． 　どのような論理式もここで示した方法によって，論理的に等価な節形式に変形することができる． 3 4 ド・モルガンの法則 5 分配則 6

8 復習 節形式（２） ：節形式への変換 例 節形式 したがって，つぎの２つの節が得られる． 節集合
復習　節形式（２） ：節形式への変換 例 節形式 　節形式からＡＮＤ記号を除去して，節を集めたものが「節集合」である． したがって，つぎの２つの節が得られる． 節集合

9 融合原理（１） 融合原理 つぎの (1) (2) 式より (3) を導出する推論規則 融合節
　これが今回の授業の山場，「融合原理」の説明図である． 　２つの論理式(1),(2)が与えられたとしよう．さらに，(1)の一部には変数Pが含まれていて，(2)の一部にはその否定(not Ｐ）が含まれているとする．（この２つのリテラル（Ｐとnot P） は，実際には，このスライドのように左端に現われている必要はない．節はリテラルをORで結合したものであり，ＯＲはその結合の順番を変えたり入れ換えたりしても等価だからである． 　このような状況になっているとき，(1)からＰを除去し，(2)からnot Pを除去して，残りのリテラルをＯＲで結合したものは，やはり，節の形をしている．これを融合節と呼び，(3)と番号を付けよう． 　このように，(1)と(2)から融合節(3)を生成するアルゴリズムを融合原理という．Pを正リテラル，not Pを負リテラルという．この正負のことをリテラルの符号という．この言葉を使って表現すると，融合原理とは，２つの節から符号だけが異なるリテラルを１個ずつキャンセル（削除）し，残りのリテラルをORで結合するアルゴリズムであるということができる． 符号の異なるリテラルを１個ずつキャンセルし， 残りのリテラルを結合する．

10 融合原理（２）：例 例 モーダス・ポネンス(Modus Ponens) 例 対偶
　前回の授業で説明したような，よく知られる推論規則も融合原理によって説明できる． 　たとえば，モーダス・ポネンスは，スライドの右半面に書かれているように，「Ｐ」及び「ＰならばＱ」という２つの前提から，「Ｑ」という結論が導かれることを表している．この問題に対して融合原理を使うと，「Ｐ」及び（「ＰならばＱ」を節形式で表した）「not P またはＱ」からPとnot Pをキャンセルして「Ｑ」を導くことができる． 　対偶についても同様である．

11 融合原理（３）：例 例 三段論法 例 例 空節（矛盾）
　その他，いろいろな推論規則を融合原理によって統一的に説明することができる．融合原理とは，それほど強力なアルゴリズムなのである．これだけ知っていればあとは知らなくとも良いとさえ言えそうである． 空節（矛盾）

12 休憩

13 融合原理（４）：導出と導出可能性 導出と導出可能性 節集合 に次々と融合原理を適用し， 節の系列 が得られるとき， から が導き出される
という． 　節集合が与えられたとき，次々と融合原理を適用し，節が次々と生成されていく．生成された節は，最初の節集合から導き出された（あるいは導出された）ものであるという． また， から へ導出可能といい， とかく．

14 融合原理（５）：健全性 P = Fの場合： P = Tの場合： 定理 任意の２つの節 Ｃ１，Ｃ２ の融合節 Ｃ は
Ｃ１，Ｃ２ の論理的帰結になっている． 証明 Ｃ１，Ｃ２ を T とする解釈を考える． P = Fの場合： P = Tの場合： 　融合原理の理論的に重要な性質として，「健全性」と「完全性」がある． 　健全性とは，融合節(3)はその親である(1),(2)の節の論理的帰結になっていることをいう．つまり，融合原理によって生成される節はでたらめなものではなく，すでに知られている知識（節）から論理的・必然的に成立するものだけが生成されるのである． 　健全性は，融合原理のワンステップだけで成り立つのではなく，何ステップに渡っても成り立つ．つまり，融合原理によって導出された論理式は，すべて最初の節集合の論理的帰結になっている． 健全性：導出したものは論理的帰結になっている． ならば

15 融合原理（６）：完全性 健全性の別な言い方： 節集合 S から空節 □ が導き出されれば， S は充足不能である． 逆 完全性
　融合原理によって，空節が導き出されたとしよう．空節というのは，節Ｐと節not Pに融合原理を適用することによってできる，１つもリテラルを含まないような節である．Ｐとnot Pから作られることからもわかるように，これは「矛盾」を表している．健全性によって，もともとの節集合が真ならば，導出された節も真であることが保証されているのだが，空節は「偽」であり，絶対に真ではない．したがって，融合原理によって空節が生成されたということは，もともとの節集合が決して真には成り得ない，すなわち，その節集合は充足不能であることを表している． 　「完全性」というのは，その逆を表している性質である．節集合が充足不能ならば，必ずその節集合から空節を導き出すことができる．

16 融合原理（７）：融合原理を用いた証明 の論理的帰結 は 同値 は充足不能 同値 は充足不能 節集合 同値 から空節を導出可能
の論理的帰結　 は 同値 は充足不能　 同値 は充足不能　 節集合 　これまでの理論をまとめると，このスライドのようになる． 　「ＱがＰの論理的帰結である」ということを証明するのが目標である．そのためには，「Ｐかつnot Q」が充足不能であることを証明すればよい．そのためには，その論理式「Ｐかつnot Q」を節集合Ｓに変換し，融合原理によって空節を導出すればよいのである． 　健全性によって，空節が導出されれば，ＱがＰの論理的帰結であることを結論してよい． 　逆に，ＱがＰの論理的帰結ならば，完全性によって，実際，必ず空節を導出することができるのである． 　この過程はすべてコンピュータによって全自動で行うことができる．（論理式を節形式に自動変換する処理と，２つの節を系統的に組み合わせて融合節を生成する処理が中心となる．） 同値 から空節を導出可能　

17 融合原理（８）：例題 例 同値 は充足不能 先ほどの例を融合原理を用いて証明したのが，このスライドである．
　先ほどの例を融合原理を用いて証明したのが，このスライドである． 　この図は「融合木」と呼ばれるグラフ構造を表している．木のノードは与えられた節集合に含まれている節，または，それらから融合原理によって導出された節を表している．融合原理で用いた２つの節（親）とそこから生成された融合節（子）とを辺で結んでいる． 　最終的に空節（□）が生成されたので，与えられた節集合は充足不能であることがわかる．したがって，「Ｑ」は「ＰならばＱ」及び「ＰまたはＱ」の論理的帰結であることがわかった．

18 融合原理（９）：例題 前提１ 暑くて湿度が高ければ， 雨が降るだろう． 前提２ 湿度が高いのに暑くない ということはあり得ない． 前提３
　すでに述べたこの例題も融合原理で解いてみよう．そのために，前提を表すすべての論理式を節形式に変換する．また，結論を表す論理式は否定した後に節形式に変換する． 前提３ いま，湿度が高い． 否定 論理的帰結 雨が降るだろう．

19 融合原理（10）：例題 前提 結論の否定 　この融合木からわかるように，空節が生成されたので，問題で与えられた３つの前提が成り立つならば，その論理的帰結として，「雨が降るだろう」ということを結論としてよいことがわかる．