第二章 謂詞邏輯2

1、2/44 離散數(shù)學(xué) 第二章 謂詞邏輯 2/43 回顧 謂詞、個(gè)體、量詞 一元、多元、域、全稱、存在 合式謂詞公式 定義： 5條 自由變?cè)图s束變?cè)?32/44 重要等價(jià)式和永真蘊(yùn)含式 31 32 33 34 35 36 ()( ( )( )() ( )() ( ) ()( ( )( )() ( )() ( ) () ( )()( ) () ( )()( ) () ( )()( ( ) () ( Ex A xB xx A xx B x Ex A xB xx A xx B x Ex A xxA x Ex A xxA x Ex A xPx A xP Ex A x )()( ( )Px A xP 33

2、/44 重要等價(jià)式和永真蘊(yùn)含式 37 38 39 40 41 42 () ( )()( ( ) () ( )()( ( ) () ( )()( ( ) () ( )()( ( ) () ( )()( ) () ( Ex A xPx A xP Ex A xPx A xP Ex A xBx A xB Ex A xBx A xB EAx B xx AB x EAx B 43 )()( ) ()( ( )( )() ( )() ( ) xx AB x Ex A xB xx A xx B x 34/44 重要等價(jià)式和永真蘊(yùn)含式 17 18 19 20 () ( )() ( )()( ( )( ) ()(

3、 ( )( )() ( )() ( ) () ( )() ( )()( ( )( ) ()( ( )( )() ( )() ( ) Ix A xx B xx A xB x Ix A xB xx A xx B x Ix A xx B xx A xB x Ix A xB xx A xx B x 35/44 量詞交換式 1 2 3 4 5 ()() ( , )()() ( , ) ()() ( , )()() ( , ) ()() ( , )()() ( , ) ()() ( , )()() ( , ) ()() ( , )()() ( , Bxy P x yyx P x y Bxy P x yyx

4、 P x y Byx P x yxy P x y Byx P x yxy P x y Bxy P x yyx P x y 6 7 8 ) ()() ( , )()() ( , ) ()() ( , )()() ( , ) ()() ( , )()() ( , ) Bxy P x yyx P x y Byx P x yxy P x y Bxy P x yyx P x y 36/44 記憶規(guī)律 ()()xy ()()yx ()()yx()()xy ()()xy()()yx ()()yx ()()xy 1B 2B 4B 3B 5B 7B 6B 8B 37/44 2.2謂詞邏輯中的推理規(guī)則 謂詞公式的

5、翻譯 推理規(guī)則 9/43 規(guī)則1：約束變?cè)母拿?guī)則 對(duì)約束變?cè)M(jìn)行換名，使得一個(gè)變?cè)谝?個(gè)公式中只呈一種形式出現(xiàn)。規(guī)則如下： 欲改名之變?cè)獞?yīng)是某量詞作用范圍內(nèi)的變 元，且應(yīng)同時(shí)更改該變?cè)诖肆吭~轄域內(nèi) 的所有約束出現(xiàn)，而公式的其余部分不變 。 新的變?cè)?hào)應(yīng)是此量詞轄域內(nèi)原先沒(méi)有 使用過(guò)的，最好是公式中未出現(xiàn)過(guò)的符號(hào) 。 () ( )() ( )x P xy P y等價(jià)于 10/43 規(guī)則1：約束變?cè)母拿?guī)則 例：對(duì)公式 進(jìn)行換名，使各變?cè)怀室环N形式出現(xiàn)。 解： 需要對(duì)約束變?cè)獂，y進(jìn)行換名 不對(duì)的： x(P(x,y)yQ(x,y,z)( , )S x z u(P(u,y)Q(u,v,

6、z)S(x,z)v u(P(u, )vQ(u,v,z)S( ,vx z) z)S(x,z),zQ(u,y)u(P(u,z 11/43 規(guī)則2：自由變?cè)拇胍?guī)則 對(duì)公式中自由變?cè)母慕凶龃搿Ｒ?guī)則 如下： 欲改變自由變?cè)拿?，必改在公式中的?一處自由出現(xiàn)。 新變?cè)粦?yīng)在原公式中以任何約束形式出 現(xiàn)。 例：對(duì)公式 的變?cè)?x,y的自由出現(xiàn)用w,t代入，得 x(P(x,y)(x,y,z)S(x,z)yQ x(P(x,t)(x,y,z)S(w,z)yQ 12/43 例如例如 對(duì)公式對(duì)公式 ( x) (P(x) Q(x)( x) (P(x) R(x) 為清楚起見(jiàn)，可對(duì)第二個(gè)約束變?cè)獮榍宄鹨?jiàn)，可對(duì)

7、第二個(gè)約束變?cè)獂進(jìn)行換名進(jìn)行換名 ( x) (P(x) Q(x)( y) (P(y) R(y) 又例如又例如 對(duì)公式對(duì)公式 ( x) (P(x) R(x,y) Q(x,y) 可對(duì)約束變?cè)蓪?duì)約束變?cè)獂進(jìn)行換名，得進(jìn)行換名，得 ( z) (P(z) R(z,y) Q(x,y) ( z) (P(z) R(x,y) Q(x,y) ( y) (P(y) R(y,y) Q(x,y) 錯(cuò)誤：錯(cuò)誤： 13/43 規(guī)則3：命題變?cè)拇鷵Q規(guī)則 用任一謂詞公式Ai代換永真公式中某一 命題變?cè)狿i的所有出現(xiàn)，所得到的新公式 B仍然是永真式（但在Ai的個(gè)體變?cè)胁?應(yīng)有中的約束變?cè)霈F(xiàn),并有 。 BB 14/43 規(guī)

