Chapter2_謂詞邏輯46前束范式

1、u 要求：理解前束范式、前束合取范式和前束析取范式的定義，要求：理解前束范式、前束合取范式和前束析取范式的定義，會(huì)將一個(gè)謂詞公式會(huì)將一個(gè)謂詞公式wffA化為前束范式、前束合取范式和前束析化為前束范式、前束合取范式和前束析取范式。取范式。u 學(xué)習(xí)本節(jié)的目的是掌握謂詞公式的標(biāo)準(zhǔn)化形式。學(xué)習(xí)本節(jié)的目的是掌握謂詞公式的標(biāo)準(zhǔn)化形式。u 重點(diǎn)：化謂詞公式為前束范式。重點(diǎn)：化謂詞公式為前束范式。復(fù)習(xí)：（1）量詞與聯(lián)結(jié)詞之間的關(guān)系（2）量詞擴(kuò)張/收縮律() ( )()( )x P xxP x () ( )()( )x P xxP x () ( )()( ( )x A xBxA xB () ( )()( ( )

2、x A xBxA xB () ( )()( )Bx A xx BA x () ( )()( )Bx A xx BA x 這里A(x)是任意包括個(gè)體變?cè)獂的謂詞公式，B是不包括個(gè)體變?cè)獂的任意謂詞公式。（3）量詞與命題聯(lián)結(jié)詞之間的一些等價(jià)式）量詞與命題聯(lián)結(jié)詞之間的一些等價(jià)式()( ( )( )() ( )() ( )x A xB xx A xx B x ()( ( )( )() ( )() ( )x A xB xx A xx B x 量詞分配律量詞分配律()( ( )( )() ( )() ( )x A xB xx A xx B x u（4）指導(dǎo)變?cè)?、作用域、約束變?cè)⒆杂勺冊(cè)┲笇?dǎo)變?cè)?、作用?/p>

