【正文】 公式；n ④ 若 A是合適公式， x是約束變量，則 (?x)A和 (?x)A也都是合適公式；n ⑤ 只有按上述規(guī)則 ① ④ 求得的公式，才是合適公式。(172。 172。(P∧Q) ? 172。 P 8. 量詞否定　　　 　 172。P(x))2023/2/27—— 母式，不包括任何量詞；p Qixi——Q i可以是 量詞 符號 ?或 ?； xi是量詞的 約束變量(i=1,2,…,k)2023/2/27P(x， z)∨ ~P(y， z)∨ Q(x， y， u))2023/2/272023/2/272. 因為母式不含量詞，所以可以變換為 合取 范式。2023/2/27但它們保持永假性。(Q2x2)…(Q kxk)M，其中p M星期六 44p合取范式的標準化過程n 應(yīng)用 合適公式性質(zhì) 將公式逐步轉(zhuǎn)化的過程。p ② 消去蘊涵符號n 蘊涵式轉(zhuǎn)化 ： P?P?∨ ∨ PQ)∨ P(x)p ?(?x)(?P(x))2023/2/27[?Q(x,z)星期六 48總結(jié)： Skolem函數(shù) 和 Skolem常量 ★若 存在量詞是在全稱量詞的轄域內(nèi) ，用 Skolem函數(shù)消去存在量詞 。2023/2/27∨ ?∧ 星期六 50p 合取范式的標準化過程n 例、化簡合適公式?(?x){P(x)?{(?y)[P(y)星期六 52p 合取范式的標準化過程n 例、化簡合適公式?(?x){?P(x)∨{(?y)[?P(y)∨ P(f(x,y))]∧ ?(?y)(?w)[?Q(x,y)∨ P(y,w)]}}③ 內(nèi)移否定符號(?x){P(x)∧{(?y)[P(y)∧ ?P(f(x,y))]∨ (?y)(?w)[?Q(x,y)∨ P(y,w)]}}2023/2/27星期六 56p 合取范式的標準化過程n 例、化簡合適公式(?y)(?z){P(A)∧{[P(y)∧ ?P(f(A,y))]∨ [?Q(A,z)∨ P(z,g(z))]}}⑦ 消去全稱量詞{P(A)∧{[P(y)∧ ?P(f(A,y))]∨ [?Q(A,z)∨ P(z,g(z))]}}2023/2/27F2,…,Fn}2023/2/27 ∨ Lim(i=1,2,…,n)pLij=Pij|?Pij:文字（ Literal） ，是原子謂詞公式 Pij或其取反n 合取范式 可定義為 子句 的 合取 ∧ (?z){P(A)∧[P(y)∨ ?Q(A,z)∨ P(z,g(z))]∧[?P(f(A,y))∨ ?Q(A,z)∨ P(z,g(z))]}量詞分配：(?x)?(?z)P(A)(?z)[?P(f(A,y))∨ ?Q(A,z)∨ P(z,g(z))]2023/2/27(?z)[?P(f(A,y))∨ ?Q(A,z)∨ P(z,g(z))]}n 為了消除子句間不必要的交互作用，保持子句的獨立性，需要做 變量換名{P(A),P(y1)∨ ?Q(A,z1)∨ P(z1,g(z1)),?P(f(A,y2))∨ ?Q(A,z2)∨ P(z2,g(z2))}將合適公式化成字句集，只需要在化成合取范式的基礎(chǔ)上，去掉 ∧ 符號以及進行 變量換名即可。每個否定符號 ~最多只用到一個謂詞符號上，并反復(fù)應(yīng)用狄摩根律。A}代替 ~（ ?x） A以 ??x){~一 如，把 (?x){p(x)=(?x)Q(x)}標準化而得到（ ?x） {p(x)=(?y)Q(y)}令這種依賴關(guān)系明顯地由函數(shù) g（ y）所定義，它把每個 y值映射到存在的那個 x。如果要消去的存在量詞不在任何一個全稱量詞的轄域內(nèi)，那么我們就用不含變量的 Skolem函數(shù)即常量。所得公式稱 前束形 。P(y)}任何母式都可以寫成由一些謂詞公式和謂詞公式的否定的析取的有限集組成的合取。因此，我們可以消去前綴。任一只由文字的析取構(gòu)成的合適公式叫做一個子句。星期六 67更換變量名稱 P(A)P(y)∨ ?Q(A,z)∨ P(z,g(z))?P(f(A,y))∨ ?Q(A,z)∨ P(z,g(z))前面出的計算的 合取范式 是{P(A)∧ {[P(y)∨ ?Q(A,z)∨ P(z,g(z))]∧ [?P(f(A,y))∨ ?Q(A,z)∨ P(z,g(z))]}}2023/2/27n 若能建造一個較為簡單的 特殊論域 ，使得只要證明子句集S在該域不可滿足，就可確保子句集在 任何可能的論域 上不可滿足，將是十分有意義的 ！n 海伯倫建立的特殊域 H就具有這樣的性質(zhì)。星期六 71歸結(jié)演繹推理歸結(jié)演繹推理1） H域和海伯倫定理p 海伯倫定理 （了解）n 子句集 S中一子句包含的變量用 H域 中元素取代后，產(chǎn)生的子句稱為 基子句 。n 歸結(jié)原理 簡單易行 ，便于計算機實現(xiàn)和執(zhí)行，從而使定理的機器自動證明成為現(xiàn)實，也成為 人工智能技術(shù)實用化的一次重要突破 。C2’；p稱 C為 C1和 C2的 歸結(jié)式（消解式） ；n 例、兩個子句pC1=P(A)∨ Q(x)∨ R(f(x))pC2=?P(A)∨ Q(y)∨ R(y)p消去 互補文字 P(A)和 ?P(A)后，生成 歸結(jié)式 ：pC12=∨ 星期六 74歸結(jié)演繹推理歸結(jié)演繹推理2）歸結(jié)原理p 歸結(jié)方法p (2)歸結(jié)式性質(zhì)n 定理 ： 兩個子句 C1和 C2的歸結(jié)式 C是 C1和 C2的邏輯推論p任一使子句 C1和 C2為真的解釋 I，必使歸結(jié)式 C為真；p歸結(jié)式 C為假的解釋 I，子句 C1或者 C2為假；n 推論 ：p設(shè) C1C2=?L，則歸結(jié)式 C為 空 ；n 以 □ 表示為空的歸結(jié)式 C，并稱 C=□ 為 空子句；n 因為 C1和 C2是一對矛盾子句，不可同時滿足，所以 □ 是 不可滿足 的子句 ；n 通過往 S中加入 □ 而產(chǎn)生的擴展子句集 S’不可滿足；n 空子句 □ 是用 歸結(jié)原理 判定子句集 S不可滿足的 成功標志 。星期六 78(4) 空子句 (矛盾)P ~PNIL（ 5）鏈式（三段論）~ P∨ R,(即 P=R) ~ R ∨ Q, (即 R = Q)~ P∨ Q,(即 P=Q)2023/2/27n 空子句 是不可滿足（即永假）的子句；2023/2/27?R}的歸結(jié)演繹樹。?Q,n 變量置換：p用 置換項 取代公式中的 變量 ；p置換項 可以是 變量 、 常量 或 函數(shù) 。g(x)),z)2023/2/27g(x)),z)我們可以為它們建立 多個置換 ：　　　　 S1 = {A/x, B/y, g(x)/z} 　　　　 S2 = {f(w)/x, z/y, C/z}　　　　 S3 = {B/x, f(w)/y, y/z}置換結(jié)果為：　　　　 {P(x, y, x, g(x)), ?P(A, B, A, z)}S1 　　　　 ={P(A, B, A, g(A)), ?P(A, B, A, g(A))}　　　　 {P(x, y, x, g(x)), ?P(A, B, A, z)}S2 　　　　 ={P(f(w)), z, f(w), g(f(w)), ?P(A, B, A, C)}　　　 {P(x, y, x, g(x)), ?P(A, B, A, z)}S3　　　　 ={P(B, f(w), B, g(B)), ?P(A, B, A, y)}S1使 潛在 的互補文字中的原子謂詞公式變?yōu)?同一 ，確認互補性。用 s1s2表示兩個置換 s1和 s2的合成。n 變量置換：p用 置換項 取代公式中的 變量 ；p置換項 可以是 變量 、 常量 或 函數(shù) 。x,A,★p① 兩個 原子謂詞公式 必須具有相同的 謂詞符號 和 參數(shù)項個數(shù) ；p② 從左到右逐個 檢查 每對參數(shù)項的 可合一性 ；p③ 若每對參數(shù)項都可合一，則合一處理成功，并 建立 用于實現(xiàn)合一的 置換 。2023/2/27g(x)),z)n ① 兩個 原子謂詞公式 必須具有相同的 謂詞 和 參數(shù)項個數(shù) ；n ② 從左到右逐個 檢查 每對參數(shù)項的 可合一性 ；px和和 A， x初次出現(xiàn) ，可合一，建立置換元素 A/x。n 建立置換 S1={A/x,星期六 90歸結(jié)演繹推理歸結(jié)演繹推理2）歸結(jié)原理 置換和合一p 歸結(jié)推理過程p (2)謂詞邏輯中的歸結(jié)推理過程n 謂詞邏輯中子句歸結(jié)的例子： ∨ ∨ R(A,f(B))星期六 91歸結(jié)演繹推理歸結(jié)演繹推理2）歸結(jié)原理 置換和合一p 歸結(jié)推理過程p (2)謂詞邏輯中的歸結(jié)推理過程n 謂詞邏輯中子句歸結(jié)的例子： ∨ ∨ ∨ 星期六 92歸結(jié)演繹推理歸結(jié)演繹推理2）歸結(jié)原理 置換和合一p 歸結(jié)推理過程p (2)謂詞邏輯中的歸結(jié)推理過程n 謂詞邏輯中子句歸結(jié)的例子： ∨ ∨ 第一對參數(shù)是可同一的，用 z/a,第二對參數(shù)也是可同一的，因為 z已經(jīng)出現(xiàn)過，所以用 a換 z,然后用 h(a,u)/x第三對參數(shù)可用 g(y)/u所以該公式是可同一的，可建立置換S1={z/a, h(a,u)/x, g(y)/u}2023/2/27星期六 97歸結(jié)演繹推理歸結(jié)演繹推理2）歸結(jié)原理p 歸結(jié)推理過程p (2)謂詞邏輯中的歸結(jié)推理過程子句集 S不可滿足2023/2/27星期六 99歸結(jié)演繹推理歸結(jié)演繹推理p 學習難點學習難點n 從以自然語言表示的事實集證明目標公式（定理）并提取回從以自然語言表示的事實集證明目標公式（定理）并提取回答的綜合題。合適公式 F永假子句集 S的不可滿足性充分必要條件有限的不可滿足的基子句集 S’ 子句集 S不可滿足性充分必要條件歸結(jié)后擴展子句集 S’子句集 S不可滿足性等價歸結(jié)的演繹推理的完備性： 若子句集 S不可滿足，就必定存在一個從 S到 空子句 □ 的歸結(jié)演繹；反之亦然。加入公式集 F；n ② 標準化 F∧ ?W為子句集 S；n ③ 通過歸結(jié)演繹證明 S不可滿足，得出 W為真的結(jié)論。3）歸結(jié)反演 —— 歸結(jié)反演系統(tǒng)p 例、歸結(jié)反演的應(yīng)用 —— 食物問題p 已知下列 事實 為真 T，n 王 (Wang)喜歡 (Like)所有種類的食物 (Food)。n 張 (Zhang)吃任何李吃的東西。3）歸結(jié)反演 —— 歸結(jié)反演系統(tǒng)p 例、歸結(jié)反演的應(yīng)用 —— 食物問題p ① 形式化 —— 把以自然語言表示的 事實 和要證明的 目標 形式化地表示為 合適公式 。Like(Wang,x)]n 蘋果 (Apples)是食物。?Killed(y)Alive(y)∧ Eat(Zhang,x)]n 王喜歡花生。n 王 (Wang)喜歡 (Like)所有種類的食物 (Food)。pFood(Apples)pFood(Apples)n 任何一個東西，若任何人吃了 (Eat)它都不會被害死(Killed)，則該東西是食物。??星期六 105歸結(jié)演繹推理歸結(jié)演繹推理∧ Eat(Zhang,x)]p?pLike(Wang,Peanuts)p?2023/2/27星期六 108歸結(jié)演繹推理歸結(jié)演繹推理3）歸結(jié)反演 —— 歸結(jié)反演系統(tǒng)p 例、歸結(jié)反演的應(yīng)用 —— 食物問題p ③ 歸結(jié)演繹 —— 應(yīng)用歸結(jié)演繹方法不斷生成 歸結(jié)式 以擴展子句集 S，直到生成 空子句 □ 。目標公式得證歸結(jié)反演樹2023/2/27結(jié)論：如果沒有利息，那么就沒有人去儲蓄錢。表示 x是利息E（ x， y） 3）歸結(jié)反演 —— 歸結(jié)反演系統(tǒng)2023/2/27S(x， y)∨ ~M（ y） ∨ I（ f（ x））（ 2） ~星期六 113p 結(jié)論的否定為~（ ~（ ?x） I（ x） =（ ?x）（ ?y）（ M（ y）=~S（ x， y）））化為子句形~（（ ?x） I（ x） ∨ （ ?x）（ ?y）（ ~星期六 114儲蓄問題的反演樹 M（ y） ∨ I（ f（ x））（ 2） ~3）歸結(jié)反演 :課堂練習p 某公司招聘工作人員， A， B， C三人應(yīng)試，經(jīng)面試后，公司表示如下想法：n （ 1） n （ 3） 提示：設(shè)用 P(x)表示錄取 x） 三人中至少錄取一人。如果錄取 A而不錄取 B，則一定錄取 C。P(C)n （ 3） ?3）歸結(jié)反演p 把上述公式化成子句集n ① P(A)∨ ∨ P(C) ③P(C) ④2023/2/27n C回答： A和 B中至少有一個是說謊者。n A回答： B和 C都是說謊者。B?pB∧ A??∧ n 化簡上述蘊含式為子句集n ① ?BB∨ A∨ Cn ⑦ B王某被害，有四個嫌疑犯 A， B， C， D，公安局派出五個偵察員，他們帶回的信息各不一樣，甲說 A， B中至少有一人作案，乙說 B星期六 122（ 1） DA（ 5） ~~（ 2）、（ 6）歸結(jié)；D（ 2）、（ 5）歸結(jié)；（ 9） 2023/2/27歸結(jié)演繹推理歸結(jié)演繹推理n 蘋果 (Apples)是食物。p 證明：n 王