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

命題論理から述語論理へ 命題論理も有用なものであることは、組合せ回路論などでも実証済み。 でも、… 東京工科大学　人工知能基礎特論

命題論理の限界 命題論理で扱えないものがある。 例： 「AはBより大きく、BはCより大きい。したがって、AはCより大きい。」 P= AはBより大きい。 Q= BはCより大きい。 R=AはCより大きい。 「PかつQならばR」 これが証明できない！ 真であることが証明できｊない！ 東京工科大学　人工知能基礎特論

これを克服するためには、文単位の論理体系では駄目で、文の内部構造も明示的に取り扱う必要がある。 ＝＝＞ 述語論理へ これを克服するためには、文単位の論理体系では駄目で、文の内部構造も明示的に取り扱う必要がある。 ＝＝＞　述語論理へ 東京工科大学　人工知能基礎特論

命題論理の適用例 東京工科大学　人工知能基礎特論

役に立っている分野はたくさんあるんだよ。 人工知能・機械学習 エキスパートシステムにおける演繹的推論 決定木による学習 バージョンスペース　など （これらは後日お話します。） 役に立っている分野はたくさんあるんだよ。 東京工科大学　人工知能基礎特論

論理体系構築の手順（復習） 字母の設定 （論理式を記述するための記号群を決める） Syntaxの設定 （記号の意味ある並びを決める。論理式であるための条件、論理式の表現規則を決める） Semanticsの設定 （論理式の意味の取り扱いを決める） その後、推論へと話を進める。 東京工科大学　人工知能基礎特論

定義４．１ 述語論理の字母 定数： a, b, c, … 必要に応じて添え字も許す。 定義４．１　述語論理の字母 定数：　 a, b, c, … 必要に応じて添え字も許す。 変数：　 x, y, z, w, … 必要に応じて添え字も許す。 東京工科大学　人工知能基礎特論

関数記号： f, g, h, … 必要に応じて添え字も許す。 関数ごとに変数の個数(arity) が決まっている。 述語記号：　P,Q, R, … 必要に応じて添え字も許す。 述語ごとに変数の個数(arity) が決まっている。 東京工科大学　人工知能基礎特論

限量記号: ∃, ∀ (読み方)∃：存在記号 ∀：全称記号 結合子:　~, ∧, ∨, →, ↔　（４種類） 限量記号: ∃, ∀ (読み方)∃：存在記号 　　 ∀：全称記号 補助記号： “(“ , “)”, “,” 　　　左括弧、右括弧、コンマ（３種類） 東京工科大学　人工知能基礎特論

ここまでで何ができたか？ 例： 太郎は花子のことが好きである。 ＝＞　好き（太郎，花子） ＝＞　love(taro, hanako) ＝＞　P(a,b) このような文を、記号化することができるようになった。 （具体例の練習は後でやりましょう。） もう少し話を進めましょう！ 東京工科大学　人工知能基礎特論

確認 字母 定数 変数 関数記号 述語記号 結合子 限量記号 補助記号 東京工科大学　人工知能基礎特論

確認 字母 定数： a, b, c, d, … 変数: x, y, z, w, … 関数記号: f, g, h, … 述語記号: P, Q, R, 結合子: ~, ∧, ∨, →, ↔ 限量記号: ∃, ∀ 補助記号: ( ) , 東京工科大学　人工知能基礎特論

定義４．２ 項(Term) 定数は項である。 変数は項である。 もし f が arity n （n変数）の関数記号であり、t1, t2,… tn が項であるならば、 f( t1, t2, … , tn ) は項である。 東京工科大学　人工知能基礎特論