3、、約束變?cè)?、自由變?cè)?) ( , )x P x y量詞指導(dǎo)變?cè)犛蚣s束變?cè)杂勺冊(cè)?）約束變?cè)獡Q名和自由變?cè)?在一公式中，有的個(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)過的個(gè)體變?cè)?，其余不變?自由變?cè)?對(duì)某自由出現(xiàn)的個(gè)體變?cè)捎脗€(gè)體常元或用與原子公式中所有個(gè)體變?cè)煌膫€(gè)體變?cè)ゴ耄姨幪幋搿?.6 前束范式前束范式(Prenex normal form2.6.1 前束范式前束范式(Prenex normal form 2.6.2 前束

4、析取范式和前束合取范式前束析取范式和前束合取范式(Prenex disjunctive normal form & Prenex conjunctive normal form 2.6.1前束范式前束范式(Prenex normal form u定義定義2.6.1:任何一個(gè)謂詞公式任何一個(gè)謂詞公式A，如果具有如下形式：，如果具有如下形式： (x1) (x2) (xn)B其中其中可能是量詞可能是量詞 或量詞或量詞 ， xi（i=1， n）是客體變是客體變?cè)?，B是不含量詞的是不含量詞的謂詞公式，則稱謂詞公式，則稱A是前束范式。是前束范式。u說明說明:前束范式前束范式的量詞均在全式的開頭的量詞均

5、在全式的開頭,它們的作用域延它們的作用域延伸到整個(gè)公式的末尾。伸到整個(gè)公式的末尾。u例例1: x y（F(x)G(y)）H(x,y)） x y(F(x,y)G(y,z) x H(x,y,z) u定理定理2.5.1:任何一個(gè)謂詞公式任何一個(gè)謂詞公式,均和一個(gè)前束范式等價(jià)。均和一個(gè)前束范式等價(jià)。前束范式的求法：前束范式的求法：第一步：否定深入。即利用量詞轉(zhuǎn)化公式，把否定聯(lián)結(jié)第一步：否定深入。即利用量詞轉(zhuǎn)化公式，把否定聯(lián)結(jié) 詞深入到命題變?cè)驮~深入到命題變?cè)椭^詞填式的謂詞填式的前面。前面。第二步：改名。即利用換名規(guī)則、代入規(guī)則更換一些變第二步：改名。即利用換名規(guī)則、代入規(guī)則更換一些變?cè)拿Q，以便

6、消除混亂。元的名稱，以便消除混亂。第三步：量詞前移。即利用量詞轄域的收縮與擴(kuò)張把量第三步：量詞前移。即利用量詞轄域的收縮與擴(kuò)張把量詞移到前面。這樣便可求出與公式等價(jià)的前束范式。詞移到前面。這樣便可求出與公式等價(jià)的前束范式。整理ppt10舉例 73頁 例題1，例題2，例題3整理ppt11例題例題2 化公式化公式( ( x x) )( ( y y)()( ( z)(P(x,z)z)(P(x,z)P(y,z)P(y,z)( ( u)Q(x,y,u)u)Q(x,y,u)為前束范式為前束范式解解 原公式原公式( ( x x) )( ( y y)()( ( z)(P(x,z)z)(P(x,z)P(y,z)

7、P(y,z)( ( u)Q(x,y,u)u)Q(x,y,u)( ( x x) )( ( y y)()( z)(z)(P(x,z)P(x,z)P(y,z)P(y,z)( ( u)Q(x,y,u)u)Q(x,y,u)( ( x x) )( ( y y)()( z)z)( ( u)(u)(P(x,z)P(x,z)P(y,z)P(y,z)Q(x,y,u)Q(x,y,u)整理ppt12()() ( , )()() ( , )()( ( , )( , )xy A x yxy B x yyA y xB x y () () ( , )()() ( , )()( ( , )( , )xy A x yxy B x

8、 yyA y xB x y ( )() ( , ) ()()( , ) ()( , )( , )xy A x yxyB x yyA y xB x y 解解 第一步否定深入第一步否定深入原式原式第二步改名，以便把量詞提到前面。第二步改名，以便把量詞提到前面。()() ( , )()()( , )()( , )( , )xy A x yuvB u vzA z uB u z ()()()()() ( , ) ( , )( , )( , )xyuvzA x yB u vA z uB u z 例題例題3 把公式把公式練習(xí)75頁（1）題將約束變?cè)獂改名為u，將約束變?cè)獃改名為z，化為前束范式化為前束范式例

9、例2:2:求下列公式的前束范式。求下列公式的前束范式。),(),()(),()(),()()6(),()()()(),()()5()()()()()4()()()()() 3()()()()()2()()()()() 1 (yxBxyAyyxByxyxAyxyxHxyGyyxFxxGxxFxxGxxFxxGxxFxxGxxFxu解解:)()()()()()()()()()()() 1 (量詞分配量詞轉(zhuǎn)換律xGxFxxGxxFxxGxxFx)()()()()()()()()()()()()()()()()()()()()2(轄域擴(kuò)張轄域擴(kuò)張換名量詞轉(zhuǎn)換律yGxFyxyGyxFxyGyxFxxGx

10、xFxxGxxFx )(,()(),()()()()(,()()(),()()()(,()()(),()()()(,()()()(),()()(,()()()(),()(),()()()(),()(),()()()(),()(),()()()(),()(),()()()(),()()5(轄域擴(kuò)張轄域擴(kuò)張轄域擴(kuò)張換名代入ztHyGzxFtyxztHtyGzxFyxztHtyGzxFyxztHtyGyzxFxzxHxyGyzxFxyxHxyGyyxFxyxHxyGyyxFxyxHxyGyyxFxyxHxyGyyxFxu (6)()() ( , )()() ( , )()( ( , )( , )()

11、 () ( , )()() ( , )()( , )( , )()() ( , )()()( , )()( ( , )( , )xy A x yxy B x yy A y xB x yxy A x yxy B x yyA y xB x yxy A x yxyB x yy A y xB x y ),(),(),(),()()()()()(,(),()(),()(),()(),(),()(),()(),()()6(zuBuzAvuByxAzvuyxzuBuzAzvuBvuyxAyxyxBxyAyyxByxyxAyx換名續(xù)2.5.2前束析取范式和前束合取范式前束析取范式和前束合取范式(Prenex

12、disjunctive normal form & Prenex conjunctive normal form u在前束范式的基礎(chǔ)上在前束范式的基礎(chǔ)上,可以定義前束析可以定義前束析(合合)取范式取范式.u定義定義2.6.2:任何一個(gè)謂詞公式任何一個(gè)謂詞公式A，如果具有如下形式則稱，如果具有如下形式則稱為前束合取范式：為前束合取范式： (x1) (x2)(xn)(A11A12A1k1) (A21A22A2k2 )(Am1Am2Amkm) 其其中中n大于等于大于等于1,Aij(j=1, ,ki ,i=1,2,3,m)為原子謂詞公為原子謂詞公式或其否定式或其否定,為為量詞量詞 或量詞或量詞 ， x

13、i（i=1， n）為）為客客體變?cè)w變?cè)? u任何一個(gè)謂詞公式任何一個(gè)謂詞公式A，如果具有如下形式則稱為前束析取范式：，如果具有如下形式則稱為前束析取范式： (x1) (x2)(xn)(A11A12A1k1)(A21A22A2k2 )(Am1Am2Amkm) 其中其中n大于等于大于等于1,Aij(j=1, ,ki ,i=1,2,3,m)為原子為原子謂詞公式或其否定謂詞公式或其否定,為為量詞量詞 或量詞或量詞 ，xi（i=1， n）為）為客體變?cè)腕w變?cè)? u定理定理2.6.2:每一個(gè)謂詞公式都可以轉(zhuǎn)化為與其等價(jià)的前束析每一個(gè)謂詞公式都可以轉(zhuǎn)化為與其等價(jià)的前束析(合合)取取范式范式.u二、前束合

14、取范式二、前束合取范式u定義定義2-6.2 2-6.2 一個(gè)一個(gè)wffAwffA稱為前束合取范式，如果它有如下形式：稱為前束合取范式，如果它有如下形式：u(Q(Q1 1x x1 1)(Q)(Q2 2x x2 2) )(Q(Qk kx xk k)(A)(A1111A12A1l1)(A(A2121A22A2l2) (A(Am1m1Am2Amlm)u其中其中Q Qi i(1ik)(1ik)為量詞為量詞 或或 ，x xi i(i=1,2, (i=1,2, ,n),n)是客體變?cè)?，是客體變?cè)?，A Aijij是原子公式或其否定。是原子公式或其否定。()()()()() ( )()xzyPxazbQ yab

15、 ()()()( ( )( )( ( )( , )( , )( )( , )( , )xuzP xP uP xQ y zQ x yP uQ x yQ y z 例如公式例如公式是前束合取范式是前束合取范式整理ppt21定理定理2-6.2 每一個(gè)每一個(gè)wffA都可轉(zhuǎn)化為與其等價(jià)的前束合取范式。都可轉(zhuǎn)化為與其等價(jià)的前束合取范式。例題例題4 將將wffD： 轉(zhuǎn)化為與其等價(jià)的前束合取范式。轉(zhuǎn)化為與其等價(jià)的前束合取范式。()() ( )() ( , )() ( , )xy P xz Q z yy R x y () ( )() ( , )() ( , )Dx P xz Q z yy R x y () ( )

16、() ( , )() ( , )Dx P xz Q z yw R x w () ( ( )() ( , )() ( ,)DxP xz Q z yw R x w 解解 第一步取消多余量詞第一步取消多余量詞第二步換名第二步換名第三步消去條件聯(lián)結(jié)詞第三步消去條件聯(lián)結(jié)詞第四步將否定深入第四步將否定深入第五步將量詞推到左邊第五步將量詞推到左邊()( ) ( )( , ) ()( , )DxP xzQ z yw R x w ()()()( )( , )( , )DxzwP xQ z yR x w ( ( x x)()( z)z)( ( w)(w)(P(x)P(x)R(x,w)R(x,w)( (Q(z,y)

17、Q(z,y)R(x,w)R(x,w)u三、前束析取范式三、前束析取范式u定義定義2-6.3 2-6.3 一個(gè)一個(gè)wffAwffA稱為前束析取范式，如果它有如下形稱為前束析取范式，如果它有如下形式：式：u(Q(Q1 1x x1 1)(Q)(Q2 2x x2 2) )(Q(Qk kx xk k)(A)(A1111A12A1l1) (A(A2121A22A2l2) (A(Am1m1Am2Amlm)u其中其中Q Qi i(1ik)(1ik)為量詞為量詞 或或 ，x xi i(i=1,2, (i=1,2, ,n),n)是客體變是客體變?cè)?，元，A Aijij是原子公式或其否定。是原子公式或其否定。()()

18、()( ( )( , )( ( )( , )xuzP xQ x yP uQ y z例如公式例如公式是前束是前束析析取范式。取范式。)定理定理2-6.3 每一個(gè)每一個(gè)wffA都可轉(zhuǎn)化為與其等價(jià)的前束析取范式。都可轉(zhuǎn)化為與其等價(jià)的前束析取范式。例題例題4 將將wffD： 轉(zhuǎn)化為與其等價(jià)的前束析取范式。轉(zhuǎn)化為與其等價(jià)的前束析取范式。()( ( )( , )() ( )() ( , )x P xQ x yy P yz Q y z ()( )( , ) () ( ) () ( , )DxP xQ x yy P yz Q y z ()( ( )( , ) () ( ) () ( , )x P xQ x yu P uz Q y z ()()()( ( )( , ) ( ( )( , )xuz P