人工知能特論2011 No.3 東京工科大学大学院 担当教員:亀田弘之 命題論理(Propositional Logic) 命題論理では、自然言語の文を単純化・ 形式化し、その枠組みで推理等を整理・ 体系化することを目指す。 例(推理の例): 泳げば、濡れる。(If P, then R.) シャワーをかかれば濡れる。(If Q, then R.) → 泳ぐかシャワーをかかれば濡れる。 (If P or Q, then R.) 2 命題論理の体系(概要) 1. syntax(文法) 2. 記号の並びに関する規約(well-formed) 論理式とはどんな形式のものなのか。 semantics Well-formed な論理式相互の関係 真・偽 3 Syntax どのような形式言語にもシンタックスがある。 例: プログラミング言語(Java, C, Prolog etc.) XML (eXtensible Markup Language) HTML (HyperText Markup Language) UML (Unified Modeling Language) UNL (Universal Networking Language) etc. 4 定義3.1 命題論理の字母は以下の記号からなる。 1. 2. 3. アトム記号(atom)の集合A(非空集合) A ={ P, Q, R, … , P1, P2, …, Q1, Q2, …} 結合子(connectives): ~, ∧, ∨, →, ↔ 補助記号(右括弧と左括弧): (, ) 5 定義3.1のコメント 命題論理はすでに述べたように、形式化さ れた文に対して定義される。対象となる文は 何らかの記号の列であり、その記号を 字母(alphabet)として定義している。 字母として {あ, い, う, …, あ1, あ2, あ3,…, い1,…, not, and, or, then, eq, [, ] } を採用してもよい。表現には自由度がある が論理体系としては同一である。 6 定義3.2 (well-formedな)論理式 1. 2. 3. (Well-formedな)論理式(formula)とは 以下のようなものである。 アトムは論理式。 ( if P ∈ A , then P is formula.) φが論理式ならば、~φは論理式。 φとψが論理式ならば、 (φ∧ψ), (φ∨ψ), (φ→ψ), (φ↔ψ) は論理式。 7 定義3.2のコメント 任意のアトムPは論理式(原始式ともいう) アトムではない論理式、例えば、~Pや (P→Q)は複合論理式ともいう。 Pがアトムのとき、Pと~Pをリテラル(literal) と呼ぶ。特に、Pを正リテラル(positive literal)、~Pを負リテラル(negative literal)と 呼ぶ。 8 論理式の例 P (P∧Q) ~((P3∧P8)∨~Q2) ((P∨Q)→R) (P→(P→P)) (~P↔(~(Q∧P))) 9 問題:論理式でない例を3つ挙げよ。 10 定義3.3 命題論理言語 命題論理言語(propositional language)と は、所与の字母から構成される論理式全体 の集合のことをいう。 11 定義3.3のコメント 定義3.1と定義3.2から得られる記号列 全体のこと。 この場合、「記号列=論理式」である。 論理式は「形式文」ともみなせるので、 命題論理言語という言い方をする。 12 Semantics 文=論理式 には意味を与えることができる。 論理学ではまずは 「真と偽」を考える。 (「真・偽」以外は後日考察する。) 今の段階では、∧や ~ は単なる記号であり、 論理積や論理否定の意味はまだ導入され ていない点に注意。これからそれらを導入 する。 13 定義3.4 解釈 Intp 命題論理言語 L に対し、Lのアトムの集合 をA とする。このとき、L の解釈 Intp とは、 A から{T, F}への写像のことをいう。 ここで、TとFを真理値と呼ぶ。 解釈Intp: A → { T, F } 解釈Intp: A {T , F} 14 定義3.5 解釈の表現法 解釈 Intp はアトム A の集合の部分集合と して記述することとする。 つまり、 Intp = { x | Intp(x) = T, x∈A } 15 解釈の例 A = { P, Q, R }において、 Intp(P)=T, Intp(Q)=T, Intp(R)=F のとき、これを Intp = { P, Q } と書く。また。 Intp(P)=T, Intp(Q)=F, Intp(R)=F のときは、 Intp = { P } と書く。 16 定義3.6 結合子の意味の定義 表.結合子の定義表 P Q ~P (P∧Q) (P∨Q) (P→Q) (P↔Q) T T F T T T T T F F F T F F F T T F T T F F F T F F T T これは真理値表 である。 17 定義3.7 φを論理式、Intpを1つの解釈とする。 このとき、もしφの真理値がIntpのもとで T であれば、 「φは解釈Intpのもとで真である」 あるいは 「解釈Intpはφを満たす(満足する)」 という。 18 例 φ=~(P∧Q), Intp={P} のとき、 φの真理値はTとなるので、φはIntpのもとで 真であり、Intpはφを満足する。 19 定義3.8 モデル φを論理式、Intpを解釈とする。このとき、 Intpがφを満足するならば、「Intpはφのモデ ルである」という。また、「φはIntpをモデルと してもつ」ともいう。 20 例 φ=((P∧Q)↔(R→Q)) Intp = { P, R } このとき、Intpはφのモデルである。 (各自確認せよ。) 21 定義3.9 モデル(その2) 論理式の集合をΣ、Intpを解釈とする。この とき、Σに属するどの論理式に対してもIntp がそのモデルになっているとき、「IntpはΣの モデルである」という。 22 例 Σ= { P, (Q∨R), (Q→R) } Intp1 = { P, R } Intp2 = { P, Q, R } Intp3 = { P, Q } このとき、Intp1とIntp2はΣのモデルであるが、 Intp3はΣのモデルではない。 (各自確認せよ。) 23 定義3.10 論理的帰結 Σ:論理式の集合 φ:論理式 このとき、Σのどのモデルもまたφのモデル になっているとき、「φはΣの論理的帰結 (logical consequence)である」といい、 Σ |= φ と書く。また、「Σは論理的にφを含意する」 などともいう。 24 定義3.11 論理的帰結(その2) Σ,Γ:論理式の集合 このとき、Σのどのモデルも論理式φ∈Γの モデルとなっているとき、「ΣはΓのモデルで ある」といい、Σ |= Γ と書き、また、「ΣはΓを 論理的に含意する」という。 25 例 P = “私は外にいる” Q = “雨が降っている” R = “私は濡れる” このとき、 ( (P∧Q) → R ) かつ Q から (P→R) が結論付けられる。 26 つまり ( (P∧Q) → R ) , Q |= ( P → R ) (この証明は次の通り) 27 解釈1 解釈2 解釈3 解釈4 解釈5 解釈6 解釈7 解釈8 P T T T T F F F F Q R ((P∧Q)→R) T T T T F F F T T F F T T T T T F T F T T F F T (P→R) T F T F T T T T 28 つまり ( (P∧Q) → R ) , Q |= ( P → R ) これのモデルは、解釈2 以外の解釈。 これのモデル は、1,2,5, 6の4つ。 解釈1,5,6は これのモデル でもある。 これらに共通のモデルは、1,5,6 の3つ。 (この証明は次の通り) 29 練習問題 Σ={(P∧Q), (P→R)} は Γ= {P,Q,R} を含 意する、すなわち、Σ|=Γ であることを示せ。 30 定理3.1 演繹定理 Σ|=(φ→ψ) のとき、またそのときに限り、 Σ∪{φ} |= ψ である。 31 証明 Σ∪{φ} |= ψ Σ∪{φ} のどのモデルもψのモデル Σのどのモデルも~φかψのモデル Σのどのモデルも(φ→ψ)のモデル Σ |= (φ→ψ) 32 定義3.12 論理的に等価(⇔) 論理式φとψは、 φ |= ψ と ψ |= φ とがともに成り立つとき、「φとψは論理的に 等価である」といい、「φ⇔ψ」と書く。 33 定義3.13 論理的に等価(その2) 論理式の集合ΣとΓが論理的に等価である とは、以下の条件が成り立つことを言い、 Σ⇔Γ と書く。 Σ |= Γ かつ Γ |=Σ 34 例 Σ = { P, ~Q, (P∨R)} , Γ = { (R∨P), (~R∨~Q), P, (P→~Q)} のとき、 Σ⇔Γである。 (各自証明せよ。) 35 定義3.14.1 φのどの解釈もφのモデルになっているとき、 φは妥当(valid)であるといい、また、φは恒 真式(tautology)であるという。 このとき、 |= φ と書く。 36 定義3.14.2 φの解釈の中にモデルが存在するとき、φは 充足可能(satisfiable)である、あるいは、無 矛盾(consistent)であるという。 37 定義3.14.3 φの解釈の中に1つもモデルが存在しない とき、φは充足不可能(unsatisfiable)である、 あるいは、矛盾(inconsistent)であるという。 38 定義3.14.4 充足可能な論理式のうち、恒真式(ト-トロ ジ)でないものをcontigentという。 39 論理式の分類 Tautology 常に真 Contigent 真のこともあれば 偽のこともある 充足可能 矛盾 常に偽 充足不可能 40 例(トートロジの例) (P∨~P) ( ( P∧(P→Q) ) → Q ) (各自で例を考えよ。) 41 命題3.1 Σ |= φ iff Σ∪{~φ} が充足不可能。 ただし、 Σ:論理式の集合 φ:論理式 (注) iff とはif and only if の略記法で、A iff B とは、AとBが同値であることを意味する。 42 証明 Σ |=φ iff φはΣのどのモデルに対しても真 iff Σ∪{~φ} はモデルを持たない iff Σ∪{~φ} は充足不可能 43 ここまでは前回の復習 44 論理式の標準形(Normal Form) 論理積標準形 conjunctive normal form (CNF) 論理和標準形 disjunctive normal form (DNF) 45 定義3.15 論理和/積標準形 Aijをリテラルとするとき、 ∨∧Aij の形の論理式を論理和標準形といい、 ∧∨Aij の形の論理式を論理積標準形という。 46 例(論理和標準形) (P∧Q ∧ R)∨(~P ∧ Q ∧ R) ∨(P ∧ Q ∧ ~R) (注)論理回路のときには、 P・Q・R + ~P・Q・R + P・Q・~R などと書いていた。 47 例(論理積標準形) (P∨~Q)∧(P∨~R) (P + ~Q)・(P + ~R) 48 定理3.2 標準形の存在 任意の論理式 φ に対して、それと等価な CNF と DNF が存在する。 (証明は各自に任せます。) 49 これ以降、論理式は CNF で考える。 そこで、例えば論理式(P∨~Q)∧(P∨~R) を { {P, ~Q}, {P, ~R} } などと書くことにする。 (P∨~Q)∧(P∨~R) の別表記法として { {P, ~Q}, {P, ~R} } を導入する。 この表現方法に 慣れてください。 50 練習問題 { ~P, Q} { {P, Q, ~R}, {~P,Q} } { {P, R}, {~P, ~R} } 51 定義3.16 節と節集合 節とはゼロ個以上の リテラルの並び のこと。 { P, Q, ~R } などと標記する。 節集合とは、節の集合のこと。 52 例 節: { P, ~Q } { } (空節) { P1, Q3, R } 節集合: { { P, ~Q }, { }, { P1, Q3, R } } 53 Horn節とHorn節集合 高々(at most)1つの正リテラルしか持たない節の ことをHorn節という。 Horn節からなる節集合をHorn節集合と呼ぶ。 例: F=(P∨~Q)∧(~R∨~P∨S)∧(~P∨~Q)∧S∧~U F={ {P,~Q}, {~R,~P,S}, {~P,~Q}, {S}, {~U} } 54 例: G=(P∨~Q)∧(R∨~P∨S) G={ {P,~Q}, {R,~P,S} } (これはHorn節集合ではない) 55 導出原理(Resolution法) 56 定義 リテラルの相補性 リテラルAとBが相補的であるとは、 A=~B であるか B=~A であることである。 また、Aと相補的なリテラルをA*と書く。 57 定義 導出節(resolvent) 2つの節C1とC2に対して、C1に属する1つ のリテラルAの相補的リテラルA*がC2に属 しているとする。 このとき、 節(C1ー{A})∪(C2ー{A*}) をC1とC2からの導出節(resolvent)と呼ぶ。 58 定義 導出原理 2つの節から導出節を作り出すことを 導出原理という。 また、この操作による推論法をresolution法 と呼ぶこととする。 59 導出原理の意味 {~P, Q}, {P} から {Q} を作り出す(導く) のが導出原理法であり、これは、いわゆる 三段論法(modus ponens)に相当するもの である。 60 練習問題 導出節をすべて求めよ。 { {A,~B,E}, {A,B,C}, {~A,~D,E},{A,~C} } (注)アトムとしてA,B,C,D,Eという記号を 用いた。今後は適宜さまざまな記号を 用いることとする。 61 答え(後日掲載します) 62 Lemma K1とK2が節集合Fの要素(節)であるとする。 このとき、もしRがK1とK2の導出節ならば、 F∪{R} はFと論理的に同値である。 すなわち、 F∪{R} F 証明は各自で挑戦してみてください。 63 定義 Res(F) Res(F) = F∪{ R | R はFからの導出節} Res0(F) = F Resn+1(F) = Res(Resn(F)) for n≧0 Res*(F) = ∪Resn(F) 64 練習問題 Resn(F) (n=0,1,2) をそれぞれ求めよ。 ただし、 F={ {A,~B,C}, {B,C}, {~A,C}, {B,~C}, {~C} } 65 Resolution定理 節集合Fに対して、Fが充足不可能であるこ とと、□∈Res*(F) であることとは同値であ る。 F is unsatisfiable □∈Res*(F) . 66 推論とは 推論(inference)とは、いくつかの命題(論理 式)からなる前提(premise)から、1つの 命題(論理式)を結論(conclusion)として導 き出す過程のこと。例えば、 彼はギリシア人かインド人である。 彼がギリシア人ならば彼はギリシア語を話せる。 彼はギリシア語を話せない。 したがって、 彼はインド人である。 前提 結論 67 分析 P = 彼はギリシア人である Q = 彼はインド人である R = 彼はギリシア語を話せる とすると、 (P∨Q)∧(P→R)∧~R 故に、Q 68 (P∨Q) (P→R) ~R ---------------------------------Q 69 この推論の正しさを示すためには、前提が すべて真のとき結論も真であることを示せ ばよい。つまり、 (P∨Q)∧(P→R)∧~R |= Q が成り立つことを示せばよい。 70 そこでまずは、… Resolution法の妥当性を 確認しよう! {~P, Q}, {P} |= Q (~P∨Q)∧P |= Q P T T F F Q T F T F (~P∨Q)∧P T F F F 71 Resolution法を用いた証明方法 Σ |= φ を証明するには、 Σ∪{~φ} |= □ を示せばよい。 (演繹定理とResolution定理より。) つまり、前提であるΣに証明したいφの否定 を追加すると矛盾が生じることを示せばよ い。(いわゆる“背理法”。) 72 証明: (P∨Q)∧(P→R)∧~R |= Q (P∨Q)∧(P→R)∧~R∧~Q がモデルを持た ないことを示す。 節集合の形で書くと、 { {P,Q}, {~P,R}, {~R}, {~Q} } これにresolution法を適用する。 (次のスライド参照) 73 { {P,Q}, {~P,R}, {~R}, {~Q} } {P,Q} {~P,R} {P} {~R} {~Q} {~P} □ 74 問題:次の推論は正しいか? 山田か田中が参加できれば、この企画は成功する。 山田が海外に出張中であれば、山田はこの企画に 参加できない。 田中も忙しければ、この企画に参加できない。 山田は海外に出張中であるが、田中は忙しくない。 故に、この企画は成功する。 75 P=山田はこの会議に参加できる Q=田中はこの会議に参加できる R=この会議は成功する S=山田は海外出張中である T=田中は忙しい (P∨Q)→R, S→~P, T→~Q, S∧~T |= R 76 (P∨Q)→R, S→~P, T→~Q, S∧~T |= R ((P∨Q)→R)∧(S→~P)∧(T→~Q)∧ ∧ (S∧~T) |= R (~(P∨Q)∨R)∧(~S∨~P)∧(~T∨~Q) ∧S∧~T |= R ((~P∧~Q)∨R)∧(~S∨~P)∧(~T∨~Q) ∧S∧~T |= R 77 ((~P∨R)∧(~Q∨R))∧(~S∨~P)∧ (~T∨~Q)∧S∧~T |= R (~P∨R)∧(~Q∨R)∧(~S∨~P)∧(~T∨~Q) ∧S∧~T |= R したがって、 (~P∨R)∧(~Q∨R)∧(~S∨~P)∧(~T∨~Q) ∧S∧~T ∧ ~R が矛盾していることを示せばよい。 78 (~P∨R)∧(~Q∨R)∧(~S∨~P)∧(~T∨~Q) ∧S∧~T ∧ ~R {~P,R} {~Q,R} {~S,~P} {~T,~Q} {S}{~T}{~R} これから、 Res*(F) を求めるとこの中には□が 含まれない。 ということは、この推論は誤っている。 (真理値表を書いて確認せよ。) 79 練習問題 次の論理式はトートロジであることを示せ。 F=(~B∧~C∧D)∨(~B∧~D) ∨(C∧D)∨B 80 練習問題 F = A∧B∧C が次の論理式の帰結であるこ とを示せ。( G |= F ) G={{~A,B},{~B,C},{A,~C},{A,B,C}} 81 推論の完全性・健全性 82 今後の予定 述語論理の導入 述語論理のシンタックス 述語論理のセマンティックス 標準形(冠頭標準形) ユニフィケーション 述語論理における導出原理 など 83 参考文献 1. 2. 3. ライプニッツの哲学 ー 論理と言語を中心 に ー, 石黒, 岩波書店(1984). Beginning Logic, E.J.Lemmon, Chapman & Hall/CRC(1965). 情報科学における論理,小野寛晰,日本評 論社(1994). 1は言語哲学の本です。論理学をより深く学ぶ場合、 一度目を通しておくとよいと思います。2は論理学の 古典的名著の1つです。日本語訳もあります。 3は皆さんのような人たちの学習参考書です。 84
© Copyright 2024 ExpyDoc