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

命题逻辑的消解 例如：设设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 命题逻辑的消解 定理：消解式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的逻辑结论。 命题逻辑的消解 推论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的不可满足性 命题逻辑的消解 上述两个推论说明，为证明子句集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为真。 命题逻辑的消解 例如：设已知的公式集为{ 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 ∨﹁Q P ﹁Q ﹁T ∨Q ﹁T T NIL Artificial Intelligence (AI)人工智能 第二章：知识表示与推理 内容提要 第二章：知识表示与推理 1.推理的基本概念 2.有哪些信誉好的足球投注网站策略 3.自然演绎推理 4.消解演绎推理 5.基于规则的演绎推理 二、确定性推理 自然演绎推理 自然演绎推理：从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。 自然演绎推理最基本的推理规则是三段论推理，它包括： 假言推理 拒取式 假言三段论 自然演绎推理 假言推理 ： 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→Q为真时，希望通过肯定后件Q为真来推出前件P为真，这是不允许的。 例如：伽利略在论证哥白尼的日心说时，曾使用了如下推理： (1)如果行星系统是以太阳为中心的，则金星会显示出位相变化； (2)金星显示出位相变化； (3)所有，行星系统是以太阳为中心的 这就是使用了肯定后件的推理，违反了经典