西電人工智能12確定性推理part5

1、西安電子科技大學(xué)西安電子科技大學(xué)Artificial Intelligence (AI)人工智能人工智能主講：戚玉濤Email：qi_第三章：確定性推理西安電子科技大學(xué)西安電子科技大學(xué)內(nèi)容提要1.1.推理的基本概念推理的基本概念2.2.搜索策略搜索策略3.3.自然演繹推理自然演繹推理4.4.歸結(jié)演繹推理歸結(jié)演繹推理5.5.基于規(guī)則的演繹推理基于規(guī)則的演繹推理西安電子科技大學(xué)西安電子科技大學(xué)自然演繹推理從一組已知為真的事實(shí)出發(fā)，直從一組已知為真的事實(shí)出發(fā)，直接運(yùn)用經(jīng)典邏輯中的推理規(guī)則推出結(jié)論的過(guò)程稱接運(yùn)用經(jīng)典邏輯中的推理規(guī)則推出結(jié)論的過(guò)程稱為自然演繹推理。為自然演繹推理。假言推理假言推理 拒取式

2、拒取式假言三段論假言三段論西安電子科技大學(xué)西安電子科技大學(xué)自然演繹推理 P, PQ Q表示：表示：由由PQ 以及以及P為真，可以推出為真，可以推出Q為真為真例如：例如：由由“如果如果x是金屬，則是金屬，則x能導(dǎo)電能導(dǎo)電”，以及，以及“銅是銅是金屬金屬”，可以推出，可以推出“銅能導(dǎo)電銅能導(dǎo)電”。PQ, Q P表示：表示：由由PQ 為真以及為真以及Q為假，可以推出為假，可以推出P為假為假例如：例如：由由“如果下雨，則地上會(huì)濕如果下雨，則地上會(huì)濕”，以及，以及“地上不地上不濕濕”，可以推出，可以推出“沒(méi)有下雨沒(méi)有下雨”。PQ, QR PR西安電子科技大學(xué)西安電子科技大學(xué)自然演繹推理當(dāng)當(dāng)PQ為真時(shí)，希

3、望通過(guò)肯定后為真時(shí)，希望通過(guò)肯定后件件Q為真來(lái)推出前件為真來(lái)推出前件P為真，這是不允許的。為真，這是不允許的。p例如：例如：伽利略在論證哥白尼的日心說(shuō)時(shí)，曾使用了伽利略在論證哥白尼的日心說(shuō)時(shí)，曾使用了如下推理：如下推理：(1)如果行星系統(tǒng)是以太陽(yáng)為中心的，則金星會(huì)顯示如果行星系統(tǒng)是以太陽(yáng)為中心的，則金星會(huì)顯示出位相變化；出位相變化；(2)金星顯示出位相變化；金星顯示出位相變化；(3)所有，行星系統(tǒng)是以太陽(yáng)為中心的所有，行星系統(tǒng)是以太陽(yáng)為中心的p這就是使用了肯定后件的推理，違反了經(jīng)典邏輯的這就是使用了肯定后件的推理，違反了經(jīng)典邏輯的邏輯規(guī)則。邏輯規(guī)則。西安電子科技大學(xué)西安電子科技大學(xué)自然演繹推理

4、當(dāng)當(dāng)PQ為真時(shí)，希望通過(guò)否定前為真時(shí)，希望通過(guò)否定前件件P來(lái)推出后件來(lái)推出后件Q為假，這也是不允許的。為假，這也是不允許的。p例如：例如：(1)如果下雨，則地上會(huì)濕如果下雨，則地上會(huì)濕(2)沒(méi)有下雨沒(méi)有下雨(3)所有，地上不濕所有，地上不濕p事實(shí)上，如果向地上灑水，地上也是會(huì)濕的。這就事實(shí)上，如果向地上灑水，地上也是會(huì)濕的。這就是使用了否定前件的推理，違反了經(jīng)典邏輯的邏輯是使用了否定前件的推理，違反了經(jīng)典邏輯的邏輯規(guī)則。規(guī)則。西安電子科技大學(xué)西安電子科技大學(xué)自然演繹推理A, B, AC, BCD, DQQ為真。為真。p因?yàn)橐驗(yàn)?A, AC C 假言推理假言推理pB, C BC 引入合取詞引入合

