Chapter2_谓词逻辑4(6前束范式)ppt课件

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

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

3、enex disjunctive normal form & Prenex conjunctive normal form),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) x H(x,

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

5、,z)(u)Q(x,y,u),(x)(y)(z)(u)(P(x,z)P(y,z)Q(x,y,u),.,解 第一步否定深入,原式,第二步改名，以便把量词提到前面。,例题3 把公式,练习 75页（1）题,将约束变元x改名为u，将约束变元y改名为z，,化为前束范式,例2:求下列公式的前束范式。,解:,2.5.2前束析取范式和前束合取范式(Prenex disjunctive normal form & Prenex conjunctive normal form) 在前束范式的基础上,可以定义前束析(合)取范式. 定义2.6.2:任何一个谓词公式A，如果具有如下形式则称为前束合取范式： (x1) (

6、x2)(xn)(A11A12A1k1) (A21A22A2k2 )(Am1Am2Amkm) 其中n大于等于1,Aij(j=1, ,ki ,i=1,2,3,m)为原子谓词公式或其否定,为量词或量词， xi（i=1， n）为客体变元.,任何一个谓词公式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:每一个谓词公式都可以转化为与其等价的前束析(合)

7、取范式.,二、前束合取范式 定义2-6.2 一个wffA称为前束合取范式，如果它有如下形式： (Q1x1)(Q2x2)(Qkxk)(A11A12A1l1)(A21A22A2l2) (Am1Am2Amlm) 其中Qi(1ik)为量词或，xi(i=1,2, ,n)是客体变元，Aij是原子公式或其否定。,例如公式,是前束合取范式,.,定理2-6.2 每一个wffA都可转化为与其等价的前束合取范式。,例题4 将wffD：,转化为与其等价的前束合取范式。,解 第一步取消多余量词,第二步换名,第三步消去条件联结词,第四步将否定深入,第五步将量词推到左边,(x)(z)(w)(P(x)R(x,w)(Q(z,y)R(x,w),三、前束析取范式 定义2-6.3 一个wffA称为前束析取范式，如果它有如下形式： (Q1x1)(Q2x2)(Qkxk)(A11A12A1l1) (A21A22A2l2) (Am1Am2Amlm) 其中Qi(1ik)为量词或，xi(i=1,2, ,n)是客体变元，Aij是原子公式或其否定。,例如公式,是前束析取范式。,),定理2-6.3 每一个wffA都可转化为与其等价的