人工知能特論2009 No.2 東京工科大学大学院 担当教員：亀田弘之.

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

1 人工知能特論2009 No.2 東京工科大学大学院 担当教員：亀田弘之

2 ここまでの復習 知能・知性の中枢は「思考と言語」 論理学は「思考の形式」を探求する学問

3 さまざまな論理体系 論理 古典論理 非古典論理

4 さまざまな論理体系 論理 古典論理 命題論理 述語論理（高階論理）　など 非古典論理

5 さまざまな論理体系 論理 古典論理 非古典論理 命題論理 述語論理（高階論理） など 様相論理 (modal logic)
述語論理（高階論理）　など 非古典論理 様相論理 (modal logic) 時相論理 (temporal logic) 多値論理 (multi-value logic) Fuzzy 論理 (fuzzy logic) 線形論理　など 現在ではさまざまな 論理体系が提案されており、分類はそんなには単純ではない。

6 参考文献 Transactions on Computational Logic, ACM. （さまざまな論理体系が今も提案され続けている）

7 本日の内容 命題論理

8 本日の内容 命題論理（もっとも基礎的な論理体系） 論理式の定義

9

10 １．１基本概念 あの山の上に雲がかかるとやがて雨が降り出す。 整数１２３４５６７は素数である。
円周率πを小数展開すると、その中に１から９までの数字がこの順に並んで現れる。 風が吹くと桶屋が儲かる。 クレタ人はみな嘘つきである。 真？ 偽？

11 問題：真か偽か述べよ。理由は？ あの山の上に雲がかかるとやがて雨が降り出す。 整数１２３４５６７は素数である。
円周率πを小数展開すると、その中に１から９までの数字がこの順に並んで現れる。 風が吹くと桶屋が儲かる。 クレタ人はみな嘘つきである。 真？ 偽？

12 問題：真か偽か述べよ。理由は？ あの山の上に雲がかかるとやがて雨が降り出す。 整数１２３４５６７は素数である。
円周率πを小数展開すると、その中に１から９までの数字がこの順に並んで現れる。 風が吹くと桶屋が儲かる。 クレタ人はみな嘘つきである。 １２７×９７２１ 真？ 偽？

13 問題：真か偽か述べよ。理由は？ ５×３＝１５ 平成の前は昭和である。 円の面積は半径の二乗に円周率πを掛け合わせたものである。
フランスの首都はパリである。 木星はガスでできており、月よりも軽い。 真？ 偽？

14 真偽を決めがたい文もある。 窓を開けてもいいですか？ そんなこと言わないでください。 これはすごい！

15 命題 真偽を決定することのできる文を、“命題”といい、命題論理学ではこれを研究の対象とする。
また、命題とともに、 “かつ”　“または”　“ならば”　“でない” なども併せて考察の対象とする。

16 命題の例 A = パリはフランスの首都である。 B = ボンはドイツの首都である。
真 A = パリはフランスの首都である。 B = ボンはドイツの首都である。 C = ロンドンはイギリスの首都である。 A,B,Cは命題である。 “A かつ B” 命題論理の考察対象である。 偽 真

17 命題論理に出てくる記号は、… 論理定数 命題記号 結合子 括弧

18 命題論理の論理式はこれらの記号のみで書かれる。
定義（命題論理の字母） 命題論理の字母は以下の記号から構成される。 アトムの集合(非空集合)： アトムはP, Q, …と表記する。 添え字を付けてP1, P2 などとも書く。 結合子（５種類）：　～,∧, ∨, →, ↔ 括弧（２種類）：　　　（, ） 命題論理の論理式はこれらの記号のみで書かれる。

19 記号を適当に並べればよい訳ではない！ 並べ方には規則（統語構造規則）がある。
疑問：次のものは論理式？ P Q R S P∧～∧∧Q ((～(P∧P2)) → P3) ）P1∨Q3（ 記号を適当に並べればよい訳ではない！　並べ方には規則（統語構造規則）がある。 シンタックスの定義が必要！

20 このような定義方法を、 帰納的定義という。
定義（論理式のシンタックス） 論理式とは以下で定義されるものである。 アトムは論理式である。 任意の論理式Fに対して、～F も論理式 である。 FとGが任意の論理式のとき、次のものは いずれも論理式である。 (F∧G), (F∨G) , (F → G), (F↔G) このような定義方法を、 帰納的定義という。 この規則に則った論理式は、 well-formed であるという。

