【正文】 第一級： ?P 歸結(jié)實(shí)例： S = ? ?R, ?P?R, ?Q?R, P? Q? ?Q 第二級： Q 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 63 推理策略分析 改進(jìn)（ 3） 策略分析： 綜合多種歸結(jié)搜索策略特征，有利于提高搜索的有效性和完備性。 因此，有 線性歸結(jié)策略。 線性歸結(jié)策略特點(diǎn)： 與諸如“支持集策略”、“單元集策略”等 搜索策略特征 相容，可視為多種策略的組合。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 64 線性歸結(jié)策略（ 1） 設(shè)子句集 S,頂子句 C0 和 B0 ? S，從 S到 Cn 推理序列中產(chǎn)生線性歸結(jié)式 Ci（ 0in)的任意歸結(jié)母式 Ci1和 Bi1 均應(yīng)滿足以下條件： ? Ci1是 Ci 直接上一級的線性歸結(jié)式； ? Bi1或者屬于子句集 S，或是某個已知的線性歸結(jié)式 Cj(ji)； 分別稱 Ci1 和 Bi1 為中心子句和邊子句。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 65 線性歸結(jié)策略（ 2） 線性歸結(jié)例： 設(shè) S=?A? B, ? A ? B, A ? ? B, ? A ? ? B? ? ? ? B A ? ? B A ? A ? ? B ? B B 歸結(jié)策略特點(diǎn)： ? 當(dāng) C0 或 B0 之一等于 ? ? 時，線性歸結(jié)為 支持集策略 ； ? 與單元?dú)w結(jié)策略類似，優(yōu)先選擇較短的母子句進(jìn)行歸結(jié)。 ? 策略完備，結(jié)構(gòu)簡單。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 66 利用 線性歸結(jié)策略 求證下列公式 永真 : (?x)(P(x) ? (Q(A) ? Q(B))) ? (? x)(P(x) ?Q(x)) 習(xí)題： 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 67 基于邏輯的 應(yīng)用系統(tǒng) ?基于規(guī)則的演繹推理系統(tǒng) 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 68 基于規(guī)則的演繹推理系統(tǒng) 問題提出： 因此，有： 基于規(guī)則的演繹推理系統(tǒng) ：直接根據(jù)問題領(lǐng)域的事實(shí)和規(guī)則，證明某目標(biāo)公式是否成立，而不是先將公式化成子句形式，用歸結(jié)反演方法證明。此種證明方法稱為 直接證明法 。 ? 基于歸結(jié)的推理可能 丟失 蘊(yùn)含式 中的 有用的控制信息 ： 子句 : A?B?C |=| ?A??B?C； ?A??C?B； ?B??C?A； (?A??B)?C； (?B?(A?C)； ? C?(A?B) ? 一階謂詞的蘊(yùn)含式常用于表示問題領(lǐng)域的各種知識： P(x,y) ? P(y,z) ? G(x,z)； 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 69 基于規(guī)則的演繹推理 PROLOG ? 定義 : 稱最多含一個正文字的子句為 Horn子句。 ? 例： ? A1? ? A2 ?? ? ? An ? B 等價式： A1 ? A2 ? ? ? An ? B ? PROLOG: 基于 Horn子句的 邏輯程序描述語言 ； ? 優(yōu)點(diǎn)： 表達(dá)能力強(qiáng)：凡能用一階邏輯描述的問題均可用 Horn子句表達(dá) 表達(dá)直觀、推理簡單 若有 ： {W ? L1? L2}，可化為： {W? L1， W? L2} 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 70 基于規(guī)則的演繹推理 PROLOG 描述： 待證目標(biāo)庫： { ? G } 規(guī)則集： { B ? C ? G, D ? B,??} 事實(shí)庫： { C， D } 推理策略： 線性歸結(jié)策略。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 71 ? 已知事實(shí)庫 : ? F1: Dog(sid)。 F2: ? Barks(sid)。 ? F3: Tail(sid)。 F4: Meows(mik). 蘊(yùn)涵規(guī)則庫 : R1: Dog(x) ? Tail(x) ? Kind(x)。 R2: Kind(s) ? ? Barks(s) ? ? Afraid(x,s)。 R3: Dog(u) ? Animal(u)。 R4: Cat(v) ? Animal(v)。 R5: Meows(w) ? Cat(w). 目標(biāo) : (? x) (? y)(Cat(x) ? Dog(y) ? ? Afraid(x,y)) PROLOG 演繹推理實(shí)例 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 72 基于規(guī)則的 逆向演繹系統(tǒng)實(shí)例 Cat (x1) ? Dog (y1) ? ?Afraid (x1, y1) Cat (x1) Dog (y1) ?Afraid (x1, y1) Cat (w) Scat (x1) Scat (mik) Dog (sid) ?Afraid (z, s) ? Bark(y1) Kind(y1) Kind(x) Dog (y1) Tail(y1) Dog (sid) Tail(Sid) ? Bark(sid) X1/w Sid / y1 X1/z, y1/s R5 Sid / Y1 Mik/x1 Y1/x Sid / y1 Sid / y1 R1 R2 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 73 基于規(guī)則的演繹系統(tǒng)小結(jié) ? 基于目標(biāo)驅(qū)動的初始表達(dá)式形式 ? 推理過程中規(guī)則的變換過程 ? 合一匹配與一致解圖的求解過程 無矛盾 、 無殘缺、經(jīng) 合一匹配 的與或解圖 。 基于蘊(yùn)涵規(guī)則的推理 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 74 AI中的應(yīng)用邏輯 ? 各種應(yīng)用邏輯 ? 時態(tài)邏輯 ? 模態(tài)邏輯 ? 模糊邏輯 ? ?? ? 對一階邏輯的改進(jìn) ? 語法結(jié)構(gòu)方面的改進(jìn) ? 推理方法方面的改進(jìn) 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 75 習(xí)題 1：將謂詞公式化為子句形式 ? ? (?x)P(x) ? (?x ) ? P(x) ? ? (?x)(P(x) ? ( (?y)(P(y) ?P(f(x,y))) ? ? (?y)(Q(x,y) ?P(y)))) 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 76 ?利用線性歸結(jié)策略求證下列公式永真 : (?x)(P(x) ? (Q(A) ? Q(B))) ? (? x)(P(x) ?Q(x)) 習(xí)題 2： 等價求證 : {(?x) (P (x) ? (Q(A) ? Q(B))) } |= (? x) (P (x) ?Q (x)) {(?x) (P (x) ? (Q(A) ? Q(B))), ?(? x) (P (x) ?Q (x))} |= 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 77 習(xí)題 3：合一匹配算法應(yīng)用 ?設(shè){Ei}={P(a,x,h(g(z))),P(z,h(y),h(y))} 對 {Ei}實(shí)施合一匹配算法。 判斷下列文字能否合一，若不能，請說明理由，若能，請求出其 mgu ?。 {Ei}={P(f(x,g(z)),h(A)),P(f(x,y),z)} 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 78 演講完畢，謝謝觀看！