【正文】 f(x,y))]?(?y)[P(y)∧ ?P(f(x,y))]p ④ 變量換名n “ ⑥ 全稱量詞前束化 ” 后，同名變量的轄域無法區(qū)分，所以為避免差錯，必須換名；n 約束變量的虛元性 進行變換；[?Q(x,z)p ⑦ 消去全稱量詞n 經(jīng)過 “ ⑤ 消去存在量詞 ” 后，所有變量均受 ?的約束；n 簡單地刪除 ?，只留下母式。∨ 星期六 51p 合取范式的標準化過程n 例、化簡合適公式?(?x){P(x)?{(?y)[P(y)星期六 582023/2/27星期六 61歸結(jié)演繹推理歸結(jié)演繹推理1） H域和海伯倫定理p 子句和子句集n 子句 —— 僅由 文字 的 析取 ∨ 構(gòu)成的合適公式n 合取范式 表示為 子句集 ，子句間隱含具有合取關(guān)系{P(A)∧[P(y)∨ ?Q(A,z)∨ P(z,g(z))]∧[?P(f(A,y))∨ ?Q(A,z)∨ P(z,g(z))]}n 可進一步表示為子句集{P(A),P(y)∨ ?Q(A,z)∨ P(z,g(z)),?P(f(A,y))∨ ?Q(A,z)∨ P(z,g(z))}2023/2/27∧ (?x)(?z)P(A),(?y)代替 ~（ A∧ B）以 ~A∧ ~B 如果用 Skolem函數(shù)代替存在的 x，我們就可以消去全部存在量詞 2023/2/27用 {A， B}代替 {A∧ B}，以消去明顯的符號 ∧ 。這樣合式公式 F化為子句集 n 證明 子句集 S的不可滿足性p確定子句集 S在 H域 上的所有解釋都不可滿足 。星期六 73歸結(jié)演繹推理歸結(jié)演繹推理2）歸結(jié)原理p 歸結(jié)方法p (1)歸結(jié)式（消解式 *）n 設(shè)有兩個子句 C1=L∨ C1’、 ∨ 星期六 76(1) 假言推理父輩子句 P ~P∨ Q（即 P=Q）消解式 QC1=P, C2=~P ∨ Q（ 2）合并 C1=P∨ Q,C2=~P∨ Q父輩子句 P∨ Q ~P∨ Q消解式 Q ∨ Q＝ Q2023/2/27P∨ R,擴展子句集 S’包含 空子句子句集 S不可滿足2023/2/27B,B,即 s1s2?s2s1 2023/2/27?P(A,星期六 88歸結(jié)演繹推理歸結(jié)演繹推理2）歸結(jié)原理 置換和合一p 【 匹配過程 】n ② 從左到右逐個 檢查 每對參數(shù)項的 可合一性 ；p參數(shù)對中有一個是變量 v（不關(guān)心另一個 t是否是變量）nv初次出現(xiàn) ，參數(shù)對可合一，以另一參數(shù) t為置換項，構(gòu)成置換元素 t/v。B,g(x)/z}∨ ∨ ∨ ∨ ∨ 星期六 95歸結(jié)演繹推理歸結(jié)演繹推理2）歸結(jié)原理p 歸結(jié)推理過程p (2)謂詞邏輯中的歸結(jié)推理過程2023/2/27p 應(yīng)用歸結(jié)演繹推理的定理證明為 歸結(jié)反演 。星期六 101歸結(jié)演繹推理歸結(jié)演繹推理n 任何一個東西，若任何人吃了 (Eat)它都不會被害死 (Killed)，則該東西是食物。p (?x)[Food(x)Food(x)]p (?x)(?y)[Eat(y,x)p (?x)[Eat(Li,x)?Eat(y,x2)n 李 (Li)吃花生 (Peanuts)且仍然活著 (Alive)。∨ 3）歸結(jié)反演 —— 歸結(jié)反演系統(tǒng)p 例、歸結(jié)反演的應(yīng)用 —— 食物問題p ③ 歸結(jié)演繹 —— 應(yīng)用歸結(jié)演繹方法不斷生成 歸結(jié)式 以擴展子句集 S，直到生成 空子句 □ 。星期六 110歸結(jié)演繹推理歸結(jié)演繹推理M（ x） (?x)((?y)(~(S(x， y)∧ M(y)))∨ （ ?y）（ I（ y）∧ E（ x， y）））(?x)((?y)(~M（ y） ∨ E（ x， f（ x）））歸結(jié)演繹推理歸結(jié)演繹推理M（ b）歸結(jié)演繹推理歸結(jié)演繹推理M（ y） ∨ E（ x， f（ x）））（ 3） ~I（ z）（ 4） S（ a， b）（ 5） n （ 2） 星期六 116歸結(jié)演繹推理歸結(jié)演繹推理∧ ?P(B)n 公司一定錄取 Cp?P(C)2023/2/27∨ P(C)n ④ ?P(C)p 應(yīng)用歸結(jié)反演： 星期六 119歸結(jié)演繹推理歸結(jié)演繹推理??Cn C回答： A和 B中至少有一個是說謊者。?∨ Cn ③ A?Cn ⑥ A D中至少有一人與此案無關(guān)，如果這五個偵察員的話都是可靠的，那么誰是罪犯。B（ 4） BB是罪犯。∨ 星期六 124歸結(jié)演繹推理歸結(jié)演繹推理星期六 125歸結(jié)演繹推理歸結(jié)演繹推理n 李 (Li)吃花生 (Peanuts)且仍然活著 (Alive)。p 問題回答系統(tǒng) 分為 2個階段：n ① 歸結(jié)反演 —— 證明目標公式為真 Tn ② 回答提取p對于標準化 取反的目標公式 而產(chǎn)生的子句（稱為 目標子句 ） G,建立其 重言式（永真式） G∨ ?G；p以 G∨ ?G取代 G,重復已進行過的歸結(jié)演繹過程，建立修改證明樹 。 B~（ 3） C∨ C① 和 ⑦ 歸結(jié)： ? A ∨ C⑧② 和 ⑧ 歸結(jié)： ? A⑨⑥ 和 ⑨ 歸結(jié)： C⑩④ 和 ⑩ 歸結(jié)： ? B結(jié)論： A和 B都是說謊者，而 C是老實人2023/2/27?Cn ④ ?A星期六 120歸結(jié)演繹推理歸結(jié)演繹推理ACp?B∨ ?3）歸結(jié)反演 —— 提取問題回答p 某記者到一個孤島采訪，遇到一個難題，即島上有許多人說假話，因而難以保證新聞報道的正確性，不過有一點他是清楚的，這個島上的人有一個特點：n 說假話的人從來不說真話，說真話的人從來不說假話；p 一次，記者遇到了孤島上的 3個人，為了弄清誰說真話，誰說假話，他向這 3個人中的每一個都提了一個同樣的問題 “誰是說謊者？ ”n A回答： B和 C都是說謊者?！?P(C)n ② ?P(A) ∨ P(B)p 用歸結(jié)反演法證明：公司一定錄取 C。M（ b）2023/2/273）歸結(jié)反演 —— 歸結(jié)反演系統(tǒng)（ 1） ~M（ y） ∨ ~S（ x， y））））（ ?x）（ ~I（ x）） ∧ （ ?x）（ ?y）（ M（ y）∧ S（ x， y））p 變量分離標準化后得下列子句：（ 3） ~I（ z）（ 4） S（ a， b）（ 5） S(x， y)∨ M(y)∨ E(x， f（ x）））（ 1） ~p 前提： (?x)[(?y)(S(x， y)∧ M(y))]=[2023/2/27星期六 106歸結(jié)演繹推理歸結(jié)演繹推理p(?x)[Eat(Li,x)∨ ∧ 星期六 104歸結(jié)演繹推理歸結(jié)演繹推理Food(x)]n 李 (Li)吃花生 (Peanuts)且仍然活著 (Alive)。p (?x)(?y)[Eat(y,x)2023/2/272023/2/272023/2/27n 但歸結(jié)原理并不能用于解決子句集不可滿足性的不可判問題，即若子句集 S是 永真的和可滿足的 ， 歸結(jié)原理 判定過程將無休止地進行下去，得不到任何結(jié)果。?P(A,B)是互補文字n L21=Q(x,f(x))和 L22=?Q(z,f(z))是互補文字n 兩個子句可以有多于一對的互補文字2023/2/27∨ ∨ ∨ ?P(A,B)是潛在的互補文字pL11和 L12是 可合一 的；p建立置換 S1={A/x,B/y}p消去互補文字 L11和 L12后，得歸結(jié)式：Q(A,f(A))∨ px和和 A， y,星期六 87歸結(jié)演繹推理歸結(jié)演繹推理2）歸結(jié)原理 置換和合一p 歸結(jié)推理過程p (2)謂詞邏輯中的歸結(jié)推理過程n 通過一個 匹配過程 去 檢查 兩個原子謂詞公式的 可合一性 ，并同時 建立 用于實現(xiàn)合一的 置換 。P(x,星期六 84置換和合一實例 1將它們分別作用于表達式，得：P[x， f（ y）， B]s1=P[z， f（ w）， B]P[x， f（ y）， B]s2=P[x， f（ A）， B]P[x， f（ y）， B]s3=P[q（ z）， f（ A）， B]P[x， f（ y）， B]s4=P[c， f（ A）， B]表達式 P[x， f（ y）， B] 的 4 個置換為s1={z/x， w/y}s2={A/y}s3={q（ z） /x， A/y}s4={c/x， A/y}2023/2/27y,y,星期六 81歸結(jié)演繹推理歸結(jié)演繹推理2）歸結(jié)原理p 歸結(jié)推理過程p (1)命題邏輯中的歸結(jié)推理過程n 例、子句集 S={?P∨ Q,n 歸結(jié)原理 簡單易行 ，便于計算機實現(xiàn)和執(zhí)行，從而使定理的機器自動證明成為現(xiàn)實，也成為 人工智能技術(shù)實用化的一次重要突破 。是子句集 S中的兩個子句，并以 C作為它們的歸結(jié)式；p通過往 S中加入 C而產(chǎn)生的擴展子句集 S’與子句集 S在 不可滿足 的意義上是等價的 ！歸結(jié)后擴展子句集 S’子句集 S不可滿足性等價2023/2/27∨ 有限的不可滿足的基子句集 S’ 子句集 S不可滿足性充分必要條件2023/2/27星期六 69歸結(jié)演繹推理歸結(jié)演繹推理1） H域和海伯倫定理p 子句和子句集合適公式 F 合取范式 子句集 S合適公式 F永假子句集 S的不可滿足性充分必要條件合適公式 F 子句集 S不等價S是 F的特例重要性質(zhì)S的不可滿足性任意論域 D上的任意解釋 I,S中都 至少 有一個 子句 真值為 F2023/2/27?P(f(x,y))]∧ ?(?y)(?w)[Q(x,y)?P(y,w)]}}消去連詞符號 ∧所有余下的量詞均被全稱量詞量化了。反復應(yīng)用分配率，如把A∨ {B∧ C}化為 Skolem函數(shù)所使用的函數(shù)符號必須是新的。在公式（ ?y） [（ ?x） P（x， y） ]中，存在量詞是在全稱量詞的轄域內(nèi)，我們允許所存在的 x可能依賴于 y值。如：（P∨ Q∨ R）2023/2/27合適公式中變量的標準化意味著對啞元改名以保證每個 星期六 64只應(yīng)用 ∨ 和 ~符號，以~A∨ B替換 A=B。(?z)[P(y)∨ ?Q(A,z)∨ P(z,g(z))]∧ ∨ Lim稱為 子句 ；n 合取范式 定義：pM=W1∧ W2∧ …∧ ?W的 永假n 即 {F1,星期六 54p 合取范式的標準化過程n 例、化簡合適公式(?x){P(x)∧{(?y)[P(y)∧ ?P(f(x,y))]∨ (?z)(?w)[?Q(x,z)∨ P(z,w)]}}⑤ 消去存在量詞{P(A)∧{(?y)[P(y)∧ ?P(f(A,y))]∨ (?z)[?Q(A,z)∨ P(z,g(z))]}}2023/2/27∨ ∧ 若要消去的 存在量詞不在任何一個全稱量詞的轄域內(nèi)，用不含變量的 Skolem函數(shù)即 Skolem常量消去存在量詞 。Skolem函數(shù)所使用的函數(shù)符號必須是 新的 ，即不允許是公式中已經(jīng)出現(xiàn)過的函數(shù)符號?！?P(z,w)]p w依賴于 z，由函數(shù) w=g(z)來定義這種依賴關(guān)系；p 用 g(z)來取代約束變量 w，消去存在量詞 ?w；p (?z)[?Q(x,z)???Qp ?(P2023/2/27Q；n 例， 2023/2/272023/2/27無參 Skolem函數(shù)有時稱 Skolem常量 。其中前束是一個存在量詞 或 全稱量詞 的序列，母式中不在含有量詞。星期六 39前束范式例 2： (?x)(?y){((?z)(P(x， z)∧ P(y， z))=(?u)Q(x， y， u))}??x)(?y)(~((?z)(P(x， z)∧ P(y， z)))∨ (?u)Q(x， y， u))(?x)(?y)(?z)(~P(x))　　　　 172。P∧ 172。p謂詞、函數(shù)名 的出現(xiàn)位置 不允許使用變量 ；p參數(shù)項 不能是 謂詞公式 ；n (?P)P(A)謂詞進行了量化；n (?y)Married(y(L1),Mary真值為 T。p （ 1）連詞n 通過連詞產(chǎn)生的復合謂詞公式（邏輯語句）的 真值表 ：P Q P P∧ Q P∨ Q P Q P QT T F T T T TF T T F T T FT F F F T F FF F T F F T T2023/2/27p （ 1）連詞（非）加在 謂詞公式 前面，稱為否定，或取反。? 謂詞演算 —— 人工智能系統(tǒng)最常用的知識表示方法，? 廣泛地應(yīng)用于各種人工智能系統(tǒng)的設(shè)計。n 所以，不知道新聞。 n 金星會顯示出位相變化。n T規(guī)則： 推理時，如果前面步驟中有一個或多個公式永真蘊涵公式 S，則可把 S引入推理過程中。星期六 17推理的控制策略⑥ 按條件個數(shù)排序l 多條規(guī)則生成的結(jié)論相同的情況下，由于條件個數(shù)較少的規(guī)則匹配所花費的時間較少而且容易實現(xiàn)，所以將條件少的規(guī)則賦予較高的優(yōu)先級，優(yōu)先被啟用。① 按就近原則排序l 該策略把最近被使用過的規(guī)則賦予較