21 ～F はFの“否定”と呼ぶ。 （F∧G)はFとGの“論理積”と呼ぶ。 （F∨G)はFとGの“論理和”と呼ぶ。 FがGの部分であるとき、 FはGの“部分式”と呼ぶ。

22 例： F = ～((A5∧A6)∨～A3) Fは論理式。 Fの部分式はすべて列挙すると以下の通り。
F, ((A5∧A6)∨～A3), (A5∧A6), A5, A6, ～A3, A3

23 アトム（例：P, Q,…）を、“原始式”あるいは“原始文”と呼ぶことがある。
それ以外のより複雑な論理式を“複合文”と呼ぶことがある。(例：～P, (P∨Q) ) Aを１つのアトムとすると、Aと～Aのことを“リテラル(literal)”といい、特に、Aのことを“正のリテラル(positive literal)”、～Aのことを“負のリテラル(negative literal)”と呼ぶ。

24 コメント Well-formed な論理式だけからなる命題論理式の集合は、１つの命題論理の言語を定める。（という言い方をすることもある）
ここまでで形式（見かけ）に関する準備が出来上がった。

25 これらはどれもwell-formed な論理式だけれど、…
疑問：次のものは何を意味している？ P P∧Q （（P→Q）∧P）→Q これらはどれもwell-formed な論理式だけれど、…

26 P = パリはフランスの首都である。 Q = いま雨が降っている。 P∧Q = パリはフランス首都であり、かつ、 いま雨が降っている。
真偽の判定ができる！

27 コメント PやQの真偽がわかれば十分だよね！ 例えば、PとQの真偽がわかれば P∧Q の真偽は分かるの？
∧　ってどういう意味？ （∧や∨の意味も明確に定義しなければ 　だめなんだ！）

28 定義（解釈 Intp） Lを命題論理の１つの言語（体系）、 Aを言語Lのアトムの集合とする。 このとき、Lの解釈IntpとはAから｛T, F ｝への写像のことをいい、 Intp = { x | Intp(x) = T, x ∊ A } と表現する。 （注）T：真　F：偽

29 解釈の例 アトムの集合A=｛P,Q,R｝に対して、例えば、 Intp(P) = T Intp(Q) = F Intp(R) = T
これを簡単に表現するために、真のものだけを集めて Intp = ｛ P, R ｝と書くことにする。

30 問題：真なる論理式（アトム）はどれ？ 論理的設定 アトムの集合A: A = {P1,P2,Q} 解釈Intp: Inpt = {P1,P2}

31 定義（論理子への意味の付与） 表．結合子の定義表 P Q ～P （P∧Q） （P∨Q） （P→Q） （P↔Q） T F
これは真理値表である。

32 コメント これで任意の well-formed な論理式に対して、真偽を判定することが可能となった。 めでたしめでたし。 よし、やったぁ
これからが本題です。

33 もう少し話を進めていきましょう。

34 練習問題（確認） 次の論理式の真理値表を示せ。 （Q∨P1）∧P1 P1→P2 (P2→（P1→Q））∧P1)→Q

35 （Q∨P1）∧P1 の答え P1 Q （ Q ∨ P1 ）　∧　P1 T 　　　T　　　　　T F 　　　T　　　　　F 　　　F　　　　　F

36 練習問題（確認） 次の論理式の値を求めよ。 （Q∨P1）∧P2 P1→P2 (P1→（P1→Q））∧P1)→Q
　　ただし、論理設定(logical settings)は、 解釈 Intp = { P1, Q } とする。

37 ここまでのまとめ 言語を定義するには、 が必要。 そこで、命題論理は論理式を対象とするので、論理式を文とみなすと… アルファベット 構文構造
意味の割り当て 　が必要。 　そこで、命題論理は論理式を対象とするので、論理式を文とみなすと…

38 命題論理の字母の定義 論理式のシンタックスの定義 意味の割り当て アトム記号群、結合子記号群、括弧記号群 アトムは論理式
φが論理式ならば～φも論理式 φとψが論理式ならば、 (φ∧ψ), (φ∨ψ), (φ→ψ), (φ↔ψ) も論理式 意味の割り当て “解釈”という概念の導入

39 もう少しがんばろう！ 目指せ、“モデル”の導入！

