Chapter2_謂詞邏輯4(6前束范式)

1、u 要求：理解前束范式、前束合取范式和前束析取范式的定義，要求：理解前束范式、前束合取范式和前束析取范式的定義，會將一個謂詞公式會將一個謂詞公式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)是任意包括個體變元x的謂詞公式，B是不包括個體變元x的任意謂詞公式。（3）量詞與命題聯(lián)結(jié)詞之間的一些等價式）量詞與命題聯(lián)結(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)變元、作用域、約束變元、自由變元）指導(dǎo)變元、作用域

3、、約束變元、自由變元() ( , )x P x y量詞指導(dǎo)變元轄域約束變元自由變元（5）約束變元換名和自由變元代入 在一公式中，有的個體變元既是約束出現(xiàn)，又是自由出現(xiàn)，這就容易產(chǎn)生混淆。為了避免混淆，可對約束變元換名或自由變元代入。 約束變元換名 將量詞轄域中某個約束出現(xiàn)的個體變元及相應(yīng)指導(dǎo)變元，改成本轄域中未曾出現(xiàn)過的個體變元，其余不變。 自由變元代入 對某自由出現(xiàn)的個體變元可用個體常元或用與原子公式中所有個體變元不同的個體變元去代入，且處處代入。2.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:任何一個謂詞公式任何一個謂詞公式A，如果具有如下形式：，如果具有如下形式： (x1) (x2) (xn)B其中其中可能是量詞可能是量詞 或量詞或量詞 ， xi（i=1， n）是客體變是客體變元，元，B是不含量詞的是不含量詞的謂詞公式，則稱謂詞公式，則稱A是前束范式。是前束范式。u說明說明:前束范式前束范式的量詞均在全式的開頭

5、的量詞均在全式的開頭,它們的作用域延它們的作用域延伸到整個公式的末尾。伸到整個公式的末尾。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:任何一個謂詞公式任何一個謂詞公式,均和一個前束范式等價。均和一個前束范式等價。前束范式的求法：前束范式的求法：第一步：否定深入。即利用量詞轉(zhuǎn)化公式，把否定聯(lián)結(jié)第一步：否定深入。即利用量詞轉(zhuǎn)化公式，把否定聯(lián)結(jié) 詞深入到命題變元和詞深入到命題變元和謂詞填式的謂詞填式的前面。前面。第二步：改名。即利用換名規(guī)則、代入規(guī)則更換一些變第二步：改名。即利用換名規(guī)則、代入規(guī)則更換一些變元的名

6、稱，以便消除混亂。元的名稱，以便消除混亂。第三步：量詞前移。即利用量詞轄域的收縮與擴(kuò)張把量第三步：量詞前移。即利用量詞轄域的收縮與擴(kuò)張把量詞移到前面。這樣便可求出與公式等價的前束范式。詞移到前面。這樣便可求出與公式等價的前束范式。整理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(

7、y,z)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

8、 B x 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）題將約束變元x改名為u，將約束變元y改名為z，化為前束范式化為前

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

10、xxGxxFxxGxxFx )(,()(),()()()()(,()()(),()()()(,()()(),()()()(,()()()(),()()(,()()()(),()(),()()()(),()(),()()()(),()(),()()()(),()(),()()()(),()()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前束析取范式和前束合取范式前束析取范式和前束合取范式(Pre

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

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

14、式.u二、前束合取范式二、前束合取范式u定義定義2-6.2 2-6.2 一個一個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)是客體變元，是客體變元，A Aijij是原子公式或其否定。是原子公式或其否定。()()()()() ( )()xzyPx

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

16、y () ( )() ( , )() ( , )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)(

17、 (Q(z,y)Q(z,y)R(x,w)R(x,w)u三、前束析取范式三、前束析取范式u定義定義2-6.3 2-6.3 一個一個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)是客體變是客體變元，元，A Aijij是原子公式或其否定。是原子公式或

18、其否定。()()()( ( )( , )( ( )( , )xuzP xQ x yP uQ y z例如公式例如公式是前束是前束析析取范式。取范式。)定理定理2-6.3 每一個每一個wffA都可轉(zhuǎn)化為與其等價的前束析取范式。都可轉(zhuǎn)化為與其等價的前束析取范式。例題例題4 將將wffD： 轉(zhuǎn)化為與其等價的前束析取范式。轉(zhuǎn)化為與其等價的前束析取范式。()( ( )( , )() ( )() ( , )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