第二章謂詞邏輯

1、第二章 謂詞邏輯1.什么叫做客體和客體變?cè)?？如何表示客體和客體變?cè)?.么叫做謂詞？3.什么叫做論域？我們定義一個(gè)“最大”的論域叫做什么？4.填空題：1存在量詞：記作( )，表示( )或者( )或者( )。2全稱量詞：記作( )，表示( )或者( )或者( )。5.什么叫做量詞的作用域？指出下面兩個(gè)謂詞公式中各個(gè)量詞的作用域。"x(F(x,y)$yP(y)Q(z)$xA(x)"x$y"z(A(x,y)B(x,y,z)C(t) 6.什么叫做約束變?cè)?？什么叫做自由變?cè)?？指出下面公式中哪些客體變?cè)羌s束變?cè)磕男┛腕w變?cè)亲杂勺冊(cè)?quot;x(F(x,y)$yP(y

2、)Q(z)$xA(x)7.填空：一個(gè)謂詞公式如果無(wú)自由變?cè)?，它就表示一個(gè)( )。8.給出的謂詞 J(x)：x是教練員， L(x) ：x是運(yùn)動(dòng)員， S(x) ：x是大學(xué)生，O(x) ：x是年老的，V(x) ：x是健壯的，C(x) ：x是國(guó)家選手，W(x) ：x是女同志， H(x) ：x是家庭婦女，A(x,y)：x欽佩y?？腕w j：金某人。用上面給出的符號(hào)將下面命題符號(hào)化 。 1所有教練員是運(yùn)動(dòng)員。 2某些運(yùn)動(dòng)員是大學(xué)生。 3某些教練是年老的，但是健壯的。4金教練既不老，但也不是健壯的。5不是所有運(yùn)動(dòng)員都是教練。6某些大學(xué)生運(yùn)動(dòng)員是國(guó)家選手。7沒有一個(gè)國(guó)家選手不是健壯的。8所有老的國(guó)家選手都是運(yùn)動(dòng)

3、員。9沒有一位女同志既是國(guó)家選手又是家庭婦女。10有些女同志既是教練又是國(guó)家選手。11所有運(yùn)動(dòng)員都?xì)J佩某些教練。12有些大學(xué)生不欽佩運(yùn)動(dòng)員。9.將下面命題符號(hào)化1金子閃光,但閃光的不一定都是金子。2沒有大學(xué)生不懂外語(yǔ)。3有些液體可以溶解所有固體。4每個(gè)大學(xué)生都愛好一些文體活動(dòng)。5每個(gè)自然數(shù)都有唯一的后繼數(shù)。10.令P表示天氣好。Q表示考試準(zhǔn)時(shí)進(jìn)行。A(x)表示x是考生。B(x)表示x提前進(jìn)入考場(chǎng)。C(x)表示x取得良好成績(jī)。E(x,y)表示x=y。利用上述符號(hào)，分別寫出下面各個(gè)命題的符號(hào)表達(dá)式。1 如果天氣不好，則有些考生不能提前進(jìn)入考場(chǎng)。2 只有所有考生提前進(jìn)入考場(chǎng)，考試才能準(zhǔn)時(shí)進(jìn)行。3 并

4、非所有提前進(jìn)入考場(chǎng)的考生都取得良好成績(jī)。4 有且只有一個(gè)提前進(jìn)入考場(chǎng)的考生未能取得良好成績(jī)。11.將下面命題符號(hào)化。1 對(duì)一個(gè)大學(xué)生來(lái)說(shuō)，僅當(dāng)他刻苦學(xué)習(xí)，才能取得優(yōu)異成績(jī)。(S(x):x是大學(xué)生；Q(x):x取得了優(yōu)異成績(jī)；H(x):x刻苦學(xué)習(xí)。)2 每個(gè)不等于0的自然數(shù)，都有唯一的前驅(qū)數(shù)。(Z(x):x是自然數(shù)； E(x,y):x=y； Q(x,y):y是x的前驅(qū)數(shù)。)12.<A,>是偏序集，B是A的非空子集。在括號(hào)內(nèi)分別寫入y是B的極小元、最小元、下界相應(yīng)的謂詞表達(dá)式。y是B的極小元Û( )y是B的最小元Û( )y是B的下界Û( )13.設(shè)論域D=

5、1,2 又已知a=1 b=2 f(1)=2 f(2)=1P(1,1)=T P(1,2)=T P(2 ,1)=F P(2,2)=F求謂詞公式"x$y(P(x,y)®P(f(x),f(y)的真值。(要求有解題的過(guò)程)14設(shè)論域?yàn)?,3，(x,y)表示 x+y=xy。求謂詞公式 Ø"x$yA(x,y) 的真值。(要求有解題的過(guò)程。)15.設(shè)謂詞P(x,y)表示x是y的因子，論域是1,2,3。求謂詞公式"x$yØA(x,y)的真值。(要求有解題過(guò)程) 16.令論域D=a,b，P(a,a)：F， Pa,b)：T， P(b,a)：T， P(b,b

6、)：F。公式( )的真值為真。A："x$yP(x,y) B：$x"yP(x,y) C："x"yP(x,y) D：Ø$x$yP(x,y)17.令論域D=a,b，P(a,a):F，P(a,b):T，P(b,a):T，P(b,b):F，公式( )的真值為真。a: Ø$x$yP(x,y) b: $x"yP(x,y) c: "x"yP(x,y) d: "x$yP(x,y)18.令Lx,y)表示x<y, 當(dāng)論域?yàn)? )時(shí), 公式"x$yL(x,y)的真值為假。a: 自然數(shù)集合 b: 整數(shù)集合

