1、离散数学 Discrete Mathematics 1 第5讲 26 前束范式 要求：理解前束范式、前束合取范式和前束 析取范式的定义，会将一个谓词公式wffA化 为前束范式、前束合取范式和前束析取范式 。 学习本节的目的是掌握谓词公式的标准化形 式。 重点：化谓词公式为前束范式。 2 复习： （1）量词与联结词之间的关系 （2）量词扩张/收缩律 这里A(x)是任意包括个体变元x的谓词公式，B 是不包括个体变元x的任意谓词公式。 3 （3）量词与命题联结词之间的一些等价式 量词分配律 4 （4）指导变元、作用域、约束变元、自由变元 量 词 指 导 变 元 辖 域 约 束 变 元 自 由 变 元
2、 5 （5）约束变元换名和自由变元代入 在一公式中，有的个体变元既是约束出现， 又是自由出现，这就容易产生混淆。为了避免混 淆，可对约束变元换名或自由变元代入。 约束变元换名 将量词辖域中某个约束出现的个体变元及相 应指导变元，改成本辖域中未曾出现过的个体变 元，其余不变。 自由变元代入 对某自由出现的个体变元可用个体常元或用 与原子公式中所有个体变元不同的个体变元去代 入，且处处代入。 6 一、前束范式 定义2-6.1 一个合式公式称为前束范式，如果它有如下形式： (Q1x1)(Q2x2)(Qkxk)A 其中Qi(1ik)为或，A为不含有量词的谓词公式。称 Q1x1Q2x2Qkxk为公式的首
3、标。 特别地，若中无量词，则也看作是前束范式。 可见，前束范式的特点是，所有量词均非否定地出现在 公式最前面，且它的辖域一直延伸到公式之末。 例如，(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)不是前束范式。 7 定理2.6.1 (前束范式存在定理) Lp中任意公式A都有与之等价 的前束范式。 斯柯林范式 前束范式的优点是全部量词集中在公式前面，其缺点是各量词 的排列无一定规则，这样当把一个公式化归为前束范式时， 其表达形式会显现多种情形，不便应用。1920年斯柯林 (Skolem)提出对前束范式
4、首标中量词出现的次序给出规定： 每个存在量词均在全称量词之前。按此规定得到的范式形式 ，称为斯柯林范式。显然，任一公式均可化为斯柯林范式。 它的优点是：全公式按顺序可分为三部分，公式的所有存在 量词、所有全称量词和辖域。这给Lp的研究提供了一定的方 便。 8 举例 73页 例题1，例题2，例题3 9 例题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
5、,y,u) 10 解 第一步否定深入 原式 第二步改名，以便把量词提到前面。 例题3 把公式 练习 75页（1）题 将约束变元x改名为u， 将约束变元y改名为z， 化为前束范式 11 二、前束合取范式 定义2-6.2 一个wffA称为前束合取范式，如果它有如下形式 ： (Q1x1)(Q2x2)(Qkxk)(A11A12A1l1)(A21A22 A2l2) (Am1Am2Amlm) 其中Qi(1ik)为量词或，xi(i=1,2, ,n)是客体变元， Aij是原子公式或其否定。 例如公式 是前束合取范式 12 定理2-6.2 每一个wffA都可转化为与其等价的前束合取范式。 例题4 将wffD：
6、转化为与其等价的前束合取范式。 解 第一步取消多余量词 第二步换名 第三步消去条件联结词 第四步将否定深入 第五步将量词推到左边 (x)(z)(w)(P(x)R(x,w)(Q(z,y)R(x,w) 13 三、前束析取范式 定义2-6.3 一个wffA称为前束析取范式，如果它有如下形 式： (Q1x1)(Q2x2)(Qkxk)(A11A12A1l1) (A21A22A2l2) (Am1Am2Amlm) 其中Qi(1ik)为量词或，xi(i=1,2, ,n)是客体变元 ，Aij是原子公式或其否定。 例如公式 是前束析取范式。 ) 14 定理2-6.3 每一个wffA都可转化为与其等价的前束析取范式。 例题4 将wffD： 转化为与其等价的前束析取范式。 解 15 练习 75页 （2） 16
