湘潭大学人工智能课件确定性推理part5

ArtificialIntelligence(AI)

人工智能第二章：知识表示与推理ArtificialIntelligence(AI)

人内容提要第二章：知识表示与推理1.推理的基本概念2.搜索策略3.自然演绎推理4.消解演绎推理5.基于规则的演绎推理二、确定性推理内容提要第二章：知识表示与推理1.推理的基本概念2.搜索策略自然演绎推理自然演绎推理：从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。自然演绎推理最基本的推理规则是三段论推理，它包括：假言推理拒取式假言三段论自然演绎推理自然演绎推理：从一组已知为真的事实出发，直接运用自然演绎推理假言推理：

P,P→Q⇒Q表示：由P→Q以及P为真，可以推出Q为真例如：由“如果x是金属，则x能导电”，以及“铜是金属”，可以推出“铜能导电”。拒取式：P→Q,﹁Q⇒﹁P表示：由P→Q为真以及Q为假，可以推出P为假例如：由“如果下雨，则地上会湿”，以及“地上不湿”，可以推出“没有下雨”。假言三段论：P→Q,Q→R⇒P→R自然演绎推理假言推理：P,P→Q⇒Q自然演绎推理注意避免以下两类错误：肯定后件的错误：当P→Q为真时，希望通过肯定后件Q为真来推出前件P为真，这是不允许的。例如：伽利略在论证哥白尼的日心说时，曾使用了如下推理：(1)如果行星系统是以太阳为中心的，则金星会显示出位相变化；(2)金星显示出位相变化；(3)所有，行星系统是以太阳为中心的这就是使用了肯定后件的推理，违反了经典逻辑的逻辑规则。自然演绎推理注意避免以下两类错误：自然演绎推理注意避免以下两类错误：否定前件的错误：当P→Q为真时，希望通过否定前件P来推出后件Q为假，这也是不允许的。例如：(1)如果下雨，则地上会湿(2)没有下雨(3)所有，地上不湿事实上，如果向地上洒水，地上也是会湿的。这就是使用了否定前件的推理，违反了经典逻辑的逻辑规则。自然演绎推理注意避免以下两类错误：自然演绎推理自然演绎推理的例子设已知如下事实：A,B,A→C,B∧C→D,D→Q求证：Q为真。证明：因为A,A→C⇒C假言推理B,C⇒B∧C引入合取词B∧C，B∧C→D⇒D假言推理D,D→Q⇒Q假言推理因此，Q为真自然演绎推理自然演绎推理的例子自然演绎推理自然演绎推理的例子设已知如下事实：(1)只要是需要编程序的课，王程都喜欢。(2)所有的程序设计语言课都是需要编程序的课。(3)C是一门程序设计语言课。求证：王程喜欢C这门课。证明：首先定义谓词Prog(x)：x是需要编程序的课。Like(x,y):x喜欢y。Lang(x):x是一门程序设计语言课自然演绎推理自然演绎推理的例子自然演绎推理自然演绎推理的例子把已知事实及待求解问题用谓词公式表示如下：Prog(x)→Like(Wang,x)(∀x)(Lang(x)→Prog(x))Lang(C)应用推理规则进行推理：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这门课。自然演绎推理自然演绎推理的例子自然演绎推理自然演绎推理的优缺点优点：定理证明过程自然，易于理解，并且有丰富的推理规则可用。缺点：是容易产生知识爆炸，推理过程中得到的中间结论一般按指数规律递增，对于复杂问题的推理不利，甚至难以实现。自然演绎推理自然演绎推理的优缺点内容提要第二章：知识表示与推理1.推理的基本概念2.搜索策略3.自然演绎推理4.消解演绎推理5.基于规则的演绎推理二、确定性推理内容提要第二章：知识表示与推理1.推理的基本概念2.搜索策略消解演绎推理消解演绎推理：是一种基于鲁滨逊（Robinson）消解原理的机器推理技术。鲁滨逊消解原理亦称为消解原理，是鲁滨逊于1965年在海伯伦（Herbrand）理论的基础上提出的一种基于逻辑的“反证法”。在人工智能中，几乎所有的问题都可以转化为一个定理证明问题。定理证明的实质，就是要对前提P和结论Q，证明P→Q永真。要证明P→Q永真，就是要证明P→Q在任何一个非空的个体域上都是永真的。这将是非常困难的，甚至是不可实现的。消解演绎推理消解演绎推理：是一种基于鲁滨逊（Robinson消解演绎推理消解演绎推理：鲁滨逊消解原理把永真性的证明转化为关于不可满足性的证明。要证明P→Q永真，只需证明P∧﹁Q不可满足因为：﹁(P→Q)⇔﹁(﹁P∨Q)⇔P∧﹁Q海伯伦(Herbrand)定理为自动定理证明奠定了理论基础。鲁滨逊(Robinson)提出的消解原理使机器定理证明成为现实。消解演绎推理消解演绎推理：消解演绎推理消解演绎推理子句集及其化简鲁滨逊消解原理消解反演推理的消解策略用消解反演求取问题的答案消解演绎推理消解演绎推理消解演绎推理消解演绎推理子句集及其化简鲁滨逊消解原理消解反演推理的消解策略用消解反演求取问题的答案消解演绎推理消解演绎推理子句集及其化简鲁滨逊消解原理是在子句集的基础上讨论问题的。因此，讨论消解演绎推理之前，需要先讨论子句集的有关概念。子句和子句集原子谓词公式及其否定统称为文字。例如:P(x)、Q(x)、﹁P(x)、﹁Q(x)等都是文字。任何文字的析取式称为子句。例如，P(x)∨Q(x)，P(x，f(x))∨Q(x，g(x))都是子句。子句集及其化简鲁滨逊消解原理是在子句集的基础上讨论问题的。因子句集及其化简子句和子句集不含任何文字的子句称为空子句。由于空子句不含有任何文字，也就不能被任何解释所满足，因此空子句是永假的，不可满足的。空子句一般被记为NIL。由子句或空子句所构成的集合称为子句集。在子句集中，子句之间是合取关系子句集中的变元受全称量词的约束任何谓词公式都可通过等价关系及推理规则化为相应的子句集子句集及其化简子句和子句集子句集及其化简把谓词公式化成子句集的步骤Step1：利用等价关系消去“→”和“↔”反复使用如下等价公式：P→Q⇔﹁P∨QP↔Q⇔(P∧Q)∨(﹁P∧﹁Q)即可消去谓词公式中的连接词“→”和“↔”。例如：

