離散數(shù)學PPT課件

1、上次課回顧v指導變元、作用域、約束變元、自由變元、閉式v約束變元換名和自由變元代入v有限論域客體變元的枚舉v謂詞公式賦值、謂詞公式等價、永真式、不可滿足式、可滿足式v謂詞公式的等價式和蘊含式第1頁/共52頁四、謂詞演算的等價式和蘊含式1、命題公式的推廣v結(jié)論：命題演算中的等價公式表和蘊含公式表都可推廣到謂詞演算中使用。PQPQ ()( ( )( )()( )( )x P xQ xxP xQ x () ( )() ( , )( ()( ( )() ( , )x P xy R x yx P xy R x y ()PQPQ PPF()( , )()( , )x H x yx H x yF 命題演算的

2、等價式謂詞演算的等價式第2頁/共52頁2、量詞與聯(lián)結(jié)詞之間的關(guān)系v將量詞前面的移到量詞后面去時，存在量詞改為全稱量詞，全稱量詞改為存在量詞；v反之，將量詞后面的移到量詞前面去時，也要做相應(yīng)的改變。( x)P(x) ( x)P(x)( x)P(x) ( x)P(x)第3頁/共52頁 這里A(x)是任意包括個體變元x的謂詞公式，B是不包括個體變元x的任意謂詞公式。3、量詞擴張/收縮律(1)第4頁/共52頁 證明 當當B為真時為真時,左右兩邊都為真左右兩邊都為真;否則否則, B為假為假,此時左此時左右兩邊都等價于右兩邊都等價于( ( x)Ax)A(x)(x), 證迄證迄.( ( x)Ax)A(x)B

3、 (x)B ( ( x)(Ax)(A(x)B)(x)B)第5頁/共52頁3、量詞擴張/收縮律(2)() ( )()( ( )x A xBxA xB () ( )()( ( )x A xBx A xB () ( )()( )Bx A xx BA x () ( )()( )Bx A xx BA x 這里A(x)是任意包括個體變元x的謂詞公式，B是不包括個體變元x的任意謂詞公式。第6頁/共52頁 證明 ( x)A(x)B ( x)(A(x)B) (B不含x) 證 ( x)A(x)B ( x)A(x)B 條件表達式 ( x) A(x)B 量詞否定 ( x)(A(x)B) 量詞轄域擴張 ( x)(A(x

4、)B) 條件表達式第7頁/共52頁 證明 B( x)A(x)( x)(BA(x) (B不含x) 證 B( x)A(x) B( x)A(x) 條件表達式 ( x)(BA(x) 量詞轄域擴張 ( x)(BA(x) 條件表達式第8頁/共52頁4、量詞與命題聯(lián)結(jié)詞之間的一些等價式量詞分配律( x)(A(x)B(x) ( x)A(x)( x)B(x)( x)(A(x)B(x)( x)A(x)( x)B(x)( x)(A(x)B(x)( x)A(x)( x)B(x)第9頁/共52頁5、量詞與命題聯(lián)結(jié)詞之間的一些蘊含式( ( x)Ax)A(x)(x)( x)x)B(x)B(x)( ( x)(Ax)(A(x)

5、(x)B B(x)(x)( ( x)(Ax)(A(x)B(x)(x)B(x)( ( x)Ax)A(x)(x)( x)Bx)B(x)(x)( ( x)Ax)A(x)(x)( ( x)x)B(x)B(x)( ( x)(Ax)(A(x)(x)B B(x)(x) )( ( x)(Ax)(A(x)(x)B(x)B(x)( ( x)Ax)A(x)(x)( ( x)Bx)B(x)(x)( ( x)(Ax)(A(x)(x)B(x)B(x)( ( x)Ax)A(x)(x)( ( x)Bx)B(x)(x)第10頁/共52頁 用分析法證明 ( x)A(x)( x)B(x)( x)(A(x)B(x) 。 證明 若(

6、x)(A(x)B(x)為假, 則必有個體a, 使A(a)B(a)為假; 因此A(a), B(a)皆為假, 所以( x)A(x)和( x)B(x)為假， 即 ( x)A(x)( x)B(x)為假。 故( x)A(x)( x)B(x)( x)(A(x)B(x) 第11頁/共52頁 表 2 1 謂詞演算中常用的等價式和蘊含式第12頁/共52頁6、多個量詞的使用考慮兩個量詞的情況。更多量詞的使用方法與其類似。對于二元謂詞如果不考慮自由變元，可以有以下八種情況。()() ( , )xy A x y()() ( , )yx A x y()() ( , )yx A x y()() ( , )yx A x y

7、()() ( , )xy A x y()() ( , )xy A x y()() ( , )xy A x y()() ( , )yx A x y 全稱量詞與存在量詞在公式中出現(xiàn)的次序，不能隨意更換。用雙向箭頭表示等價，單向箭頭表示蘊含，見它們之間的關(guān)系。第13頁/共52頁()() ( , )()() ( , )xy A x yyx A x y ()() ( , )()() ( , )xy A x yyx A x y 有兩個等價關(guān)系：第14頁/共52頁()() ( , )()() ( , )xy A x yyx A x y ()() ( , )()() ( , )yx A x yxy A x y

8、 ()() ( , )()() ( , )yx A x yxy A x y ()() ( , )()() ( , )xy A x yyx A x y ()() ( , )()() ( , )yx A x yxy A x y ()() ( , )()() ( , )xy A x yyx A x y 具有兩個量詞的謂詞公式有如下一些蘊含關(guān)系：第15頁/共52頁作業(yè) P66:3,4,5 P72:2a),4,7 第16頁/共52頁定義2-6.1 一個合式公式稱為前束范式，如果它有如下形式：(Q1x1)(Q2x2)(Qkxk)A其中Qi(1ik)為 或 , A為不含有量詞的謂詞公式。v特別地，若謂詞公式

9、中無量詞，則該公式也看作是前束范式。v前束范式的特點:所有量詞均非否定地出現(xiàn)在公式最前面，且它的轄域一直延伸到公式之末。一、前束范式第17頁/共52頁例如，( 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)不是前束范式。第18頁/共52頁 定理2.6.1 (前束范式存在定理) 任意謂詞公式A都有與之等價的前束范式。 證明：第19頁/共52頁前束范式的求取方法第20頁/共52頁舉例73頁 例題1、例題2、例題3第21頁/共52頁例題2 化公式( ( x x) )( ( y y)()( ( z)

10、(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)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)第22頁/共52

11、頁()() ( , )()() ( , )()( ( , )( , )xy A x yxy B x yy A y xB x y () () ( , )()() ( , )()( ( , )( , )xy A x yxy B x yy A y xB x y ( )() ( , ) ()()( , ) () ( ( , )( , )xy A x yxyB x yyA y xB x y 解 第一步否定深入原式第二步改名，以便把量詞提到前面。()() ( , )()()( , )() ( ( , )( , )xy A x yuvB u vzA z uB u z ()()()()() ( , ) ( ,

12、 )( ( , )( , )xyuvzA x yB u vA z uB u z 例題3 把公式將約束變元x改名為u，將約束變元y改名為z，化為前束范式第23頁/共52頁練習( x)( y)( z)P(x,y,z)( u)Q(x,u)( v)Q(y,v)( x)( y)( z)P(x,y,z)( u)Q(x,u) ( v)Q(y,v)( x)( y)( ( z)P(x,y,z)( u) Q(x,u) ( v)Q(y,v)( x)( y)( z)( u)( v)(P(x,y,z)Q(x,u) Q(y,v)第24頁/共52頁定義定義2-6.2 一個一個wffA稱為前束合取范式，如果它有稱為前束合取范

13、式，如果它有如下形式：如下形式：(Q1x1)(Q2x2)(Qkxk)(A11A12A1l1)(A21A22A2l2) (Am1Am2Amlm)其中：其中：vQi(1ik)為量詞為量詞 或或 ，vxi(i=1,2, ,n)是客體變元，是客體變元，vAij是原子公式或其否定。是原子公式或其否定。二、前束合取范式第25頁/共52頁()()()() () ( ) ()xzyPxazbQ yab ( )( )( )( ( )( ) ( ( )( , ) ( , )( ) ( , )( , )xuz P xPuP xQ y zQx yPuQx yQ y z 是前束合取范式舉例第26頁/共52頁定理2-6.

14、2 每一個wffA都可轉(zhuǎn)化為與其等價的前束合取范式。證明：略。第27頁/共52頁例題4 將wffD： 轉(zhuǎn)化為與其等價的前束合取范式。()() ( )() ( , )() ( , )xy P xz Q z yy R x y () ( ) () ( , )() ( , )Dx P xz Q z yy R x y () ( ) () ( , )() ( , )Dx P xz Q z ywR x w 解 第一步取消多余量詞第二步換名第三步消去條件聯(lián)結(jié)詞第四步將否定深入第五步將量詞推到左邊() ( ( ) () ( , )() ( , )DxP xz Q z yw R x w ()( ) ( )( ,

15、) ()( , )DxP xzQ z yw R x w ()()()( )( , )( , )DxzwP xQ z yR x w D( x)( z)( w)(P(x)R(x,w)(Q(z,y)R(x,w)第六步化為合取范式第28頁/共52頁求前束合取范式的方法 第一步：消去多余量詞 第二步：換名 第三步：消去條件聯(lián)結(jié)詞 第四步：將否定深入 第五步：將量詞推到左邊 第六步：化為合取范式第29頁/共52頁定義定義2-6.3 一個一個wffA稱為前束析取范式，如果它稱為前束析取范式，如果它有如下形式：有如下形式：(Q1x1)(Q2x2)(Qkxk)(A11A12A1l1) (A21A22A2l2)

16、(Am1Am2Amlm)其中其中:Qi(1ik)為量詞為量詞 或或 ，xi(i=1,2, ,n)是客體變元，是客體變元，Aij是原子公式或其否定。是原子公式或其否定。二、前束析取范式第30頁/共52頁舉例是前束析取范式。()()()( ( )( , )( ( )( , )xuzP xQ x yP uQ y z)第31頁/共52頁定理2-6.3 每一個wffA都可轉(zhuǎn)化為與其等價的前束析取范式。證明：略。第32頁/共52頁例題4 將wffD： 轉(zhuǎn)化為與其等價的前束析取范式。()( ( )( , )() ( )() ( , )x P xQ x yy P yz Q y z ()( )( , ) ()

17、( ) () ( , )DxP xQ x yy P yz Q y z ()( ( )( , ) () ( ) () ( , )x P xQ x yu P uz Q y z ()()()( ( )( , ) ( ( )( , )xuz P xQ x yP uQ y z 解第33頁/共52頁求前束析取范式的方法 第一步：消去多余量詞 第二步：換名 第三步：消去條件聯(lián)結(jié)詞 第四步：將否定深入 第五步：將量詞推到左邊 第六步：化為析取范式第34頁/共52頁作業(yè) P75:（1）b),（2） b、c) 第35頁/共52頁27 謂詞演算的推理理論v謂詞邏輯是命題邏輯的進一步深化和發(fā)展，謂詞演算的推理方法，可

18、以看作是命題演算推理方法的擴張。因此命題邏輯的推理理論在謂詞邏輯中幾乎可以完全照搬，只不過這時涉及的公式是謂詞邏輯的公式罷了。v在謂詞邏輯中，某些前提和結(jié)論可能受到量詞的約束，為確立前提和結(jié)論之間的內(nèi)部聯(lián)系，有必要消去量詞和添加量詞，因此正確理解和運用有關(guān)量詞規(guī)則是謂詞邏輯推理理論中十分重要的關(guān)鍵所在。第36頁/共52頁回顧：約束變元、自由變元v定義2.7.1 在謂詞公式A(x)中，若x自由出現(xiàn)在量詞( y)或( y)的轄域， 則稱A(x)對于y是自由的。v由定義可知，若y在A(x)中不是約束出現(xiàn)，則A(x)對于y一定是自由的。第37頁/共52頁一、有關(guān)量詞消去和添加規(guī)則量詞消去規(guī)則：(1)全

19、稱量詞消去規(guī)則：稱為全稱指定規(guī)則，簡稱US規(guī)則(2)存在量詞消去規(guī)則：稱為存在指定規(guī)則，簡稱ES規(guī)則量詞產(chǎn)生規(guī)則：(3)存在量詞產(chǎn)生規(guī)則：稱為存在推廣規(guī)則，簡稱EG規(guī)則(4)全稱量詞產(chǎn)生規(guī)則：稱為全稱推廣規(guī)則，簡稱UG規(guī)則第38頁/共52頁全稱（U）存在（E）消去規(guī)則消去規(guī)則USES產(chǎn)生規(guī)則產(chǎn)生規(guī)則UGEG第39頁/共52頁量詞消去規(guī)則：(1) 全稱量詞消去規(guī)則(稱為全稱指定規(guī)則，簡稱US規(guī)則) ( x)A(x)A(c) ，其中c為任意個體常元第40頁/共52頁量詞消去規(guī)則：(2)存在量詞消去規(guī)則(稱為存在指定規(guī)則，簡稱ES規(guī)則)( x)A(x)A(c)，其中c為特定個體常元成立充分條件是：c

20、不得在前提中或者居先推導公式中出現(xiàn)或自由出現(xiàn)；第41頁/共52頁量詞產(chǎn)生規(guī)則：(3) 存在量詞產(chǎn)生規(guī)則(稱為存在推廣規(guī)則，簡稱EG規(guī)則)A(c)( y)A(y)，其中c為特定個體常元 成立充分條件：取代c的個體變元y不在A(c)中出現(xiàn)；第42頁/共52頁量詞產(chǎn)生規(guī)則：(4) 全稱量詞產(chǎn)生規(guī)則(稱為全稱推廣規(guī)則，簡稱UG規(guī)則)A(x)( y)A(y) 成立條件：必須能夠證明前提A(x)對于x的任意取值都成立；第43頁/共52頁真值表法：前真：看后真；后假：前至少有一個假。直接證法：由一組前提，利用一些公認的推理規(guī)則，根據(jù)已知的等價或蘊含公式，推演得到有效的結(jié)論。間接證法要證明H1 H2 Hn C

21、，只要證明H1，H2，Hn與是C是不相容的。要證明H1 H2 Hn (R C)。 如能證明H1 H2 Hn R C，即證得H1 H2 Hn (RC)。這個證明稱為CP規(guī)則。命題推理方法第44頁/共52頁二、Lp中推理實例v Lp的推理方法是Ls推理方法的擴展，因此在Lp中利用的推理規(guī)則也是T規(guī)則、P規(guī)則和CP規(guī)則，還有已知的等價式，蘊含式以及有關(guān)量詞的消去和產(chǎn)生規(guī)則。v 使用的推理方法是直接構(gòu)造法和間接證法。第45頁/共52頁例題例題1 證明蘇格拉底論證：證明蘇格拉底論證： 所有的人都是要死的。所有的人都是要死的。 蘇格拉底是人。蘇格拉底是人。 所以蘇格拉底是要死的。所以蘇格拉底是要死的。解

22、設(shè) H(x)：x是一個人。 M(x)：x是要死的。 s：蘇格拉底。故蘇格拉底論證可符號化為：( x)(H(x) M(x) H(s)M(s)證明(1) ( x)(H(x) M(x) P (2) H(s)M(s) US(1)(3) H(s) P(4) M(s) T(2)(3)I第46頁/共52頁例題2 證明證明注意（3）（4）兩條次序不能顛倒。( x)(C(x)W(x)R(x)( x x)(C(x)Q(x)( x x)(Q(x)R(x)(1) ( x)(C(x)W(x)R(x) P(2) ( x x)(C(x)Q(x) P(4) C(a)W(a)R(a) US(1)(3) C(a)Q(a) ES(

23、2)(5) C(a) T(3)I(6) W(a)R(a) T(4)(5)I(7) Q(a) T(3)I(8) R(a) T(6)I(9) Q(a)R(a) T(7)(8)I(10) ( x x)(Q(x)R(x) EG第47頁/共52頁例題3 證明 ( x)(P(x)Q(x)( x)P(x)( x x)Q(x)用間接證法。要證S SC C，即要證S SC CT T，而S SC CS SC C，所以S SC CT T即S SC CT T，亦就是(S SC)C)F F，S SC CF F。假定C C為T T，推出矛盾。(1) ( x)P(x)( x x)Q(x) P(附加前提)(2) ( x x)P(x)( x)Q(x) T(1)E(3) ( x x)P(x) T(2)I(4) ( x)Q(x) T(2)I(5) P(c) ES(3)(6) Q(c) US(4)(7) P(c)Q(c) T(5)(6)I(8) (P(c)Q(c) T(7)E(9) ( x)(P(x)Q(x) P(10) P(c)Q(c) US(9)(11) (P(c)Q(c) (P(c)Q(c) (矛盾)T(8)(10)I第48頁/共52頁證法2 本題可用CP規(guī)則原題為( x)(P(x)Q(x