【正文】 3）歸結(jié)反演 —— 提取問(wèn)題。p 問(wèn)題：n 張吃什么食物？2023/2/27n 張 (Zhang)吃任何李吃的東西。n 任何一個(gè)東西，若任何人吃了 (Eat)它都不會(huì)被害死 (Killed)，則該東西是食物。3）歸結(jié)反演 —— 提取問(wèn)題回答p 例、 提取問(wèn)題回答 的應(yīng)用 —— 食物問(wèn)題p 已知下列事實(shí)為真，n 王 (Wang)喜歡 (Like)所有種類(lèi)的食物 (Food)。3）歸結(jié)反演 —— 提取問(wèn)題回答2023/2/27n 結(jié)果 —— 修改證明樹(shù) 的樹(shù)根不再是 空子句 □ ，而是 ?G，且 G中的變量已為其 置換項(xiàng) 取代，實(shí)現(xiàn)了回答提取。星期六 123p 歸結(jié)反演 可實(shí)現(xiàn) 問(wèn)題回答系統(tǒng)n 目標(biāo)公式往往 受存在量詞約束 ，如 (?x)W(x)；n 不僅證明目標(biāo)公式為真 T；n 回答提取 —— 給出使 W(x)為真 T的 x的某個(gè)取值。（ 3）、（ 8）歸結(jié)。C是罪犯。~（ 8） C （ 1）、（ 4）歸結(jié)；（ 7） C∨ D（ 6） ∨ ~C∨ ~∨ C∨ （ 2） BA2023/2/27 C中至少有一人作案，丙說(shuō) C， D中至少有一人作案，丁說(shuō) A， C中至少有一人與此案無(wú)關(guān)，戊說(shuō) B星期六 121p 例 :∨ ∨ ?B∨ Cn ⑤ ?B∨ ∨ ?∨ n ② ??A3）歸結(jié)反演 —— 提取問(wèn)題回答n 設(shè) A、 B、 C三個(gè)命題表示 A、 B、 C三人是老實(shí)人。B2023/2/27ABp?C∨ ?pC∨ ??A?Cn B回答： A和 C都是說(shuō)謊者。BCp?A∧ ?pA3）歸結(jié)反演 —— 提取問(wèn)題回答n 設(shè) A、 B、 C三個(gè)命題表示 A、 B、 C三人是老實(shí)人。p 誰(shuí)是說(shuō)謊者？2023/2/27n B回答： A和 C都是說(shuō)謊者。星期六 118歸結(jié)演繹推理歸結(jié)演繹推理① ②P(B)P(C)n ③ ?P(B)∨ P(B)∨ P(B)星期六 117歸結(jié)演繹推理歸結(jié)演繹推理P(C)p 把要求證的 問(wèn)題否定 ，并用謂詞公式表示出來(lái)： pP(B)如果錄取 B，則一定錄取 C。?pP(A)∨ P(C)n （ 2） pP(A)3）歸結(jié)反演p 把公司的想法用謂詞公式表示如下：n （ 1） 2023/2/27p （ 如果錄取 B，則一定錄取 C。如果錄取 A而不錄取 B，則一定錄取 C。三人中至少錄取一人。星期六 115歸結(jié)演繹推理歸結(jié)演繹推理S（ x， y） ∨ ~S（ x， y） ∨ ~歸結(jié)演繹推理歸結(jié)演繹推理3）歸結(jié)反演 —— 歸結(jié)反演系統(tǒng)2023/2/27M（ y）∨ ~S（ x， y）））（ ~（ ?x） I（ x） ∧ （ ~（ ?x）（ ?y）（ ~3）歸結(jié)反演 —— 歸結(jié)反演系統(tǒng)2023/2/27S（ x， y） ∨ ~S（ x， y） ∨ ~M(y)∨ I(f(x)))∧ (~S(x， y)∨ ~M（ y）） ∨ （ ?y）（ I（ y） ∧ E（ x， y）））p 令 y=f(x)為 Skolem函數(shù)，則得子句形(?x)(?y)((~星期六 112p 把前提化為子句形：(?x)(~(?y)(S(x， y)∧ M(y))∨ (?y)(I(y)∧ E(x，y)))(?y)(I(y)∧ E(x， y)]結(jié)論： ~(?x)I(x)=(?x)(?y)(M(y)=~S(x， y))歸結(jié)演繹推理歸結(jié)演繹推理表示 x獲得 y表示 x是錢(qián)I（ x） p 令： S（ x， y）表示 x儲(chǔ)蓄 y前提：每個(gè)儲(chǔ)蓄錢(qián)的人都獲得利息。星期六 111p 例 3）歸結(jié)反演 —— 歸結(jié)反演系統(tǒng)p 例、歸結(jié)反演的應(yīng)用 —— 食物問(wèn)題p ③ 歸結(jié)演繹 —— 應(yīng)用歸結(jié)演繹方法不斷生成 歸結(jié)式 以擴(kuò)展子句集 S，直到生成 空子句 □ 。2023/2/27星期六 109歸結(jié)演繹推理歸結(jié)演繹推理3）歸結(jié)反演 —— 歸結(jié)反演系統(tǒng)p 例、歸結(jié)反演的應(yīng)用 —— 食物問(wèn)題p ③ 歸結(jié)演繹 —— 應(yīng)用歸結(jié)演繹方法不斷生成 歸結(jié)式 以擴(kuò)展子句集 S，直到生成 空子句 □ 。2023/2/27星期六 107歸結(jié)演繹推理歸結(jié)演繹推理3）歸結(jié)反演 —— 歸結(jié)反演系統(tǒng)p 例、歸結(jié)反演的應(yīng)用 —— 食物問(wèn)題p ③ 歸結(jié)演繹 —— 應(yīng)用歸結(jié)演繹推理不斷生成 歸結(jié)式 以擴(kuò)展子句集 S，直到生成 空子句 □ 。Like(Wang,Peanuts)取反2023/2/27Eat(Zhang,x3)n 王喜歡花生。Eat(Li,x3)?Alive(Li)pEat(Li,Peanuts)pAlive(Li)n 張 (Zhang)吃任何李吃的東西。pEat(Li,Peanuts)3）歸結(jié)反演 —— 歸結(jié)反演系統(tǒng)p 例、歸結(jié)反演的應(yīng)用 —— 食物問(wèn)題p ② 標(biāo)準(zhǔn)化 —— 將事實(shí)公式和 取反后的目標(biāo)公式 分別標(biāo)準(zhǔn)化為子句，并組成字句集 S。Food(x2)2023/2/27Alive(y)∨ Food(x)]p?Alive(y)p(?x)(?y)[Eat(y,x)Like(Wang,x)]p?Food(x1)∨ Like(Wang,x1)n 蘋(píng)果 (Apples)是食物。p(?x)[Food(x)3）歸結(jié)反演 —— 歸結(jié)反演系統(tǒng)p 例、歸結(jié)反演的應(yīng)用 —— 食物問(wèn)題p ② 標(biāo)準(zhǔn)化 —— 將事實(shí)公式和 取反后的目標(biāo)公式 分別標(biāo)準(zhǔn)化為子句，并組成子句集 S。p Like(Wang,Peanuts)減少謂詞數(shù)2023/2/27?Alive(Li)n 張 (Zhang)吃任何李吃的東西。p Eat(Li,Peanuts)?∧ ?∧ p Food(Apples)n 任何一個(gè)東西，若任何人吃了 (Eat)它都不會(huì)被害死 (Killed)，則該東西是食物。?n 王 (Wang)喜歡 (Like)所有種類(lèi)的食物 (Food)。星期六 103歸結(jié)演繹推理歸結(jié)演繹推理p 證明 ：n 王喜歡花生。n 李 (Li)吃花生 (Peanuts)且仍然活著 (Alive)。n 蘋(píng)果 (Apples)是食物。星期六 102歸結(jié)演繹推理歸結(jié)演繹推理p 歸結(jié)反演系統(tǒng) 組成 ：n 標(biāo)準(zhǔn)化部件p將 F∧ ?W標(biāo)準(zhǔn)化為子句，并合并為子句集 S；n 歸結(jié)演繹部件p按照歸結(jié)演繹推理，控制定理證明的全過(guò)程。3）歸結(jié)反演 —— 歸結(jié)反演系統(tǒng)p 歸結(jié)反演的 基本思路 ：n 要從作為事實(shí)的公式集 F證明目標(biāo)公式 W為真；n ① 先將 W取反 ?W2023/2/27星期六 100欲證 F1∧F2∧ … ∧Fn ?W永真，可以通過(guò) F1∧F2∧ … ∧Fn ∧ ?W的永假來(lái)證明。答的綜合題。p 教學(xué)要求教學(xué)要求 ———— 掌握掌握p 主要內(nèi)容主要內(nèi)容n 掌握掌握 歸結(jié)反演方法歸結(jié)反演方法 和和 提取問(wèn)題回答技術(shù)提取問(wèn)題回答技術(shù) ；；n 學(xué)會(huì)建立學(xué)會(huì)建立 歸結(jié)反演樹(shù)歸結(jié)反演樹(shù) 和和 修改證明樹(shù)修改證明樹(shù) 。3）歸結(jié)反演 ★p 歸結(jié)演繹推理 為 反證法證明定理 提供了有效手段。2023/2/27星期六 98歸結(jié)演繹推理歸結(jié)演繹推理2）歸結(jié)原理p 歸結(jié)推理過(guò)程p (3)歸結(jié)演繹的完備性n 基于歸結(jié)的演繹推理是完備的p若子句集 S不可滿(mǎn)足，就必定存在一個(gè)從 S到 空子句 □的歸結(jié)演繹；p反之，若存在一個(gè)從 S到 空子句 □ 的歸結(jié)演繹，則 S必定是不可滿(mǎn)足的；n 歸結(jié)演繹的完備性可用海伯倫定理進(jìn)行證明，因此歸結(jié)原理是建立在海伯倫定理之上的。星期六 96歸結(jié)演繹推理歸結(jié)演繹推理2）歸結(jié)原理p 歸結(jié)推理過(guò)程p (2)謂詞邏輯中的歸結(jié)推理過(guò)程2023/2/27星期六 94歸結(jié)演繹推理歸結(jié)演繹推理2）歸結(jié)原理p 歸結(jié)推理過(guò)程p (2)謂詞邏輯中的歸結(jié)推理過(guò)程2023/2/27星期六 93置換和合一實(shí)例 3求公式集F={P(a， x， f(g(y)))， P(z， h(z， u)， f(u))}的合一。?R(z,f(z))n L11=P(x,y)和 L12=?Q(z,f(z))R(x,f(y))pC2=?P(A,B)Q(x,f(x))pC1=P(x,y)?R(z,f(z))2023/2/27?P(A,B)R(z,f(y))?R(z,f(z))n L21=Q(x,f(x))和 L22=?Q(z,f(z))是潛在的互補(bǔ)文字pL21和 L22是 可合一 的；p建立置換 S2={z/x}p消去互補(bǔ)文字 L21和 L22后，得歸結(jié)式：P(z,y)?Q(z,f(z))R(x,f(y))pC2=?P(A,B)Q(x,f(x))pC1=P(x,y)?R(z,f(z))p變量的置換必須在整個(gè)子句范圍內(nèi)進(jìn)行2023/2/27∨ ?Q(z,f(z))∨ ?R(z,f(z))n L11=P(x,y)和 L12=?Q(z,f(z))R(x,f(y))pC2=?P(A,B)Q(x,f(x))pC1=P(x,y)2023/2/27B/y,x出現(xiàn)過(guò) ，已經(jīng)建立置換元素 A/x，可合一；pg(x)和 z， z初次出現(xiàn) ，可合一，建立置換元素 g(x)/z；n ③ 若每對(duì)參數(shù)項(xiàng)都可合一，則 合一處理成功 。py和和 B， y初次出現(xiàn) ，可合一，建立置換元素 B/y。A,?P(A,x,星期六 89歸結(jié)演繹推理歸結(jié)演繹推理2）歸結(jié)原理 置換和合一p 歸結(jié)推理過(guò)程p (2)謂詞邏輯中的歸結(jié)推理過(guò)程n 匹配過(guò)程的例子n P(x,nv出現(xiàn)過(guò) ，則已建立相應(yīng)的置換元素，就取其置換項(xiàng)，代替該變量，檢查是否與另一參數(shù)同一；若不同一，則處理失??；p參數(shù)對(duì)中沒(méi)有變量，則必須相同，否則合一處理失敗。2023/2/27n 【 匹配過(guò)程 】 z)2023/2/27B,g(x)),y,p置換元素 —— t/v（ 置換項(xiàng) /變量 ）p置換 —— 若干 置換元素 的集合；n 合一處理：p通過(guò)多個(gè) 變量置換 ，使相應(yīng)于 潛在 互補(bǔ)文字的原子謂詞公式 同一化 的過(guò)程。星期六 86歸結(jié)演繹推理歸結(jié)演繹推理2）歸結(jié)原理 置換和合一p 歸結(jié)推理過(guò)程p (2)謂詞邏輯中的歸結(jié)推理過(guò)程n 子句 中 含有變量 ， 不能直接發(fā)現(xiàn)和消去互補(bǔ)文字 ；n 需對(duì) 潛在 的互補(bǔ)文字先作 變量置換 和 合一處理。 L表示一表達(dá)式，則有 （ Ls1） s2=L（ s1s2） （ s1s2） s3=s1（ s2s3）置換是不可交換的。星期六 85置換和合一實(shí)例 2置換是可結(jié)合的。2023/2/27A,?P(A,x,星期六 83　　　　P(x,A,?P(A,x,p置換元素 —— t/v（ 置換項(xiàng) /變量 ）p置換 —— 若干 置換元素 的集合；n 合一處理：P(x,星期六 82歸結(jié)演繹推理歸結(jié)演繹推理2）歸結(jié)原理 置換和合一 ★p 歸結(jié)推理過(guò)程p (2)謂詞邏輯中的歸結(jié)推理過(guò)程n 子句 中 含有變量 ， 不能直接發(fā)現(xiàn)和消去互補(bǔ)文字 ；n 需對(duì) 潛在 的互補(bǔ)文字先作 變量置換 和 合一處理。?R}的歸結(jié)演繹樹(shù)。P∨ R,2023/2/27?Q,星期六 80歸結(jié)演繹推理歸結(jié)演繹推理2）歸結(jié)原理p 歸結(jié)推理過(guò)程 —— 歸結(jié)演繹樹(shù)p (1)命題邏輯中的歸結(jié)推理過(guò)程n 子句 中 文字 只是原子命題公式或其取反， 不帶變量 ；n 易于判別哪些 子句 對(duì)包含 互補(bǔ)文字 ；n 例、子句集 S={?P∨ Q,p 基本思路 ★n 通過(guò) 歸結(jié)方法 不斷 擴(kuò)充 待判定的 子句集 S，并設(shè)法使其 包含進(jìn)指示矛盾的 空子句 。星期六 79歸結(jié)演繹推理歸結(jié)演繹推理2）歸結(jié)原理p 動(dòng)機(jī)n 為提高判定子句集 S不可滿(mǎn)足的有效性 ，魯賓遜于 1965年提出了 歸結(jié) (Resolution)原理 ，也稱(chēng)為 消解原理 。星期六 77(3) 重言式父輩子句 P∨ Q ~P∨ ~ Q消解式 Q ∨ ~ QC1=P∨ Q,C2=~P∨ ~Q父輩子句 P∨ Q ~P∨ ~ Q消解式 P ∨ ~ P或者2023/2/27歸結(jié)后的擴(kuò)展子句集 S’子句集 S不可滿(mǎn)足性等價(jià)2023/2/27星期六 75歸結(jié)演繹推理歸結(jié)演繹推理2）歸結(jié)原理p 歸結(jié)方法p (3)空子句n 設(shè) C1=L、 和 C2R(y)C1’ C2’2023/2/27Q(y)R(f(x))Q(x)C2=?L∨ C2’p① 從 C1和 C2中 消去互補(bǔ)文字 L和 ?L；p② C1’和 C2’通過(guò) ∨ 組成新的子句C=C1’∨ 2023/2/27星期六 72歸結(jié)演繹推理歸結(jié)演繹推理2）歸結(jié)原理 ★p 動(dòng)機(jī)n 為提高判定子句集 S不可滿(mǎn)足的有效性 ，魯賓遜于 1965年提出了 歸結(jié) (Resolution)原理 ，也稱(chēng)為 消解原理 。n 海伯倫定理 ：p子句集 S不可滿(mǎn)足的 充要條件 是存在一個(gè)有限的不可滿(mǎn)足的基子句集 S’。2023/2/27n H域性質(zhì) —— 對(duì)于子句集 S的任一可能論域 D上的任一解釋 I，總能在 S的 H域 上構(gòu)造一個(gè)相應(yīng)的解釋 I*，使子句集 S具有相同的真值。星期六 70歸結(jié)演繹推理歸結(jié)演繹推理1） H域和海伯倫定理p H域 （了解）n