離散數(shù)學第2章第3節(jié)

1、Discrete Mathematics山東科技大學山東科技大學信息科學與工程學院信息科學與工程學院上次課回顧上次課回顧v指導變元、作用域、約束變元、自由變元、閉式指導變元、作用域、約束變元、自由變元、閉式v約束變元換名和自由變元代入約束變元換名和自由變元代入v有限論域客體變元的枚舉有限論域客體變元的枚舉v謂詞公式賦值、謂詞公式等價、永真式、不可滿足謂詞公式賦值、謂詞公式等價、永真式、不可滿足式、可滿足式式、可滿足式v謂詞公式的等價式和蘊含式謂詞公式的等價式和蘊含式四、謂詞演算的等價式和蘊含式四、謂詞演算的等價式和蘊含式1、命題公式的推廣、命題公式的推廣v結(jié)論結(jié)論：命題演算中的等價公式表和蘊含

2、公式表都：命題演算中的等價公式表和蘊含公式表都可推廣到謂詞演算中使用。可推廣到謂詞演算中使用。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、量詞與聯(lián)結(jié)詞、量詞與聯(lián)結(jié)詞之間的關(guān)系之間的關(guān)系v將量詞前面將量詞前面的移到量詞后面去時，存在量詞的移到量詞后面去時，存在量詞改為全稱量詞，全稱量詞改為存在量詞；改為全稱