40 一般に、論理式はどのような解釈をするかで真理値は変わってしまう。例えば、論理式φは解釈Intp1では偽になるが、解釈Intp2なら真になるといった具合に。

41 定義（モデル） 論理式φがある解釈Intpで真となるとき、 解釈Intpをその論理式の“モデル”と呼ぶ こととする。また、φはモデルIntpをもつ とも言うこととする。 例：解釈Intp={P,Q} はφ = (P∧Q） のモデルであるが、ψ = (P→～Q) のモデルではない。φは解釈Intpをモデルとしてもつ。

42 定義（モデル）の拡張 Σを論理式の集合とし、Intpを１つの解釈とする。このとき、もしΣに含まれるすべての論理式に対して解釈Intpのもとで真となるとき、解釈IntpはΣのモデルと呼ぶ。また、 Σは解釈Intpをモデルとして持つとも言う。 （今後はこの定義を採用する。）

43 例： Σ= { P, ( Q∨R ), ( Q → R ) } Intp1 = { P, R }, Intp2={ P,Q, R }, Intp3 = { P, Q } このとき、Intp1もIntp2もともに Σのモデルであるが、Intp3はΣのモデルではない。

44 そろそろ次の話、推論にはいりましょう。

45 定義（論理的帰結） Σ：論理式の集合 φ：１つの論理式 どの論理式ψ∈Σのモデルもまた論理式φのモデルとなっているとき、“φはΣの論理的帰結(logical consequence)”と呼び、 Σ|= φ と書く。“Σはφを論理的に含意する”とも言う。

46 例： P=私は家の外にいる。 Q=雨が降っている。
R=私は濡れる。 「家の外にいて、かつ、雨が降っている、ならば、濡れる」　　( ( P∧Q ) → R )

47 例（続き） 「家の外にいて、かつ、雨が降っている、ならば、濡れる」  ( ( P∧Q ) → R ) いま確かに「雨が降っている」。Q
ということは、「いま外にいれば濡れる」ことになる。 　つまり、 ( ( P∧Q ) → R ),Q |= ( P → R )

48 問題：次の推論が正しいことを示せ。 ( ( P∧Q ) → R ),Q |= ( P → R )
ヒント：　真理値表を書いてみる。

49 コメント（注意事項） →　と　|= とは別物です！

50 演繹定理（重要） Σ∪{ φ } |= ψ iff Σ |= ( φ→ ψ ) iff: if and only if

51 論理的等価 φとψとが論理的に等価であるとは、 　　　　　φ|=ψ かつ ψ|=φ が成り立つことを言う。

52 来週の予告 推論 三段論法からresolution法へ

53 推論の例 AならばBである。 いま、Aである。
したがって、Bである。 これは三段論法と呼ばれるものである。 これは別名、modus ponens という。

54 推論の図式化 　　　A→B　　A ーーーーーーーー 　　　　　B

55 推論の例 例えば、 ( ( P∧Q ) → R ),Q |= ( P → R ) が成り立つことを統一的かつ簡単な方法でできないだろうか？

56 事実１：( ( P∧Q ) → R ) 事実２：Q 示したい事実： ( P → R )

57 前提１：( ( P∧Q ) → R ) 前提２：Q 論理的帰結： ( P → R )

58 問題の整理 前提から帰結を得るためには、 推論を行うことになり、 その結果得られるものを
証明という。 「推論」や「証明」といった概念（用語）を整理することが必要。

59 推論を機械的に行えないか？ Resolution という強力な方法が現在しられている。次回これについて詳細します。 つぎのスライドがresolutionを適用した例です。 （一応目を通しておいてください。次回詳しく説明します。理論的にはあと一息で楽になります。がんばりましょう。）

60 問題例 論理式F= （~B∧~C ∧ D） ∨(~B∧~D) ∨(C∧D)∨B は常に真であることを示しなさい。 （注）常に真となる論理式を恒真式という。

61 回答例 ~Fを仮定すると矛盾が生じることを確認する（背理法による証明）。 ~F= （B∨C∨~D） ∧(B∨D) ∧(~C∨~D) ∧~B
節(clause)と節集合(clausal set)の記法に書き換える。 ~F={ {B,C,~D}, {B,D}, {~C,~D}, {~B} }

62 { B, C, ~D } { B, D } { ~C, ~D } { ~B } { B, ~D } { B } { }
{ } { } が得られたということは、矛盾が検出されたということ。

63 おわり