(∀x)((∀y)P(x,y)→﹁(∀y)(Q(x,y)→R(x,y)))经等价变化后为：

(∀x)(﹁(∀y)P(x,y)∨﹁(∀y)(﹁Q(x,y)∨R(x,y)))子句集及其化简把谓词公式化成子句集的步骤子句集及其化简Step2：利用等价关系把“¬”移到紧靠谓词的位置上反复使用双重否定率：﹁(﹁P)⇔P摩根定律：﹁(P∧Q)⇔﹁P∨﹁Q﹁(P∨Q)⇔﹁P∧﹁Q量词转换率：﹁(∀x)P(x)⇔(∃x)﹁P(x)﹁(∃x)P(x)⇔(∀x)﹁

P(x)使得每个否定符号最多只作用于一个谓词上。例如：上式(∀x)(﹁(∀y)P(x,y)∨﹁(∀y)(﹁Q(x,y)∨R(x,y)))经等价变换后为

(∀x)((∃y)﹁P(x，y)∨(∃y)(Q(x，y)∧﹁R(x，y))子句集及其化简Step2：利用等价关系把“¬”移到紧靠谓词子句集及其化简Step3：重新命名变元，使不同量词约束的变元有不同的名字例如：上式经重新命名变换后为

(∀x)((∃y)﹁P(x，y)∨(∃z)(Q(x，z)∧﹁R(x，z)))Step4：消去存在量词。消去存在量词时，需要区分以下两种情况：1）存在量词不出现在全称量词的辖域内，只要用一个新的个体常量替换受该存在量词约束的变元，就可消去该存在量词。例如：(∃x)P(x)可化为P(A)2）存在量词位于一个或者多个全称量词的辖域内子句集及其化简Step3：重新命名变元，使不同量词约束的变子句集及其化简如下面的谓词公式：(∀x1)…(∀xn)(∃y)P(x1，x2,…,xn,y)则需要用Skolem函数f(x1，x2,…,xn)替换受该存在量词约束的变元y，然后再消去该存在量词。例如：继续上面的例子(∀x)((∃y)﹁P(x，y)∨(∃z)(Q(x，z)∧﹁R(x，z)))式子中存在量词(y)及(z)都位于(x)的辖域内，所以需要用Skolem函数替换，设替换y和z的Skolem函数分别是f(x)和g(x)，则替换后得到：(∀x)(﹁P(x,f(x))∨(Q(x,g(x))∧﹁R(x,g(x))))子句集及其化简如下面的谓词公式：子句集及其化简Step5：把全称量词全部移到公式的左边上式中由于只有一个全称量词，而且它位于公式的最左边，所以这里不需要做任何工作。如果在公式内部有全称量词，就需要把它们都移到公式的左边。Step6：利用等价关系

P∨(Q∧R)⇔(P∨Q)∧(P∨R)

把公式化为Skolem标准形Skolem标准形的一般形式为(∀x1)…(∀xn)M(x1,x2,……,xn)其中，M(x1,x2,……,xn)是Skolem标准形的母式，它由子句的合取所构成。子句集及其化简Step5：把全称量词全部移到公式的左边子句集及其化简例如：前面的公式化为Skolem标准形后为

(∀x)(

(﹁P(x,f(x))∨Q(x,g(x)))

∧(﹁P(x,f(x))﹁R(x,g(x))))Step7：消去全称量词。由于母式中的全部变元均受全称量词的约束，并且全称量词的次序已无关紧要，因此可以省掉全称量词。例如：上式消去全称量词后为(﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x)))Step8：对变元更名，使不同子句中的变元不同名例如：上式经更名后得到(﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(y,f(y))∨﹁R(y,g(y)))子句集及其化简例如：前面的公式化为Skolem标准形后为子句集及其化简Step9：消去合取词，就得到子句集。例如：消去合取词后，上式(﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(y,f(y))∨﹁R(y,g(y)))

