【正文】 ?(I(s(x)) ?O(x))) 2022/8/17 90 (14) 利用歸結(jié)反演法，先證明 F1 ? F2 ? F3 ? 172。G是不可滿足的。 F1 ? F2 ? F3 ? 172。G的子句集為 （ 1） 172。N(x) ? GZ(x) （ 2） 172。N(y) ? I(y) （ 4） 172。E(u) ? I(s(u)) （ 3） 172。I(z) ? E(z) ?O(z) （ 5） N(a) （ 6） 172。O(a) （ 7） 172。I(s(a)) 2022/8/17 91 (1) 例 已知： （ 1）如果 x和 y是同班同學(xué)，則 x的老師也是 y的老師。 （ 2）王先生是小李的老師。 （ 3）小李和小張是同班同學(xué)。 問：小張的老師是誰？ 解 首先定義如下謂詞： T(x,y)表示 x是 y的老師 C(x,y)表示 x與 y是同班同學(xué)。 已知條件可以表示成如下謂詞公式： F1： ?x ?y?z(C(x,y) ? T(z,x) ?T(z,y)) F2: T(Wang,Li) F3: C(Li,Zhang) 2022/8/17 92 (2) 為了得到答案，首先要先證明小張的老師是存在的。 即證明： G： ?xT(x,Zhang) (1) 172。C(x,y) ? 172。T(z,x) ? T(z,y) (2)T(Wang,Li) (3)C(Li,Zhang) (4) 172。T(u,Zhang) 求 F1 ? F2 ? F3? 172。 G的子句集： F1： ?x ?y?z(C(x,y) ? T(z,x) ?T(z,y)) F2: T(Wang,Li) F3: C(Li,Zhang) 2022/8/17 93 (3) 歸結(jié)演繹得： (5) 172。C(Li,y) ? T(Wang,y) [(1),(2),{Wang/z,Li/x}] (6) 172。C(Li,Zhang) [(4),(5),{Wang/u,Zhang/y}] (7)Nil [(3),(6)] 這說明小張的老師確實(shí)是存在的。 (1) 172。C(x,y) ? 172。T(z,x) ? T(z,y) (2)T(Wang,Li) (3)C(Li,Zhang) (4) 172。T(u,Zhang) 2022/8/17 94 (4) 為了求取答案，給原來的子句增加一個(gè)輔助謂詞ANS（ u）， 得到： (4)39。 172。T(u,Zhang) ? ANS（ u） 原來的子句集變?yōu)椋? (1) 172。C(x,y) ? 172。T(z,x) ? T(z,y) (2)T(Zhang,Li) (3)C(Li,Zhang) (4)39。 172。T(u,Zhang) ? ANS（ u） 重新歸結(jié)演繹得： (5) 39。 172。C(Li,y) ? T(Wang,y) [(1),(2),{Wang/z,Li/x}] (6) 39。 172。C(Li,Zhang) ? ANS（ u） [(4) 39。,(5) 39。,{Wang/u,Zhang/y}] (7) 39。 ANS（ Wang） [(3),(6) 39。] 這說明小張的老師存在且求得小張的老師是王先生。 2022/8/17 95 (5) ? 應(yīng)用歸結(jié)原理求取問題答案（方法思路） （ 1）先為待求解的問題找一個(gè)合適的 求證目標(biāo)謂詞 ； （ 2）再增配（ 以析取形式 ）一個(gè) 輔助謂詞 ，該謂詞的 變?cè)?必須與對(duì)應(yīng) 目標(biāo)謂詞 中的 變?cè)?完全 一致 ； （ 3）進(jìn)行歸結(jié)； （ 4）當(dāng)歸結(jié)是剛好 只剩下輔助謂詞 時(shí)，輔助謂詞中原變?cè)恢蒙系?項(xiàng) 就是 所求 的結(jié)果。 說明： 其中輔助謂詞是一個(gè)形式謂詞，其作用僅是提取問題的答案。有時(shí)就用需求證的目標(biāo)謂詞。 2022/8/17 96 (6) 例 已知：（ 1）如果 x是 y的父親， y又是 z的父親，則 x是 z的祖父。 （ 2）老李是大李的父親。 （ 3）大李是小李父親。 問：上述人員誰和誰是祖孫關(guān)系？ 解 首先定義如下謂詞： G(x,y)表示 x是 y的祖父。 F(x,y)表示 x與 y是父親。 已知條件可以表示成如下謂詞公式： F1： ?x ?y?z(F(x,y) ? F(y,z) ?G(x,z)) F2: F(Lao,Da) F3: F(Da,Xiao) 2022/8/17 97 (7) 并求其子句集如下： (1) 172。 F(x,y) ? 172。 F(y,z) ? G(x,z) (2) F(Lao,Da) (3)F(Da,Xiao) 設(shè)求證的公式為： G： ?x ?yG(x,y) (既存在 x和 y,x是 y的祖父 ) 把其否定化為子句形式再析取一個(gè)輔助謂詞 GA(u， v) (4) 172。 G(u， v) ? GA(u， v) 已知條件可以表示成如下謂詞公式： F1： ?x ?y?z(F(x,y) ? F(y,z) ?G(x,z)) F2: F(Lao,Da) F3: F(Da,Xiao) 2022/8/17 98 (8) 把其否定化為子句形式再析取一個(gè)輔助謂詞 GA(u， v) (1) 172。 F(x,y) ? 172。 F(y,z) ? G(x,z) (2) F(Lao,Da) (3) F(Da,Xiao) (4) 172。 G(u， v) ? GA(u， v) 對(duì)上式進(jìn)行歸結(jié)： (5) 172。 F(Da， z)? G (Lao， z) [(1),(2),{Lao/x,Da/y}] (6) G(Lao， Xiao) [(3),(5),{Xiao/x}] (7) GA(Lao,Xiao) [(4),(6),{Lao/u,Xiao/v}] 所以上述人員中，老李是小李的祖父。 2022/8/17 99 (9) ? 練習(xí) 1：已知如下事實(shí)： （ 1）小李只喜歡較容易的課程； （ 2）工程類課程是較難的； （ 3） PR系的所有課程都是較容易的。 （ 4） PR150是 PR系的一門課程 應(yīng)用歸結(jié)演繹推理回答問題：小李喜歡什么課程？ 2022/8/17 100 (10) 練習(xí) 2：設(shè) A、 B、 C中有人從來不說真話，也有人從來不說謊話，某人向這三人分別同時(shí)提出一個(gè)問題：誰是說謊者？ A答： “ B和 C都是說謊者 ” ； B答： “ A和 C都是說謊者 ” ； C答： “ A和 B中至少有一個(gè)人說謊 ” 。用歸結(jié)原理求誰是老實(shí)人，誰是說謊者？ 2022/8/17 101 問題的提出 幾種常用的歸結(jié)策略 歸結(jié)策略的類型 2022/8/17 102 （ 1） ? 研究歸結(jié)原理的目的是實(shí)現(xiàn)機(jī)器推理 ? 用歸結(jié)原理實(shí)現(xiàn)機(jī)器推理的一般性算法 Step1 將子句集 S置入 CLAUSES表中； Step2 若空子句 NIL在 CLAUSES中，則歸結(jié)成功，結(jié) 束。 Step3 若 CLAUSES表中存在可歸結(jié)的子句對(duì)，則歸結(jié) 之，并將歸結(jié)式并入 CLAUSES表中，轉(zhuǎn) Step2； Step4 歸結(jié)失敗，退出。 ? Step3中子句對(duì)進(jìn)行歸結(jié)的順序怎么確定 最簡單的方法是采用窮舉式地進(jìn)行歸結(jié)。 2022/8/17 103 （ 2） ? 水平浸透法具體作法 第一輪 歸結(jié)先讓 CLAUSES表（原子句集 S）中的子句兩兩見面 進(jìn)行歸結(jié)，將產(chǎn)生的歸結(jié)集合記為 S1，再將 S1并入 CLAUSES中，得到 CLAUSES= S ∪ S1 ； 再一輪 歸結(jié)時(shí)，又讓 S ∪ S1 ∪ S2與 S2中的子句進(jìn)行歸結(jié) ?? 如此進(jìn)行，知道某一個(gè) Sk中出現(xiàn)空子句為止。 下一輪 歸結(jié)讓新的 CLAUSES表（ S ∪ S1 ）中的子句與 S1中 的子句互相見面進(jìn)行歸結(jié)，并把產(chǎn)生的歸結(jié)式集合記為 S2，再將 S2并入 CLAUSES中； 2022/8/17 104 （ 3） S：（ 1） P ? Q （ 2） 172。 P ? Q （ 3） P ? 172。 Q （ 4） 172。 P ? 172。 Q S1：（ 5） Q [(1),(2)] （ 6） P [(1),(3)] （ 7） Q ? 172。 Q [(1),(4)] （ 8） 172。 P ? P [(1),(4)] （ 9） Q ? 172。 Q [(2),(3)] （ 10） 172。 P ? P [(2),(3)] （ 11） 172。 P [(2),(4)] （ 12） 172。 Q [(3),(4)] S2：（ 13） P ? Q [(1),(7)] （ 14） P ? Q [(1),(8)] （ 15） P ? Q [(1),(9)] （ 16） P ? Q [(1),(10)] （ 17） Q [(1),(11)] （ 18） P [(1),(12)] （ 19） Q [(2),(6)] （ 20） 172。 P ? Q [(2),(7)] （ 21） 172。 P ? Q [(2),(8)] （ 22） 172。 P ? Q [(2),(9)] （ 23） 172。 P ? Q [(2),(10)] （ 24） 172。 P [(2),(12)] 2022/8/17 105 （ 4） （ 25） P [(3),(5)] （ 26） P ? 172。 Q [(3),(7)] （ 27） P ? 172。 Q [(3),(8)] （ 28） P ? 172。 Q [(3),(9)] （ 29） P ? 172。 Q [(3),(10)] （ 30） 172。 Q [(3),(11)] （ 31） 172。 P [(4),(5)] （ 32） 172。 Q [(4),(6)] （ 33） 172。 P ? 172。 Q [(4),(7)] （ 34） 172。 P ? 172。 Q [(4),(8)] （ 35） 172。 P ? 172。 Q [(4),(9)] （ 36） 172。 P ? 172。 Q [(4),(10)] （ 37） Q [(5),(7)] （ 38） Q [(5),(9)] （ 39） NIL [(5),(12)] 2022/8/17 106 （ 5） ? 控制策略所解決的問題 歸結(jié)過程中中間子句的爆炸。 ? 控制策略的目的 歸結(jié)點(diǎn)盡量的少。 ? 控制策略的原則 給出控制策略，