西電人工智能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é)自然演繹推理從一組已知為真的事實出發(fā)，直從一組已知為真的事實出發(fā)，直接運用經(jīng)典邏輯中的推理規(guī)則推出結(jié)論的過程稱接運用經(jīng)典邏輯中的推理規(guī)則推出結(jié)論的過程稱為自然演繹推理。為自然演繹推理。假言推理假言推理 拒取式

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為假為假例如：例如：由由“如果下雨，則地上會濕如果下雨，則地上會濕”，以及，以及“地上不地上不濕濕”，可以推出，可以推出“沒有下雨沒有下雨”。PQ, QR PR西安電子科技大學(xué)西安電子科技大學(xué)自然演繹推理當(dāng)當(dāng)PQ為真時，希

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

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

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

6、學(xué)西安電子科技大學(xué)自然演繹推理把已知事實及待求解問題用謂詞公式表示如下：把已知事實及待求解問題用謂詞公式表示如下： Prog(x)Like(Wang , x) (x)( Lang(x)Prog(x) Lang(C)應(yīng)用推理規(guī)則進行推理：應(yīng)用推理規(guī)則進行推理： 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這門課。這門課。西安電子科技大學(xué)西安電子科技大學(xué)自然演繹推

7、理定理證明過程自然，易于理解，并且有定理證明過程自然，易于理解，并且有豐富的推理規(guī)則可用。豐富的推理規(guī)則可用。是容易產(chǎn)生知識爆炸，推理過程中得到是容易產(chǎn)生知識爆炸，推理過程中得到的中間結(jié)論一般按指數(shù)規(guī)律遞增，對于復(fù)雜問的中間結(jié)論一般按指數(shù)規(guī)律遞增，對于復(fù)雜問題的推理不利，甚至難以實現(xiàn)。題的推理不利，甚至難以實現(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é)原理的機器推理技術(shù)。歸結(jié)原理的機器推理技術(shù)。魯濱遜歸結(jié)原理亦稱為魯濱遜歸結(jié)原理亦稱為消解原理消解原理，是魯濱遜于，是魯濱遜于1965年在年在海伯倫（海伯倫（Herbrand）理論的基礎(chǔ)上提出的一種基于邏）理論的基礎(chǔ)上提出的一種基于邏輯的輯的“反證法反證法”。在人工智能中，幾乎所有的問題都可以轉(zhuǎn)化為一個定理在人工智能中，幾乎所有的問題都可以轉(zhuǎn)化為一個定理證明問題。定理證明的實質(zhì)，就是要對前提證明問題。定理證明的實質(zhì)，就是要對前提P和結(jié)論和結(jié)論Q，證明證明PQ永真。永真。要證明要證明PQ永真，就是要證明永真，就是要證明PQ在任何一個非空的在任何一個非空的個體域上都是永真的。

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

10、演繹推理子句集及其化簡子句集及其化簡魯濱遜歸結(jié)原理魯濱遜歸結(jié)原理歸結(jié)反演推理的歸結(jié)策略歸結(jié)反演推理的歸結(jié)策略用歸結(jié)反演求取問題的答案用歸結(jié)反演求取問題的答案西安電子科技大學(xué)西安電子科技大學(xué)歸結(jié)演繹推理子句集及其化簡子句集及其化簡魯濱遜歸結(jié)原理魯濱遜歸結(jié)原理歸結(jié)反演推理的歸結(jié)策略歸結(jié)反演推理的歸結(jié)策略用歸結(jié)反演求取問題的答案用歸結(jié)反演求取問題的答案西安電子科技大學(xué)西安電子科技大學(xué)子句集及其化簡v無論是海伯倫理論，還是魯濱遜歸結(jié)原理是在無論是海伯倫理論，還是魯濱遜歸結(jié)原理是在子子句集句集的基礎(chǔ)上討論問題的。因此，討論歸結(jié)演繹的基礎(chǔ)上討論問題的。因此，討論歸結(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é)子句集及其化簡不含任何文字的子句稱為不含任何文字的子句稱為空子句空子句。p由于空子句不含有任何文字，也就不能被任何解釋由于空子句不含有任何文字，也就不能被任何解釋所滿足，因此空子句是所滿足，因此空子句是永假的永假的，不可滿足的不可滿足的。p空子句一般被

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

13、x)(y)P(x,y) (y)(Q(x,y)R(x,y) 經(jīng)等價變化后為：經(jīng)等價變化后為： (x)(y)P(x,y) (y)(Q(x,y)R(x,y)西安電子科技大學(xué)西安電子科技大學(xué)子句集及其化簡2：利用等價關(guān)系把利用等價關(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) 使得每個否定符號最多只作用于一個謂詞上。使得每個否定符號最多只作用于一個謂詞上。p例如：例如：上式經(jīng)等價變換后為上式經(jīng)等價變

14、換后為 (x)(y)P(x，y)(y)( Q(x，y) R(x，y)西安電子科技大學(xué)西安電子科技大學(xué)子句集及其化簡3：重新命名變元，使不同量詞約束的變元有不同重新命名變元，使不同量詞約束的變元有不同的名字的名字p例如：例如：上式經(jīng)重新命名變換后為上式經(jīng)重新命名變換后為 (x)(y)P(x，y)(z)( Q(x，z) R(x，z)消去存在量詞。消去存在量詞。消去存在量詞時，需要區(qū)分以消去存在量詞時，需要區(qū)分以下兩種情況：下兩種情況：p1）存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)，只要用一）存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)，只要用一個新的個體常量替換受該存在量詞約束的變元，就個新的個體常量替換受該存在量詞

15、約束的變元，就可消去該存在量詞?？上ピ摯嬖诹吭~。p2）存在量詞位于一個或者多個全稱量詞的轄域內(nèi)）存在量詞位于一個或者多個全稱量詞的轄域內(nèi)西安電子科技大學(xué)西安電子科技大學(xué)子句集及其化簡 如下面的謂詞公式：如下面的謂詞公式： (x1)(xn) (y)P(x1，x2 , xn ,y) 則需要用則需要用Skolem函數(shù)函數(shù)f(x1，x2 , xn)替換受該存在量替換受該存在量詞約束的變元詞約束的變元y，然后再消去該存在量詞。，然后再消去該存在量詞。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é)子句集及其化簡把全稱量詞全部移到公式的左邊把全稱量詞全部移到公式的左邊p上式中由于只有一個全稱量詞，而且它位于公式的上式中由于只有一個全稱量詞，而且它位于公式的最左邊，所以這里不需要做任何工作。最左邊，所以這里不需要做任何工作。p如果在公式內(nèi)部有全稱量詞，就需要把它們都移到如果在公式內(nèi)部有全稱量

17、詞，就需要把它們都移到公式的左邊。公式的左邊。利用等價關(guān)系利用等價關(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é)子句集及其化簡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) )消去全稱量詞。由于母式中的全部變元均受全消去全稱量詞。由于母式中的全部變元均受全稱量詞的約束，并且全稱量詞的次序已無關(guān)緊要，因稱量詞的約束，并且全稱量詞的次序已無關(guān)緊要，因此可以省掉全稱量詞。此可以省掉全稱量詞。p例如：例如：上式消去全稱量詞后為上式消去全稱量詞后為 (P(x , f(x)Q(x , g(x) (P(x , f(x)R(x , g(x)西安電子科技大學(xué)西安電子科技大學(xué)子句集

19、及其化簡對變元更名，對變元更名，使不同子句中的變元不同名使不同子句中的變元不同名p由于每一個子句都對應(yīng)著母式中的一個合取元，并由于每一個子句都對應(yīng)著母式中的一個合取元，并且所有變元都是由全稱量詞量化的，因此且所有變元都是由全稱量詞量化的，因此任意兩個任意兩個不同子句的變量之間實際上不存在任何關(guān)系，更換不同子句的變量之間實際上不存在任何關(guān)系，更換變量名不會影響公式的真值。變量名不會影響公式的真值。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é)子句集及其化簡在上述化簡過程中，由于在消去存在量詞時所用的在上述化簡過程中，由于在消去存在量詞時所用的Skolem函數(shù)可以不同，因此函數(shù)可以不同，因此化簡后的標(biāo)準(zhǔn)子句集是不化簡后的標(biāo)準(zhǔn)子句集是不唯一的唯一的。因此，當(dāng)原謂詞公式為因此，當(dāng)原謂詞公式為非永假非永假時，它與其標(biāo)準(zhǔn)子句集時，它與其標(biāo)準(zhǔn)子句集并不等價。但當(dāng)原謂詞公式為永假（或不可滿足）時，并不等價。但當(dāng)原謂詞公式為永假（或不可滿足）時，其標(biāo)準(zhǔn)子句集則一定是永假的，

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

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

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

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

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

26、補，那么可從，那么可從C1和和C2中中分別消去分別消去L1和和L2，并將，并將C1和和C2中中余下的余下的部分按析取關(guān)系構(gòu)成一個新的子句部分按析取關(guān)系構(gòu)成一個新的子句C12，則稱這，則稱這一過程為一過程為歸結(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，通過歸結(jié)可以得到，通過歸結(jié)可以得到p C12= QRS設(shè)設(shè)C1=Q，C2=Q，求，求C1和和C2的歸結(jié)式的歸結(jié)式C12。解：解：這里這里

27、L1=Q，L2=Q，通過歸結(jié)可以得到，通過歸結(jié)可以得到p C12= NIL西安電子科技大學(xué)西安電子科技大學(xué)命題邏輯的歸結(jié)設(shè)設(shè)設(shè)設(shè)C1 =P Q ，C2=Q，C3=P，求，求C1、C2、C3的歸結(jié)式的歸結(jié)式C123。解：若先對解：若先對C1、C2歸結(jié)，可得到歸結(jié)，可得到p C12=P然后再對然后再對C12和和C3歸結(jié)，得到歸結(jié)，得到p C123=NIL如果改變歸結(jié)順序，同樣可以得到如果改變歸結(jié)順序，同樣可以得到相同的結(jié)果，即其歸結(jié)過程是不唯相同的結(jié)果，即其歸結(jié)過程是不唯一的。一的。其歸結(jié)歸結(jié)過程可用右圖來表示，其歸結(jié)歸結(jié)過程可用右圖來表示，該樹稱為該樹稱為歸結(jié)樹歸結(jié)樹。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也為真。也為真。對于解釋對于解釋I，L和和L中必有一個為假。中必有一個為假。若若L為假為假，則必有，則必有C1為真，不然就會使為真，不然就會使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中的兩個子句，中的兩個子句，C12是是C1和和C2的歸結(jié)式，若的歸結(jié)式，若用用C12代替代替C1和和C2后得到新的子句后得到新的子句集集S1，則由，則由S1的不可滿足性可以推出原子句集的不可滿足性可以推出原子句集S的不可的不可滿足性。即：滿足性。即： S1的不可滿足性的不可滿足性S的不可滿足性的不可滿足性v推論推論2：設(shè)設(shè)C1和和C2是子句集是子句集S中的兩個子句，中的兩個子句，C12

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