人工知能論理と推論 (1) 知識を組み合わせて知識を生み出す 命題論理 (Propositional Logic) 人工知能と論理 命題論理の構文 命題論理の意味 節形式 1
なぜ人工知能で論理を学ぶのか なぜ人工知能で論理 (LOGIC) を学ぶのか. 言語としての論理 構文, 意味 アルゴリズムとしての論理 推論 知識ベース ELL, ASK 知識 知識 推論アルゴリズム (= LOGIC) 知識 知識表現言語 (=LOGIC) 今回の授業では と呼ばれる古典的な論理を学ぶ. その前に, なぜ, 人工知能で論理を学ぶのかを説明しておく. 一般に, 人間がコンピュータに情報を与える 言語 といえば, すぐプログラミング言語が思いつく. それはコンピュータへの命令の列すなわちプログラムを具体的に記述したものである. しかし, そもそもAIの究極的な目的の1つは, そのようにいちいち命令しなくても, ふつうの言葉で意図を伝えれば, 自動的に適切な命令を組み立てて実行してくれる知的な情報システムを目指しているのである. そのようなAIシステムでは, コンピュータと人間が日本語や英語などの で対話することを理想としている. その言語は必ずしもコンピュータへの命令を表したものではなく,AIシステムに何らかの知識を与えたり, 解いて欲しい問題を与えたりするために使われる.AIシステムは獲得した知識を と呼ばれる一種のデータベースに蓄える. ただ, 残念ながら, コンピュータが自然言語を理解するという技術はまだ開発の途上にあり, 現状ではそれをじゅうぶんに利用することはできない. そこで何らかの人工的な言語で, しかもプログラミング言語ではなく, 知識を与えたり, 問題を記述するための と呼ばれる類の言語が必要となる. そのようなもののうちで, 現在, 最も中心的な役割を果たしているのが, 論理に基づく言語なのである. つまり, ここでは論理とは言語のことである. したがって, それを理解するには, 他のいろいろな言語を理解するのと同様に, 正しい文を生成するための文法規則 ( ) や与えられた文を解釈する規則 ( ) を理解する必要がある. つまり, 知識や問題を表現する手段という静的な側面が,AIにおける論理の第一の役割である. それに対し, AIにおける論理の第二の役割は動的なものである.AIシステムは, 与えられた知識ベース内の複数の知識を使って, 新しい知識を動的に生成する機能が求められる. その機能を という. コンピュータに推論を行わせるアルゴリズムは, と呼ばれる論理的な規則に基づいている. したがって, ここでは論理とは という動的な計算手順を作り出すものとして働くことになる. 2
いろいろな論理と推論がある 完全な知識に基づく数学的な推論 命題論理 : 命題 ( 文 ) を1つの記号で表現 述語論理 : オブジェクトとその関係を記号で表現不確実な知識に基づく推論 ファジィ推論 : あいまいで主観的な知識を扱う 確率推論 : 観測事実から命題が真である確率を計算知識が欠けているときの推論 帰納推論 : 多数の観測事実から一般法則を導く 仮説推論 : 観測事実を説明できる仮説や信念を導く 単に論理や推論といっても,AIではさまざまなものが考えられている. まず, 数学の試験問題を解くときのように, 問題を解決するための知識が正確ですべてそろっているとき, それは であるという. そういう場合には, ギリシャ時代から発展してきて現在でも多くの科学で使われている標準的で数学的な論理と推論の方法がある. もっとも単純なのは, 命題 ( 文 ) を1つの記号で表現する である. それをやや複雑にしたものとして, 命題 ( 文 ) を主語や目的語を表現する名詞 ( オブジェクト ) とそれらの間の関係を表現する動詞 ( 述語 ) などに分解して, 複数の記号で1つの命題を構造的に表現する がある. 実際の応用システムでは, 数学と異なり, すべての知識が正確であるとは限らない. そのような を扱うための推論手法として, や がある. また, の推論手法として, や などがある. 3
就職試験に見る命題論理 (1) 次の1~3はいずれも事実であるとする. 1お風呂が好きな人は, きれい好きである. 2 歯みがきが好きな人は, お風呂が好きである. 3お酒が好きな人は, タバコが好きであり, しかも歯みがきが好きである. このとき, 次のア~オの中で確実にいえることをすべて選べ. ア. 歯みがきが好きな人は, タバコが好きである. イ. お酒が好きな人は, 歯みがきが好きである. ウ. タバコが好きな人は, きれい好きである. エ. タバコが好きでない人は, お風呂が好きでない. オ. きれい好きでない人は, お酒が好きでない. 公務員試験や企業の入社試験の第 1 次試験にはよくこのような問題がでる. これは受験者の論理的な思考能力を問うのが目的である. 先へ進む前に, まずあなた自身でこの問題の解答を考えてみてほしい. 4
就職試験に見る命題論理 (2) 論理式 知識を記号を使った論理式で簡潔に表現する 1お風呂 きれい 2 歯みがき お風呂 3お酒 タバコ 歯みがきア. 歯みがき タバコイ. お酒 歯みがきウ. タバコ きれいエ. タバコ お風呂オ. きれい お酒 この問題を解く第 1 のポイントは命題 ( 真偽を判定できる文 ) を記号で表すことである. そうしなければ, 日本語や日常的な常識に惑わされて, 正しい解答を導くことの障害となってしまう. 記号というのは,A,B,C などのことである. たとえば, お風呂が好きである という命題を A と表す. しかし, 我々日本人向けには, 漢字やひらがなも記号なので,A ではなく お風呂 とするのがわかりやすい. 同様に, きれい好きである を きれい と表現する. つぎに,1 の お風呂が好きな人は, きれい好きである を お風呂が好きならば, きれい好きである のように読み替える. このように, 命題論理では, は, である という文を, であるならば, である のように論理学的に表現しなおすとよい. そしてそれを の形で記号で表現する. を, を という.1 の場合は, お風呂 きれいとなる. このように文を記号で表現したものを という. 同様に考えると, 2 は, 歯みがき お風呂となる. 3 の命題はやや複雑である. タバコが好きであり, しかも歯みがきが好き のように 2 つの命題がどちらも真であることを表すために, 命題論理では標準的には (and) という言葉を使い, という記号で表現する. したがって, 全体として,3 の論理式は, お酒 タバコ 歯みがきとなる. この問題では使われていないが,2 つの命題のうち少なくとも一方が真であることを表すために, 論理学では, (or) という言葉を使い, という記号で表現するので, これも覚えておこう. また, 命題 である に対して, それを (not) という言葉によって否定した でない という命題を論理式として表すには, 否定したい命題を表す論理式 ( とする ) の前に特別な記号 (-) を付けて ( - ) とするか, または, の上全体に横線を引く. この授業では, この PowerPoint のノートの文書では前者, スライドでは後者を用いることにする. このようにして, 事実 1~3 をすべて論理式で表現したら, 確実に成り立つかどうか判定したい命題ア ~ オもすべて論理式で表現する. その結果がスライドに表示されている. 5
就職試験に見る命題論理 (3) 推論規則 P Q Q P 対偶 P Q Q R P R 三段論法 P Q P Q モーダスポネンス P Q R P Q P R こうして, すべての事実 1~5とすべての設問ア~オを論理式にしてしまえば, もう, もとの日本語表現を読み返す必要はなく, すべての判断は論理学が決めている というもので機械的にできるのである. 推論規則のうち, よく知られているものを4つ紹介する. 1つめは というものである. これは, P Q が真であるとわかっているときに, - Q -P という対偶命題も真であると結論してよいという推論規則である. また, 逆に, -Q -P が真ならば, P Q も真である. これをこの問題に適用すると,1 お風呂 きれい が真なので, その対偶命題 -きれい -お風呂 ( お風呂が好きでないならば, きれい好きでない ) が真であると結論できる. 2つめは と呼ばれるもので, P Q と Q R のように,1つめの命題の結言と2つめの命題の前言が同じ ( ともにQ) であるような2つの命題が真であるとわかっているときに, Qを仲立ちにした2つの命題をつないだ P R も真であると結論してよいという推論規則である. 3つめは, というギリシャ語で呼ばれているもので,P QとPが真であるときに,Qが真であると結論するものである. 4つめは特に知られた命名はされていないのだが, P Q R のように結言が (and) で結ばれている命題が真であるときには, それを分解した P Q と P R もそれぞれ真であると結論してよいという推論規則である. これを3の お酒 タバコ 歯みがき に適用すると, お酒 タバコお酒 歯みがきという2つの命題が真となることがわかる. 以上の4つの推論規則ではまだまだ足りないのだが, これで実用上多くの問題をカバーすることができるので, 就職試験対策くらいならこれで良しとしよう. 6
就職試験に見る命題論理 (4) 推論 お風呂 歯みがき きれい お酒 タバコ ア. 歯みがき タバコイ. お酒 歯みがきウ. タバコ きれいエ. タバコ お風呂オ. きれい お酒 以上からわかった事実を図にしたのがこのスライドである.P Qという命題にあわせて, 図では, ノードP からノードQに矢印 ( 有向辺 ) を付けている. では, 設問ア~オが確実に成り立つかどうか判定してみよう. ア. 歯みがき が真であると仮定しても タバコ という結論が得られない. イ. すでに説明したように,3から お酒 歯みがき が真であるので, これは確実に言える. ウ. タバコ が真であると仮定しても きれい という結論が得られない. エ. これは対偶を考えて, お風呂 タバコ と同じことであるが, お風呂 が真であると仮定しても タバコ という結論が得られない. オ. これは対偶を考えて, お酒 きれい と同じことである. お酒 歯みがき, 歯みがき お風呂, お風呂 きれい を用いて3 段論法を2 回適用すると, お酒 きれい が真となる. 以上から, 確実に言えるのは, イとオである. 7
命題論理の構文 (1) 構文要素 構文要素を一定の規則で並べると論理式となる. 命題論理の構文要素 論理定数 : true と false 命題記号 : それ以上分解できない命題 ( 原始命題 ) を表す記号.p, q, r など. 論理記号 : 命題を結合して複合した命題を作る記号. AND かつ 連言 OR または 選言 NO でない 否定 IMPLY EQUIV ならば 等しい 含意 同値 命題論理の文法を説明する. それは, 論理式を作るための正しい規則からなっている. まず, 論理式を作るための素材ともいえる を覚えてほしい. これは,,, の3つに分類される. その説明はこのスライドに書かれているとおりである. 8
命題論理の構文 (2) 論理式 論理式 : 原始命題を論理記号でつないだ文. 論理式 論理定数は論理式である. 命題記号は論理式である. P ( P) true false が論理式ならば, は論理式である. P が論理式ならば, 以下の 4 つも論理式である. ( P Q) ( P Q) ( P Q) ( P Q) 例 p ( ( q ( r))) は論理式である. P p ( q( r)) は論理式でない. これらの構文要素を適切な規則にしたがって並べた記号列が文法的に正しい論理式である. その規則はこのスライドに書かれた 4 つである. 9
命題論理の構文 (3) 論理式 ( 続き ) リテラル 命題記号はリテラルである. 命題記号はリテラルである. p p 正リテラル 負リテラル カッコの省略ルール 論理記号の優先順位 と の結合則の利用 (( p q) r) = p q r 例 (( p) (( ( q r)) s)) のカッコを省略すると p ( q r) s 1 個の命題記号自体, または, その否定を という. とくに, 前者を, 後者を という. また,5つの論理記号の結合の をこのスライドのように約束し, 不必要なカッコは省略してよいこととする. たとえば,(P Q) Rは, が より結合の優先順位が高いので, カッコを省略して, P Q Rとしてよい. また, だけ, あるいは だけが連続して結合している部分は, この論理記号の (P Q) R = P (Q R) (P Q) R = P (Q R) により, カッコによる結合の順番が意味を持たないことから, まとめてカッコを省略できる. 10
命題論理の意味 (1): 解釈の概念 解釈 : 論理式を真偽に対応付ける写像 論理式 ( 構文領域 ) true false p q p p q 解釈 真偽値 ( 意味領域 ) ( ) ( ) 命題変数 p,q,.. の解釈だけは自由に決められる.. つぎに, 文法的に正しい論理式が与えられたとして, それが何を意味するのかを決める規則を学ぶ. ここでいう 意味 とは, 命題論理の場合, その論理式が表している命題が真なのか偽なのかということである. その中心となる概念は, 論理式を真偽に対応付けるための というものである. スライドの図のように, 論理式の集合 ( と呼ぶ) と真偽値の集合 ( と呼ぶ) を考える. 解釈とは, 構文領域に含まれる論理式の1つ1つを意味領域に含まれる真偽値に対応付けるもの ( ) である. そのような対応は組合せに応じてたくさんあるので, 解釈というものもたくさんあることになる. しかし, つぎのような条件によって, 実際には, 命題変数だけに対する対応 ( 意味 ) を決めることにして, それ以外の論理式に対する対応 ( 意味 ) は自動的に決まるようにする. 1つめの条件は,true という論理式には( 真 ) を対応付け,falseという論理式には( 偽 ) を対応付けるということである. これは,true, falseの常識的な意味付けを要求している条件である. 2つめの条件は,not, and, or,, の5つの論理記号を用いて作られた論理式の意味は, その中に含まれる命題変数の意味に基づいて, 計算によって自動的に求めるということである. その計算規則は, つぎのスライドで. 11
命題論理の意味 (2): 論理式の解釈 命題変数 p,q,.. の解釈を決めると, 他の論理式の解釈は : true の値は( 真 ), false の値は( 偽 ) ( P) の値は P の値の逆. ( P Q) ( P Q) ( P Q) ( P Q) の値は, 以下の真理値表に基づいて決める. P Q P Q P Q P Q P Q このスライドがその計算規則である. これを使うと, どんな複雑な論理式の値も命題変数の値に基づいて計算することができる. 12
命題論理の意味 (3): 論理式の解釈 例 p=, q=, r = p =, q=, r = のとき ( p q) r = ( ) = = のとき ( p q) r = ( ) = = これは論理式の意味 ( 真偽値 ) の計算例である. 13
命題論理の意味 (4): 恒真 恒真どんな解釈をしても真 例 p p ( p q) ( p q) p q p q p p q (p q) ( p q) ここからは解釈との関連で特別な性質をもつ論理式について見ていこう. どんな解釈をしても真である論理式は であるという. このスライドの2つの例のうち, 1つめは必ず真となることはすぐわかる.2つめがそうであることはすぐにはわからないので, 真理値表を使って,4 通りのすべての解釈に対して, この論理式が真であることを確認している. この2つめの結果は, それ自体が重要で, 覚えておく価値がある. つまり,p q(pならばq) という論理式は-p q(pでないか, または,qである) と等価 ( 常に同じ値をもつ ) ということである. この2つの論理式は意味内容が全く同じなのである. 14
命題論理の意味 (5): 充足不能と充足可能 充足不能どんな解釈をしても偽例 p p 充足可能ある解釈のもとで真 例 p q 充足不能 p p 充足可能 p q 恒真 p p どんな解釈をしても偽である論理式は であるという. ある解釈 ( 少なくとも1つの解釈 ) のもとで真となる論理式は であるという. 15
命題論理の意味 (6): 論理的帰結 論理的帰結 P1, P2,, Pn のすべてが真となるどんな解釈によっても Q が真のとき, Q は P 1 P 2,,, Pn であるといい, つぎのように書く. P1, P2,, Pn Q 例 P QQ, R P R の論理的帰結 論理式 P1,P2,...,Pnのすべてが真となる解釈はいろいろあるだろうが, そのような解釈からどれを採用しても, その解釈のもとで論理式 Qが真となるとき,QはP1,P2,...,Pnの であるといい, このスライドのような表記をする. 冒頭の就職試験問題の場合には, P1,P2,...,Pnは1,2,3に対応し,Qは設問ア~ オの1つ1つに対応する. 問題文の中で 確実に言えるものはどれか という設問は, 論理的帰結になっているものはどれか という意味である. したがって, それを判断する一般的な方法は, 論理的帰結の定義にしたがって, つぎのようなものとなる. まず, P1,P2,...,Pnのすべてを真とする解釈をすべて求める. これは命題変数に真偽値を与えるすべての組合せについて, 論理式の値を計算することによってできる. つぎに, それらの解釈ごとにQが真かどうかを計算する. どの解釈に対してもQが真ならば, 定義によって,QはP1,P2,...,Pnの論理的帰結であり,Qであることが確実に言える. そうでなければ,Qは論理的帰結ではない. しかし, この方法はすべての解釈について論理式の真偽を計算するので多くの手間が必要である. すでに学んだいくつかの推論規則を用いればそのような手間を軽減して結論を導くことができるのである. 16
17
節形式 (1): 節形式への変換 節 : リテラルの選言. p q r 節形式 : 節の連言. ( p q) ( p q) r どんな論理式も以下の変換ルール ( 左辺を右辺に書換え ) で等価な節形式に変換できる. 1 P Q = ( P Q) ( Q P) 2 3 P Q P = = P Q P 4 ( P Q) = ( P) ( Q) 5 ( P Q) = ( P) ( Q) ド モルガンの法則 ( P Q) R = ( P R) ( Q R) 分配則 6 節形式への変換 論理式の形はかなり複雑なものになり得るが, その意味 ( 真偽値 ) を変えることなく, それをもっと簡単な論理式に変換できる. その簡単な論理式とは, と呼ばれる形のものである. 節は (0 個以上の ) リテラルを (or) で結合したもの ( ) である. また, (0 個以上の ) 節を (and) で結合したもの ( ) を節形式という. 通常, 節形式となっている論理式からは をはずし, 結合されていた節を集めた集合 ( ) の表現を採用する. 論理式を節形式に変換する方法は機械的である. このスライドに示されている6つの等式を用い, 論理式の中にいずれかの等式の左辺に合致する部分があったら, それを対応する右辺に書き換える. そのような書換えを可能なだけ繰り返し, もうそれ以上書き換えられなくなったら, そのときの論理式は節形式になっている. 1つめの等式を使えば, という論理記号を除去できる. 2つめの等式を使えば, という論理記号を除去できる. この時点で論理記号は,not, and, or だけとなる. つぎに,4つめと5つめの等式( ) を使うと, カッコ内のandとorを反転させながら外側に出し,notを論理式の内部に移動させることができる.notを最も内側まで移動すると, 命題変数の直前にnotがついたもの, すなわち, リテラルができてくる. 3つめの等式は, その途中でnot が連続した場合には, 連続した2 個を除去するものである. 6つめの等式は,andがカッコの内側にあって, その外側にorがあるとき, を適用して,orを内側にし,andは外側にするものである. これを繰り返すとすべてのandが最も外側に来て, その内側はorによりリテラルを結合したもの, すなわち, 節となる. 18
節形式 (2) : 節形式への変換 例 p ( q r) = p ( q r) = p ( q r) = p ( q r) = p ( q r) = ( p q) ( p r) 節形式 したがって, つぎの 2 つの節が得られる. 節集合 p q p r これがその例. 最初に与えられた論理式がどの等式によって書き換えられているかを確認してほしい. 19
節形式 (3) : 節形式と if-then ルール 節は if-then ルールに対応する. 負リテラル = 条件の AND p q = p q ( if p then q) p q r = p q r ( if p & q then r) 恒真 を説明したスライドで確認したように, じつは, 節 -p q というのは,p q と等価である. この例ばかりでなく, 一般に, どのような節も, もし かつ ならば, または である というような if-then というものと等価なものである. 節は正リテラルと負リテラルを (or) で結合した論理式であるが, その中の負リテラルの否定記号 (-) を取り外したものが, if-then ルールの条件部 ( もし かつ ならば ) にきて, それらがすべて (and) で結合される. 20
節形式 (4) : 節形式と if-then ルール ( 特殊ケース ) 正リテラル = 結論の OR p q r s = p q r s p q = true p q p q = p q false = true false 空節矛盾 一方, 節の中のすべての正リテラルは (or) で結合されたままif-then ルールの結論部 ( または である ) になる. 特殊ケースとして, 節の中に負リテラルが1つもなければ, if-then ルールの条件部は true とする. また, 節の中に正リテラルが1つもなければ, if-then ルールの結論部は false とする. 最後に, 節が1つもリテラルを含まないものを というが, これはいまの約束を使えば,true false ( つまり, 真ならば偽 ) となり, 常に偽である論理式, あるいは, であることを表す論理式である. このような if-then ルールは, 知識を論理的に表現するための言語の基本的な構文として使われることが多い. 21