8、則4：取代規(guī)則 設(shè) 都是含n個(gè)自由變?cè)闹^詞公式，且A是 A的子公式。若在A中用B取代A的一處 或多處出現(xiàn)后所得的新公式是B ，則有 。如果A為永真式，則B也是永真式。 1212( ,.,)( ,.,)nnA x xxB x xx AB 15/43 謂詞邏輯的推理 在謂詞邏輯中，推理的形式結(jié)構(gòu)仍為在謂詞邏輯中，推理的形式結(jié)構(gòu)仍為 CHHH n . 21 若若 是永真式，是永真式， 則稱由前提則稱由前提 邏輯的推出結(jié)論邏輯的推出結(jié)論C， 在此在此 , C均為謂詞公式。均為謂詞公式。 n HHH,., 21 n HHH,., 21 CHHH n . 21 16/43 規(guī)則5：量詞的增加和刪除規(guī)則

9、全稱特指規(guī)則US：從 可得 出結(jié)論A(y) ，其中y是個(gè)體域中任一個(gè) 體，即： 注意：y不能和A(x)中其它指導(dǎo)變?cè)孛?。 存在特指規(guī)則ES：從 可得出 結(jié)論A(a) ，其中a是 和在此 之前不曾出現(xiàn)過(guò)的個(gè)體常量，即： 注意：a不能和指定前提中任一自由變?cè)?同名，也不能和使用本規(guī)則以前任一推導(dǎo) 步驟上得到的公式的自由變?cè)?() ( )x A x () ( )( )x A xA y () ( )x A x () ( )x A x () ( )( )x A xA a () ( )( )x A xA a 17/43 規(guī)則5：量詞的增加和刪除規(guī)則 存在推廣規(guī)則存在推廣規(guī)則EG：從：從A(a)

