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