Chapter謂詞邏輯前束范式

會(huì)計(jì)學(xué)1Chapter謂詞邏輯前束范式第5講§2—6前束范式要求：理解前束范式、前束合取范式和前束析取范式的定義，會(huì)將一個(gè)謂詞公式wffA化為前束范式、前束合取范式和前束析取范式。學(xué)習(xí)本節(jié)的目的是掌握謂詞公式的標(biāo)準(zhǔn)化形式。重點(diǎn)：化謂詞公式為前束范式。第1頁/共26頁復(fù)習(xí)：（1）量詞與聯(lián)結(jié)詞?之間的關(guān)系（2）量詞擴(kuò)張/收縮律這里A(x)是任意包括個(gè)體變?cè)獂的謂詞公式，B是不包括個(gè)體變?cè)獂的任意謂詞公式。第2頁/共26頁（3）量詞與命題聯(lián)結(jié)詞之間的一些等價(jià)式量詞分配律第3頁/共26頁（4）指導(dǎo)變?cè)?、作用域、約束變?cè)?、自由變?cè)吭~指導(dǎo)變?cè)犛蚣s束變?cè)杂勺冊(cè)?頁/共26頁（5）約束變?cè)獡Q名和自由變?cè)朐谝还街?，有的個(gè)體變?cè)仁羌s束出現(xiàn)，又是自由出現(xiàn)，這就容易產(chǎn)生混淆。為了避免混淆，可對(duì)約束變?cè)獡Q名或自由變?cè)搿?/p>

約束變?cè)獡Q名將量詞轄域中某個(gè)約束出現(xiàn)的個(gè)體變?cè)跋鄳?yīng)指導(dǎo)變?cè)某杀据犛蛑形丛霈F(xiàn)過的個(gè)體變?cè)?，其余不變?/p>

自由變?cè)雽?duì)某自由出現(xiàn)的個(gè)體變?cè)捎脗€(gè)體常元或用與原子公式中所有個(gè)體變?cè)煌膫€(gè)體變?cè)ゴ耄姨幪幋?。?頁/共26頁第二章謂詞邏輯（PredicateLogic）

2.6前束范式(PrenexNormalForm)2.6前束范式(Prenexnormalform)2.6.1前束范式(Prenexnormalform)

2.6.2前束析取范式和前束合取范式(Prenexdisjunctivenormalform&Prenexconjunctivenormalform)

第6頁/共26頁

2.6前束范式(PrenexNormalForm)2.6.1前束范式(Prenexnormalform)

定義2.6.1:任何一個(gè)謂詞公式A，如果具有如下形式：

(□x1)(□x2)…(□xn)B其中□可能是量詞或量詞，xi（i=1，…n）是客體變?cè)珺是不含量詞的謂詞公式，則稱A是前束范式。說明:前束范式的量詞均在全式的開頭,它們的作用域延伸到整個(gè)公式的末尾。例1:xy（（F(x)∧G(y)）∧┐H(x,y)）√xy(F(x,y)∧G(y,z))∨xH(x,y,z)×第7頁/共26頁定理2.5.1:任何一個(gè)謂詞公式,均和一個(gè)前束范式等價(jià)。前束范式的求法：第一步：否定深入。即利用量詞轉(zhuǎn)化公式，把否定聯(lián)結(jié)詞深入到命題變?cè)椭^詞填式的前面。第二步：改名。即利用換名規(guī)則、代入規(guī)則更換一些變?cè)拿Q，以便消除混亂。第三步：量詞前移。即利用量詞轄域的收縮與擴(kuò)張把量詞移到前面。這樣便可求出與公式等價(jià)的前束范式。第8頁/共26頁舉例73頁例題1，例題2，例題3第9頁/共26頁例題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))第10頁/共26頁解第一步否定深入原式第二步改名，以便把量詞提到前面。例題3把公式練習(xí)75頁（1）題將約束變?cè)獂改名為u，將約束變?cè)獃改名為z，化為前束范式第11頁/共26頁例2:求下列公式的前束范式。第12頁/共26頁解:第13頁/共26頁

第14頁/共26頁

第15頁/共26頁

第16頁/共26頁2.5.2前束析取范式和前束合取范式(Prenexdisjunctivenormalform&Prenexconjunctivenormalform)

在前束范式的基礎(chǔ)上,可以定義前束析(合)取范式.定義2.6.2:任何一個(gè)謂詞公式A，如果具有如下形式則稱為前束合取范式：

(□x1)(□x2)…(□xn)[(A11∨A12∨…∨A1k1)∧

(A21∨A22∨…∨A2k2)∧…∧(Am1∨Am2∨…∨Amkm)]

其中n大于等于1,Aij(j=1,…,ki,i=1,2,3,…,m)為原子謂詞公式或其否定,□為量詞或量詞，xi（i=1，…n）為客體變?cè)?第17頁/共26頁任何一個(gè)謂詞公式A，如果具有如下形式則稱為前束析取范式：

(□x1)(□x2)…(□xn)[(A11∧A12∧…∧A1k1)∨(A21∧A22∧…∧A2k2)∨…∨(Am1∧Am2∧…∧Amkm)]

其中n大于等于1,Aij(j=1,…,ki,i=1,2,3,…,m)為原子謂詞公式或其否定,□為量詞或量詞，xi（i=1，…n）為客體變?cè)?定理2.6.2:每一個(gè)謂詞公式都可以轉(zhuǎn)化為與其等價(jià)的前束析(合)取范式.第18頁/共26頁二、前束合取范式定義2-6.2一個(gè)wffA稱為前束合取范式，如果它有如下形式：(Q1x1)(Q2x2)…(Qkxk)[(A11∨A12∨…∨A1l1)∧(A21∨A22∨…∨A2l2)∧…∧(Am1∨Am2∨…∨Amlm)]其中Qi(1≤i≤k)為量詞或，xi(i=1,2,…,n)是客體變?cè)?，Aij是原子公式或其否定。例如公式是前束合取范式第19頁/共26頁定理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))]第20頁/共26頁三、前束析取范式定義2-6.3一個(gè)wffA稱為前束析取范式，如果它有如下形式：(Q1x1)(Q2x2)…(Qkxk)[(A11∧A12∧…∧A1l1)∨(A21∧A22∧…∧A2l2)∨…∨(Am1∧Am2∧…∧Amlm)]其中Qi(1≤i≤k)為量詞或，xi(i=1,2,…,n)是客體變?cè)?，Aij是原子公式或其否定。例如公式是前束析取范式。)第21頁/共26頁定理2-6.3每一個(gè)wffA都可轉(zhuǎn)化為與其等價(jià)的前束析取范式。例