1、離散數(shù)學 Discrete Mathematics,第5講 26 前束范式,要求：理解前束范式、前束合取范式和前束析取范式的定義，會將一個謂詞公式wffA化為前束范式、前束合取范式和前束析取范式。 學習本節(jié)的目的是掌握謂詞公式的標準化形式。 重點：化謂詞公式為前束范式。,復習：,（1）量詞與聯(lián)結(jié)詞之間的關(guān)系,（2）量詞擴張/收縮律,這里A(x)是任意包括個體變元x的謂詞公式，B是不包括個體變元x的任意謂詞公式。,（3）量詞與命題聯(lián)結(jié)詞之間的一些等價式,量詞分配律,（4）指導變元、作用域、約束變元、自由變元,量詞,指導變元,轄域,約束變元,自由變元,（5）約束變元換名和自由變元代入 在一公式中，

2、有的個體變元既是約束出現(xiàn)，又是自由出現(xiàn)，這就容易產(chǎn)生混淆。為了避免混淆，可對約束變元換名或自由變元代入。 約束變元換名 將量詞轄域中某個約束出現(xiàn)的個體變元及相應指導變元，改成本轄域中未曾出現(xiàn)過的個體變元，其余不變。 自由變元代入 對某自由出現(xiàn)的個體變元可用個體常元或用與原子公式中所有個體變元不同的個體變元去代入，且處處代入。,一、前束范式 定義2-6.1 一個合式公式稱為前束范式，如果它有如下形式： (Q1x1)(Q2x2)(Qkxk)A 其中Qi(1ik)為或，A為不含有量詞的謂詞公式。稱Q1x1Q2x2Qkxk為公式的首標。 特別地，若中無量詞，則也看作是前束范式。 可見，前束范式的特點是

3、，所有量詞均非否定地出現(xiàn)在 公式最前面，且它的轄域一直延伸到公式之末。 例如，(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都有與之等價的前束范式。 斯柯林范式 前束范式的優(yōu)點是全部量詞集中在公式前面，其缺點是各量詞的排列無一定規(guī)則，這樣當把一個公式化歸為前束范式時，其表達形式會顯現(xiàn)多種情形，不便應用。1920年斯柯林(Skolem)提出對前束范式首標中量詞出現(xiàn)的次序給出規(guī)定：每個存在量詞均在全稱量詞之前。按此規(guī)定得到的范式形式

4、，稱為斯柯林范式。顯然，任一公式均可化為斯柯林范式。它的優(yōu)點是：全公式按順序可分為三部分，公式的所有存在量詞、所有全稱量詞和轄域。這給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),解 第一步否定深入,原式,第二步改名，以便把量詞提到前面。,例題3 把公式,練習 75頁（

5、1）題,將約束變元x改名為u，將約束變元y改名為z，,化為前束范式,二、前束合取范式 定義2-6.2 一個wffA稱為前束合取范式，如果它有如下形式： (Q1x1)(Q2x2)(Qkxk)(A11A12A1l1)(A21A22A2l2) (Am1Am2Amlm) 其中Qi(1ik)為量詞或，xi(i=1,2, ,n)是客體變元，Aij是原子公式或其否定。,例如公式,是前束合取范式,定理2-6.2 每一個wffA都可轉(zhuǎn)化為與其等價的前束合取范式。,例題4 將wffD：,轉(zhuǎn)化為與其等價的前束合取范式。,解 第一步取消多余量詞,第二步換名,第三步消去條件聯(lián)結(jié)詞,第四步將否定深入,第五步將量詞推到左邊,(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是原子公式或其否定。,例