導出原理とProlog -論理と形式化 授業資料-

Slides:



Advertisements
Similar presentations
課題 1 課題提出時にはグラフを添付すること. この反応が1次であることを示すためには、 ln ([N 2 O 5 ] 0 / [N 2 O 5 ]) vs. t のプロットが原点を通る直線となることを示せばよい。 与えられたデータから、 t [s] ln ([N.
Advertisements

自然言語処理 平成 24 年 11 月 5 日 (No5)- 東京工科大学 コンピュータサイエンス学部 亀田弘之.
立命館大学 情報理工学部 知能情報学科 谷口忠大. Information このスライドは「イラ ストで学ぶ人工知能概 論」を講義で活用した り,勉強会で利用した りするために提供され ているスライドです.イラ ストで学ぶ人工知能概 論.
円線図とは 回路の何らかの特性を複素平面上の円で表したもの 例えば、ZLの変化に応じてZinが変化する様子 Zin ZL
J: Magical Switches JAG 模擬地区予選 2013 原案:保坂 解答:保坂・楠本 解説:保坂.
プログラミング言語論論理型言語 論理型プログラミング言語 水野嘉明
確率と統計 平成23年12月8日 (徐々に統計へ戻ります).
融合原理による推論 (resolution)
「Postの対応問題」 の決定不能性の証明
知的インタフェース 例示によるプログラミング 予測インタフェース 制約インタフェース.
4.3 連立1次方程式   Ax = b   (23) と書くことができる。
計算の理論 II 帰納的関数(つづき) 月曜4校時 大月美佳.
プログラミング 平成24年10月23日 森田 彦.
3 一次関数 1章 一次関数とグラフ §3 一次関数の式を求めること          (3時間).
プログラミング言語論 プログラミング言語の 特徴と分類 水野嘉明
充足不能性と導出原理 充足不能性の証明 スコーレム標準形 エルブラン解釈 導出原理 基礎節に対する導出 導出原理の完全性と健全性.
Prolog演習 PowerPointのアニメーション機能を利用すると分かりやすいと思います.
プログラミング言語論 第12回 論理型プログラミング 情報工学科 篠埜 功.
人工知能特論2011 資料No.6 東京工科大学大学院 担当教員 亀田弘之.
香川大学工学部 富永浩之 情報数学1 第5-2章 命題論理式の 同値変形とカルノー表 香川大学工学部 富永浩之
Semantics with Applications
数理論理学 第1回 茨城大学工学部情報工学科 佐々木 稔.
第4回 カルノー図による組合せ回路の簡単化 瀬戸 目標 ・AND-OR二段回路の実現コスト(面積、遅延)が出せる
第4回放送授業.
表現系工学特論 項書換え系(4) 完備化 1.語問題と等式証明 2.合流性とチャーチ・ロッサ性 3.完備化手続き.
プログラミング 平成24年10月30日 森田 彦.
計算量理論輪講 岩間研究室 照山順一.
数理論理学 第11回 茨城大学工学部情報工学科 佐々木 稔.
自動定理証明と応用 (automated theorem proving and its application)
4. 組み合わせ回路の構成法 五島 正裕.
数理統計学 第4回 西山.
プログラミング 平成25年11月5日 森田 彦.
不完全な知識 不完全な知識に基づく問題解決 フレーム問題 制約条件記述問題 非単調推論 極小限定 常識の定式化 並列極小限定.
プロジェクト演習Ⅱ インタラクティブゲーム制作 イントロダクション2
プログラミング2 関数
ねらい 方程式の意味や、方程式の解、解くことの意味について理解する。
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
人工知能概論 第14回 言語と論理(3) 証明と質問応答
形式言語の理論 5. 文脈依存言語.
計算の理論 II Turing機械の合成 月曜5校時 大月美佳 2004/11/15 佐賀大学理工学部知能情報システム学科.
数理論理学 第3回 茨城大学工学部情報工学科 佐々木 稔.
2節 連立方程式の利用 1.連立方程式を使った問題
オートマトンとチューリング機械.
並行プログラミング concurrent programming
25. Randomized Algorithms
数理統計学 西 山.
プログラミング言語論 第10回 練習問題解答例 情報工学科 篠埜 功.
論理プログラミング 導出の効率化 論理プログラム ホーン節 ホーン集合に対する導出戦略 論理式の手続き的解釈 Prolog
マイクロソフト Access での SQL 演習 第2回 集計,集約
数理論理学 第12回 茨城大学工学部情報工学科 佐々木 稔.
11.再帰と繰り返しの回数.
融合原理 (resolution) 人工知能 論理と推論(2) 論理的帰結 節形式 融合原理 知識を組み合わせて知識を生み出す
 型推論3(MLの多相型).
4. システムの安定性.
電気回路学I演習 2012/11/16 (金) I1 I2 問1 Z0 V1 V2 問2 I1 I2 V1 Z0 V2 Z,Y,K行列の計算
基礎プログラミング演習 第6回.
知能情報工学演習I 第7回(後半第1回) 課題の回答
計算の理論 I プッシュダウンオートマトン 火曜3校時 大月 美佳 平成16年7月6日 佐賀大学知能情報システム学科.
東京工科大学 コンピュータサイエンス学部 亀田弘之
演習1:次の問A,Bの問題,正解,解説をするpptを作成しなさい.
数理論理学 第9回 茨城大学工学部情報工学科 佐々木 稔.
ウェブデザイン演習 第6回.
or-6. 待ち行列シミュレーション (オペレーションズリサーチを Excel で実習するシリーズ)
1.Scheme の式とプログラム.
香川大学工学部 富永浩之 情報数学1 第5-2章 命題論理式の 同値変形とカルノー表 香川大学工学部 富永浩之
3 一次関数 1章 一次関数とグラフ §4 方程式とグラフ         (3時間).
東京工科大学 コンピュータサイエンス学部 亀田弘之
東京工科大学 コンピュータサイエンス学部 亀田弘之
数理論理学 最終回 茨城大学工学部情報工学科 佐々木 稔.
アルゴリズム ~すべてのプログラムの基礎~.
Presentation transcript:

導出原理とProlog -論理と形式化 授業資料- 亀山(幸)、2015/6/5, 6/12

例1 H1 P :- Q. H1 Q ⊃ P H2 Q :- R. H2 R ⊃ Q H3 R. H3 R G1 ?- P. H2 H3 G2 ?- Q. R⊃Q R H1 G3 ?- R. Q⊃P Q G4 ?-. (ok) P

例2 H1 Q :- R, S. H1 R∧S ⊃ Q H2 R :- S. H2 S ⊃ R H3 S. H3 S H2 H3 G1 ?- Q. S⊃R S H3 G2 ?- R, S. R S H1 G3 ?- S, S. R∧S⊃Q R∧S G4 ?- S. Q G5 ?- . (ok)

例3-1 H1 P :- Q, R. H1 Q∧R ⊃ P H2 P :- S. H2 S ⊃ P H3 Q :- S. H3 S ⊃ Q G1 ?- P. (fail) S⊃Q S G2 ?- Q, R. Q R H1 G3 ?- S, R. Q∧R⊃P Q∧R G4 ?- R. (fail) P G1に適用可能なのは、H1 だけでなく、H2 もあった!

例3-2 H1 P :- Q, R. H1 Q∧R ⊃ P H2 P :- S. H2 S ⊃ P H3 Q :- S. H3 S ⊃ Q G1 ?- P. G2 ?- S. H2 G3 ?- . (ok) H4 S⊃P S P

Prologの実行の微妙な点 H1 P H1 P. H2 P :- P. H2 P ⊃ P H3 P :- P. H3 P ⊃ P 上にあるホーン節から先に試すので、 ゴール ?- P. を H1, H2に対して走らせると 止まるが、 H3, H4 に対して走らせると、止まらない。 論理的には、 H1 ∧ H2 と  H3 ∧ H4 は同値

述語論理の例(本来の導出原理) H1 add(0,X, X). H2 add(s(X),Y,s(Z)) :- add(X, Y, Z). ゴール ?- add(s(s(0)), s(0), W). H1 ∀X. add(0, X, X) H2 ∀X,Y,Z. (add(X,Y,Z) ⊃ add(s(X),Y, s(Z))) ゴール ∃W.(add(s(s(0)), s(0), W)).

述語論理の例(本来の導出原理) [Z1:=s(Z2)] [Z2:=s(0)] H2 [X:=0,Y:=s(0),Z:=Z2] H1[X:=s(0)] a(0,s(0),Z2)⊃ a(s(0),s(0),Z1)). H2 [X:=s(0),Y:=s(0),Z:=Z1] a(0,s(0),Z2) a(s(0),s(0),Z1)⊃a(s(s(0)),s(0),W)) a(s(0), s(0), Z1) a(s(s(0)), s(0), W) [W:=s(Z1)] H1 ∀X. (add(0, X, X)) H2 ∀X,Y,Z. (add(X,Y,Z) ⊃ add(s(X),Y,s(Z)))

