述語論理式の構文と意味 一階述語論理式の構文 一階述語論理式の意味 述語，限量記号 自然言語文の述語論理式表現 解釈 妥当，充足不能

Presentation on theme: "述語論理式の構文と意味 一階述語論理式の構文 一階述語論理式の意味 述語，限量記号 自然言語文の述語論理式表現 解釈 妥当，充足不能"— Presentation transcript:

1 述語論理式の構文と意味 一階述語論理式の構文 一階述語論理式の意味 述語，限量記号 自然言語文の述語論理式表現 解釈 妥当，充足不能
閉式の充足不能性

2 述語論理 述語（predicate）の導入 「太郎は人間である」 「花子は人間である」 命題論理による表現 述語論理による表現 述語
「太郎は人間である」　 「花子は人間である」 命題論理による表現 述語論理による表現 述語 「・・・人間である」という共通する情報が欠落してしまう

3 述語論理 限量記号(quantifier)の導入 は である： すべての　　は　　である：　 ある　　は　　である： 全称記号 存在記号

4 一階述語論理の構文 語彙 個体定数（constant）： 個体変数（variable）： 関数記号（function symbol）：
述語記号（predicate symbol）： 論理記号（connective）： 限量記号（quantifier）： 補助記号（punctuation symbol）：

5 一階述語論理の構文 項（term）の帰納的定義 （１）個体定数は項である． （２）個体変数は項である． （３） が 引数の関数記号， が項
（３）　 が　 引数の関数記号，　　　　 が項 　　⇒　　　　　　　　は項である． （４）項とは（１），（２），（３）を有限回繰り返し適用して得られる記号列のみである．

6 一階述語論理の構文 整式（wff）の帰納的定義 （１） が 引数の述語記号， が項 ⇒ は整式（素式）である． （２） が整式
（１）　　が　　引数の述語記号，　　　　　が項 　　⇒　　　　　　　　は整式（素式）である． （２）　　　　が整式 　　⇒　　　　　　　　　　　　　　　　　　　は整式である． （３）　　が整式，　 が個体変数 　　⇒　　　　　　 は整式である． （４）整式とは（１），（２），（３）を有限回繰り返し適用して得られる記号列のみである．

7 限量記号の作用 作用域（scope）: の （ただし ） 束縛変数（bound variable）： の に現れる
自由変数（free variable）： 束縛変数以外の変数 束縛変数 束縛変数 自由変数

8 限量記号の作用 束縛関係： の と部分式 の自由変数 は に束縛されるという．
束縛関係：　　　 の　 と部分式　 の自由変数 　は　　に束縛されるという． 閉式（closed formula）: すべての変数が束縛されている整式で，文（sentence）ともいう． 自由変数 自由変数

9 自然言語文→述語論理式表現 翻訳の基本パターン すべてのものが である．（Everything is p.) ⇒
　　　　　⇒ 　　なものが存在する．(Something is p.) 　 ⇒ すべての　　は　　である．（Every p is q.） ある　　は　　である．（Some p is q.）

10 自然言語文→述語論理式表現 なぜ 「ある p は q である」 を 「 」と表現すべきなのか？ 「ある p は q である」
否定 否定

11 表現の例 ① 試験が難しい科目の受験者は皆喜ばない． ② 試験が難しくなければ喜ぶ受験者がいる． ③ 数学の受験者しか喜ばない． ① ② ③
①　試験が難しい科目の受験者は皆喜ばない． ②　試験が難しくなければ喜ぶ受験者がいる． ③　数学の受験者しか喜ばない． ① ② ③ ： x は試験が難しい. ： x は y の受験者である. ： x は喜ぶ. ： 数学.

12 一階述語論理式の意味 解釈（interpretation）： 変数割り当て： 領域（domain）： D 割り当て: （１）個体定数 c ：
（２）関数記号 f ： （３）述語記号 p ： 変数割り当て： 個体変数 x に対して : x に 　　　　を割り当て，x 以外には　　 　　　　　　　　　 による割り当てをする変数割り当て．

13 一階述語論理式の意味 　　　　 による意味評価

14 述語論理式を解釈してみよう

15 充足可能性 ：論理式 ：解釈 ：変数割り当て は を充足する（ ）． を充足する が存在する（しない）． は充足可能（不能）である．
　　：論理式　　　：解釈　　　：変数割り当て 　　　　　　　　　　　　　は　　を充足する（　　　　　）． 　 を充足する が存在する（しない）． 　　　　　　　は充足可能（不能）である． 任意の　　について 　　　　　　　は　　を充足する（　　　　）． 　 が閉式　　（またはその集合　　）を充足す 　るとき，　　を　　（または　　）のモデルという．

16 妥当性 任意の解釈と任意の変数割り当てが論理式 を充足するとき， は妥当であるという（ ）． は妥当である． は充足不能である．
任意の解釈と任意の変数割り当てが論理式　 を充足するとき，　は妥当であるという（　　　）． 　は妥当である．　　　　　は充足不能である． 　　　　 任意の　　　 　について 　　　　　　任意の　　　 ，　　　 について 　　　　　　任意の　　　　 について 閉式

17 論理的帰結 を充足する任意の解釈と任意の変数割り当てが必ず を充足するとき， は の論理的帰結であるという（ ）． ：論理式の集合 ：論理式
　　：論理式の集合　　　：論理式 　　　を充足する任意の解釈と任意の変数割り当てが必ず　　を充足するとき，　 は　　の論理的帰結であるという（　　　　　）． 閉式 は充足不能である.

18 閉式の充足不能性 閉式 の充足不能性を考える． 命題論理式 が恒偽な命題論理式であれば 任意の解釈 で 一般には決定できない
閉式　　　　　　の充足不能性を考える． 一般には決定できない ある　　 がFであれば決定できる 命題論理式 が恒偽な命題論理式であれば 任意の解釈　　 で

19 閉式の充足不能性 恒偽 恒偽 標準的解釈

20 まとめると… 一階述語論理式の充足不能性 　　　　　　　　　　閉式の充足不能性 　　　　　 の充足不能性 充足不能であれば決定可能 　　　　　　　　　　 標準的な解釈の存在