5、取詞pBC，BCD D 假言推理假言推理pD, DQ Q 假言推理假言推理p因此，因此，Q為真為真西安電子科技大學(xué)西安電子科技大學(xué)自然演繹推理 (1) 只要是需要編程序的課，王程都喜歡。只要是需要編程序的課，王程都喜歡。 (2) 所有的程序設(shè)計(jì)語(yǔ)言課都是需要編程序的課。所有的程序設(shè)計(jì)語(yǔ)言課都是需要編程序的課。 (3) C是一門(mén)程序設(shè)計(jì)語(yǔ)言課。是一門(mén)程序設(shè)計(jì)語(yǔ)言課。王程喜歡王程喜歡C C這門(mén)課。這門(mén)課。首先定義謂詞首先定義謂詞 Prog(x)：x是需要編程序的課。是需要編程序的課。 Like(x, y): x喜歡喜歡y。 Lang(x): x是一門(mén)程序設(shè)計(jì)語(yǔ)言課是一門(mén)程序設(shè)計(jì)語(yǔ)言課西安電子科技大

6、學(xué)西安電子科技大學(xué)自然演繹推理把已知事實(shí)及待求解問(wèn)題用謂詞公式表示如下：把已知事實(shí)及待求解問(wèn)題用謂詞公式表示如下： Prog(x)Like(Wang , x) (x)( Lang(x)Prog(x) Lang(C)應(yīng)用推理規(guī)則進(jìn)行推理：應(yīng)用推理規(guī)則進(jìn)行推理： Lang(y)Prog(y) 全稱固化全稱固化 Lang(C)，Lang(y)Prog(y) Prog(C) 假言推理假言推理 C/y Prog(C), Prog(x)Like(Wang , x) Like(Wang , C) 假假言推理言推理 C/x因此，王程喜歡因此，王程喜歡C這門(mén)課。這門(mén)課。西安電子科技大學(xué)西安電子科技大學(xué)自然演繹推

7、理定理證明過(guò)程自然，易于理解，并且有定理證明過(guò)程自然，易于理解，并且有豐富的推理規(guī)則可用。豐富的推理規(guī)則可用。是容易產(chǎn)生知識(shí)爆炸，推理過(guò)程中得到是容易產(chǎn)生知識(shí)爆炸，推理過(guò)程中得到的中間結(jié)論一般按指數(shù)規(guī)律遞增，對(duì)于復(fù)雜問(wèn)的中間結(jié)論一般按指數(shù)規(guī)律遞增，對(duì)于復(fù)雜問(wèn)題的推理不利，甚至難以實(shí)現(xiàn)。題的推理不利，甚至難以實(shí)現(xiàn)。西安電子科技大學(xué)西安電子科技大學(xué)內(nèi)容提要1.1.推理的基本概念推理的基本概念2.2.搜索策略搜索策略3.3.自然演繹推理自然演繹推理4.4.歸結(jié)演繹推理歸結(jié)演繹推理5.5.基于規(guī)則的演繹推理基于規(guī)則的演繹推理西安電子科技大學(xué)西安電子科技大學(xué)歸結(jié)演繹推理是一種基于魯濱遜（是一種基于魯濱遜

8、（Robinson）歸結(jié)原理的機(jī)器推理技術(shù)。歸結(jié)原理的機(jī)器推理技術(shù)。魯濱遜歸結(jié)原理亦稱為魯濱遜歸結(jié)原理亦稱為消解原理消解原理，是魯濱遜于，是魯濱遜于1965年在年在海伯倫（海伯倫（Herbrand）理論的基礎(chǔ)上提出的一種基于邏）理論的基礎(chǔ)上提出的一種基于邏輯的輯的“反證法反證法”。在人工智能中，幾乎所有的問(wèn)題都可以轉(zhuǎn)化為一個(gè)定理在人工智能中，幾乎所有的問(wèn)題都可以轉(zhuǎn)化為一個(gè)定理證明問(wèn)題。定理證明的實(shí)質(zhì)，就是要對(duì)前提證明問(wèn)題。定理證明的實(shí)質(zhì)，就是要對(duì)前提P和結(jié)論和結(jié)論Q，證明證明PQ永真。永真。要證明要證明PQ永真，就是要證明永真，就是要證明PQ在任何一個(gè)非空的在任何一個(gè)非空的個(gè)體域上都是永真的。

9、這將是非常困難的，甚至是不可個(gè)體域上都是永真的。這將是非常困難的，甚至是不可實(shí)現(xiàn)的。實(shí)現(xiàn)的。西安電子科技大學(xué)西安電子科技大學(xué)歸結(jié)演繹推理魯濱遜歸結(jié)原理把永真性的證明轉(zhuǎn)化為關(guān)于不可滿足魯濱遜歸結(jié)原理把永真性的證明轉(zhuǎn)化為關(guān)于不可滿足性的證明。性的證明。要證明要證明PQ永真永真，只需證明，只需證明PQ不可滿足不可滿足p因?yàn)椋阂驗(yàn)椋?(PQ) ( PQ) P Q海伯倫海伯倫(Herbrand)定理為自動(dòng)定理證明奠定了理論基礎(chǔ)。定理為自動(dòng)定理證明奠定了理論基礎(chǔ)。魯濱遜魯濱遜(Robinson)提出的歸結(jié)原理使機(jī)器定理證明成為提出的歸結(jié)原理使機(jī)器定理證明成為現(xiàn)實(shí)?，F(xiàn)實(shí)。西安電子科技大學(xué)西安電子科技大學(xué)歸結(jié)