H2 add(s(X),Y,s(Z)) :- add(X, Y, Z). G1→G2 [X:=s(0),Y:=s(0),Z:=Z1]+[W:=s(Z1)] 答え W:=s(s(s(0))) G2→G3 [X:=0,Y:=s(0),Z:=Z2]+[Z1:=s(Z2)] G3→G4 [X:=s(0)]+[Z2:=s(0)] G1 ?- add(s(s(0)), s(0), W). G2 ?- add( s(0) , s(0), Z1). by H2 G3 ?- add( 0 , s(0), Z2). by H2 G4 ?- . (ok) by H1 H2 add(s(X),Y,s(Z)) :- add(X, Y, Z).

単一化 (unification) add(s(X), Y ,s(Z)) vs add(s(s(0)), s(0), W) 単一化問題: X, Y, Z, W をうまくとることによって、 両者を一致させることができるか? YES  [X:=s(0),Y:=s(0),W:=s(Z)] 単一化問題の解: 両者を一致させられるかどうか、と、 YESの場合は、一致させる代入のうち、最も制約が少ないもの

今日の演習 Parent(Alice, Bob). Parent(Alice, Chris). Parent(Chris, Diana). Parent(Eliza, Diana). GP(X, Z) :- Parent(X,Y), Parent(Y,Z). ?- GP(Alice, X). と ?- GP(Eliza, X). を Prolog風に実行する過程を書きなさい。もし余力があれば、得られた解に対応するNKの証明図も書きなさい。

