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

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

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

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

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

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

本日の内容 命題論理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

おわり