例 設定： 定数：　a, b, c 変数： x1, x2, y 関数記号： f, g 　 ( ｆ は1変数関数、ｇ は3変数関数) 述語記号: P, Q, R, S ( arityはそれぞれ、2, 1, 2, 3） 東京工科大学　人工知能基礎特論

例（続き） 項の例： a x2 f( b ) f( f( f( x1 ) ) ) g(x2, x1, f( f( f( a ) ) ) ) 述語論理式の構成要素 東京工科大学　人工知能基礎特論

これらはなぜ項ではないのでしょうか？説明してみましょう。 例（続き） 項でないものの例： f( a, b ) P( a, c ) ( a ∨ b ) これらはなぜ項ではないのでしょうか？説明してみましょう。 東京工科大学　人工知能基礎特論

定義４．３　( well-formed ) 論理式 Pはn変数の述語記号であり、 t1, t2,… tn が項であるならば、P(t1, t2,… tn ) は論理式である。アトムあるいは原始式と呼ぶ。 φが論理式ならば、~φは論理式。 φとψが論理式ならば、 (φ∧ψ), (φ∨ψ), (φ→ψ), (φ↔ψ) は論理式。 φが論理式、xが変数ならば、 ∃x φ , ∀x φ は論理式。 東京工科大学　人工知能基礎特論

補足 アトムでない論理式のことを、複合論理式(composite formula)と呼ぶことがある。 東京工科大学　人工知能基礎特論

論理式の例 論理式の例 Q(a) P( f( f( x1 ) ), g( a, c, f( b ) ) ) P( f( f( x1 ) ), g( a, c, f( b ) ) ) → Q(a) ~∀x Q(x) ∃x1 ~∀x2 (∃yR(x2,x1) ∧ Q(b) ) 東京工科大学　人工知能基礎特論

論理式の例（続き） 論理式でない例 ( P(a,b) ∨ f( y ) ) P( a ) Q( P(a, b ) ) ∀a Q(a) 東京工科大学　人工知能基礎特論

補足 命題論理のときと同様に、字母と論理式定義規則から得られる記号列（論理式）の集合を（1階述語論理）言語 (first-order language) と呼ぶ。 東京工科大学　人工知能基礎特論

定義４．４　スコープ（参照範囲） 論理式 ∀x φ　における∀xのスコープは、φであり、論理式 ∃x φ　における∃xのスコープは、φである。 例： ∃x (P(x,y)→Q(x)) ∃x (∀y P(x,y)∧Q(x)) ∃x のスコープ ∀y のスコープ 東京工科大学　人工知能基礎特論

定義４．５　変数の束縛 束縛変数 自由変数 東京工科大学　人工知能基礎特論

定義４．６　閉じた論理式 自由変数を１つも含まない論理式のこと。 例： ~∀y P(a,y) 東京工科大学　人工知能基礎特論

定義４．７ 基礎項(ground term)と 基礎論理式(groung formula) 基礎項：変数を１つも含まない項のこと。 基礎論理式：変数を１つも含まない 　　　　　　　　　論理式のこと。 例： 　f(a), g(b, f(a), c) P(a, f(b) ) ∀x P(x,a) ＜＝　これは基礎論理式 　　　　　　　　　　　　ではない！ 東京工科大学　人工知能基礎特論

Semantics 東京工科大学　人工知能基礎特論

定義４．８ pre-interpretation J 集合D:解釈のための領域（非空集合） 定数記号に対して、Dの要素を割り当てる。 関数記号f (n変数関数)に対して、DnからDへの写像を割り当てる。 つまり、集合Dに基づいて、定数記号や 関数記号の意味（実体）を決める。 これが、pre-interpretation。 東京工科大学　人工知能基礎特論

例 東京工科大学　人工知能基礎特論

定義４．９　変数割り当てV 変数記号に領域Dの要素を割り当てる。 （variable assignment） V:　変数記号の集合∋x　→　d∈D 東京工科大学　人工知能基礎特論

定義４．１０ 項割り当て 定数記号に対して、pre-interpretation Jに基づいてDの要素を割り当てる。 定義４．１０　項割り当て 定数記号に対して、pre-interpretation Jに基づいてDの要素を割り当てる。 変数記号に対して、変数割り当てVに基づいてDの要素を割り当てる。 t1, t2, …,tn がd1, d2, … ,dn に割り当てられるとき、f(t1, t2, …,tn ）は、 Jf(d1, d2, … ,dn ）に割り当てられる。 東京工科大学　人工知能基礎特論

定義４．１１　解釈I Pre-interpretation J が定められているとき、述語記号Pに対して、Dnから{ T, F } への写像を割り当てることを解釈という。 東京工科大学　人工知能基礎特論

まずはここまで 今日は「述語論理の導入」でした。 命題論理の限界（述語論理の必要性） 述語論理の定義 述語論理におけるsyntax 定数、変数 項 関数、述語 述語論理におけるsyntax 述語論理におけるsemantics Pre-interpretation から interpretatione へ 東京工科大学　人工知能基礎特論