就变为下述子句集﹁P(x,f(x))∨Q(x,g(x))﹁P(y,f(y))∨﹁R(y,g(y))子句集及其化简Step9：消去合取词，就得到子句集。子句集及其化简子句集的意义在上述化简过程中，由于在消去存在量词时所用的Skolem函数可以不同，因此化简后的标准子句集是不唯一的。因此，当原谓词公式为非永假时，它与其标准子句集并不等价。但当原谓词公式为永假（或不可满足）时，其标准子句集则一定是永假的，即Skolem化并不影响原谓词公式的永假性。子句集S的不可满足性：对于任意论域中的任意一个解释，S中的子句不能同时取得真值T。子句集及其化简子句集的意义子句集及其化简定理：设有谓词公式F，其子句集为S，则F不可满足的充要条件是S不可满足。由此定理可知，要证明一个谓词公式是不可满足的，只要证明其相应的标准子句集是不可满足的就可以了。由于子句集中的子句之间是合取关系，子句集中只要有一个子句为不可满足，则整个子句集就是不可满足的。空子句是不可满足的。因此，一个子句集中如果包含有空子句，则此子句集就一定是不可满足的。这个结论是鲁滨逊消解原理的主要依据。子句集及其化简定理：设有谓词公式F，其子句集为S，则F不可满消解演绎推理消解演绎推理子句集及其化简鲁滨逊消解原理消解反演推理的消解策略用消解反演求取问题的答案消解演绎推理消解演绎推理鲁滨逊消解原理鲁滨逊消解原理的基本思想首先把欲证明问题的结论否定，并加入子句集，得到一个扩充的子句集S'；然后设法检验子句集S'是否含有空子句，若含有空子句，则表明S'是不可满足的；若不含有空子句，则继续使用消解法，在子句集中选择合适的子句进行消解，直至导出空子句或不能继续消解为止。鲁滨逊消解原理包括命题逻辑的消解谓词逻辑的消解鲁滨逊消解原理鲁滨逊消解原理的基本思想命题逻辑的消解消解推理的核心是求两个子句的消解式消解式的定义及性质若P是原子谓词公式，则称P与﹁P为互补文字设C1和C2是子句集中的任意两个子句，如果C1中的文字L1与C2中的文字L2互补，那么可从C1和C2中分别消去L1和L2，并将C1和C2中余下的部分按析取关系构成一个新的子句C12，则称这一过程为消解，称C12为C1和C2的消解式，称C1和C2为C12的亲本子句。命题逻辑的消解消解推理的核心是求两个子句的消解式命题逻辑的消解例如：设C1=P∨Q∨R，C2=﹁P∨S，求C1和C2的消解式C12。解：这里L1=P，L2=﹁P，通过消解可以得到C12=Q∨R∨S例如：设C1=﹁Q，C2=Q，求C1和C2的消解式C12。解：这里L1=﹁Q，L2=Q，通过消解可以得到