10、演繹推理子句集及其化簡(jiǎn)子句集及其化簡(jiǎn)魯濱遜歸結(jié)原理魯濱遜歸結(jié)原理歸結(jié)反演推理的歸結(jié)策略歸結(jié)反演推理的歸結(jié)策略用歸結(jié)反演求取問(wèn)題的答案用歸結(jié)反演求取問(wèn)題的答案西安電子科技大學(xué)西安電子科技大學(xué)歸結(jié)演繹推理子句集及其化簡(jiǎn)子句集及其化簡(jiǎn)魯濱遜歸結(jié)原理魯濱遜歸結(jié)原理歸結(jié)反演推理的歸結(jié)策略歸結(jié)反演推理的歸結(jié)策略用歸結(jié)反演求取問(wèn)題的答案用歸結(jié)反演求取問(wèn)題的答案西安電子科技大學(xué)西安電子科技大學(xué)子句集及其化簡(jiǎn)v無(wú)論是海伯倫理論，還是魯濱遜歸結(jié)原理是在無(wú)論是海伯倫理論，還是魯濱遜歸結(jié)原理是在子子句集句集的基礎(chǔ)上討論問(wèn)題的。因此，討論歸結(jié)演繹的基礎(chǔ)上討論問(wèn)題的。因此，討論歸結(jié)演繹推理之前，需要先討論子句集的有關(guān)概念