7、 c: 有理數(shù)集合 d:實(shí)數(shù)集合19.設(shè)論域?yàn)?,2,3，已知謂詞公式 $xP(x,3) ®("yØP(3,y) ®$zP(1,z) 的真值為假，則x=2時(shí)，使P(x,3)為真。此說(shuō)法是否正確？針對(duì)你的答案說(shuō)明原因。20.什么叫做對(duì)謂詞公式賦值？21.什么叫做謂詞公式的永真式？22.什么叫做謂詞公式A與B等價(jià)？23.什么叫做謂詞公式A永真蘊(yùn)含B？24.設(shè) 是個(gè)不含客體變?cè)獂的謂詞公式，在下面的等價(jià)公式中，哪些是不正確？說(shuō)明不正確的原因。1. "xA(x)BÛ"x(A(x)B)2. "xA(x)BÛ&quo

8、t;x(A(x)B)3. B"xA(x)Û"x(BA(x)4. "xA(x)BÛ"x(A(x)B)25.證明下面等價(jià)公式 $x(A(x)B(x)Û"xA(x)$xB(x) 26.證明下面等價(jià)公式 $xA(x)"xB(x)Þ"x(A(x)B(x) 27.下面謂詞公式等價(jià)成立嗎？對(duì)你的回答給予證明或者舉反例。$xA(x)$xB(x) Û $x(A(x)B(x) 28.下面謂詞公式等價(jià)成立嗎？對(duì)你的回答給予證明或者舉反例。"x(A(x)B(x) Û"x

9、A(x)"xB(x) 29.下面永真蘊(yùn)涵式成立嗎？對(duì)你的回答給予證明或者舉反例。$xA(x)$xB(x) Þ$x(A(x)B(x) 30.下面永真蘊(yùn)涵式成立嗎？對(duì)你的回答給予證明或者舉反例。"x(A(x)B(x) Þ"xA(x)"xB(x) 31.什么叫做謂詞公式的前束范式？32.不是謂詞公式 "x(A(x,y)®$yB(x,y) 的前束范式的為 ( )a: "x$y(A(x,t)® B(x,y) b: "x$t(A(x,y)® B(x,t) c: "x$y(A(x

10、,y)® B(x,y) d: "t$y(A(t,x)® B(t,y) 33.寫出謂詞公式 "x(P(x)R(x)(Ø$xP(x)Q(x)的前束范式。34.分別指出推理規(guī)則US、ES、的名稱、形式、作用以及使用這些規(guī)則時(shí)的注意事項(xiàng)。35.舉例說(shuō)明在謂詞推理時(shí)，使用ES時(shí)所指定的客體c不應(yīng)該是在此之前用US規(guī)則所指定的客體c (即本次用ES特指客體c，不應(yīng)該是以前特指的客體)。并分析發(fā)生的錯(cuò)誤。36.舉例說(shuō)明在謂詞推理時(shí)，使用ES時(shí)所指定的客體c不應(yīng)該是在此之前用ES規(guī)則所指定的客體c (即本次用ES特指客體c，不應(yīng)該是以前特指的客體)。并分析發(fā)生

11、的錯(cuò)誤。37.分別指出推理規(guī)則EG、UG的名稱、形式、作用以及使用這些規(guī)則時(shí)的注意事項(xiàng)。38.用謂詞邏輯推理的方法證明下面推理的有效性。(要求按照推理的格式書寫推理過(guò)程。)"xC(x), $x(A(x)ÚB(x), "x(B(x)®ØC(x) Þ $xA(x)39.用謂詞邏輯推理的方法證明下面推理的有效性。(要求按照推理的格式書寫推理過(guò)程。) “不認(rèn)識(shí)錯(cuò)誤的人，也不能改正錯(cuò)誤。有些誠(chéng)實(shí)的人改正了錯(cuò)誤。所以有些誠(chéng)實(shí)的人是認(rèn)識(shí)了錯(cuò)誤的人?！痹O(shè)A(x):x是認(rèn)識(shí)錯(cuò)誤的人。 B(x):x改正了錯(cuò)誤。C(x):x是誠(chéng)實(shí)的人。命題符號(hào)化為：&qu

12、ot;x(ØA(x)ØB(x)，$x(C(x)B(x), Þ $x(C(x)A(x)40.用謂詞邏輯推理證明下面推理的有效性。（要求按照推理格式書寫推理過(guò)程。）"x(A(x)®(ØB(x)ÚØC(x), "x(A(x)®(ØC(x)®D(x), $x(A(x)ÙØD(x) Þ $x(A(x)ÙØB(x)41.用謂詞邏輯推理證明下面推理的有效性。$x(A(x)Ù(B(x)®ØC(x), "

13、x(A(x) ® (C(x) ÚØD(x), "x(A(x) ®D(x) Þ $x(A(x) ÙØ B(x)42.用謂詞邏輯推理證明下面推理的有效性。（要求按照推理格式書寫推理過(guò)程。）“鳥都會(huì)飛。猴子都不會(huì)飛。所以，猴子都不是鳥?！?3.用謂詞邏輯推理證明下面推理的有效性。（要求按照推理格式書寫推理過(guò)程。）“一些病人喜歡所有醫(yī)生。任何病人都不喜歡庸醫(yī)。所以沒有醫(yī)生是庸醫(yī)?！?4. 給定謂詞如下：S(x):x是學(xué)生；L(x):x是校領(lǐng)導(dǎo)； G(x):x是好的；T(x):x是老師；P(x): x受過(guò)處分； C(x,y)

14、:y表?yè)P(yáng)x。用上述謂詞表達(dá)下面各個(gè)命題，并且用謂詞邏輯推理方法證明下面推理的有效性?！皼]有受過(guò)處分的學(xué)生，都受到過(guò)校領(lǐng)導(dǎo)的表?yè)P(yáng)；有些好學(xué)生，僅僅受到老師的表?yè)P(yáng)；所有好學(xué)生，都沒有受過(guò)處分。所以，有的老師是校領(lǐng)導(dǎo)?！?5.用謂詞邏輯推理證明下面推理的有效性。（要求按照推理格式書寫推理過(guò)程。）“任何人如果他喜歡步行，他就不喜歡乘汽車；每個(gè)人或者喜歡乘汽車或者喜歡騎自行車。有的人不愛騎自行車，因此有的人不愛步行?！?6. 給定謂詞 M(x):x是高山俱樂(lè)部成員。H(x):x是滑雪者。 D(x):x是登山者。L(x,y):x喜歡y。 客體：a:小楊；b:小劉；c:小林；d:雨；e:雪。用謂詞邏輯推理證

15、明方法，解決下面問(wèn)題。（要求按照推理格式書寫推理過(guò)程。）“小楊、小劉和小林為高山俱樂(lè)部成員，該俱樂(lè)部的每個(gè)成員是個(gè)滑雪者或登山者。沒有一個(gè)登山者喜歡雨。而所有滑雪者都喜歡雪。凡是小楊喜歡的，小劉就不喜歡。小楊喜歡雨和雪。試證明該俱樂(lè)部是否有個(gè)是登山者而不是滑雪者的成員。如果有，他是誰(shuí)？”47.用謂詞邏輯推理證明下面推理的有效性。（要求按照謂詞邏輯推理格式，書寫推理過(guò)程。）$x(ØP(x)® Q(x), "x(ØQ(x)ÚØR(x), "xR(x) Þ$xP(x)48.用謂詞邏輯推理證明下面推理的有效性。 （要求按照

16、謂詞邏輯推理格式，書寫推理過(guò)程。）"x(P(x)®(Q(x)ÙR(x), Ø"x(R(x)®Q(x) Þ$x(R(x)ÙØP(x)49. 用謂詞邏輯推理證明下面推理的有效性。(要求：按照教材中推理的格式寫出推理過(guò)程)"x(ØC(x)Ú(ØA(x)ÚØB(x), "x(A(x)®(ØC(x)®D(x), Ø"x(ØA(x)ÚD(x) Þ $x(A(x)

17、7;ØB(x) 50.用謂詞邏輯推理證明下面推理的有效性。(要求：按照邏輯推理格式書寫推理過(guò)程) "x($y(S(x,y) ÙM(y) ® $z(P(z)ÙR(x,z) ÞØ$zP(z) ®"x"y (S(x,y) ® ØM(y)51.設(shè)：(x)表示x是自然數(shù)；(x)表示x是奇數(shù)；(x)表示x是偶數(shù)；(x)表示x能被整除。用上面給定的謂詞表示下面各個(gè)命題，然后用謂詞邏輯推理方法證明下面推理的有效性。（注：要按照教材中推理的書寫格式描述推理過(guò)程）“每個(gè)自然數(shù)不是奇數(shù)就是偶數(shù)；所

18、有奇數(shù)都不能被整除；有些自然數(shù)能被整除；因此，有些自然數(shù)是偶數(shù)?！?2.用謂詞邏輯推理方法證明下面推理的有效性。（注：要按照教材中推理的書寫格式描述推理過(guò)程）$x(A(x)ÙØ"y(ØB(y)ÚØC(x,y), "x(A(x)®"y(D(y )® ØC(x,y) Þ$y(B(y)Ù ØD(y) 53.用謂詞邏輯推理證明下面推理的有效性。(要求按照教材格式寫出推理過(guò)程)"x(A(x)®$y(B(y)®ØC(x,y),

19、"x(A(x)®"y(C(x,y)ÚD(y), $xA(x)Ù"yØD(y)Þ $yØB(y)54. 給定謂詞如下：A(x):x是書刊；B(x)：x是合法出版的；C(x)：x是人；D(x)：x感到憂慮。先用這些謂詞將下面各個(gè)命題符號(hào)化，再用謂詞邏輯推理方法證明這個(gè)推理是正確的。“如果有些書刊是非法出版的，則所有人都感到憂慮。一些人不感到憂慮。因此，所有書刊都是合法出版的?！?5.用謂詞邏輯推理證明下面推理的有效性。(按照教材格式寫出推理過(guò)程)$xA(x), $x(B(x)ÙØC(x),

20、 "z(A(z)Ù"x$yD(x,y)®"y(B(y)®C(y), Þ"y$xØD(x,y)56.給定謂詞：N(x):x是自然數(shù)，E(x):x是偶數(shù)，O(x):x是奇數(shù)，D(x,y):x可被y整除。用上述謂詞表達(dá)下面各命題，并用謂詞邏輯推理方法證明其推理的有效性?！懊總€(gè)自然數(shù)不是偶數(shù)，就是奇數(shù)。自然數(shù)為偶數(shù)，當(dāng)且僅當(dāng)它能被2整除。并不是所有自然數(shù)都可以被2整除。所以，有的自然數(shù)是奇數(shù)?！?7.用謂詞推理證明下面推理的有效性。（注：要按照教材中推理的書寫格式描述推理過(guò)程）$x(A(x)Ù$y(B(

21、y)ÙC(x,y), "x(A(x)®"y(D(y)®ØC(x,y) ÞØ"y(B(y)®D(y) 58.分析下面推理過(guò)程是否正確。如果有錯(cuò)誤，請(qǐng)指出錯(cuò)誤所在之處。并寫出正確的推理過(guò)程。"x(A(x)B(x)， $xA(x) Þ $xB(x) "x(A(x)B(x) P A(c)B(c) US $xA(x) P A(c) ES B(c) T I11 $xB(x) EG 59.用謂詞邏輯推理的方法證明下面推理的有效性。要求按照推理的格式書寫推理過(guò)程。 $xP(x),

22、"x(Q(x) ®Ø R(x), "x(ØP(x)Ú R(x) Þ $xØ Q(x)1.答案：定義：能夠獨(dú)立存在的事物，稱之為客體，也稱之為個(gè)體。它可以是具體的，也可以是抽象的事物。通常用小寫英文字母a、b、c、.表示。定義：用小寫英文字母x、y、z.表示任何客體，則稱這些字母為客體變?cè)?.答案：定義：一個(gè)大寫英文字母后邊有括號(hào)，括號(hào)內(nèi)是若干個(gè)客體變?cè)?，用以表示客體的屬性或者客體之間的關(guān)系，稱之為謂詞。如果括號(hào)內(nèi)有n個(gè)客體變?cè)Q該謂詞為n元謂詞。3.答案：定義：在命題函數(shù)中客體變?cè)娜≈捣秶Q之為論域，也稱之

23、為個(gè)體域。論域是一個(gè)集合。定義：由所有客體構(gòu)成的論域，稱之為全總個(gè)體域。它是個(gè)“最大”的論域。4.答案：1存在量詞：記作($ )，表示 ( 有些 ) 或者( 一些 )或者( 至少一個(gè) )。2全稱量詞：記作(" )，表示 ( 每個(gè) ) 或者(任何一個(gè) )或者( 所有的 )。5.答案：在謂詞公式中，量詞的作用范圍稱之為量詞的作用域，也叫量詞的轄域。在"x(F(x,y)$yP(y)Q(z)$xA(x)中："x的作用域：(F(x,y)$yP(y)$y的作用域：P(y)$x的作用域：A(x)在"x$y"z(A(x,y)B(x,y,z)C(t)中：&quo

24、t;x的作用域：$y"z(A(x,y)B(x,y,z)$y的作用域："z(A(x,y)B(x,y,z)"z的作用域：(A(x,y)B(x,y,z)6.答案：定義：如果客體變?cè)獂在"x或者$x的轄域內(nèi)，則x在此轄域內(nèi)約束出現(xiàn)，并稱x在此轄域內(nèi)是約束變?cè)７駝tx是自由出現(xiàn)，并稱x是自由變?cè)Ｔ?quot;x(F(x,y)$yP(y)Q(z)$xA(x)中F(x,y)中的x和P(y)中的y以及A(x)中x是約束變?cè)?。而F(x,y)中的y和Q(z)中的z是自由變?cè)?.答案：(命題)8. 答案：1"x(J(x)L(x) 2$x(L(x)S(x)3$x(

25、J(x)O(x)V(x) 4J(j)ØO(j)ØV(j)5Ø"x(L(x)J(x) 或者 $x(L(x)ØJ(x)6$x(S(x)L(x)C(x) 7$Øx(C(x)ØV(x) 或者 "x(C(x)V(x) 8"x(O(x)C(x)L(x) 9Ø$x(W(x)C(x)H(x) 10$x(W(x)J(x)C(x) 11"x(L(x)$y(J(y)A(x,y)12$x(S(x)"y(L(y)ØA(x,y)9.答案：1設(shè)：G(x)：x是金子。 F(x)：x閃光。則命題的表

26、達(dá)式為"x(G(x)®F(x) ÙØ"x(F(x)®G(x) 或者"x(G(x)®F(x) Ù$x(F(x) ÙØG(x) 2設(shè) S(x)：x是大學(xué)生。F(x)：x是外語(yǔ)。K(x,y)：x懂得y。則命題的表達(dá)式為Ø$x(S(x)Ù"y(F(y) ®ØK(x,y) 或者"x(S(x) ®$y(F(y)ÙK(x,y)3設(shè)F(x)：x是液體。.S(x)：x是固體。D(x,y)：x可溶解y。則命題的表達(dá)式為$x(F

27、(x)Ù"y(S(y)®D(x,y)4設(shè)S(x)：x是大學(xué)生。L(x,y)：x愛好y。C(x)：x是文娛活動(dòng)。P(x)：x是體育活動(dòng)。則命題的表達(dá)式為："x(S(x) ®$y(C(y)P(y)ÙL(x,y) 5設(shè)令N(x)：x是自然數(shù)。A(x,y)：y是x的后繼數(shù)。 E(x,y)：x=y 則命題的表達(dá)式為"x(N(x)$y(N(y)A(x,y)"z(N(z)A(x,z)E(y,z) 10.答案：1ØP®$xA(x)Ù ØB(x)2Q®"x(A(x)

28、4; D(x)3Ø"x(A(x) Ù(B(x)® C(x)4$xA(x)ÙB(y) ÙØC(x) Ù"y(A(y) ÙB(y) ÙC(y)® E(x,y)11.答案：1"x(S(x)(Q(x)H(x)2"x(Z(x)ØE(x,0)$y(Z(y)Q(x,y)"z(Z(z)Q(x,z)E(y,z) 12.答案：y是B的極小元Û( $y(yBØ$x(xBxyxy)y是B的最小元Û( $y(yB"x(xB

29、yx) )y是B的下界Û( $y(yA"x(xByx)13.答案：解： "x$y(P(x,y)®P(f(x),f(y)Û$y(P(1,y) ®P(f(1),f(y) Ù$y(P(2,y) ®P(f(2),f(y)Û(P(1,1) ®P(f(1),f(1)Ú (P(1,2) ®P(f(1),f(2)Ù P(2,1) ®P(f(2),f(1)Ú(P(2,2) ®P(f(2),f(2) Û(P(1,1) ®P(2,2)&#

30、218;(P(1,2) ®P(2,1)Ù (P(2,1) ®P(1,2)Ú(P(2,2) ®P(1,1)Û(T®F )Ú (T®F)Ù(F®T) Ú (F®T)Û(FÚ F)Ù(T Ú T)ÛFÙT ÛF14.答案：解： Ø"x$yA(x,y) Û$x"yØA(x,y)Û"yØA(2,y) Ú"y&

31、#216;A(3,y)Û(ØA(2,2) Ù ØA(2,3) Ú( ØA(3,2) Ù ØA(3,3) )Û (FÙ T) Ú (TÙ T)ÛFÚ TÛT 15.答案：解： "x$yØA(x,y) Û$yØA(1,y) Ù $yØA(2,y) Ù$yØA(3,y)Û(ØA(1,1) ÚØA(1,2) ÚØA(

32、1,3)Ù(ØA(2,1) ÚØA(2,2) ÚØA(2,3) Ù (ØA(3,1) ÚØA(3,2) ÚØA(3,3) Û(F ÚF) ÚF)Ù (T ÚF) ÚT) Ù (T ÚT ÚT) ÛF 16.答案：A17.答案：令論域D=a,b，P(a,a):F，P(a,b):T，P(b,a):T，P(b,b):F，公式( d )的真值為真。a: Ø$x$yP(x,y)

33、 b: $x"yP(x,y) c: "x"yP(x,y) d: "x$yP(x,y) 因?yàn)閍: Ø$x$yP(x,y)ÛØ($yP(a,y)Ú$yP(b,y)ÛØ(P(a,a)ÚP(a,b)Ú(P(b,a)ÚP(b,b)ÛØ(FÚT)Ú(TÚF) ÛFb: $x"yP(x,y) Û "yP(a,y)Ú"yP(b,y)Û(P(a,a)ÙP(

34、a,b)Ú(P(b,a)ÙP(b,b)Û (FÙT) Ú (TÙF) ÛF c: "x"yP(x,y) Û"yP(a,y) Ù"yP(b,y)Û(P(a,a)ÙP(a,b)Ù(P(b,a)ÙP(b,b)Û (FÙT)Ù(TÙF) ÛF d:"x$yP(x,y)Û $yP(a,y) Ù$yP(b,y)Û (P(a,a)ÚP(a,b

35、)Ù(P(b,a)ÚP(b,b)Û (FÚT)Ù(TÚF) ÛT 18.答案：a19.答案：解：此說(shuō)法正確。因?yàn)?xP(x,3)®("yØP(3,y)®$zP(1,z) 的真值為假，所以 $xP(x,3) 的真值為真，"yØP(3,y) 的真值為真，$zP(1,z) 的真值為假。由$xP(x,3) 的真值為真，得P(1,3)為真，或者P(2,3)為真，或者P(3,3)為真。由"yØP(3,y) 的真值為真，得P(3,1)、P(3,2)、P(3,3

36、)均為假。由$zP(1,z) 的真值為假，得P(1,1)、P(1,2)、P(1,3)均為假。綜合上述情況得, P(2,3)為真，20.答案：若將給定的謂詞公式中的命題變?cè)?，用確定的命題代替，對(duì)公式中的客體變?cè)谜撚蛑械目腕w代替，這個(gè)過(guò)程就稱之為對(duì)謂詞公式作指派，或稱之為對(duì)謂詞公式賦值。21.答案：給定謂詞公式A，E是其論域，如果不論對(duì)公式A作任何賦值，都使得A的真值為真，則稱公式A在論域E上是永真式。如果不論對(duì)什么論域E，都使得公式A為永真式，則稱A為永真式。22.答案：給定謂詞公式A、B，E是它們的論域，如果不論對(duì)公式A、B作任何賦值，都使得A與B的真值相同(或者說(shuō)A«B是永真式)

37、，則稱公式A與B在論域E上是等價(jià)的。如果不論對(duì)什么論域E，都使得公式A與B等價(jià)，則稱A與B等價(jià)，記作AÛB。23.答案：給定謂詞公式A、B，E是它們的論域，如果不論對(duì)公式A、B作任何賦值，使得AB為永真式，則稱在論域E上公式A永真蘊(yùn)含B。如果不論對(duì)什么論域E，都使得公式AB為永真式，則稱A永真蘊(yùn)含B，記作AÞB。24.答案：解：4式不正確。因?yàn)?quot;xA(x)BÛØ"xA(x)BÛ$xØA(x)BÛ$x(ØA(x)B) Û$x(A(x)B)所以 "xA(x)B不等價(jià)于 "

38、;x(A(x)B)，即4式不成立。25.答案：證明 "xA(x)$xB(x)ÛØ"xA(x)$xB(x) Û$xØA(x)$xB(x)Û$x(ØA(x)B(x)Û$x(A(x)B(x) 26.答案：證明 $xA(x)"xB(x)ÛØ$xA(x)"xB(x) Û"xØA(x)"xB(x) Þ"x(ØA(x)B(x)Û"x(A(x)B(x)27.答案：不成立。因?yàn)楦鶕?jù)量詞分配公式知

39、道，只有公式 $x(A(x)B(x) Þ $xA(x)$xB(x) 成立。而沒有 $xA(x)$xB(x) Þ $x(A(x)B(x)?？梢耘e如下反例說(shuō)明：令A(yù)(x)表示x是男生， B(x)表示x是女生。則 $xA(x)$xB(x)表示“有些人是男生也有些人是女生”，這顯然是真的命題。而$x(A(x)B(x)表示“有這樣的人，他既是男生也是女生。”，這顯然是假命題。所以$xA(x)$xB(x)Þ$ x(A(x)B(x) 不成立。所以沒有等價(jià)公式 $xA(x)$xB(x) Û $x(A(x)B(x) 成立。28.答案：不成立。因?yàn)楦鶕?jù)量詞分配公式知道，只有

40、公式 "xA(x)"xB(x) Þ"x(A(x)B(x) 成立。而沒有"x(A(x)B(x) Þ"xA(x)"xB(x)。可以舉如下反例說(shuō)明：令A(yù)(x)表示x是男生， B(x)表示x是女生。則 "x(A(x)B(x)表示“任何一個(gè)人來(lái)說(shuō)，他或者是男生或者是女生。”，這顯然是真的命題。而"xA(x)"xB(x)表示“要么大家都是男生，要么大家都是女生?！保@然由"x(A(x)B(x)不能推出"xA(x)"xB(x)。所以"x(A(x)B(x) &#

41、222; "xA(x)"xB(x) 不成立。所以沒有等價(jià)公式 "x(A(x)B(x) Û"xA(x)"xB(x) 成立。29.答案：不成立?？梢耘e如下反例說(shuō)明：令A(yù)(x)表示x是男生， B(x)表示x是女生。則 前件$xA(x)$xB(x)表示“有些人是男生也有些人是女生”，這顯然是真的命題。而后件$x(A(x)B(x) 表示“有這樣的人，他既是男生也是女生?！边@顯然是假命題。所以$xA(x)$xB(x)Þ$ x(A(x)B(x) 不成立。30.答案：不成立?？梢耘e如下反例說(shuō)明：令A(yù)(x)表示x是男生， B(x)表示x是女生

42、。則前件 "x(A(x)B(x) 表示“任何一個(gè)人來(lái)說(shuō)，他或者是男生或者是女生?！边@顯然是真的命題。而后件 "xA(x)"xB(x) 表示“要么大家都是男生，要么大家都是女生?！憋@然由"x(A(x)B(x)不能推出"xA(x)"xB(x)。所以"x(A(x)B(x) Þ "xA(x)"xB(x) 不成立。31.答案：前束范式定義： 一個(gè)謂詞公式符合下面條件，就是前束范式：所有量詞前面都沒有聯(lián)接詞；所有量詞都在公式的左面；所有量詞的轄域都延伸到公式的末尾。32.答案：c33.答案：解"x

43、(P(x)R(x)(Ø$xP(x)Q(x)ÛØ"x(P(x)R(x)(Ø$xP(x)Q(x) (去)Û$xØ(P(x)R(x)("xØP(x)Q(x) (量詞轉(zhuǎn)換)Û$x(ØP(x)ØR(x)("xØP(x)Q(x) (后移Ø)Û$x(ØP(x)ØR(x)("yØP(y)Q(z) (換變?cè)?Û$x(ØP(x)ØR(x)"y(ØP(y)Q(z) (擴(kuò)

44、量詞轄域)Û$x"y(ØP(x)ØR(x)(ØP(y)Q(z) (擴(kuò)量詞轄域)34.答案：US：全稱特指規(guī)則 (Universal Specialization)形式： "xA(x)ÞA(c) (其中c是論域內(nèi)指定客體)作用：去掉全稱量詞。注意事項(xiàng)：c不是A(x)中的符號(hào)。ES：存在特指規(guī)則 (Existential Specialization)形式： $xA(x)ÞA(c) (其中c是論域內(nèi)指定客體)作用：去掉存在量詞。注意事項(xiàng)： c不是A(x)中的符號(hào)。 用ES指定的客體c不應(yīng)該是在此之前用US規(guī)則或者用ES

45、規(guī)則所指定的客體c (即本次用ES特指客體c，不應(yīng)該是以前特指的客體)。35.答案：例： 令A(yù)(x)表示x是自然數(shù)，B(x)表示x是整數(shù)。 "x(A(x)B(x) P A(c)B(c) US 如c=0.1 $xA(x) P A(c) × ES A(0.1)為F得出0.1是自然數(shù)的錯(cuò)誤結(jié)論。36.答案：例： 令A(yù)(x)表示x是自然數(shù)，B(x)表示x是整數(shù)。 $xB(x) P B(c) ES 如c1 $xA(x) P A(c) × ES A(1)為F得出1是自然數(shù)的錯(cuò)誤結(jié)論。37.答案：EG：存在推廣規(guī)則 (Existential Generalization)形式：

46、 A(c)$ÞxA(x) (其中c是論域內(nèi)指定客體)作用：添加存在量詞。注意事項(xiàng)：x不是A(c)中的符號(hào)。UG：全稱推廣規(guī)則 (Universal Generalization)形式： A(c)Þ"xA(x) (其中c是論域內(nèi)任何指定客體)作用：添加全稱量詞。注意事項(xiàng)：x不是A(c)中的符號(hào)。c一定是任意的客體，否則不可全稱推廣。38.答案： $x(A(x)ÚB(x), P A(a)ÚB(a) ES "xC(x) P C(a) US "x(B(x)ØC(x) P B(a)ØC(a) US ØB(

47、a) T I12 A(a) T I10 $xA(x) EG 39.答案： $x(C(x)B(x) P C(c)B(c) ES C(c) T I1 B(c) T I2 "x(ØA(x)ØB(x) P ØA(c)ØB(c) US ØØA(c) T I12 A(c) T E1 C(c)A(c) T I9 $x(C(x)A(x) EG 40.答案：證明. $x(A(x)ÙØD(x) P A(a)ÙØD(a) ES A(a) T I ØD(a) T I "x(A(x)

48、4;(ØC(x)®D(x) P A(a)®(ØC(a)®D(a) US ØC(a)®D(a) T I C(a) T I "x(A(x)®(ØB(x)ÚØC(x) P A(a)®(ØB(a)ÚØC(a) US ØB(a)ÚØC(a) T I ØB(a) T I A(a)ÙØB(a) T I $x(A(x)ÙØB(x) EG 41.答案：證明. $x(A(x)&

49、#217;(B(x)®ØC(x), P A(a)Ù(B(a)®ØC(a) ES A(a) T I (B(a)®ØC(a) T I "x(A(x) ® (C(x) ÚØD(x) P A(a) ® (C(a) ÚØD(a) US (C(a) ÚØD(a) T I "x(A(x) ®D(x) P A(a) ®D(a) US D(a) T I C(a) T I ØB(a) T I A(a)Ù&#

50、216;B(a) T I $x(A(x)ÙØB(x) EG 42.答案：證明.設(shè) B(x):x是鳥；F(x):x會(huì)飛；M(x):x是猴子。命題符號(hào)化為："x(B(x)F(x)， "x(M(x)ØF(x) Þ "x(M(x)ØB(x) "x(B(x)F(x) P B(a)F(a) US "x(M(x)ØF(x) P M(a)ØF(a) US ØF(a)ØB(a) T E18 M(a)ØB(a) T I13 "x(M(x)ØB(x

51、) UG 43.答案：證明.設(shè): P(x):x是病人, D(x):x是醫(yī)生, Q(x):x是庸醫(yī), L(x,y): x喜歡y. 命題符號(hào)化：$x(P(x)"y(D(y)L(x,y)， "x(P(x)"y(Q(y)ØL(x,y) ÞØ$y(D(y)Q(y) $x(P(x)"y(D(y)L(x,y) P P(a)"y(D(y)L(a,y) ES P(a) T I1 "y(D(y)L(a,y) T I2 "x(P(x)"y(Q(y)ØL(x,y) P P(a)"y(Q(y

52、)ØL(a,y) US "y(Q(y)ØL(a,y) T I11 D(b)L(a,b) US Q(b)ØL(a,b) US L(a,b) ØQ(b) T E18 D(b)ØQ(b) T I13 ØD(b)ØQ(b) T E16 Ø(D(b)Q(b) T E8 "yØ(D(y)Q(y) UG $Øy(D(y)Q(y) T E2544.答案：證明. 上述各個(gè)命題符號(hào)化為： "x(S(x) ÙØP(x) ®$y(L(y)ÙC(x,y

53、), $x(S(x)ÙG(x)Ù"y(C(x,y)®T(y) ,"x(S(x) ÙG(x) ®ØP(x) Þ$y(T(y)ÙL(y) $x(S(x)ÙG(x)Ù"y(C(x,y)®T(y) P (S(a)ÙG(a)Ù"y(C(a,y)®T(y) ES S(a)ÙG(a) T I1 "x(S(x) ÙG(x) ®ØP(x) P (S(a) ÙG(a) 

54、4;ØP(a) US ØP(a) T I11 S(a) T I1 S(a) Ù ØP(a) T I9 "x(S(x) ÙØP(x) ®$y(L(y)ÙC(x,y) P (S(a) ÙØP(a) ®$y(L(y)ÙC(a,y) US $y(L(y)ÙC(a,y) T I2 L(b) ÙC(a,b) ES C(a,b)®T(b) US L(b) T I1 C(a,b) T I2 T(b) T I11 T(b)ÙL(b) T I9

55、$y(T(y)ÙL(y) EG 45.答案：證明. 設(shè) A(x):x是人, B(x):x是喜歡步行, C(x):x喜歡乘汽車，D(x):x喜歡騎自行車。上述各個(gè)命題符號(hào)化為："x(A(x)(B(x)ØC(x), "x(A(x)(C(x)D(x), $x(A(x)ØD(x) Þ $x(A(x)ØB(x) $x(A(x)ØD(x) P A(a)ØD(a) ES A(a) T I ØD(a) T I "x(A(x)(B(x)ØC(x) P A(a)(B(a)ØC(a) U

56、S B(a)ØC(a) T I "x(A(x)(C(x)D(x) P A(a)(C(a)D(a) US C(a)D(a) T I C(a) T I ØB(a) T I A(a)ØB(a) T I $x(A(x)ØB(x) EG 46.答案：命題符號(hào)化為：M(a), M(b), M(c), "x(M(x)( H(x)D(x), Ø$x(D(x)L(x,d), "x(H(x)L(x,e) "y(L(a,y)ØL(b,y), L(a,d)L(a,e) L(a,d)L(a,e) P L(a,e) T &

57、quot;y(L(a,y)ØL(b,y) P L(a,e)ØL(b,e) US ØL(b,e) T I11 "x(H(x)L(x,e) P H(b)L(b,e) US ØH(b) T I12 "x(M(x)(H(x)D(x) P M(b)(H(b)D(b) US M(b) P H(b)D(b) T I11 D(b) T I10 D(b)ØH(b) T 所以小劉是登山者，而不是滑雪者。47.答案： $x (ØP(x)® Q(x) P ØP(a)® Q(a) ES "xR(x)

58、P R(a) US "x(ØQ(x)ÚØR(x) P ØQ(a)ÚØR(a) US ØQ(a) T I12 ØØP(a) T I10 P(a) T E1 $xA(x) EG 48.答案： Ø"x(R(x)®Q(x) P $ xØ (R(x)®Q(x) T E Ø (R(a)®Q(a) ES Ø (ØR(a)ÚQ (a) T E R(a) ÙØQ (a) T E R(a) T I

59、 ØQ(a) T I "x(P(x)®(Q(x)ÙR(x), P P(a)®(Q(a)ÙR(a) US ØQ(a)ÚØR(a) T I Ø(Q (a) ÙR(a) T E ØP(a) T I R(a) ÙØP (a) T I $x(R(x)ÙØP(x) EG 49.答案： Ø"x(ØA(x)ÚD (x) P $ xØ (ØA(x)ÚD(x) T E Ø (&

60、#216;A(a)ÚD(a) ES A(a) ÙØD (a) T E A(a) T I ØD(a) T I "x(A(x)®(ØC(x)®D(x) P A(a)(ØC(a)® D(a) US ØC(a)® D(a) T I C(a)D(a) T E C(a) T I "x(ØC(x)Ú(ØA(x)ÚØB(x) P ØC(a)Ú(ØA(a)ÚØB(a) US Ø

61、;A(a)ÚØB(a) T I ØB(a) T I A(a)ØB(a) T I $x(A(x)ØB(x) EG 50.答案： Ø$zP(z) P (附加前提) "zØP(z) T E "x($y(S(x,y) ÙM(y) ® $z(P(z)ÙR(x,z) P $y(S(a,y) ÙM(y) ® $z(P(z)ÙR(a,z) US ØP(b) US ØP(b)ÚØR(a,b) T I Ø(P(b)&

62、#217;R(a,b) T E "zØ(P(z)ÙR(a,z) UG Ø$z (P(z)ÙR(a,z) T E Ø$y(S(a,y) ÙM(y) T I "yØ (S(a,y) ÙM(y) T E "y (ØS(a,y) ÚØM(y) T E "y (S(a,y) ®ØM(y) T E "x "y (S(x,y) ®ØM(y) US Ø$zP(z) ®"x&

63、quot;y (S(x,y) ® ØM(y) CP51.答案：先命題符號(hào)化為："x(N(x)(ØO(x)E(x), "x(O(x)ØC(x), $x(N(x)C(x) Þ $x(N(x)E(x) $x(N(x)C(x) P N(a)C(a) ES N(a) T I C(a) T I "x(O(x)ØC(x) P O(a)ØC(a) US ØO(a) T I "x(N(x)(ØO(x)E(x) P N(a)(ØO(a)E(a) US ØO(a)E(

64、a) T I E(a) T I N(a)E(a) T I $x(N(x)E(x) EG 52.答案：證明. $x(A(x)Ù Ø"y(ØB(y)ÚØC(x,y), P A(a)Ù Ø"y(ØB(y)ÚØC(a,y) ES A(a) T I Ø"y(ØB(y)ÚØC(a,y) T I $yØ(ØB(y)ÚØC(a,y) T E $y(B(y)ÙC(a,y) T E "x

65、(A(x)®"y(D(y )® ØC(x,y) P A(a)®"y(D(y )® ØC(a,y) US "y(D(y )® ØC(a,y) T I B(b)ÙC(a,b) ES B(b) T I C(a,b) T I D(b)® ØC(a,b) US ØD(b) T I B(b)ÙØD(b) T I $y(B(y)ÙØD(y) EG 53.答案：證明. $xA(x) Ù"yØD(y) P $xA(x) T I "yØD(y) T I