C12=NIL命题逻辑的消解例如：设C1=P∨Q∨R，C2=﹁P∨S，求C命题逻辑的消解例如：设设C1=﹁P∨

Q

，C2=﹁Q，C3=P，求C1、C2、C3的消解式C123。解：若先对C1、C2消解，可得到C12=﹁P然后再对C12和C3消解，得到C123=NIL如果改变消解顺序，同样可以得到相同的结果，即其消解过程是不唯一的。其消解消解过程可用右图来表示，该树称为消解树。﹁P∨Q﹁Q﹁P

P

NIL﹁P∨Q

P

Q﹁Q

NIL命题逻辑的消解例如：设设C1=﹁P∨Q，C2=﹁Q，命题逻辑的消解定理：消解式C12是其亲本子句C1和C2的逻辑结论。证明：设C1=L∨C1’，C2=﹁L∨C2’关于解释I为真，则只需证明C12=C1’∨C2’关于解释I也为真。对于解释I，L和﹁L中必有一个为假。若L为假，则必有C1'为真，不然就会使C1为假，这将与前提假设C1为真矛盾，因此只能有C1'为真。同理，若﹁L为假，则必有C2'为真。因此，必有C12=C1'∨C2'关于解释I也为真。即C12是C1和C2的逻辑结论。命题逻辑的消解定理：消解式C12是其亲本子句C1和C2的逻辑命题逻辑的消解推论1：设C1和C2是子句集S中的两个子句，C12是C1和C2的消解式，若用C12代替C1和C2后得到新的子句集S1，则由S1的不可满足性可以推出原子句集S的不可满足性。即：

S1的不可满足性⇔S的不可满足性推论2：设C1和C2是子句集S中的两个子句，C12是C1和C2的消解式，若把C12加入S中得到新的子句集S2，则S与S2的不可满足性是等价的。即：

S2的不可满足性⇔S的不可满足性命题逻辑的消解推论1：设C1和C2是子句集S中的两个子句，C命题逻辑的消解上述两个推论说明，为证明子句集S的不可满足性，只要对其中可进行消解得子句进行消解，并把消解式加入到子句集S中，或者用消解式代替他的亲本子句，然后对新的子句集证明其不可满足性就可以了。如果经消解能得到空子句，根据空子句的不可满足性，即可得到原子句集S是不可满足的结论。在命题逻辑中，对不可满足的子句集S，其消解原理是完备的。即：子句集S是不可满足的，当且仅当存在一个从S到空子句的消解过程。

