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

2、有的個(gè)體變?cè)仁羌s束出現(xiàn)，又是自由出現(xiàn)，這就容易產(chǎn)生混淆。為了避免混淆，可對(duì)約束變?cè)獡Q名或自由變?cè)搿?約束變?cè)獡Q名 將量詞轄域中某個(gè)約束出現(xiàn)的個(gè)體變?cè)跋鄳?yīng)指導(dǎo)變?cè)?，改成本轄域中未曾出現(xiàn)過(guò)的個(gè)體變?cè)?，其余不變?自由變?cè)?對(duì)某自由出現(xiàn)的個(gè)體變?cè)捎脗€(gè)體常元或用與原子公式中所有個(gè)體變?cè)煌膫€(gè)體變?cè)ゴ耄姨幪幋搿?一、前束范式 定義2-6.1 一個(gè)合式公式稱為前束范式，如果它有如下形式： (Q1x1)(Q2x2)(Qkxk)A 其中Qi(1ik)為或，A為不含有量詞的謂詞公式。稱Q1x1Q2x2Qkxk為公式的首標(biāo)。 特別地，若中無(wú)量詞，則也看作是前束范式。 可見，前束范式的特點(diǎn)是

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都有與之等價(jià)的前束范式。 斯柯林范式 前束范式的優(yōu)點(diǎn)是全部量詞集中在公式前面，其缺點(diǎn)是各量詞的排列無(wú)一定規(guī)則，這樣當(dāng)把一個(gè)公式化歸為前束范式時(shí)，其表達(dá)形式會(huì)顯現(xiàn)多種情形，不便應(yīng)用。1920年斯柯林(Skolem)提出對(duì)前束范式首標(biāo)中量詞出現(xiàn)的次序給出規(guī)定：每個(gè)存在量詞均在全稱量詞之前。按此規(guī)定得到的范式形式

4、，稱為斯柯林范式。顯然，任一公式均可化為斯柯林范式。它的優(yōu)點(diǎn)是：全公式按順序可分為三部分，公式的所有存在量詞、所有全稱量詞和轄域。這給Lp的研究提供了一定的方便。,舉例 73頁(yè) 例題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 把公式,練習(xí) 75頁(yè)（

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