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

《Chapter2_谓词逻辑4(6前束范式).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、alform&Prenexconjunctivenormalform)2.6前束范式(PrenexNormalForm)2.6.1前束范式(Prenexnormalform)定义2.6.1:任何一个谓词公式A，如果具有如下形式：(□x1)(□x2)…(□xn)B其中□可能是量词或量词，xi（i=1，…n）是客体变元，B是不含量词的谓词公式，则称A是前束范式。说明:前束范式的量词均在全式的开头,它们的作用域延伸到整个公式的末尾。例1:xy（（F(x)∧G(y)）∧┐H(x,y)）√xy(F(x,y)∧G(y,z))∨xH(x,y,z)×定理2.5.1:任何一个谓

4、词公式,均和一个前束范式等价。前束范式的求法：第一步：否定深入。即利用量词转化公式，把否定联结词深入到命题变元和谓词填式的前面。第二步：改名。即利用换名规则、代入规则更换一些变元的名称，以便消除混乱。第三步：量词前移。即利用量词辖域的收缩与扩张把量词移到前面。这样便可求出与公式等价的前束范式。举例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(

5、y,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前束析取范式和前束合取范式(Prenexdisjunctivenormalform&Prenexconjunctivenormalform)在前束范式的基础上,可以定义前束析(合)取范式.定义2.6.2:任何一个谓词公式A，如果具有如下形式则称为前束合取范式：(□x1)(□x

6、2)…(□xn)[(A11∨A12∨…∨A1k1)∧(A21∨A22∨…∨A2k2)∧…∧(Am1∨Am2∨…∨Amkm)]其中n大于等于1,Aij(j=1,…,ki,i=1,2,3,…,m)为原子谓词公式或其否定,□为量词或量词，xi（i=1，…n）为客体变元.任何一个谓词公式A，如果具有如下形式则称为前束析取范式：(□x1)(□x2)…(□xn)[(A11∧A12∧…∧A1k1)∨(A21∧A22∧…∧A2k2)∨…∨(Am1∧Am2∧…∧Amkm)]其中n大于等于1,Aij(j=1,…,ki,i=1,2,3,…,m)为原子谓词公式或其否定,□为量词或量词，xi

7、（i=1，…n）为客体变元.定理2.6.2:每一个谓词公式都可以转化为与其等价的前束析(合)取范式.二、前束合取范式定义2-6.2一个wffA称为前束合取范式，如果它有如下形式：(Q1x1)(Q2x2)…(Qkxk)[(A11∨A12∨…∨A1l1)∧(A21∨A22∨…∨A2l2)∧…∧(Am1∨Am2∨…∨Amlm)]其中Qi(1≤i≤k)为量词或，xi(i=1,2,…,n)是客体变元，Aij是原子公式或其否定。例如公式是前束合取范式定理2-6.2每一个wffA都可转化为与其等价的前束合取范式。例题4将wf