解答 H1 Parent(Alice, Bob). H2 Parent(Alice, Chris). H3 Parent(Chris, Diana). H4 Parent(Eliza, Diana). H5 GP(X, Z) :- Parent(X,Y), Parent(Y,Z). ヘッド ボディ(本体) ?- GP(Eliza, X). H5の変種 H5’ GP(X1,Z1):-P(X1,Y1),P(Y1,Z1). を考え、そのヘッドと単一化  [X1:=Eliza, Z1:=X] (あるいは[X1:=Eliza, X:=Z1]と考えてもよい) ?- Parent(Eliza,Y1), Parent(Y1,X). ゴールの1つ目の原子論理式を H4のヘッドと単一化。   [Y1:=Diana] ?- Parent(Diana, X).  ゴールの1つ目と単一化可能なヘッドをもつホーン節がないので失敗。 バックトラックポイントはもうのこっていないので、失敗する。

解答 H1 Parent(Alice, Bob). H2 Parent(Alice, Chris). H3 Parent(Chris, Diana). H4 Parent(Eliza, Diana). H5 GP(X, Z) :- Parent(X,Y), Parent(Y,Z). ヘッド ボディ(本体) ?- GP(Alice, X). H5の変種 H5’ GP(X1,Z1):-P(X1,Y1),P(Y1,Z1). を考え、そのヘッドと単一化  [X1:=Alice, Z1:=X] (あるいは[X1:=Alice, X:=Z1]と考えてもよい) ?- Parent(Alice,Y1), Parent(Y1,X). ゴールの1つ目の原子論理式を H1,H2のヘッドと単一化(※)、まずはH1から。   [Y1:=Bob] ?- Parent(Bob, X).  ゴールの1つ目と単一化可能なヘッドをもつホーン節がないので失敗。  バックトラックポイント※まで戻り、H2のヘッドと単一化。   [Y1:=Chris] ?- Parent(Chris,X). ゴールの1つ目とH3のヘッドを単一化。   [X:=Diana] ?-. 成功!  ここまでの代入をまとめると [X:=Diana,X1:=Alice,Y1:=Chris,Z1:=Diana]   (next) バックトラックポイントはもうのこっていないので、失敗する。