11、。推理之前，需要先討論子句集的有關(guān)概念。原子謂詞公式及其否定統(tǒng)稱為原子謂詞公式及其否定統(tǒng)稱為文字文字。p例如例如: P(x)、Q(x)、 P(x)、 Q(x)等都是文字。等都是文字。任何任何文字文字的的析取式析取式稱為稱為子句子句。p例如，例如，P(x)Q(x)，P(x，f(x)Q(x，g(x)都是子都是子句。句。西安電子科技大學(xué)西安電子科技大學(xué)子句集及其化簡(jiǎn)不含任何文字的子句稱為不含任何文字的子句稱為空子句空子句。p由于空子句不含有任何文字，也就不能被任何解釋由于空子句不含有任何文字，也就不能被任何解釋所滿足，因此空子句是所滿足，因此空子句是永假的永假的，不可滿足的不可滿足的。p空子句一般被

12、記為空子句一般被記為NIL。由子句或空子句所構(gòu)成的集合稱為由子句或空子句所構(gòu)成的集合稱為子句集子句集。p在子句集中，子句之間是在子句集中，子句之間是合取關(guān)系合取關(guān)系p子句集中的子句集中的變?cè)苋Q量詞的約束變?cè)苋Q量詞的約束p任何謂詞公式都可通過(guò)等價(jià)關(guān)系及推理規(guī)則化為相任何謂詞公式都可通過(guò)等價(jià)關(guān)系及推理規(guī)則化為相應(yīng)的子句集應(yīng)的子句集西安電子科技大學(xué)西安電子科技大學(xué)子句集及其化簡(jiǎn)1： 利用等價(jià)關(guān)系消去利用等價(jià)關(guān)系消去“”和和“”p反復(fù)使用如下等價(jià)公式：反復(fù)使用如下等價(jià)公式： PQ PQ PQ (PQ)(PQ) 即可消去謂詞公式中的連接詞即可消去謂詞公式中的連接詞“”和和“”。p例如：例如： (

13、x)(y)P(x,y) (y)(Q(x,y)R(x,y) 經(jīng)等價(jià)變化后為：經(jīng)等價(jià)變化后為： (x)(y)P(x,y) (y)(Q(x,y)R(x,y)西安電子科技大學(xué)西安電子科技大學(xué)子句集及其化簡(jiǎn)2：利用等價(jià)關(guān)系把利用等價(jià)關(guān)系把“”移到緊靠謂詞的位置上移到緊靠謂詞的位置上p反復(fù)使用反復(fù)使用 雙重否定率：雙重否定率：(P) P 摩根定律：摩根定律： (PQ) PQ (PQ) PQ 量詞轉(zhuǎn)換率：量詞轉(zhuǎn)換率： (x)P(x) (x) P(x) (x)P(x) (x) P(x) 使得每個(gè)否定符號(hào)最多只作用于一個(gè)謂詞上。使得每個(gè)否定符號(hào)最多只作用于一個(gè)謂詞上。p例如：例如：上式經(jīng)等價(jià)變換后為上式經(jīng)等價(jià)變

14、換后為 (x)(y)P(x，y)(y)( Q(x，y) R(x，y)西安電子科技大學(xué)西安電子科技大學(xué)子句集及其化簡(jiǎn)3：重新命名變?cè)?，使不同量詞約束的變?cè)胁煌匦旅冊(cè)?，使不同量詞約束的變?cè)胁煌拿值拿謕例如：例如：上式經(jīng)重新命名變換后為上式經(jīng)重新命名變換后為 (x)(y)P(x，y)(z)( Q(x，z) R(x，z)消去存在量詞。消去存在量詞。消去存在量詞時(shí)，需要區(qū)分以消去存在量詞時(shí)，需要區(qū)分以下兩種情況：下兩種情況：p1）存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)，只要用一）存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)，只要用一個(gè)新的個(gè)體常量替換受該存在量詞約束的變?cè)?，就個(gè)新的個(gè)體常量替換受該存在量詞

