【正文】 ? 例： P(x)?Q(y), ~P(f(z))?R(z) = Q(y)?R(z)2/27/2023 136人工智能講義歸結(jié)舉例設(shè)公理集：(?x)(R(x)?L(x))(?x)(D(x)?~L(x))(?x)(D(x)?I(x))求證： (?x)(I(x)?~R(x))化子句集： (?x)(R(x)?L(x)) = (?x)(~R(x)?L(x))= ~R(x)?L(x) (1)2/27/2023 137人工智能講義 (?x)(D(x)?~L(x))= (?x)(~D(x)?~L(x))= ~D(x)?~L(x) (2) (?x)(D(x)?I(x))= D(A)?I(A)= D(A) (3) I(A) (4)2/27/2023 138人工智能講義? 目標求反： ~(?x)(I(x)?~R(x))= (?x)~(I(x)?~R(x))= (?x)(~I(x)?R(x))= ~I(x)?R(x) (5)換名后得字句集：~R(x1)?L(x1)~D(x2)?~L(x2)D(A) I(A) ~I(x5)?R(x5)2/27/2023 139人工智能講義例題得歸結(jié)樹~R(x1)?L(x1)~D(x2)?~L(x2)D(A) I(A) ~I(x5)?R(x5)I(A) ~I(x5)?R(x5) R(A){ A/x5} ~R(x1)?L(x1) L(A){ A/x1} ~D(x2)?~L(x2) ~D(A){ A/x2} D(A) nil2/27/2023 140人工智能講義歸結(jié)反演求解 提取回答的過程? 先進行歸結(jié)，證明結(jié)論的正確性；? 用重言式代替結(jié)論求反得到的子句；? 按照證明過程，進行歸結(jié)；? 最后，在原來為空的地方，得到的就是提取的回答。（目標公式的否定或由它們的后裔產(chǎn)生的子句）策略： 每次歸結(jié)時，至少有一個子句來自于 T或由 T導出的歸結(jié)式。另一類是重復的，如 P,Q, ～ P, ～ 歸結(jié)過程的控制策略?刪除策略 設(shè)有兩個子句 C和 D，若有置換 243。2/27/2023 123人工智能講義歸結(jié)原理? 概述? 命題邏輯的歸結(jié)法? 子句形? Herbrand定理? 歸結(jié)原理? 歸結(jié)過程的策略控制2/27/2023 124人工智能講義歸結(jié)原理? 概述? 命題邏輯的歸結(jié)法? 子句形? Herbrand定理? 歸結(jié)原理? 歸結(jié)過程的策略控制2/27/2023 125人工智能講義歸結(jié)過程的控制策略? 要解決的問題：–歸結(jié)方法的知識爆炸。??? 直至 1965年 Robinson提出了 歸結(jié)原理 。： 63 + 64 = 1512個元素 H2 ： 元素個數(shù)有 63 數(shù)量級（由于變量最多的函數(shù)是 k(x,y,z),三個變 量都可能取值于 H1的六個元素） S2180。2/27/2023 110人工智能講義封閉語義樹 舉例例 子句集 S={～ P(x)∨Q(x),P(f(y)), ～ Q(f(y))} H={a,f(a),f(f(a)),…} A={P(a),Q(a),P(f(a)),Q(f(a)),…} 語義樹： N0 N11 N12N21 N22 N23 N24N31 N32 N33 N34 N35 N36 N37 N38P(a)Q(a)P(f(a))N41 N42 N43 N44N45 N46N47 N48N49 N410N411N413 N415N412 N414 N416這是一個無限樹，然而它是否是一個封閉樹？Q(f(a))Χ ΧΧΧΧ ΧΧΧ ΧΧI(N41)={P(a),Q(a),P(f(a)),Q(f(a))},它使 S的子句 ～ Q(f(y))的基例 ～ Q(f(a))為假 ， 而 N41的父輩不能使子句的基例為假2/27/2023 111人工智能講義封閉語義樹 舉例例 子句集 S={～ P(x)∨Q(x),P(f(y)), ～ Q(f(y))} H={a,f(a),f(f(a)),…} A={P(a),Q(a),P(f(a)),Q(f(a)),…} 封閉語義樹： N0 N11 N12N21 N22 N23 N24N31 N32 N36 N37 N38P(a)Q(a)P(f(a))N41 N42 N49 N410N413N414Q(f(a))Χ ΧΧΧΧΧΧ ΧΧΧ2/27/2023 112人工智能講義Herbrand定理? H域? H解釋? 語義樹? 結(jié)論： Herbrand定理2/27/2023 113人工智能講義Herbrand定理? H域? H解釋? 語義樹? 結(jié)論： Herbrand定理2/27/2023 114人工智能講義Herbrand定理 （結(jié)論）Herbrand定理：1. 子句集 S是不可滿足的，當且僅當對應(yīng)于 S的完全語義數(shù)是棵有限封閉樹 。可以通過對語義樹每一個分支來計算 S的真值。不過在 H上證明 S的不可滿足性仍然是不可能的。 2/27/2023 101人工智能講義H解釋 舉例? 例 1 S={P(a), ～ P(x)∨P(f(x)) } S的 H域 H∞ = {a,f(a),f(f(a))， …} S的原子集為 A={P(a),P(f(a)),P(f(f(a))), … } S的 H解釋：I1*= {P(a),P(f(a)),P(f(f(a))), … } S| I1*=TI2*= {～ P(a),P(f(a)),P(f(f(a))), … } S| I2*=F I3*= {P(a), ～ P(f(a)),P(f(f(a))), … } S| I3*=F我們關(guān)心的是：對論域上的任一解釋 I，若有 S| I=T,如何求得一個相應(yīng)的 H解釋 I*,使得 S| I*=T成立。成為可數(shù)問題。– 此域稱為 H域： H0為 G中所出現(xiàn)的常量的集合，若 G中沒有常量，就任取常量 ， H0={a}。對于非永真（或永假）的公式就不一定能在有限步內(nèi)得到結(jié)論。2/27/2023 84人工智能講義子句形? G是不可滿足的 = S是不可滿足的–G與 S不等價，但在不可滿足的意義下是一致的。2/27/2023 80人工智能講義子句形 ( Skolem 標準形 )? ? ? ? ? ? ? ? ? ? ? ? ?–量詞消去原則：消去存在量詞 “ ?” ，略去全程量詞 “ ?”。 2/27/2023 70人工智能講義歸結(jié)原理? 概述? 命題邏輯的歸結(jié)法? 子句形? Herbrand定理? 歸結(jié)原理? 歸結(jié)過程的策略控制2/27/2023 71人工智能講義歸結(jié)原理? 概述? 命題邏輯的歸結(jié)法? 子句形? Herbrand定理? 歸結(jié)原理? 歸結(jié)過程的策略控制2/27/2023 72人工智能講義命題邏輯的歸結(jié)法? 基本單元：簡單命題（陳述句）例： 命題： A A A3 和 B求證： A1ΛA 2ΛA 3成立，則 B成立，即： A1ΛA 2ΛA 3 → B反證法：證明 A1ΛA 2ΛA 3Λ ～ B 是矛盾式 （永假式） 2/27/2023 73人工智能講義命題邏輯的歸結(jié)法? 建立子句集– 合取范式：命題、命題和的與， 如：PΛ （ P∨Q ） Λ （ ～ P∨Q ）子句集 S：合取范式形式下的子命題（元素）的集合例：命題公式： PΛ （ P∨Q ） Λ （ ～ P∨Q ） 子句集 S： S = {P, P∨Q, ～ P∨Q} 2/27/2023 74人工智能講義命題邏輯的歸結(jié)法? 歸結(jié)式消除互補對，求新子句 → 得到歸結(jié)式 。2/27/2023 59人工智能講義AO*算法舉例目標目標初始節(jié)點n0n1n2n3n4n5n6n7n8 h(n0)=3 h(n1)=2 h(n2)=4 h(n3)=4 h(n4)=1 h(n5)=1 h(n6)=2 h(n7)=0 h(n8)=0連接線的代價=后繼節(jié)點個數(shù)2/27/2023 60人工智能講義n0n1 n2n3n4n5n6n7n8n0(3)n1(2)n4(1)n5(1)紅色代價 ： 4藍色 代價 ： 32/27/2023 61人工智能講義n0n1n2n3n4n5n6n7n8n4(1)n5(1)紅色代價 ： 4藍色 代價 ： 6n1 (25)n2(4)n3(4)n0(3)n0(34)2/27/2023 62人工智能講義n0n1n2n3n4n5n6n7n8n4(1)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(4)n5(1)n5(12)2/27/2023 63人工智能講義n0n1n2n3n4n5n6n7n8紅色代價 ： 5藍色 代價 ： 6n0(4)n4(1)n5(12)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(45)2/27/2023 64人工智能講義n0n1n2n3n4n5n6n7n8n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)2/27/2023 65人工智能講義目標目標初始節(jié)點n0n1n2n3n4n5n6n7n8n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)2/27/2023 66人工智能講義目標目標初始節(jié)點n0n1n2n3n4n5n6n7n8初始節(jié)點可解n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)2/27/2023 67人工智能講義歸結(jié)原理? 概述? 命題邏輯的歸結(jié)法? 子句形? Herbrand定理? 歸結(jié)原理? 歸結(jié)過程的策略控制2/27/2023 68人工智能講義歸結(jié)原理? 概述? 命題邏輯的歸結(jié)法? 子句形? Herbrand定理? 歸結(jié)原理? 歸結(jié)過程的策略控制2/27/2023 69人工智能講義概述? 歸結(jié)原理 由 1965年提出。這時，從 s出發(fā)，選擇那些指針所指向的邊得到的局部圖，為當前代價值最小的局部圖。 f(n) = g(n) ＋ h(n) = d(n) ＋ m ＋ c － 2b其中， d(n)為節(jié)點深度。3, NEST={ni|f(ni)fm}IF NEST ≠ ( ) n=NEST中 g最小的節(jié)點 ELSE n=FIRST(OPEN), fm=f(n)。 h(ni)ninjh(nj)c(ni,nj)2/27/2023 43人工智能講義h單調(diào)的性質(zhì)? 定理 5：若 h(n)是單調(diào)的，則 A*擴展了節(jié)點