人工知能特論2007 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 ( それぞれ、2, 1, 2,

例（続き） 項の例： 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 } への写像を割り当てることを解釈という。