15、約束的變?cè)涂上ピ摯嬖诹吭~?？上ピ摯嬖诹吭~。p2）存在量詞位于一個(gè)或者多個(gè)全稱量詞的轄域內(nèi)）存在量詞位于一個(gè)或者多個(gè)全稱量詞的轄域內(nèi)西安電子科技大學(xué)西安電子科技大學(xué)子句集及其化簡(jiǎn) 如下面的謂詞公式：如下面的謂詞公式： (x1)(xn) (y)P(x1，x2 , xn ,y) 則需要用則需要用Skolem函數(shù)函數(shù)f(x1，x2 , xn)替換受該存在量替換受該存在量詞約束的變?cè)~約束的變?cè)獃，然后再消去該存在量詞。，然后再消去該存在量詞。p例如：例如：繼續(xù)上面的例子繼續(xù)上面的例子 (x)(y)P(x，y)(z)( Q(x，z) R(x，z) 式子中存在量詞式子中存在量詞( y)及及( z)

16、都位于都位于( x)的轄域內(nèi)，所的轄域內(nèi)，所以需要用以需要用Skolem函數(shù)替換，設(shè)替換函數(shù)替換，設(shè)替換y和和z的的Skolem函函數(shù)分別是數(shù)分別是f(x)和和g(x)，則替換后得到：，則替換后得到： (x)(P(x , f(x)(Q(x , g(x)R(x , g(x)西安電子科技大學(xué)西安電子科技大學(xué)子句集及其化簡(jiǎn)把全稱量詞全部移到公式的左邊把全稱量詞全部移到公式的左邊p上式中由于只有一個(gè)全稱量詞，而且它位于公式的上式中由于只有一個(gè)全稱量詞，而且它位于公式的最左邊，所以這里不需要做任何工作。最左邊，所以這里不需要做任何工作。p如果在公式內(nèi)部有全稱量詞，就需要把它們都移到如果在公式內(nèi)部有全稱量

17、詞，就需要把它們都移到公式的左邊。公式的左邊。利用等價(jià)關(guān)系利用等價(jià)關(guān)系 P (QR) (PQ) (PR) 把公式化為把公式化為Skolem標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形pSkolem標(biāo)準(zhǔn)形的一般形式為標(biāo)準(zhǔn)形的一般形式為 (x1)(xn) M(x1,x2,xn)p其中，其中， M(x1,x2,xn)是是Skolem標(biāo)準(zhǔn)形的母式，它標(biāo)準(zhǔn)形的母式，它由子句的由子句的合取合取所構(gòu)成。所構(gòu)成。西安電子科技大學(xué)西安電子科技大學(xué)子句集及其化簡(jiǎn)pSkolem標(biāo)準(zhǔn)形的一般形式為標(biāo)準(zhǔn)形的一般形式為(x1)(xn) M(x1,x2,xn)p其中，其中， M(x1,x2,xn)是是Skolem標(biāo)準(zhǔn)形的母式，它標(biāo)準(zhǔn)形的母式，它由子句的合

18、取所構(gòu)成。由子句的合取所構(gòu)成。p例如：例如：前面的公式化為前面的公式化為Skolem標(biāo)準(zhǔn)形后為標(biāo)準(zhǔn)形后為 (x)( (P(x , f(x)Q(x , g(x) (P(x , f(x) R(x , g(x) )消去全稱量詞。由于母式中的全部變?cè)苋トQ量詞。由于母式中的全部變?cè)苋Q量詞的約束，并且全稱量詞的次序已無(wú)關(guān)緊要，因稱量詞的約束，并且全稱量詞的次序已無(wú)關(guān)緊要，因此可以省掉全稱量詞。此可以省掉全稱量詞。p例如：例如：上式消去全稱量詞后為上式消去全稱量詞后為 (P(x , f(x)Q(x , g(x) (P(x , f(x)R(x , g(x)西安電子科技大學(xué)西安電子科技大學(xué)子句集

19、及其化簡(jiǎn)對(duì)變?cè)?，?duì)變?cè)?，使不同子句中的變?cè)煌共煌泳渲械淖冊(cè)煌鹥由于每一個(gè)子句都對(duì)應(yīng)著母式中的一個(gè)合取元，并由于每一個(gè)子句都對(duì)應(yīng)著母式中的一個(gè)合取元，并且所有變?cè)际怯扇Q量詞量化的，因此且所有變?cè)际怯扇Q量詞量化的，因此任意兩個(gè)任意兩個(gè)不同子句的變量之間實(shí)際上不存在任何關(guān)系，更換不同子句的變量之間實(shí)際上不存在任何關(guān)系，更換變量名不會(huì)影響公式的真值。變量名不會(huì)影響公式的真值。p例如：例如：上式經(jīng)更名后得到上式經(jīng)更名后得到 (P(x , f(x)Q(x , g(x) (P(y , f(y)R(y , g(y)消去合取詞，就得到消去合取詞，就得到子句集子句集。p例如：例如：消去

20、合取詞后，上式就變?yōu)橄率鲎泳浼ズ先≡~后，上式就變?yōu)橄率鲎泳浼疨(x , f(x)Q(x , g(x)P(y , f(y)R(y , g(y)西安電子科技大學(xué)西安電子科技大學(xué)子句集及其化簡(jiǎn)在上述化簡(jiǎn)過(guò)程中，由于在消去存在量詞時(shí)所用的在上述化簡(jiǎn)過(guò)程中，由于在消去存在量詞時(shí)所用的Skolem函數(shù)可以不同，因此函數(shù)可以不同，因此化簡(jiǎn)后的標(biāo)準(zhǔn)子句集是不化簡(jiǎn)后的標(biāo)準(zhǔn)子句集是不唯一的唯一的。因此，當(dāng)原謂詞公式為因此，當(dāng)原謂詞公式為非永假非永假時(shí)，它與其標(biāo)準(zhǔn)子句集時(shí)，它與其標(biāo)準(zhǔn)子句集并不等價(jià)。但當(dāng)原謂詞公式為永假（或不可滿足）時(shí)，并不等價(jià)。但當(dāng)原謂詞公式為永假（或不可滿足）時(shí)，其標(biāo)準(zhǔn)子句集則一定是永假的，

21、其標(biāo)準(zhǔn)子句集則一定是永假的，即即Skolem化并不影響化并不影響原謂詞公式的永假性原謂詞公式的永假性。對(duì)于對(duì)于任意論域中的任意一個(gè)解任意論域中的任意一個(gè)解釋釋?zhuān)琒中的子句不能同時(shí)取得真值中的子句不能同時(shí)取得真值T。西安電子科技大學(xué)西安電子科技大學(xué)子句集及其化簡(jiǎn)設(shè)有謂詞公式設(shè)有謂詞公式F，其子句集為，其子句集為S，則，則F不可不可滿足的充要條件是滿足的充要條件是S不可滿足不可滿足。由此定理可知，要證明一個(gè)謂詞公式是不可滿足的，由此定理可知，要證明一個(gè)謂詞公式是不可滿足的，只要證明其相應(yīng)的標(biāo)準(zhǔn)子句集是不可滿足的就可以了。只要證明其相應(yīng)的標(biāo)準(zhǔn)子句集是不可滿足的就可以了。由于子句集中的子句之間是合取關(guān)

22、系，子句集中只要由于子句集中的子句之間是合取關(guān)系，子句集中只要有一個(gè)子句為不可滿足，則整個(gè)子句集就是不可滿足有一個(gè)子句為不可滿足，則整個(gè)子句集就是不可滿足的。的?？兆泳涫遣豢蓾M足的。因此，一個(gè)子句集中如果包含空子句是不可滿足的。因此，一個(gè)子句集中如果包含有空子句，則此子句集就一定是不可滿足的。有空子句，則此子句集就一定是不可滿足的。這個(gè)結(jié)論是這個(gè)結(jié)論是魯濱遜歸結(jié)原理的主要依據(jù)。魯濱遜歸結(jié)原理的主要依據(jù)。西安電子科技大學(xué)西安電子科技大學(xué)歸結(jié)演繹推理子句集及其化簡(jiǎn)子句集及其化簡(jiǎn)魯濱遜歸結(jié)原理魯濱遜歸結(jié)原理歸結(jié)反演推理的歸結(jié)策略歸結(jié)反演推理的歸結(jié)策略用歸結(jié)反演求取問(wèn)題的答案用歸結(jié)反演求取問(wèn)題的答案西

23、安電子科技大學(xué)西安電子科技大學(xué)魯濱遜歸結(jié)原理 為了判斷子句集的不可滿足性，需要對(duì)所有可能論域上的所為了判斷子句集的不可滿足性，需要對(duì)所有可能論域上的所有解釋進(jìn)行判定。只有當(dāng)子句集對(duì)有解釋進(jìn)行判定。只有當(dāng)子句集對(duì)任何非空個(gè)體域任何非空個(gè)體域上的上的任何任何一個(gè)解釋一個(gè)解釋都是不可滿足的，才可斷定該子句集不可滿足。都是不可滿足的，才可斷定該子句集不可滿足。 海伯倫構(gòu)造了一個(gè)特殊的論域（海伯倫構(gòu)造了一個(gè)特殊的論域（海伯倫域海伯倫域），并證明），并證明只要對(duì)只要對(duì)這個(gè)特殊域上的一切解釋進(jìn)行判定，就可知子句集是否不可這個(gè)特殊域上的一切解釋進(jìn)行判定，就可知子句集是否不可滿足滿足。 海伯倫定理：海伯倫定理：

24、子句集不可滿足的子句集不可滿足的充要條件充要條件是是存在一個(gè)有限的存在一個(gè)有限的不可滿足的基子句集不可滿足的基子句集。 海伯倫從理論上給出了證明子句集不可滿足性的可行性及方海伯倫從理論上給出了證明子句集不可滿足性的可行性及方法，但是要在計(jì)算機(jī)上實(shí)現(xiàn)是很困難的。法，但是要在計(jì)算機(jī)上實(shí)現(xiàn)是很困難的。西安電子科技大學(xué)西安電子科技大學(xué)魯濱遜歸結(jié)原理首先把欲證明問(wèn)題的結(jié)論首先把欲證明問(wèn)題的結(jié)論否定否定，并加入子句集，得到，并加入子句集，得到一個(gè)擴(kuò)充的子句集一個(gè)擴(kuò)充的子句集S；然后設(shè)法檢驗(yàn)子句集然后設(shè)法檢驗(yàn)子句集S是否含有空子句，若含有空子句，是否含有空子句，若含有空子句，則表明則表明S是不可滿足的；若不

25、含有空子句，則繼續(xù)使用是不可滿足的；若不含有空子句，則繼續(xù)使用歸結(jié)法，在子句集中選擇合適的子句進(jìn)行歸結(jié)，歸結(jié)法，在子句集中選擇合適的子句進(jìn)行歸結(jié)，直至直至導(dǎo)出空子句或不能繼續(xù)歸結(jié)為止導(dǎo)出空子句或不能繼續(xù)歸結(jié)為止。命題邏輯命題邏輯消解原理消解原理謂詞邏輯謂詞邏輯消解原理消解原理西安電子科技大學(xué)西安電子科技大學(xué)命題邏輯的歸結(jié)v歸結(jié)推理的核心是求兩個(gè)子句的歸結(jié)推理的核心是求兩個(gè)子句的歸結(jié)式歸結(jié)式若若P是原子謂詞公式，則稱是原子謂詞公式，則稱P與與P為為互補(bǔ)文字互補(bǔ)文字設(shè)設(shè)C1和和C2是子句集中的任意兩個(gè)子句，如果是子句集中的任意兩個(gè)子句，如果C1中的中的文字文字L1與與C2中的中的文字文字L2互補(bǔ)互

26、補(bǔ)，那么可從，那么可從C1和和C2中中分別消去分別消去L1和和L2，并將，并將C1和和C2中中余下的余下的部分按析取關(guān)系構(gòu)成一個(gè)新的子句部分按析取關(guān)系構(gòu)成一個(gè)新的子句C12，則稱這，則稱這一過(guò)程為一過(guò)程為歸結(jié)歸結(jié)，稱，稱C12為為C1和和C2的的歸結(jié)式歸結(jié)式，稱，稱C1和和C2為為C12的的親本子句親本子句。西安電子科技大學(xué)西安電子科技大學(xué)命題邏輯的歸結(jié)設(shè)設(shè)C1=PQR，C2=PS，求，求C1和和C2的歸的歸結(jié)式結(jié)式C12。解：解：這里這里L(fēng)1=P，L2=P，通過(guò)歸結(jié)可以得到，通過(guò)歸結(jié)可以得到p C12= QRS設(shè)設(shè)C1=Q，C2=Q，求，求C1和和C2的歸結(jié)式的歸結(jié)式C12。解：解：這里這里

27、L1=Q，L2=Q，通過(guò)歸結(jié)可以得到，通過(guò)歸結(jié)可以得到p C12= NIL西安電子科技大學(xué)西安電子科技大學(xué)命題邏輯的歸結(jié)設(shè)設(shè)設(shè)設(shè)C1 =P Q ，C2=Q，C3=P，求，求C1、C2、C3的歸結(jié)式的歸結(jié)式C123。解：若先對(duì)解：若先對(duì)C1、C2歸結(jié)，可得到歸結(jié)，可得到p C12=P然后再對(duì)然后再對(duì)C12和和C3歸結(jié)，得到歸結(jié)，得到p C123=NIL如果改變歸結(jié)順序，同樣可以得到如果改變歸結(jié)順序，同樣可以得到相同的結(jié)果，即其歸結(jié)過(guò)程是不唯相同的結(jié)果，即其歸結(jié)過(guò)程是不唯一的。一的。其歸結(jié)歸結(jié)過(guò)程可用右圖來(lái)表示，其歸結(jié)歸結(jié)過(guò)程可用右圖來(lái)表示，該樹(shù)稱為該樹(shù)稱為歸結(jié)樹(shù)歸結(jié)樹(shù)。P QQP P NILP

28、Q P QQ NIL西安電子科技大學(xué)西安電子科技大學(xué)命題邏輯的歸結(jié)v定理：定理：歸結(jié)式歸結(jié)式C12是其親本子句是其親本子句C1和和C2的邏輯結(jié)論。的邏輯結(jié)論。v證明：證明：設(shè)設(shè)C1=LC1 ，C2=LC2關(guān)于解釋關(guān)于解釋I為真，則為真，則只需證明只需證明C12= C1 C2關(guān)于解釋關(guān)于解釋I也為真。也為真。對(duì)于解釋對(duì)于解釋I，L和和L中必有一個(gè)為假。中必有一個(gè)為假。若若L為假為假，則必有，則必有C1為真，不然就會(huì)使為真，不然就會(huì)使C1為假，這將為假，這將與前提假設(shè)與前提假設(shè)C1為真矛盾，因此只能有為真矛盾，因此只能有C1為真。為真。同理，同理，若若L為假為假，則必有，則必有C2為真。為真。因此

29、，必有因此，必有C12= C1C2關(guān)于解釋關(guān)于解釋I也為真。即也為真。即C12是是C1和和C2的邏輯結(jié)論。的邏輯結(jié)論。西安電子科技大學(xué)西安電子科技大學(xué)命題邏輯的歸結(jié)v推論推論1：設(shè)設(shè)C1和和C2是子句集是子句集S中的兩個(gè)子句，中的兩個(gè)子句，C12是是C1和和C2的歸結(jié)式，若的歸結(jié)式，若用用C12代替代替C1和和C2后得到新的子句后得到新的子句集集S1，則由，則由S1的不可滿足性可以推出原子句集的不可滿足性可以推出原子句集S的不可的不可滿足性。即：滿足性。即： S1的不可滿足性的不可滿足性S的不可滿足性的不可滿足性v推論推論2：設(shè)設(shè)C1和和C2是子句集是子句集S中的兩個(gè)子句，中的兩個(gè)子句，C12

30、是是C1和和C2的歸結(jié)式，若的歸結(jié)式，若把把C12加入加入S中得到新的子句集中得到新的子句集S2，則則S與與S2的不可滿足性是等價(jià)的。即：的不可滿足性是等價(jià)的。即： S2的不可滿足性的不可滿足性S的不可滿足性的不可滿足性西安電子科技大學(xué)西安電子科技大學(xué)命題邏輯的歸結(jié)v上述兩個(gè)推論說(shuō)明，為證明子句集上述兩個(gè)推論說(shuō)明，為證明子句集S的不可滿足性，的不可滿足性，只要對(duì)其中可進(jìn)行歸結(jié)得子句進(jìn)行歸結(jié)，只要對(duì)其中可進(jìn)行歸結(jié)得子句進(jìn)行歸結(jié)，并把歸并把歸結(jié)式加入到子句集結(jié)式加入到子句集S中，或者用歸結(jié)式代替他的親中，或者用歸結(jié)式代替他的親本子句本子句，然后對(duì)新的子句集證明其不可滿足性就，然后對(duì)新的子句集證明其不可滿足性就可以了?？梢粤?。v如果經(jīng)歸結(jié)能得到空子句，根據(jù)空子句的不可滿如果經(jīng)歸結(jié)能得到空子句，根據(jù)空子句的不可滿足性，即可得到原子句集足性，