命题逻辑的消解上述两个推论说明，为证明子句集S的不可满足性，命题逻辑的消解命题逻辑的消解反演消解原理：假设F为已知前提，G为欲证明的结论，消解原理把证明G为F的逻辑结论转化为证明F∧﹁G为不可满足。再根据上述定理，在不可满足的意义上，公式集F∧﹁G与其子句集是等价的，即把公式集上的不可满足转化为子句集上的不可满足。应用消解原理证明定理的过程称为消解反演。命题逻辑的消解命题逻辑的消解反演命题逻辑的消解命题逻辑的消解反演：在命题逻辑中，已知F，证明G为真的消解反演过程如下：①否定目标公式G，得﹁G;②把﹁G并入到公式集F中，得到{F，﹁G}；③把{F，﹁G}化为子句集S。④应用消解原理对子句集S中的子句进行消解，并把每次得到的消解式并入S中。如此反复进行，若出现空子句，则停止消解，此时就证明了G为真。命题逻辑的消解命题逻辑的消解反演：在命题逻辑中，已知F，证明命题逻辑的消解例如：设已知的公式集为{P,(P∧Q)→R,(S∨T)→Q,T}，求证结论R。解：假设结论R为假,将﹁R加入公式集，并化为子句集：S={P,﹁P∨﹁Q∨R,﹁S∨Q,﹁T∨Q,T,﹁R}其消解过程如右图的消解演绎树所示。该树根为空子句。子句集S不可满足，即假设﹁R为真是错误的，于是R为真。﹁P∨﹁Q∨R﹁R﹁P∨﹁QP﹁Q﹁T∨Q﹁TTNIL命题逻辑的消解例如：设已知的公式集为{P,(P∧Q)→R问题？问题？ArtificialIntelligence(AI)

人工智能第二章：知识表示与推理ArtificialIntelligence(AI)

人内容提要第二章：知识表示与推理1.推理的基本概念2.搜索策略3.自然演绎推理4.消解演绎推理5.基于规则的演绎推理二、确定性推理内容提要第二章：知识表示与推理1.推理的基本概念2.搜索策略自然演绎推理自然演绎推理：从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。自然演绎推理最基本的推理规则是三段论推理，它包括：假言推理拒取式假言三段论自然演绎推理自然演绎推理：从一组已知为真的事实出发，直接运用自然演绎推理假言推理：

P,P→Q⇒Q表示：由P→Q以及P为真，可以推出Q为真例如：由“如果x是金属，则x能导电”，以及“铜是金属”，可以推出“铜能导电”。拒取式：P→Q,﹁Q⇒﹁P表示：由P→Q为真以及Q为假，可以推出P为假例如：由“如果下雨，则地上会湿”，以及“地上不湿”，可以推出“没有下雨”。假言三段论：P→Q,Q→R⇒P→R自然演绎推理假言推理：P,P→Q⇒Q自然演绎推理注意避免以下两类错误：肯定后件的错误：当P→Q为真时，希望通过肯定后件Q为真来推出前件P为真，这是不允许的。例如：伽利略在论证哥白尼的日心说时，曾使用了如下推理：(1)如果行星系统是以太阳为中心的，则金星会显示出位相变化；(2)金星显示出位相变化；(3)所有，行星系统是以太阳为中心的这就是使用了肯定后件的推理，违反了经典逻辑的逻辑规则。自然演绎推理注意避免以下两类错误：自然演绎推理注意避免以下两类错误：否定前件的错误：当P→Q为真时，希望通过否定前件P来推出后件Q为假，这也是不允许的。例如：(1)如果下雨，则地上会湿(2)没有下雨(3)所有，地上不湿事实上，如果向地上洒水，地上也是会湿的。这就是使用了否定前件的推理，违反了经典逻辑的逻辑规则。自然演绎推理注意避免以下两类错误：自然演绎推理自然演绎推理的例子设已知如下事实：A,B,A→C,B∧C→D,D→Q求证：Q为真。证明：因为A,A→C⇒C假言推理B,C⇒B∧C引入合取词B∧C，B∧C→D⇒D假言推理D,D→Q⇒Q假言推理因此，Q为真自然演绎推理自然演绎推理的例子自然演绎推理自然演绎推理的例子设已知如下事实：(1)只要是需要编程序的课，王程都喜欢。(2)所有的程序设计语言课都是需要编程序的课。(3)C是一门程序设计语言课。求证：王程喜欢C这门课。证明：首先定义谓词Prog(x)：x是需要编程序的课。Like(x,y):x喜欢y。Lang(x):x是一门程序设计语言课自然演绎推理自然演绎推理的例子自然演绎推理自然演绎推理的例子把已知事实及待求解问题用谓词公式表示如下：Prog(x)→Like(Wang,x)(∀x)(Lang(x)→Prog(x))Lang(C)应用推理规则进行推理：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这门课。自然演绎推理自然演绎推理的例子自然演绎推理自然演绎推理的优缺点优点：定理证明过程自然，易于理解，并且有丰富的推理规则可用。缺点：是容易产生知识爆炸，推理过程中得到的中间结论一般按指数规律递增，对于复杂问题的推理不利，甚至难以实现。自然演绎推理自然演绎推理的优缺点内容提要第二章：知识表示与推理1.推理的基本概念2.搜索策略3.自然演绎推理4.消解演绎推理5.基于规则的演绎推理二、确定性推理内容提要第二章：知识表示与推理1.推理的基本概念2.搜索策略消解演绎推理消解演绎推理：是一种基于鲁滨逊（Robinson）消解原理的机器推理技术。鲁滨逊消解原理亦称为消解原理，是鲁滨逊于1965年在海伯伦（Herbrand）理论的基础上提出的一种基于逻辑的“反证法”。在人工智能中，几乎所有的问题都可以转化为一个定理证明问题。定理证明的实质，就是要对前提P和结论Q，证明P→Q永真。要证明P→Q永真，就是要证明P→Q在任何一个非空的个体域上都是永真的。这将是非常困难的，甚至是不可实现的。消解演绎推理消解演绎推理：是一种基于鲁滨逊（Robinson消解演绎推理消解演绎推理：鲁滨逊消解原理把永真性的证明转化为关于不可满足性的证明。要证明P→Q永真，只需证明P∧﹁Q不可满足因为：﹁(P→Q)⇔﹁(﹁P∨Q)⇔P∧﹁Q海伯伦(Herbrand)定理为自动定理证明奠定了理论基础。鲁滨逊(Robinson)提出的消解原理使机器定理证明成为现实。消解演绎推理消解演绎推理：消解演绎推理消解演绎推理子句集及其化简鲁滨逊消解原理消解反演推理的消解策略用消解反演求取问题的答案消解演绎推理消解演绎推理消解演绎推理消解演绎推理子句集及其化简鲁滨逊消解原理消解反演推理的消解策略用消解反演求取问题的答案消解演绎推理消解演绎推理子句集及其化简鲁滨逊消解原理是在子句集的基础上讨论问题的。因此，讨论消解演绎推理之前，需要先讨论子句集的有关概念。子句和子句集原子谓词公式及其否定统称为文字。例如:P(x)、Q(x)、﹁P(x)、﹁Q(x)等都是文字。任何文字的析取式称为子句。例如，P(x)∨Q(x)，P(x，f(x))∨Q(x，g(x))都是子句。子句集及其化简鲁滨逊消解原理是在子句集的基础上讨论问题的。因子句集及其化简子句和子句集不含任何文字的子句称为空子句。由于空子句不含有任何文字，也就不能被任何解释所满足，因此空子句是永假的，不可满足的。空子句一般被记为NIL。由子句或空子句所构成的集合称为子句集。在子句集中，子句之间是合取关系子句集中的变元受全称量词的约束任何谓词公式都可通过等价关系及推理规则化为相应的子句集子句集及其化简子句和子句集子句集及其化简把谓词公式化成子句集的步骤Step1：利用等价关系消去“→”和“↔”反复使用如下等价公式：P→Q⇔﹁P∨QP↔Q⇔(P∧Q)∨(﹁P∧﹁Q)即可消去谓词公式中的连接词“→”和“↔”。例如：

(∀x)((∀y)P(x,y)→﹁(∀y)(Q(x,y)→R(x,y)))经等价变化后为：

(∀x)(﹁(∀y)P(x,y)∨﹁(∀y)(﹁Q(x,y)∨R(x,y)))子句集及其化简把谓词公式化成子句集的步骤子句集及其化简Step2：利用等价关系把“¬”移到紧靠谓词的位置上反复使用双重否定率：﹁(﹁P)⇔P摩根定律：﹁(P∧Q)⇔﹁P∨﹁Q﹁(P∨Q)⇔﹁P∧﹁Q量词转换率：﹁(∀x)P(x)⇔(∃x)﹁P(x)﹁(∃x)P(x)⇔(∀x)﹁

P(x)使得每个否定符号最多只作用于一个谓词上。例如：上式(∀x)(﹁(∀y)P(x,y)∨﹁(∀y)(﹁Q(x,y)∨R(x,y)))经等价变换后为

(∀x)((∃y)﹁P(x，y)∨(∃y)(Q(x，y)∧﹁R(x，y))子句集及其化简Step2：利用等价关系把“¬”移到紧靠谓词子句集及其化简Step3：重新命名变元，使不同量词约束的变元有不同的名字例如：上式经重新命名变换后为

(∀x)((∃y)﹁P(x，y)∨(∃z)(Q(x，z)∧﹁R(x，z)))Step4：消去存在量词。消去存在量词时，需要区分以下两种情况：1）存在量词不出现在全称量词的辖域内，只要用一个新的个体常量替换受该存在量词约束的变元，就可消去该存在量词。例如：(∃x)P(x)可化为P(A)2）存在量词位于一个或者多个全称量词的辖域内子句集及其化简Step3：重新命名变元，使不同量词约束的变子句集及其化简如下面的谓词公式：(∀x1)…(∀xn)(∃y)P(x1，x2,…,xn,y)则需要用Skolem函数f(x1，x2,…,xn)替换受该存在量词约束的变元y，然后再消去该存在量词。例如：继续上面的例子(∀x)((∃y)﹁P(x，y)∨(∃z)(Q(x，z)∧﹁R(x，z)))式子中存在量词(y)及(z)都位于(x)的辖域内，所以需要用Skolem函数替换，设替换y和z的Skolem函数分别是f(x)和g(x)，则替换后得到：(∀x)(﹁P(x,f(x))∨(Q(x,g(x))∧﹁R(x,g(x))))子句集及其化简如下面的谓词公式：子句集及其化简Step5：把全称量词全部移到公式的左边上式中由于只有一个全称量词，而且它位于公式的最左边，所以这里不需要做任何工作。如果在公式内部有全称量词，就需要把它们都移到公式的左边。Step6：利用等价关系

P∨(Q∧R)⇔(P∨Q)∧(P∨R)

把公式化为Skolem标准形Skolem标准形的一般形式为(∀x1)…(∀xn)M(x1,x2,……,xn)其中，M(x1,x2,……,xn)是Skolem标准形的母式，它由子句的合取所构成。子句集及其化简Step5：把全称量词全部移到公式的左边子句集及其化简例如：前面的公式化为Skolem标准形后为

(∀x)(

(﹁P(x,f(x))∨Q(x,g(x)))

∧(﹁P(x,f(x))﹁R(x,g(x))))Step7：消去全称量词。由于母式中的全部变元均受全称量词的约束，并且全称量词的次序已无关紧要，因此可以省掉全称量词。例如：上式消去全称量词后为(﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x)))Step8：对变元更名，使不同子句中的变元不同名例如：上式经更名后得到(﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(y,f(y))∨﹁R(y,g(y)))子句集及其化简例如：前面的公式化为Skolem标准形后为子句集及其化简Step9：消去合取词，就得到子句集。例如：消去合取词后，上式(﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(y,f(y))∨﹁R(y,g(y)))

