资源描述：
《第5讲§2—6前束范式（先回顾命题的几种范式及唯一性）（》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第5讲§2—6前束范式（先回顾命题的几种范式及唯一性）(不唯一）要求：理解前束范式、前束合取范式和前束析取范式的定义，会将一个谓词公式wffA化为前束范式、前束合取范式和前束析取范式。目的：是掌握谓词公式的标准化形式。重点：化谓词公式为前束范式。（1）指导变元、作用域、约束变元、自由变元量词指导变元辖域约束变元自由变元复习：（2）约束变元换名和自由变元代入在一公式中，有的个体变元既是约束出现，又是自由出现，这就容易产生混淆。为了避免混淆，可对约束变元换名或自由变元代入。约束变元换名将量词辖域中某个约束出现的个体变元及
2、相应指导变元，改成本辖域中未曾出现过的个体变元，其余不变。自由变元代入对某自由出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且处处代入。（3）量词与联结词¬之间的关系（后面化范式时用到）（4）量词扩张/收缩律（后面化范式时用到）这里A(x)是任意包括个体变元x的谓词公式，B是不包括个体变元x的任意谓词公式。（5）量词与命题联结词之间的一些等价式（后面化范式时用到）量词分配律一、前束范式（prenexnormalforms）定义2-6.1一个公式，若量词均①非否定地出现在全式的开头，它们的
3、作用域，延伸到②整个公式的末尾，则该公式叫前束范式。即：一个合式公式称为前束范式，如果它有如下形式：(Q1x1)(Q2x2)…(Qkxk)A其中Qi(1≤i≤k)为或，xi(1≤i≤k)为客体变元,A为不含有量词的谓词公式.称Q1x1Q2x2…Qkxk为公式的首标。特别地，不含量词的公式也看作是前束范式。【例】(x)(y)(z)(P(x,y)Q(y,z)),R(x,y)等都是前束范式，而(x)P(x)(y)Q(y),(x)(P(x)(y)Q(x,y))不是前束范式。x不是谓词公式，所以也非
4、前束范式,但Ｐ是命题变元，所以是前束范式．(x)┐(y)(z)(P(x,y)Q(y,z))也不是（¬(x)P(x)(x)¬P(x)；¬(x)P(x)(x)¬P(x)）(对定义中①）（还有其它的6个（或更多）也可，还有量词的深入等）(对定义中②）定理2.6.1(前束范式存在定理)谓词逻辑中任意公式A都有与之等价的前束范式。化A公式为前束范式的步骤：（0）消去多余量词；（1）将A化为受限公式（此步有时也可省,主要是为复杂公式化为前束范式作准备,另外也为化前束析(合)取范式作准备）；（2）将A中的否定“
5、¬”深入到原子公式前且使每个原子（为化前束析（合）取范式作准备）公式前最多只有一个“¬”（用量词转化率、德根定律、双重否定率等）；（3）将约束变元改名（因对自由变元代入有可能不等价），使①不同量词的约束变元均不同名，②且约束变元与自由变元也不同名（此步有时也可省，如：(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)）；（4）将所有量词均提到公式最前面，且使它们的辖域延伸到公式最末（即量词作用域的扩张）。（也可改名后再做）【例】【例】化公式(x)(y)((z)(P(x,z)∧P(y,z))(
6、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,z))∨(u)Q(x,y,u))(x)(y)(z)(u)(┐P(x,z)∨┐P(y,z)∨Q(x,y,u))注：一定要考察自由变元与约束变元有无重名，换名后可直接提取量词，不用再看“B”是否有冲突。解第一步否定深入原式第二步改名（一般把后出现的同名约束变元改名），以便把量词提到前面。【例】把公式化为前束范式（此式并没先化为受
7、限公式）此题有错！请注意二、前束合取范式定义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都可转化为与其等价的前束合取范式。【例】将wffD：转化为与其等价的前束合取范式。解第一步取消多余量词第
8、二步换名第三步消去条件联结词第四步将否定深入（第二步可放在此步后）第五步将量词推到左边(x)(z)(w)[(┐P(x)∨┐R(x,w))∧(┐Q(z,y)∨┐R(x,w))]三、前束析取范式定义2-6.3一个wffA称为前束析取范式，如果它有如下形式：(Q1x1)(Q2x2)…(Qkxk)[(A11∧A12∧…∧A1l1)∨(A21∧A
