【正文】 ood)。p (?x)[Food(x)?Like(Wang,x)]n 蘋果 (Apples)是食物。p Food(Apples)n 任何一個東西，若任何人吃了 (Eat)它都不會被害死 (Killed)，則該東西是食物。p (?x)(?y)[Eat(y,x)∧ ?Killed(y)?Food(x)]p (?x)(?y)[Eat(y,x)∧ Alive(y)?Food(x)]n 李 (Li)吃花生 (Peanuts)且仍然活著 (Alive)。p Eat(Li,Peanuts)∧ Alive(Li)n 張 (Zhang)吃任何李吃的東西。p (?x)[Eat(Li,x)?Eat(Zhang,x)]n 王喜歡花生。p Like(Wang,Peanuts)減少謂詞數(shù)2023/2/27星期六 104歸結演繹推理歸結演繹推理3）歸結反演 —— 歸結反演系統(tǒng)p 例、歸結反演的應用 —— 食物問題p ② 標準化 —— 將事實公式和 取反后的目標公式 分別標準化為子句，并組成子句集 S。n 王 (Wang)喜歡 (Like)所有種類的食物 (Food)。p(?x)[Food(x)?Like(Wang,x)]p?Food(x1)∨ Like(Wang,x1)n 蘋果 (Apples)是食物。pFood(Apples)pFood(Apples)n 任何一個東西，若任何人吃了 (Eat)它都不會被害死(Killed)，則該東西是食物。p(?x)(?y)[Eat(y,x)∧ Alive(y)?Food(x)]p?Eat(y,x2)∨ ?Alive(y)∨ Food(x2)2023/2/27星期六 105歸結演繹推理歸結演繹推理3）歸結反演 —— 歸結反演系統(tǒng)p 例、歸結反演的應用 —— 食物問題p ② 標準化 —— 將事實公式和 取反后的目標公式 分別標準化為子句，并組成字句集 S。n 李 (Li)吃花生 (Peanuts)且仍然活著 (Alive)。pEat(Li,Peanuts)∧ Alive(Li)pEat(Li,Peanuts)pAlive(Li)n 張 (Zhang)吃任何李吃的東西。p(?x)[Eat(Li,x)?Eat(Zhang,x)]p?Eat(Li,x3)∨ Eat(Zhang,x3)n 王喜歡花生。pLike(Wang,Peanuts)p?Like(Wang,Peanuts)取反2023/2/27星期六 106歸結演繹推理歸結演繹推理3）歸結反演 —— 歸結反演系統(tǒng)p 例、歸結反演的應用 —— 食物問題p ③ 歸結演繹 —— 應用歸結演繹推理不斷生成 歸結式 以擴展子句集 S，直到生成 空子句 □ 。2023/2/27星期六 107歸結演繹推理歸結演繹推理3）歸結反演 —— 歸結反演系統(tǒng)p 例、歸結反演的應用 —— 食物問題p ③ 歸結演繹 —— 應用歸結演繹方法不斷生成 歸結式 以擴展子句集 S，直到生成 空子句 □ 。2023/2/27星期六 108歸結演繹推理歸結演繹推理3）歸結反演 —— 歸結反演系統(tǒng)p 例、歸結反演的應用 —— 食物問題p ③ 歸結演繹 —— 應用歸結演繹方法不斷生成 歸結式 以擴展子句集 S，直到生成 空子句 □ 。2023/2/27星期六 109歸結演繹推理歸結演繹推理3）歸結反演 —— 歸結反演系統(tǒng)p 例、歸結反演的應用 —— 食物問題p ③ 歸結演繹 —— 應用歸結演繹方法不斷生成 歸結式 以擴展子句集 S，直到生成 空子句 □ 。2023/2/27星期六 110歸結演繹推理歸結演繹推理3）歸結反演 —— 歸結反演系統(tǒng)p 例、歸結反演的應用 —— 食物問題p ③ 歸結演繹 —— 應用歸結演繹方法不斷生成 歸結式 以擴展子句集 S，直到生成 空子句 □ 。目標公式得證歸結反演樹2023/2/27星期六 111p 例 前提：每個儲蓄錢的人都獲得利息。結論：如果沒有利息，那么就沒有人去儲蓄錢。p 令： S（ x， y）表示 x儲蓄 yM（ x） 表示 x是錢I（ x） 表示 x是利息E（ x， y） 表示 x獲得 yp 前提： (?x)[(?y)(S(x， y)∧ M(y))]=[(?y)(I(y)∧ E(x， y)]結論： ~(?x)I(x)=(?x)(?y)(M(y)=~S(x， y))歸結演繹推理歸結演繹推理3）歸結反演 —— 歸結反演系統(tǒng)2023/2/27星期六 112p 把前提化為子句形：(?x)(~(?y)(S(x， y)∧ M(y))∨ (?y)(I(y)∧ E(x，y)))(?x)((?y)(~(S(x， y)∧ M(y)))∨ （ ?y）（ I（ y）∧ E（ x， y）））(?x)((?y)(~S(x， y)∨ ~M（ y）） ∨ （ ?y）（ I（ y） ∧ E（ x， y）））p 令 y=f(x)為 Skolem函數(shù)，則得子句形(?x)(?y)((~S(x， y)∨ ~M(y)∨ I(f(x)))∧ (~S(x， y)∨ M(y)∨ E(x， f（ x）））（ 1） ~S（ x， y） ∨ ~M（ y） ∨ I（ f（ x））（ 2） ~S（ x， y） ∨ ~M（ y） ∨ E（ x， f（ x）））歸結演繹推理歸結演繹推理3）歸結反演 —— 歸結反演系統(tǒng)2023/2/27星期六 113p 結論的否定為~（ ~（ ?x） I（ x） =（ ?x）（ ?y）（ M（ y）=~S（ x， y）））化為子句形~（（ ?x） I（ x） ∨ （ ?x）（ ?y）（ ~M（ y）∨ ~S（ x， y）））（ ~（ ?x） I（ x） ∧ （ ~（ ?x）（ ?y）（ ~M（ y） ∨ ~S（ x， y））））（ ?x）（ ~I（ x）） ∧ （ ?x）（ ?y）（ M（ y）∧ S（ x， y））p 變量分離標準化后得下列子句：（ 3） ~I（ z）（ 4） S（ a， b）（ 5） M（ b）歸結演繹推理歸結演繹推理3）歸結反演 —— 歸結反演系統(tǒng)2023/2/27星期六 114儲蓄問題的反演樹 歸結演繹推理歸結演繹推理3）歸結反演 —— 歸結反演系統(tǒng)（ 1） ~S（ x， y） ∨ ~M（ y） ∨ I（ f（ x））（ 2） ~S（ x， y） ∨ ~M（ y） ∨ E（ x， f（ x）））（ 3） ~I（ z）（ 4） S（ a， b）（ 5） M（ b）2023/2/27星期六 115歸結演繹推理歸結演繹推理3）歸結反演 :課堂練習p 某公司招聘工作人員， A， B， C三人應試，經面試后，公司表示如下想法：n （ 1） 三人中至少錄取一人。n （ 2） 如果錄取 A而不錄取 B，則一定錄取 C。n （ 3） 如果錄取 B，則一定錄取 C。p 用歸結反演法證明：公司一定錄取 C。p （ 提示：設用 P(x)表示錄取 x） 2023/2/27星期六 116歸結演繹推理歸結演繹推理3）歸結反演p 把公司的想法用謂詞公式表示如下：n （ 1） 三人中至少錄取一人。pP(A)∨ P(B)∨ P(C)n （ 2） 如果錄取 A而不錄取 B，則一定錄取 C。pP(A)∧ ?P(B)?P(C)n （ 3） 如果錄取 B，則一定錄取 C。 pP(B)?P(C)p 把要求證的 問題否定 ，并用謂詞公式表示出來： n 公司一定錄取 Cp?P(C)2023/2/27星期六 117歸結演繹推理歸結演繹推理3）歸結反演p 把上述公式化成子句集n ① P(A)∨ P(B)∨ P(C)n ② ?P(A)∨ P(B)∨ P(C)n ③ ?P(B)∨ P(C)n ④ ?P(C)p 應用歸結反演： ① ②P(B)∨ P(C) ③P(C) ④2023/2/27星期六 118歸結演繹推理歸結演繹推理3）歸結反演 —— 提取問題回答p 某記者到一個孤島采訪，遇到一個難題，即島上有許多人說假話，因而難以保證新聞報道的正確性，不過有一點他是清楚的，這個島上的人有一個特點：n 說假話的人從來不說真話，說真話的人從來不說假話；p 一次，記者遇到了孤島上的 3個人，為了弄清誰說真話，誰說假話，他向這 3個人中的每一個都提了一個同樣的問題 “誰是說謊者？ ”n A回答： B和 C都是說謊者。n B回答： A和 C都是說謊者。n C回答： A和 B中至少有一個是說謊者。p 誰是說謊者？2023/2/27星期六 119歸結演繹推理歸結演繹推理3）歸結反演 —— 提取問題回答n 設 A、 B、 C三個命題表示 A、 B、 C三人是老實人。n A回答： B和 C都是說謊者。pA??B∧ ?Cp?A?B∨ Cn B回答： A和 C都是說謊者。pB??A∧ ?Cp?B?A∨ Cn C回答： A和 B中至少有一個是說謊者。pC??A∨ ?Bp?C?A∧ B2023/2/27星期六 120歸結演繹推理歸結演繹推理3）歸結反演 —— 提取問題回答n 設 A、 B、 C三個命題表示 A、 B、 C三人是老實人。n 化簡上述蘊含式為子句集n ① ?A∨ ?Bn ② ?A∨ ?Cn ③ A∨ B∨ Cn ④ ?B∨ ?Cn ⑤ ?A∨ ?B∨ ?Cn ⑥ A∨ Cn ⑦ B∨ C① 和 ⑦ 歸結： ? A ∨ C⑧② 和 ⑧ 歸結： ? A⑨⑥ 和 ⑨ 歸結： C⑩④ 和 ⑩ 歸結： ? B結論： A和 B都是說謊者，而 C是老實人2023/2/27星期六 121p 例 :王某被害，有四個嫌疑犯 A， B， C， D，公安局派出五個偵察員，他們帶回的信息各不一樣，甲說 A， B中至少有一人作案，乙說 B， C中至少有一人作案，丙說 C， D中至少有一人作案，丁說 A， C中至少有一人與此案無關，戊說 B， D中至少有一人與此案無關，如果這五個偵察員的話都是可靠的，那么誰是罪犯。2023/2/27星期六 122（ 1） A∨ B（ 2） B∨ C（ 3） C∨ D（ 4） ~A∨ ~C（ 5） ~B∨ ~D（ 6） B∨ ~C（ 1）、（ 4）歸結；（ 7） B是罪犯。 （ 2）、（ 6）歸結；（ 8） C∨ ~D（ 2）、（ 5）歸結；（ 9） C是罪犯。 （ 3）、（ 8）歸結。2023/2/27星期六 123p 歸結反演 可實現(xiàn) 問題回答系統(tǒng)n 目標公式往往 受存在量詞約束 ，如 (?x)W(x)；n 不僅證明目標公式為真 T；n 回答提取 —— 給出使 W(x)為真 T的 x的某個取值。p 問題回答系統(tǒng) 分為 2個階段：n ① 歸結反演 —— 證明目標公式為真 Tn ② 回答提取p對于標準化 取反的目標公式 而產生的子句（稱為 目標子句 ） G,建立其 重言式（永真式） G∨ ?G；p以 G∨ ?G取代 G,重復已進行過的歸結演繹過程，建立修改證明樹 。n 結果 —— 修改證明樹 的樹根不再是 空子句 □ ，而是 ?G，且 G中的變量已為其 置換項 取代，實現(xiàn)了回答提取。歸結演繹推理歸結演繹推理3）歸結反演 —— 提取問題回答2023/2/27星期六 124歸結演繹推理歸結演繹推理3）歸結反演 —— 提取問題回答p 例、 提取問題回答 的應用 —— 食物問題p 已知下列事實為真，n 王 (Wang)喜歡 (Like)所有種類的食物 (Food)。n 蘋果 (Apples)是食物。n 任何一個東西，若任何人吃了 (Eat)它都不會被害死 (Killed)，則該東西是食物。n 李 (Li)吃花生 (Peanuts)且仍然活著 (Alive)。n 張 (Zhang)吃任何李吃的東西。p 證明：n 王喜歡花生。p 問題：n 張吃什么食物？2023/2/27星期六 125歸結演繹推理歸結演繹推理3）歸結反演 —— 提取