第3章基于谓词逻辑机器推理.pptVIP

第三章 基于谓词逻辑的机器推理;第一节 一阶谓词逻辑; 谓词、函数、量词; 谓词、函数、量词; 谓词、函数、量词; 谓词、函数、量词; 谓词公式;　　 谓词公式是谓词演算的基本单元，也称为原子公式。通过引入连词和量词，可以把原子公式组合为复合谓词公式。 1） 连词谓词演算中使用的连词主要有:?（非）、∧（与）、∨（或）、=（蕴涵，也表示为 -）和?（等价，也表示为 ?）。 看几个例子：?Inroom(Robot,R2) Isa(Liming, Student)∧Lives(Liming,House-1)∧Color(House-1, White)Isa(Wang, Teacher)∨Isa(Wang, Officer)At(Liming,School)=At(Wang, School) At(Liming,School)?At(Wang, School) ;一阶谓词　　若限定不允许对谓词、连词、量词和函数名进行量化处理，且参数项不能是谓词公式，则这样的谓词演算是一阶的。例如: （? P）P(A)、 （? P） （? x）P(x) 、 Married(y(L1), Mary，y)（y是变量）都不是一阶谓词公式。 本书中所用到的谓词演算均是一阶的。;谓词公式的永真性和可满足性　　1） 谓词公式的永真性 　　若某谓词公式P对于某论域D上的所有可能的解释都有真值T，则称P在D上是永真的；若P在每个可能的非空论域上均永真，则称P是永真的。　　2） 谓词公式的可满足性　　对于谓词公式P，若在论域D上至少可以建立一个解释，使P有真值T，则称P在D上是可满足的；若至少有一个论域使P可满足，则称P是可满足的。　　3） 谓词公式的永假性　　若某谓词公式P对于论域D上的所有可能的解释都有真值F，则称P在D上是永假的(即不可满足的)；若P在每个可能的非空论域上均永假，则称P是永假的。;谓词逻辑中的形式演绎推理（谓词公式的性质）　　尽管谓词公式具有强大的形式化表示功能，但由于包括了多种连词和量词以及它们的嵌套应用，会使表示形式过于复杂，不利于演绎推理系统的设计和高效运作。为此，化简谓词公式到某些约定的标准形式是很有意义的，谓词公式的性质则为化简工作提供了依据。下面给出关于谓词公式的常用性质： 1） 双重否定 ?(?P) ? P2） 蕴涵式转化 P?Q ? ?P∨Q3） 狄· 摩根定律 ?(P∨Q) ? ?P∧?Q ?(P∧Q) ? ?P∨?Q4)　分配律　　　 P∧(Q∨R) ?(P∧Q)∨(P∧R）　　　　P∨(Q∧R) ? (P∨Q)∧(P∨R)5）交换律 P∨Q ? Q∨P ,P∧Q ? Q∧P;　　6）结合律　　　? (P∧Q)∧R ? P∧(Q∧R）　　　? (P∨Q)∨R ? P∨（Q∨R）　　7）逆否律　　　　P?Q ? Q?P　　8）量词否定　　　　?($x)P(x) ? (?x)(?P(x))　　　　?(?x)P(x) ?（?x)(?P(x))　　9) 量词分配　　　　(?x)[P(x)∧Q(x)] ? (?x)P(x)∧(?x)Q(x)　　　　(?x)[P(x)∨Q(x)] ?（?x）P(x)∨(?x)Q(x)　　10) 约束变量的虚元性（约束变量名的变换不影响合适公式的真值）　　　　(?x)P(x) ? (?y)P(y)　　　　(?x)P(x) ? (?y)P(y);第二节 归结演绎推理;子句集;子句集（求子句集的步骤）;谓词公式的标准化 1.标准化需求 谓词公式的标准化是为基于谓词演算的演绎推理服务的，常见的基于谓词演算的推理有归结反演和规则演绎。这二种演绎推理都要求以所谓的量词前束范式来表示谓词公式，形如： 　　　　（Q1x1）（Q2x2）…（Qkxk ）M 其中M称为母式，不包括任何量词，量词全都集中置于M的前面，Qi 可以是量词符号?或$ ，xi 是量词的约束变量（i=1,2,…,k）。; 谓词公式的标准化 归结反演要求母式M标准化为 合取范式，定义如下：　　　　M = W1∧W2∧…∧Wn 　　　　Wi = Li1∨Li2∨…∨Lim (i=1,2,…,n)　　　　Lij= Pij | ?Pij (j=1,2,…,m)Lij称为文字（Literal）,只能是原子谓词公式Pij或其取反。与合取范式对偶的是析取范式，定义如下：　　　　M = W1∨W2∨…∨Wn 　　　　Wi = Li1∧Li2∧…∧Lim (i=1,2,…,n) 　　　　Lij= Pij | ? Pij (j=1,2,…,m)　　;2.合取范式的标准化过程　　将谓词公式化简为标准的合取范式,