离散数学 前束范式

离散数学DiscreteMathematics第5讲§2—6前束范式要求：理解前束范式、前束合取范式和前束析取范式的定义，会将一个谓词公式wffA化为前束范式、前束合取范式和前束析取范式。学习本节的目的是掌握谓词公式的标准化形式。重点：化谓词公式为前束范式。复习：（1）量词与联结词¬之间的关系（2）量词扩张/收缩律()()()()xPxxPx()()()()xPxxPx()()()(())xAxBxAxB()()()(())xAxBxAxB()()()(())BxAxxBAx()()()(())BxAxxBAx这里A(x)是任意包括个体变元x的谓词公式，B是不包括个体变元x的任意谓词公式。（3）量词与命题联结词之间的一些等价式()(()())()()()()xAxBxxAxxBx()(()())()()()()xAxBxxAxxBx量词分配律()(()())()()()()xAxBxxAxxBx（4）指导变元、作用域、约束变元、自由变元()(,)xPxy量词指导变元辖域约束变元自由变元（5）约束变元换名和自由变元代入在一公式中，有的个体变元既是约束出现，又是自由出现，这就容易产生混淆。为了避免混淆，可对约束变元换名或自由变元代入。约束变元换名将量词辖域中某个约束出现的个体变元及相应指导变元，改成本辖域中未曾出现过的个体变元，其余不变。自由变元代入对某自由出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且处处代入。一、前束范式定义2-6.1一个合式公式称为前束范式，如果它有如下形式：(Q1x1)(Q2x2)…(Qkxk)A其中Qi(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))不是前束范式。定理2.6.1(前束范式存在定理)Lp中任意公式A都有与之等价的前束范式。斯柯林范式前束范式的优点是全部量词集中在公式前面，其缺点是各量词的排列无一定规则，这样当把一个公式化归为前束范式时，其表达形式会显现多种情形，不便应用。1920年斯柯林(Skolem)提出对前束范式首标中量词出现的次序给出规定：每个存在量词均在全称量词之前。按此规定得到的范式形式，称为斯柯林范式。显然，任一公式均可化为斯柯林范式。它的优点是：全公式按顺序可分为三部分，公式的所有存在量词、所有全称量词和辖域。这给Lp的研究提供了一定的方便。举例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,z))∨(u)Q(x,y,u))(x)(y)(z)(u)(┐P(x,z)∨┐P(y,z)∨Q(x,y,u))(){()(,)()()[(,)()((,)(,))]}xyAxyxyBxyyAyxBxy(){()(,)()()[(,)()((,)(,))]}xyAxyxyBxyyAyxBxy(){()(,)()()[(,)()((,)(,))]}xyAxyxyBxyyAyxBxy解第一步否定深入原式第二步改名，以便把量词提到前面。(){()(,)()()[(,)()((,)(,))]}xyAxyuvBuvzAzuBuz()()()()(){(,)[(,)((,)(,))]}xyuvzAxyBuvAzuBuz例题3把公式练习75页（1）题将约束变元x改名为u，将约束变元y改名为z，化为前束范式二、前束合取范式定义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是原子公式或其否定。()()(){[()()][()()]}xzyPxazbQyab例如公式()()()((()())(()(,))((,)())((,)(,)))xuzPxPuPxQyzQxyPuQxyQyz是前束合取范式定理2-6.2每一个wffA都可转化为与其等价的前束合取范式。例题4将wffD：转化为与其等价的前束合取范式。()[()()()(,)()(,)]xyPxzQzyyRxy()[()()(,)()(,)]DxPxzQzyyRxy()[()()(,)()(,)]DxPxzQzywRxw解第一步取消多余量词第二步换名第三步消去条件联结词第四步将否定深入第五步将量词推到左边()[(()()(,))()(,)]DxPxzQzywRxw()[()()(,))()(,)]DxPxzQzywRxw()()()[(()(,))(,)]DxzwPxQzyRxw(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∧A22∧…∧A2l2)∨…∨(Am1∧Am2∧…∧Amlm)]其中Qi(1≤i≤k)为量词或，xi(i=1,2,…,n)是客体变元，Aij是原子公式或其否定。例如公式是前束析取范式。()()()((()(,))(()(,))xuzPxQxyPuQyz)定理2-6.3每一个wffA都可转化为与其等价的前束析取范式。例题4将wffD：转化为与其等价的前束析取范式。()(()(,))(()()()(,))xPxQxyyPyzQyz()(()(,))(()()()(,))DxPxQxyyPyzQyz()(()(,))(()()()(,))xPxQxyuPuzQyz()()()(()(,))(()(,))xuzPxQxyPuQyz解练习75页（2）