3、量詞，全稱量詞改為存在量詞；v反之，將量詞后面的反之，將量詞后面的移到量詞前面去時，也移到量詞前面去時，也要做相應(yīng)的改變。要做相應(yīng)的改變。( x)P(x) ( x)P(x)( x)P(x) ( x)P(x) 這里這里A(x)是任意包括個體變元是任意包括個體變元x的謂詞公式，的謂詞公式，B是不包括個體變元是不包括個體變元x的任意謂詞公式。的任意謂詞公式。3、量詞擴張、量詞擴張/收縮律收縮律(1) 證明證明 當當B為真時為真時,左右兩邊都為真左右兩邊都為真;否則否則, B為假為假,此時左右兩此時左右兩邊都等價于邊都等價于( ( x)Ax)A(x)(x), 證迄證迄.( ( x)Ax)A(x)B (

4、x)B ( ( x)(Ax)(A(x)B)(x)B)3、量詞擴張、量詞擴張/收縮律收縮律(2)() ( )()( ( )x A xBx A xB () ( )()( ( )x A xBx A xB () ( )()( )Bx A xx BA x () ( )()( )Bx A xx BA x 這里這里A(x)是任意包括個體變元是任意包括個體變元x的謂詞公式，的謂詞公式，B是不包括個體變元是不包括個體變元x的任意謂詞公式。的任意謂詞公式。證明證明 ( x)A(x)B ( x)(A(x)B) (B不含不含x)證證 ( x)A(x)B ( x)A(x)B 條件表達式條件表達式 ( x) A(x)B

5、量詞否定量詞否定 ( x)(A(x)B) 量詞轄域擴張量詞轄域擴張 ( x)(A(x)B) 條件表達式條件表達式證明證明 B( x)A(x)( x)(BA(x) (B不含不含x)證證 B( x)A(x) B( x)A(x) 條件表達式條件表達式 ( x)(BA(x) 量詞轄域擴張量詞轄域擴張 ( x)(BA(x) 條件表達式條件表達式4、量詞與命題聯(lián)結(jié)詞之間的一些等價式、量詞與命題聯(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

6、)5、量詞與命題聯(lián)結(jié)詞之間的一些蘊含式、量詞與命題聯(lián)結(jié)詞之間的一些蘊含式( ( x)Ax)A(x)(x)( x)x)B(x)B(x)( ( x)(Ax)(A(x)(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)

7、Ax)A(x)(x)( ( x)Bx)B(x)(x)用分析法證明用分析法證明( x)A(x)( x)B(x)( x)(A(x)B(x) 。 證明證明 若若( 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) 表表 2 1 謂詞演算中常用的等價式和蘊含式謂詞演算中常用的等價式和蘊含式6、多個量詞的使用、多個量詞的使用考慮兩個量詞的情況。更多

8、量詞的使用方法與其類似?？紤]兩個量詞的情況。更多量詞的使用方法與其類似。對于二元謂詞如果不考慮自由變元，可以有以下八種情況。對于二元謂詞如果不考慮自由變元，可以有以下八種情況。()() ( , )xy A x y()() ( , )yx A x y()() ( , )yx A x y()() ( , )yx A x y()() ( , )xy A x y()() ( , )xy A x y()() ( , )xy A x y()() ( , )yx A x y 全稱量詞與存在量詞在公式中出現(xiàn)的次序，不能隨意更換。全稱量詞與存在量詞在公式中出現(xiàn)的次序，不能隨意更換。用雙向箭頭表示等價，單向箭頭表

9、示蘊含，見它們之間的關(guān)系。用雙向箭頭表示等價，單向箭頭表示蘊含，見它們之間的關(guān)系。()() ( , )()() ( , )xy A x yyx A x y ()() ( , )()() ( , )xy A x yyx A x y 有兩個等價關(guān)系：有兩個等價關(guān)系：()() ( , )()() ( , )xy A x yyx A x y ()() ( , )()() ( , )yx A x yxy A x y ()() ( , )()() ( , )yx A x yxy A x y ()() ( , )()() ( , )xy A x yyx A x y ()() ( , )()() ( , )y

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

11、束范式的特點:所有量詞均非否定地出現(xiàn)在公所有量詞均非否定地出現(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 (前束范式存在定理前束范式存在定理) 任意謂詞公式任意謂詞公式A都有都有與之等價的前束范式。與之等價的前束范式。證明：證明：前束范式的求取方法前束范式的求取方法舉例舉例73頁 例題1、例題2、例題3例

12、題例題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)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

13、(x,z)P(x,z)P(y,z)P(y,z)Q(x,y,u)Q(x,y,u)()() ( , )()() ( , )()( ( , )( , )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 解解 第一步否定深入第一步否定深入原式原式第二步改名，以便把量詞提到前面。第二步改名，以便把量詞提到前面。()() ( , )()()

14、( , )() ( ( , )( , )xy A x yuvB u vzA z uB u z ()()()()() ( , ) ( , )( ( , )( , )xyuvzA x yB u vA z uB u z 例題例題3 把公式把公式將約束變元x改名為u，將約束變元y改名為z，化為前束范式化為前束范式練習練習( 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)(

15、v)(P(x,y,z)Q(x,u) Q(y,v)定義定義2-6.2 一個一個wffA稱為前束合取范式，如果它有如下稱為前束合取范式，如果它有如下形式：形式：(Q1x1)(Q2x2)(Qkxk)(A11A12A1l1)(A21A22A2l2) (Am1Am2Amlm)其中：其中：vQi(1ik)為量詞為量詞 或或 ，vxi(i=1,2, ,n)是客體變元，是客體變元，vAij是原子公式或其否定。是原子公式或其否定。二、前束合取范式二、前束合取范式()()()() () ( ) ()xzyPxazbQ yab ( )()( )( ( )( ) ( ( )( , ) ( , )( ) ( , )(

16、, )xuzP xPuP xQ y zQ x yPuQ x yQ y z 是前束合取范式是前束合取范式舉例舉例定理定理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 y () ( ) () ( , )() ( , )Dx P xz Q z ywR x w 解解 第一

17、步取消多余量詞第一步取消多余量詞第二步換名第二步換名第三步消去條件聯(lián)結(jié)詞第三步消去條件聯(lián)結(jié)詞第四步將否定深入第四步將否定深入第五步將量詞推到左邊第五步將量詞推到左邊() ( ( ) () ( , )() ( , )DxP xz Q z yw R x w ()( ) ( )( , ) ()( , )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)第六步化為合取范式第六步化為合取范式求前束合取范式的方法求前束合取范式的方法第一步：消去多余量詞第一步：消去多余量詞

18、第二步：換名第二步：換名第三步：消去條件聯(lián)結(jié)詞第三步：消去條件聯(lián)結(jié)詞第四步：將否定深入第四步：將否定深入第五步：將量詞推到左邊第五步：將量詞推到左邊第六步：化為合取范式第六步：化為合取范式定義定義2-6.3 一個一個wffA稱為前束析取范式，如果它有稱為前束析取范式，如果它有如下形式：如下形式：(Q1x1)(Q2x2)(Qkxk)(A11A12A1l1) (A21A22A2l2) (Am1Am2Amlm)其中其中:Qi(1ik)為量詞為量詞 或或 ，xi(i=1,2, ,n)是客體變元，是客體變元，Aij是原子公式或其否定。是原子公式或其否定。二、前束析取范式二、前束析取范式舉例舉例是前束是前

19、束析析取范式。取范式。()()()( ( )( , )( ( )( , )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 y

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

21、理方法的擴算的推理方法，可以看作是命題演算推理方法的擴張。因此命題邏輯的推理理論在謂詞邏輯中幾乎可張。因此命題邏輯的推理理論在謂詞邏輯中幾乎可以完全照搬，只不過這時涉及的公式是謂詞邏輯的以完全照搬，只不過這時涉及的公式是謂詞邏輯的公式罷了。公式罷了。v在謂詞邏輯中，某些前提和結(jié)論可能受到量詞的約在謂詞邏輯中，某些前提和結(jié)論可能受到量詞的約束，為確立前提和結(jié)論之間的內(nèi)部聯(lián)系，有必要消束，為確立前提和結(jié)論之間的內(nèi)部聯(lián)系，有必要消去量詞和添加量詞，因此正確理解和運用有關(guān)量詞去量詞和添加量詞，因此正確理解和運用有關(guān)量詞規(guī)則是謂詞邏輯推理理論中十分重要的關(guān)鍵所在。規(guī)則是謂詞邏輯推理理論中十分重要的關(guān)鍵所

22、在?；仡櫍杭s束變元、自由變元回顧：約束變元、自由變元v定義定義2.7.1 在謂詞公式在謂詞公式A(x)中，若中，若x自由出現(xiàn)在量詞自由出現(xiàn)在量詞( y)或或( y)的轄域，的轄域， 則稱則稱A(x)對于對于y是自由的。是自由的。v由定義可知，若由定義可知，若y在在A(x)中不是約束出現(xiàn)，則中不是約束出現(xiàn)，則A(x)對對于于y一定是自由的。一定是自由的。一、有關(guān)量詞消去和添加規(guī)則一、有關(guān)量詞消去和添加規(guī)則量詞消去規(guī)則：量詞消去規(guī)則：(1)全稱量詞消去規(guī)則：稱為全稱指定規(guī)則，簡稱全稱量詞消去規(guī)則：稱為全稱指定規(guī)則，簡稱US規(guī)則規(guī)則(2)存在量詞消去規(guī)則：稱為存在指定規(guī)則，簡稱存在量詞消去規(guī)則：稱為

23、存在指定規(guī)則，簡稱ES規(guī)則規(guī)則量詞產(chǎn)生規(guī)則：量詞產(chǎn)生規(guī)則：(3)存在量詞產(chǎn)生規(guī)則：稱為存在推廣規(guī)則，簡稱存在量詞產(chǎn)生規(guī)則：稱為存在推廣規(guī)則，簡稱EG規(guī)則規(guī)則(4)全稱量詞產(chǎn)生規(guī)則：稱為全稱推廣規(guī)則，簡稱全稱量詞產(chǎn)生規(guī)則：稱為全稱推廣規(guī)則，簡稱UG規(guī)則規(guī)則全稱（U）存在（E）消去規(guī)則消去規(guī)則USES產(chǎn)生規(guī)則產(chǎn)生規(guī)則UGEG量詞消去規(guī)則：量詞消去規(guī)則：(1) 全稱量詞消去規(guī)則全稱量詞消去規(guī)則(稱為全稱指定規(guī)則，簡稱稱為全稱指定規(guī)則，簡稱US規(guī)規(guī)則則) ( x)A(x)A(c) ，其中，其中c為任意個體常元為任意個體常元量詞消去規(guī)則：量詞消去規(guī)則：(2)存在量詞消去規(guī)則存在量詞消去規(guī)則(稱為存在指定

24、規(guī)則，簡稱稱為存在指定規(guī)則，簡稱ES規(guī)規(guī)則則)( x)A(x)A(c)，其中，其中c為特定個體常元為特定個體常元成立充分條件是：成立充分條件是：c不得在前提中或者居先推導公式中出現(xiàn)或不得在前提中或者居先推導公式中出現(xiàn)或自由出現(xiàn)；自由出現(xiàn)；量詞產(chǎn)生規(guī)則：量詞產(chǎn)生規(guī)則：(3) 存在量詞產(chǎn)生規(guī)則存在量詞產(chǎn)生規(guī)則(稱為存在推廣規(guī)則，簡稱稱為存在推廣規(guī)則，簡稱EG規(guī)規(guī)則則)A(c)( y)A(y)，其中，其中c為特定個體常元為特定個體常元 成立充分條件：取代成立充分條件：取代c的個體變元的個體變元y不在不在A(c)中出現(xiàn)；中出現(xiàn)；量詞產(chǎn)生規(guī)則：量詞產(chǎn)生規(guī)則：(4) 全稱量詞產(chǎn)生規(guī)則全稱量詞產(chǎn)生規(guī)則(稱為

25、全稱推廣規(guī)則，簡稱稱為全稱推廣規(guī)則，簡稱UG規(guī)規(guī)則則)A(x)( y)A(y) 成立條件：必須能夠證明前提成立條件：必須能夠證明前提A(x)對于對于x的任意取值的任意取值都成立；都成立；真值表法：前真：看后真；后假：前至少有一個假。直接證法：由一組前提，利用一些公認的推理規(guī)則，根據(jù)已知的等價或蘊含公式，推演得到有效的結(jié)論。間接證法要證明H1 H2 Hn C，只要證明H1，H2，Hn與是C是不相容的。要證明H1 H2 Hn (R C)。 如能證明H1 H2 Hn R C，即證得H1 H2 Hn (RC)。這個證明稱為CP規(guī)則。命題推理方法二、二、Lp中推理實例中推理實例v Lp的推理方法是的推理

26、方法是Ls推理方法的擴展，因此推理方法的擴展，因此在在Lp中利用的推理規(guī)則也是中利用的推理規(guī)則也是T規(guī)則、規(guī)則、P規(guī)則和規(guī)則和CP規(guī)則，還有已知的等價式，蘊含式以及有規(guī)則，還有已知的等價式，蘊含式以及有關(guān)量詞的消去和產(chǎn)生規(guī)則。關(guān)量詞的消去和產(chǎn)生規(guī)則。v使用的推理方法是直接構(gòu)造法和間接證法。使用的推理方法是直接構(gòu)造法和間接證法。例題例題1 證明蘇格拉底論證：證明蘇格拉底論證： 所有的人都是要死的。所有的人都是要死的。 蘇格拉底是人。蘇格拉底是人。 所以蘇格拉底是要死的。所以蘇格拉底是要死的。解解 設(shè)設(shè) H(x)：x是一個人。是一個人。 M(x)：x是要死的。是要死的。 s：蘇格拉底。：蘇格拉底。

27、故蘇格拉底論證可符號化為：故蘇格拉底論證可符號化為：( 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例題例題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(2)(5) C(a) T(3)I(6) W

28、(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例題例題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