10、可得出結(jié)論可得出結(jié)論 ， 其中其中a是個(gè)體域中的某一個(gè)個(gè)體，即：是個(gè)體域中的某一個(gè)個(gè)體，即： 注意：注意：y不和不和A(a)中其他自由變?cè)蛑笇?dǎo)變?cè)?。中其他自由變?cè)蛑笇?dǎo)變?cè)?全稱推廣規(guī)則全稱推廣規(guī)則UG：從：從A(x) 可得出結(jié)論可得出結(jié)論 ， 其中其中x是個(gè)體域中的任意個(gè)體，即：是個(gè)體域中的任意個(gè)體，即： 使用條件使用條件: (1)x不是給定前提中任一公式的自由變?cè)?；不是給定前提中任一公式的自由變?cè)?(2)x不是在前面推導(dǎo)步驟中使用不是在前面推導(dǎo)步驟中使用ES規(guī)則引入規(guī)則引入 的變?cè)坏淖冊(cè)?(3)若在前面推導(dǎo)過(guò)程中使用若在前面推導(dǎo)過(guò)程中使用ES規(guī)則引入新變規(guī)則引入新變 元元

11、u時(shí)，時(shí)，x是自由變?cè)?，那么在是自由變?cè)?，那么在A(x)中，中，u應(yīng)應(yīng) 約束出現(xiàn)。約束出現(xiàn)。 ( )() ( )A xy A y ( )() ( )A ay A y () ( )y A y () ( )y A y UG-Universal Generalization EG-Existential Generalization UI-Universal Instantiation EI-Existential Instantiation US-Universal Specialisation ES- Existential Specialisation 19/43 謂詞邏輯中的推理 例1： 證