就变为下述子句集﹁P(x,f(x))∨Q(x,g(x))﹁P(y,f(y))∨﹁R(y,g(y))子句集及其化简Step9：消去合取词，就得到子句集。子句集及其化简子句集的意义在上述化简过程中，由于在消去存在量词时所用的Skolem函数可以不同，因此化简后的标准子句集是不唯一的。因此，当原谓词公式为非永假时，它与其标准子句集并不等价。但当原谓词公式为永假（或不可满足）时，其标准子句集则一定是永假的，即Skolem化并不影响原谓词公式的永假性。子句集S的不可满足性：对于任意论域中的任意一个解释，S中的子句不能同时取得真值T。子句集及其化简子句集的意义子句集及其化简定理：设有谓词公式F，其子句集为S，则F不可满足的充要条件是S不可满足。由此定理可知，要证明一个谓词公式是不可满足的，只要证明其相应的标准子句集是不可满足的就可以了。由于子句集中的子句之间是合取关系，子句集中只要有一个子句为不可满足，则整个子句集就是不可满足的。空子句是不可满足的。因此，一个子句集中如果包含有空子句，则此子句集就一定是不可满足的。这个结论是鲁滨逊消解原理的主要依据。子句集及其化简定理：设有谓词公式F，其子句集为S，则F不可满消解演绎推理消解演绎推理子句集及其化简鲁滨逊消解原理消解反演推理的消解策略用消解反演求取问题的答案消解演绎推理消解演绎推理鲁滨逊消解原理鲁滨逊消解原理的基本思想首先把欲证明问题的结论否定，并加入子句集，得到一个扩充的子句集S'；然后设法检验子句集S'是否含有空子句，若含有空子句，则表明S'是不可满足的；若不含有空子句，则继续使用消解法，在子句集中选择合适的子句进行消解，直至导出空子句或不能继续消解为止。鲁滨逊消解原理包括命题逻辑的消解谓词逻辑的消解鲁滨逊消解原理鲁滨逊消解原理的基本思想命题逻辑的消解消解推理的核心是求两个子句的消解式消解式的定义及性质若P是原子谓词公式，则称P与﹁P为互补文字设C1和C2是子句集中的任意两个子句，如果C1中的文字L1与C2中的文字L2互补，那么可从C1和C2中分别消去L1和L2，并将C1和C2中余下的部分按析取关系构成一个新的子句C12，则称这一过程为消解，称C12为C1和C2的消解式，称C1和C2为C12的亲本子句。命题逻辑的消解消解推理的核心是求两个子句的消解式命题逻辑的消解例如：设C1=P∨Q∨R，C2=﹁P∨S，求C1和C2的消解式C12。解：这里L1=P，L2=﹁P，通过消解可以得到C12=Q∨R∨S例如：设C1=﹁Q，C2=Q，求C1和C2的消解式C12。解：这里L1=﹁Q，L2=Q，通过消解可以得到

C12=NIL命题逻辑的消解例如：设C1=P∨Q∨R，C2=﹁P∨S，求C命题逻辑的消解例如：设设C1=﹁P∨

Q

，C2=﹁Q，C3=P，求C1、C2、C3的消解式C123。解：若先对C1、C2消解，可得到C12=﹁P然后再对C12和C3消解，得到C123=NIL如果改变消解顺序，同样可以得到相同的结果，即其消解过程是不唯一的。其消解消解过程可用右图来表示，该树称为消解树。﹁P∨Q﹁Q﹁P

P

NIL﹁P∨Q

P

Q﹁Q