Chapter谓词逻辑前束范式.pptx

《Chapter谓词逻辑前束范式.pptx》由会员分享，可在线阅读，更多相关《Chapter谓词逻辑前束范式.pptx（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第5讲 26 前束范式 要求：理解前束范式、前束合取范式和前束析取范式的定义，会将一个谓词公式wffA化为前束范式、前束合取范式和前束析取范式。学习本节的目的是掌握谓词公式的标准化形式。重点：化谓词公式为前束范式。第1页/共26页复习：（1）量词与联结词之间的关系（2）量词扩张/收缩律 这里A(x)是任意包括个体变元x的谓词公式，B是不包括个体变元x的任意谓词公式。第2页/共26页（3）量词与命题联结词之间的一些等价式）量词与命题联结词之间的一些等价式量词分配律量词分配律第3页/共26页（4）指导变元、作用域、约束变元、自由变元量词指导变元辖域约束变元自由变元第4页/共26页（5）约束变元换名

2、和自由变元代入 在一公式中，有的个体变元既是约束出现，又是自由出现，这就容易产生混淆。为了避免混淆，可对约束变元换名或自由变元代入。约束变元换名 将量词辖域中某个约束出现的个体变元及相应指导变元，改成本辖域中未曾出现过的个体变元，其余不变。自由变元代入 对某自由出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且处处代入。第5页/共26页第二章 谓词逻辑（Predicate Logic）2.6前束范式(Prenex Normal Form)2.6 前束范式(Prenex normal form)2.6.1 前束范式(Prenex normal form)2.6.2 前

3、束析取范式和前束合取范式(Prenex disjunctive normal form&Prenex conjunctive normal form)第6页/共26页 2.6 前束范式(Prenex Normal Form)2.6.1前束范式(Prenex normal form)定义2.6.1:任何一个谓词公式A，如果具有如下形式：(x1)(x2)(xn)B其中可能是量词或量词，xi（i=1，n）是客体变元，B是不含量词的谓词公式，则称A是前束范式。说明:前束范式的量词均在全式的开头,它们的作用域延伸到整个公式的末尾。例1:xy（F(x)G(y)）H(x,y)）xy(F(x,y)G(y,z)

4、x H(x,y,z)第7页/共26页定理2.5.1:任何一个谓词公式,均和一个前束范式等价。前束范式的求法：第一步：否定深入。即利用量词转化公式，把否定联结 词深入到命题变元和谓词填式的前面。第二步：改名。即利用换名规则、代入规则更换一些变元的名称，以便消除混乱。第三步：量词前移。即利用量词辖域的收缩与扩张把量词移到前面。这样便可求出与公式等价的前束范式。第8页/共26页举例 73页 例题1，例题2，例题3第9页/共26页例题例题2 化公式化公式(x x)(y y)()(z)(P(x,z)z)(P(x,z)P(y,z)P(y,z)(u)Q(x,y,u)u)Q(x,y,u)为前束为前束范式范式解

5、解 原公式原公式(x x)(y y)()(z)(P(x,z)z)(P(x,z)P(y,z)P(y,z)(u)Q(x,y,u)u)Q(x,y,u)(x x)(y y)()(z)(z)(P(x,z)P(x,z)P(y,z)P(y,z)(u)Q(x,y,u)u)Q(x,y,u)(x x)(y y)()(z)z)(u)u)(P(x,z)P(x,z)P(y,z)P(y,z)Q(x,y,u)Q(x,y,u)第10页/共26页解解 第一步否定深入第一步否定深入原式原式第二步改名，以便把量词提到前面。第二步改名，以便把量词提到前面。例题例题3 把公式把公式练习75页（1）题将约束变元x改名为u，将约束变元y改

6、名为z，化为前束范式化为前束范式第11页/共26页例2:求下列公式的前束范式。第12页/共26页解:第13页/共26页 第14页/共26页 第15页/共26页 第16页/共26页2.5.2前束析取范式和前束合取范式(Prenex disjunctive normal form&Prenex conjunctive normal form)在前束范式的基础上,可以定义前束析(合)取范式.定义2.6.2:任何一个谓词公式A，如果具有如下形式则称为前束合取范式：(x1)(x2)(xn)(A11A12A1k1)(A21A22A2k2)(Am1Am2Amkm)其 中 n大 于 等 于1,Aij(j=1,

7、ki,i=1,2,3,m)为原子谓词公式或其否定,为量词或量词，xi（i=1，n）为客体变元.第17页/共26页任何一个谓词公式A，如果具有如下形式则称为前束析取范式：(x1)(x2)(xn)(A11A12A1k1)(A21A22A2k2)(Am1Am2Amkm)其中n大于等于1,Aij(j=1,ki,i=1,2,3,m)为原子谓词公式或其否定,为量词或量词，xi（i=1，n）为客体变元.定理2.6.2:每一个谓词公式都可以转化为与其等价的前束析(合)取范式.第18页/共26页二、前束合取范式定义2-6.2 一个wffA称为前束合取范式，如果它有如下形式：(Q1x1)(Q2x2)(Qkxk)(

8、A11A12A1l1)(A21A22A2l2)(Am1Am2Amlm)其中Qi(1ik)为量词或，xi(i=1,2,n)是客体变元，Aij是原子公式或其否定。例如公式例如公式是前束合取范式是前束合取范式第19页/共26页定理定理2-6.2 每一个每一个wffA都可转化为与其等价的前束合取范式。都可转化为与其等价的前束合取范式。例题例题4 将将wffD：转化为与其等价的前束合取范式。转化为与其等价的前束合取范式。解解 第一步取消多余量词第一步取消多余量词第二步换名第二步换名第三步消去条件联结词第三步消去条件联结词第四步将否定深入第四步将否定深入第五步将量词推到左边第五步将量词推到左边(x x)(

9、)(z)z)(w)w)(P(x)P(x)R(x,w)R(x,w)(Q(z,y)Q(z,y)R(x,w)R(x,w)第20页/共26页三、前束析取范式定义2-6.3 一个wffA称为前束析取范式，如果它有如下形式：(Q1x1)(Q2x2)(Qkxk)(A11A12A1l1)(A21A22A2l2)(Am1Am2Amlm)其中Qi(1ik)为量词或，xi(i=1,2,n)是客体变元，Aij是原子公式或其否定。例如公式例如公式是前束是前束析析取范式。取范式。)第21页/共26页定理2-6.3 每一个wffA都可转化为与其等价的前束析取范式。例题4 将wffD：转化为与其等价的前束析取范式。解解第22页/共26页小结：本节介绍了谓词公式的前束范式、前束析取范式和前束合取范式.重点掌握前束析取范式和前束合取范式求法。作业:第23页/共26页作业:求下列公式的前束析取范式和前束合取范式.第24页/共26页第25页/共26页谢谢您的观看！第26页/共26页