12、明： ()( )()( )( ) ()( ) x M xx H xM x x H x 試證明是前提 和的邏輯結(jié)果。 (1) ()( ) (2) ( ) ,(1) (3) ()( )( ) (4) ( )( ) ,(3) (5) ( ) x H xP H yES x H xM xP H yM yUS M y ,(2),(4) (6) ()( ) ,(5) T x M xEG H(a) H(a)M(a) M(a) 20/43 謂詞邏輯中的推理 例2：試證明 證明： ()( ( )( ) ()( ( )( )()( ( )( )x P xQ xx Q xR xx P xR x ， (1) ()( (

13、 )( ) (2) ( )( ) ,(1) (3) ()( ( )( ) (4) ( )( ) ,(3) (5) x P xQ xP P xQ xUS x Q xR xP Q xR xUS ( )( ) ,(2),(4) (6) ()( ( )( ) ,(5) P xR xT x P xR xUG 21/43 謂詞邏輯中的推理 例3： 證明： ()( ( )()( )( , ) ()( ( )()( ( )( , ) ()( )( ) x R xy D yL x y x R xy S yL x y x D xS x 已知前提， 試推出結(jié)論： (1) ()( ( )()( )( , ) (2)

14、( ( )()( )( , ) ,(1) (3) ( ) x R xy D yL x yP R ay D yL a yES R a ,(2) (4) ()( )( , ) ,(2) (5) ( )( , ) ,(4) (6) ()( ( )()( ( )( , ) T y D yL a yT D uL a uUS x R xy S yL x y (7) ( )()( ( )( , ) ,(6) (8) ()( ( )( , ) ,(3),(7) P R ay S yL a yUS y S yL a yT 22/43 謂詞邏輯中的推理 (9) ( )( , ) ,(8) (10) ( , )(

15、) ,(9) (11) ( )( ) , S uL a uUS L a uS uT D uS uT (5),(10) (12) ()( )( ) ,(11)x D xS xUG ()( ( )()( )( , ) ()( ( )()( ( )( , ) ()( )( ) x R xy D yL x y x R xy S yL x y x D xS x 已知前提， 試推出結(jié)論： 接上頁(yè) 23/43 例例4 指出下面推理的錯(cuò)誤指出下面推理的錯(cuò)誤. 設(shè)設(shè)D(x,y)表示表示“x可被可被y 整除整除” ,個(gè)體域個(gè)體域 為為 5,7 ,10 ,11 . 因?yàn)橐驗(yàn)镈(5，5)和和D(10,5)為真，所以為

16、真，所以 xD(x,5)為真為真. 因?yàn)橐驗(yàn)镈(7，5)和和D(11,5)為假，所以為假，所以 xD(x,5)為假為假. 但有下面的推理過(guò)程：但有下面的推理過(guò)程： (1) xD(x,5) 前提前提 (2) D(z,5) (1);ES (3) xD(x,5) (2);UG 因此，因此， xD(x,5) xD(x,5). 錯(cuò)！錯(cuò)！ 24/43 反證法舉例 例5： 證明： ()( ( )( ),()( ( )( ),() ( ) () ( ) x A xB xx B xC xx C x x A x 給定前提 試推出結(jié)論： (1) () ( ) () (2) ()( ) ,(1) (3) ( ) x

17、A xP xA xT A a 假設(shè)前提 ,(2) (4) ()( ( )( ) (5) ( )( ) ,(4) (6) ( ) ES x A xB xP A aB aUS B a ,(3),(5) (7) ()(B( )C( ) (8) ( )( ) ,(7) (9) ( ) T xxxP B aC aUS C a ,(6),(8) (10) ()C( ) T xxP 25/43 反證法舉例 (11) ( ) ,(10) (12) ( )( ) ,(9),(11) (13) ()A( ) F,( C aUS C aC aT xx 1),(12) 接上頁(yè) 26/43 謂詞邏輯中的推理 例6：使用

18、CP規(guī)則證明 證明： 因此原來(lái)的證明轉(zhuǎn)化為證明下式： ()()( )( )()( )() ( )xyP xQ yxP xy Q y ()( )()() () ( )() ( )() ( )() ( ) xP xy Qy x P xy Q yx P xy Q y 由于 ()()( )( )() ( )() ( )xyP xQ yx P xy Q y 27/43 謂詞邏輯中的推理 證明 ()()( )( )() ( )() ( )xyP xQ yx P xy Q y (1) () ( ) () (2) ( ) ,(1) (3) ()()( )( ) x P xP P aES xyP xQ y 附加

19、前提 (4) ()( )( ) ,(3) (5) ( )( ) ,(4) (6) ( ) ,(2), P yP aQ yUS P aQ bUS Q bT (5) (7) () ( ) ,(6) (8) () ( )()Q(y) ,(1),(7) y Q yUG x P xyCP 28/43 例7 對(duì)多個(gè)量詞的使用情況，觀察下列推理過(guò)程. 證明（證明（1） 前提前提),(yxyPx （2） （1）；）；US),(yzyP （3） （2）；）；ES),(dzP （4） （3）；）；UG),(dxxP （5） （4）；）；EG),(yxxPy 推出錯(cuò)誤結(jié)論：推出錯(cuò)誤結(jié)論： 與與 可交換可交換. yx

20、 注意：公式注意：公式(2)中中z有兩種可能有兩種可能 1)若若z是自由個(gè)體變?cè)?，則此時(shí)是自由個(gè)體變?cè)?，則此時(shí)y的值是隨的值是隨z的變化而變的變化而變 化的，因此不能用化的，因此不能用ES規(guī)則將規(guī)則將y改為個(gè)體常元改為個(gè)體常元d。 2)若若z是個(gè)體常元，則公式是個(gè)體常元，則公式(3)沒(méi)錯(cuò)，但此時(shí)不能用沒(méi)錯(cuò)，但此時(shí)不能用UG規(guī)規(guī) 則得到則得到(4) 。),(dxxP 錯(cuò) ！ 錯(cuò) ！ 29/43 謂詞邏輯求解實(shí)際問(wèn)題 步驟： 根據(jù)問(wèn)題的需要定義一組謂詞 將實(shí)際問(wèn)題符號(hào)化 使用推理規(guī)則有效推理 注意： 符號(hào)化的原則：全稱量詞對(duì)應(yīng)邏輯聯(lián)結(jié)詞 ，存在量詞對(duì)應(yīng)邏輯聯(lián)結(jié)詞 推理時(shí)首先引入帶存在量詞的前提，以

21、保 證“ES”規(guī)則的有效性 30/43 謂詞邏輯求解實(shí)際問(wèn)題 例8：證明蘇格拉底的三段論。 所有的人都是要死的， 蘇格拉底是人， 所以蘇格拉底是要死的。 解：M(x):x是人；D(x):x是要死的；c:蘇 格拉底。 蘇格拉底三段論可以表示成： 證明： (1) M(c) P (2) P (3) M(c)D(c) US, (2) (4) D(c) T,1,3 x(M(x)D(x),M(c)D(c) x(M(x)D(x) 31/43 謂詞邏輯求解實(shí)際問(wèn)題 例9：所有的自然數(shù)都是整數(shù)，任何整數(shù) 不是奇數(shù)就是偶數(shù)，并非每個(gè)自然數(shù)都是 偶數(shù)。所以，某些自然數(shù)是奇數(shù)。 解：第一步，定義謂詞： N(x)：x是

22、自然數(shù)； I(x)：x是整 數(shù)； Q(x)：x是奇數(shù)； O(x)：x是 偶數(shù)。 第二步，問(wèn)題符號(hào)化： ()( )( ) ()( ( )( ( )( ) ()( )( ) ()( )( ) x N xI x x I xQ xO x x N xO x x N xQ x 32/43 謂詞邏輯求解實(shí)際問(wèn)題 第三步，證明: ()( )( ),()( ( )( ( )( ) ()( )( )()( )( ) x N xI xx I xQ xO x x N xO xx N xQ x (1) ()( )( ) (2) () ( )( ) ,(1) (3) N(a)( ) ,(2) (4) x N xO xP

23、xN xO xT O aES N(a) ,(3) (4) ( ) ,(3) (5) ()( )( ) (6) N T O aT x N xI xP (a)I(a) ,(5) (7) I(a) ,(4),(6) US T 33/43 謂詞邏輯求解實(shí)際問(wèn)題 (8) ()( ( )( ( )( ) (9) ( )( ( )( ) ,(8) (10) ( )( ) ,(7),(9) (11) ( ) x I xQ xO xP I aQ aO aUS Q aO aT Q a ,(4),(10) (12) ( )( ) ,(4),(11) (13) ()( )( ) ,(12) T N aO aT x N

24、 xQ xEG 接上頁(yè) 34/43 謂詞邏輯求解實(shí)際問(wèn)題 例10：每個(gè)報(bào)考研究生的大學(xué)畢業(yè)生要 么參加研究生入學(xué)考試，要么推薦為免考 生；每個(gè)報(bào)考研究生的大學(xué)畢業(yè)生當(dāng)且僅 當(dāng)學(xué)習(xí)成績(jī)優(yōu)秀才被推薦為免試生；有些 報(bào)考研究生的大學(xué)畢業(yè)生學(xué)習(xí)成績(jī)優(yōu)秀， 但并非所有報(bào)考研究生的大學(xué)畢業(yè)生學(xué)習(xí) 成績(jī)都優(yōu)秀。因此，有些報(bào)考研究生的大 學(xué)畢業(yè)生要參加研究生入學(xué)考試。 解：定義謂詞如下： YJS(x)：x是要報(bào)考研究生的 大學(xué)畢業(yè)生； MKS(x)：x是免考生； CJYX(x)：x是成績(jī)優(yōu)秀的； CJKS(x)：x是參加考試的。 35/43 謂詞邏輯求解實(shí)際問(wèn)題 第二步，符號(hào)化問(wèn)題 ()( )( )( ) (

25、)( )( )( ) ()( )( ) ()( )( ) ()( )( ) x YJS xCJKS xMKS x x YJS xMKS xCJYX x x YJS xCJYX x x YJS xCJYX x x YJS xCJKS x 36/43 謂詞邏輯求解實(shí)際問(wèn)題 第三步，證明 (1) ()( )( ) (2) () ( )( ) ,(1) ( ) (a)( ) 3 x YJS xCJYX xP xYJS xCJYX xT YJSCJYX a ,(2) ( ) (a) ,( ) ( ) ( ) 43 5,( ) ( ) 3 6 ES YJST CJYX aT ()( )( )( ) ( )

26、 (a)( )( ) ,( ) ( ) (a)( ) ,( ),( ) ( ) 76 847 9 x YJS xCJKS xMKS xP YJSCJaMKS aUS CJKSMKS aT KS ()( )( )( ) xYJS xMKS xCJYX xP 37/43 謂詞邏輯求解實(shí)際問(wèn)題 () ( )( )( ) ,( ) () ( )( ) ,( ),() () ( ) 10 9 11410 12 YJS aMKS aCJYX aUS MKS aCJYX aT MKS a ,( ),() () ( ) ,( ),( () ( )( ) ,( ), 511 13812) 144 (13 1 )

27、 ( 5) KS T CJaT YJS aCJKS aT ()( )( ) 1 ,( 4)x YJS xCJKS xEG 接上頁(yè) 38/43 謂詞邏輯求解實(shí)際問(wèn)題 例11：所有的蜂鳥(niǎo)都五彩斑斕；沒(méi)有大鳥(niǎo)以蜜為生；不以蜜 為生的鳥(niǎo)都色彩單調(diào)；因此，蜂鳥(niǎo)都是小鳥(niǎo)。 解：定義謂詞如下： P(x)：x是只蜂鳥(niǎo)； Q(x)：x是大鳥(niǎo)； R(x)：x是以蜜為生的鳥(niǎo)； S(x)：x五彩斑斕。 ( ( )( ),( ( )( ), ( )( )( ( )( ) x P xS xx Q xR x xR xS xx P xQ x 39/43 謂詞邏輯求解實(shí)際問(wèn)題 ( ( )( ),( ( )( ), ( )( )

28、( ( )( ) x P xS xx Q xR x xR xS xx P xQ x 證明 ： (1)( ( )( ) (2)( )( )(1) (3)( )( ) (4)( )( ),(3) (5)( )( ),(4) (6)( ( )( ) (7)( )( ),(6) (8)( )( ),(7) (9)( )( ),(8) (10)( )( ),(2)(5) (11)( ) x P xS xP P xS xUS xR xS xP R xS xUS S xR xT x Q xR xP xQ xR xT Q xR xUS R xQ xT P xR xT P x ， ( ),(10)(9) (12

29、)( ( )( ),(11) Q xT x P xQ xUG 40/43 隨堂練習(xí) 練習(xí)：符號(hào)化下列命題，并利用推理規(guī)則 論證結(jié)論。 所有牛都有角，有些動(dòng)物是牛，所以有些 動(dòng)物有角 41/43 2.3謂詞公式的范式 命題邏輯中的兩種范式都可以直接推廣到 謂詞邏輯中來(lái)，只要把原子命題公式換成 原子謂詞公式即可， 根據(jù)量詞在公式中出現(xiàn)的情況不同，又可 分為前束范式和斯柯林范式。 42/43 前束范式 定義：對(duì)任一謂詞公式F，如果其中所有 量詞均非否定的出現(xiàn)在公式的最前面，且 它們的轄域?yàn)檎麄€(gè)公式，則稱公式F為前 束范式。 ()()()( ( , )( , )( , , )xyz P x yQ x yR x y z 43/43 前束范式 任意一個(gè)公式都可以轉(zhuǎn)化成與之等價(jià)的前 束范式，方法如下： 消去公式中的聯(lián)結(jié)詞 和，例如 將公式內(nèi)的否定符號(hào)深入到謂詞變?cè)安?化簡(jiǎn)到謂詞變?cè)爸挥幸粋€(gè)否定號(hào)； 利用改名、代入規(guī)則使所有的約束變?cè)?不同名，且使自由變?cè)c約束變?cè)嗖煌?名； 擴(kuò)充量詞的轄域至整個(gè)公式。 ()()ABABAB ABAB 44/43 前束范式 例：將下列公式轉(zhuǎn)化成前束范式。 解： () ( )() ( )() ( )x P xy R yx F x () ( )() ( )() ( )x P xy R yx F x () ( )() ( )() ( )x P xy R