人工智能原理教案归结推理方法命题逻辑的归结.docVIP

2.2 命题逻辑的归结2.2.1 命题逻辑基础逻辑可分为经典逻辑和非经典逻辑，其中经典逻辑包括命题逻辑和谓词逻辑。归结原理是一种主要基于谓词（逻辑）知识表示的推理方法，而命题逻辑是谓词逻辑的基础。因此，在讨论谓词逻辑之前，先讨论命题逻辑的归结，便于内容上的理解。　　本节中，将主要介绍命题逻辑的归结方法，以及有关的一些基础知识和重要概念，如数理逻辑基本公式变形、前束范式、子句集等。　　描述事实、事物的状态、关系等性质的文字串，取值为真或假（表示是否成立）的句子称作命题。　　命题：非真即假的简单陈述句　　在命题逻辑里，单元命题是基本的单元或作为不可再分的原子。下面所列出的是一些基本的数理逻辑公理公式和一些有用的基本定义，如合取范式、子句集，这些公式和定义在归结法的推理过程中是必不可少的，也是归结法的基础，应该熟练掌握。－数理逻辑的基本定义　　下面所列的是一些数理逻辑中重要的定义，在后面的分析中要用到：　　·合取式：p与q，记做p q　　·析取式：p或q，记做p q　　·蕴含式：如果p则q，记做p → q　　·等价式：p当且仅当q，记做p q　　·若A无成假赋值，则称A为重言式或永真式；　　·若A无成真赋值，则称A为矛盾式或永假式；　　·若A至少有一个成真赋值，则称A为可满足的；　　·析取范式：仅由有限个简单合取式组成的析取式　　·合取范式：仅由有限个简单析取式组成的合取式 　－数理逻辑的基本等值式　　下面这些基本的等式在归结原理实施之前的公式转化过程中是非常重要的。只有将逻辑公式正确转换成为归结原理要求的范式，才能够保证归结的正常进行。 　　·交换律：pq q ∨p ；　　　　　　　p q q ∧ p 　　·结合律： (pq) ∨ rp∨(q ∨r);　　　　　　　 (p q) ∧ rp ∧(q ∧ r)　　·分配律： p(q ∧ r) (p∨q)∧(p ∨r) ；　　　　　　　 p (q ∨ r) (p ∧ q) ∨(p ∧ r)　　·双重否定律：p ～～p　　·等幂律：p p∨p；p p∧p　　·摩根律: ～ (pq) ～ p ～ q ；　　　　　　　～ (p q) ～ p ～ q 　　·吸收律: p(p∧q ) p ；　　　　　　　p (p∨q ) p 　　·同一律: p0 p ；　　　　　　　p1 p 　　·零律：p1 1　　　　　　p0 0　　·排中律：p～p 1　　·矛盾律：p～p 0　　·蕴含等值式：p → q ～ pq 　　·等价等值式：pq (p → q)∧(q → p)　　·假言易位式: p → q ～ p → ～ q 　　·等价否定等值式：pq ～p～q　　·归谬论：(p → q)(p → ～q) ～p－合取范式 　　范式：范式是公式的标准形式，公式往往需要变换为同它等价的范式，以便对它们作一般性的处理。 　　合取范式：单元子句、单元子句的或（）的与（）。　　如：P（ PQ）（ ～PQ） 　　例：求取P (Q → R) → S 的合取范式　　解： P (Q → R) → S　　　　= ～（P(～QR) ）∨S　　　　= ～P～(～QR) ∨S　　　　= ～P(～～Q～R) S　　　　= ～P(Q∧～R) S　　　　= ～PS∨(Q∧～R)　　　　= (～PS∨Q) ∧( ～PS∨～R) 　　注意：首先一定要将原有的命题公式整理、转换成为各个或语句的与，不然后续推导没有意义。转换是基于数理逻辑的基本等值公式进行的，或转换到与中。思路与代数学的提取公因式方法相似。 　－子句集 　　命题公式的子句集S是合取范式形式下的子命题（元素）的集合。　　子句集是合取范式中各个合取分量的集合，生成子句集的过程可以简单地理解为将命题公式的合取范式中的与符号，置换为逗号，。 　　上例转换的合取范式：(～PS∨Q) ∧( ～PS∨～R) 　　其子句集为　　S = {～PS∨Q, ～PS∨～R}　　又如，有命题公式：P（ PQ）（ ～PQ）　　其子句集 S：S = {P, PQ, ～PQ} 2.2.2 命题逻辑的归结　　归结法推理的核心是求两个子句的归结式，因此需要先讨论归结式的定义和性质。　　归结式的定义设C1和C2是子句集中的任意两个子句，如果C1中的文字L1与C2中的文字L2互补，那么可从C1和C2中分别消去L1和L2，并将C1和C2中余下的部分按析取关系构成一个新子句C12，则称这一个过程为归结，称C12为C1和C2的归结式，称C1和C2为C12的亲本子句。　　例如：有子句：C1＝PC1， 　　　　　　　　　C2＝～PC2　　存在互补对 P和～P，　　则可得归结式：C12 = C1