離散數(shù)學(xué)復(fù)習(xí)題及答案

1、1. 寫出命題公式 （P （P Q）的真值表。答案：2.證明 答案：3. 證明以下蘊涵關(guān)系成立： 答案：4. 寫出下列式子的主析取范式：答案：5. 構(gòu)造下列推理的論證：pq, pØr, st, Øsr, Øt Þ q答案：st 前提 t 前提s 拒取式I12sr 前提r 假言推理I11pr 前提p 拒取式I12pq 前提q 析取三段論I106. 用反證法證明：p(Ø(rs)Øq), p, Øs Þ Øq7. 請將下列命題符號化：所有魚都生活在水中。答案：令F( x )：x是魚 W( x )：x生活在水中8

2、. 請將下列命題符號化：存在著不是有理數(shù)的實數(shù)。答案：令 Q ( x )：x 是有理數(shù) R ( x )：x 是實數(shù)9. 請將下列命題符號化：盡管有人聰明，但并非一切人都聰明。答案：令M(x)：x 是人 C(x)：x 是聰明的 則上述命題符號化為10. 請將下列命題符號化：對于所有的正實數(shù)x,y，都有x+yx。答案：令P(x):x是正實數(shù) S(x,y): x+yx11. 請將下列命題符號化：每個人都要參加一些課外活動。答案：令P(x):x是人 Q(y): y是課外活動 S(x,y):x參加y12. 請將下列命題符號化：某些人對某些藥物過敏。答案：令P(x):x是人 Q(y): y是藥 S(x,y

3、):x對y過敏13. 求的對偶式:答案：14. 求下列謂詞公式的前束范式：答案：15. 證明：答案：16. 用反證法證明：Ø"x(P(x)Q(x) , "xP(x) Þ Ø"xQ(x)答案：17. 證明：前提： "x(C(x)®W(x)R(x), $x(C(x)Q(x).結(jié)論： $x(Q(x)R(x).答案：n (1) $x(C(x)Q(x) 前提引入n (2) C(a)Q(a) (1)ESn (3) C(a) (2)化簡規(guī)則n (4) "x(C(x)®W(x)R(x) 前提引入n (5) C(

4、a)®W(a)R(a) (4)USn (6) W(a)R(a) (3)(5)假言推理n (7) R(a) (6)化簡規(guī)則n (8) Q(a) (2)化簡規(guī)則n (9) R(a)Q(a) (7)(8)合取引入規(guī)則n (10) $x(Q(x)R(x) (9)EG18. 判斷：下列命題是否正確？答案：n (1) n (2) ×n (3) n (4) n (5) n (6) n (7) n (8) ×19. 列出下列集合的元素n (1) x|xN$t(t2,3x=2t)n (2) x|xN$t$s(t0,1s3,4t<x<s)n (3) x|xN"t

5、(t整除2®xt)答案：n (1) 4,6n (2) 1,2,3n (3) 3,4,520. S=0,1,2,3,4,5,6,7,8,9，A=2,4,5,6,8B=1,4,5,9，C=x|xZ+, 2x5答案：21. 一個學(xué)校有507，292，312和344個學(xué)生分別選擇了A,B,C,D四門課程。有14人選了A和B，213人選了A和D，211人選了B和C ，43人選了C和D。沒有學(xué)生同時選擇A和C，也沒有學(xué)生同時選擇B和D。問共有多少學(xué)生在這四門課程中選了課？答案：解：畫文氏圖280+87+38+88 + 14+211+213+43=97422. 分別求下列集合的冪集(1) 

6、6; (2)Ø (3)1,Ø,1答案：n 解:(1) (Ø)=Ø 空集Ø的冪集的基數(shù)為1n (2) (Ø)=Ø,Ø 冪集的基數(shù)為2n (3) (1,Ø,1)=Ø,1,Ø,1,1,Ø,1 23. A=0,1,B=1,2,C=3,4,5,求A×B, B×A, A×B×C, A2, C2 .答案：n A×B=(0,1),(0,2),(1,1),(1,2)n B×A=(1,0),(2,0),(1,1),(2,1)n A

7、15;B×C= (0,1,3), (0,1,4), (0,1,5), (0,2,3), (0,2,4), (0,2,5), (1,1,3), (1,1,4), (1,1,5), (1,2,3), (1,2,4), (1,2,5)n A2 = (0,0), (0,1), (1,0), (1,1)n C2 = (3,3), (3,4), (3,5), (4,3), (4,4),(4,5),(5,3), (5,4),(5,5)24. n 1. 設(shè)A=1,2,3, 4,5, 6,7,8,下列選項正確的是（C）n A. 1A B. 1,2,3 A C. 4,5 A D. ØA n 2

8、. 設(shè)A=x|x3 x=0, B=x|x2 4<0,xz,C=x|y=2x-1,D=x|x+y=5, xy=6則有 （A）n A. A=B B. A=C C. C=D D. C=A25. 求關(guān)系的定義域和值域：n 設(shè)A = 2，4，6，8，R是A上的小于關(guān)系，即當(dāng)a, bA且a< b時，（a, b）R，求R及D( R ),C( R )答案：R = （2，4）,（2，6）,（2，8）,（4，6）,（4，8）,（6，8）.R的定義域D( R ) =2，4，6，R的值域C( R ) = 4，6，8。26. 設(shè)A = a, b, c, d ,求A上的恒等關(guān)系。答案：IA= (a, a),

9、(b, b), (c, c), (d, d)。27. 設(shè)A = 1,2,3,4,5, R是A上的小于等于關(guān)系, 即當(dāng)a b時, (a, b) R。求R的關(guān)系矩陣和關(guān)系圖。答案：解:易知A上的小于等于關(guān)系為R = （1,1),(1,2),(1,3),(1,4),(1,5),(2,2),(2,3), (2,4),(2,5),(3,3),(3,4),(3,5),(4,4),(4,5),(5,5)其關(guān)系矩陣為28. X=a,b,c，Y=1,2， 關(guān)系R=(a,1),(b,2),(c,1) S=(a,1),(b,1),(c,1)求RS、RS和R的補答案：29. 設(shè)A=1，2，3，B =a, b, c,

10、d,C =x, y, z，R是A到B的二元關(guān)系，R = (1, a), (1, b), (2, b), (3, c)，S是B到C的二元關(guān)系，S = (a, x), (b, x), (b, y), (b, z)。求復(fù)合關(guān)系RS的關(guān)系矩陣.答案：30. 答案：31. 設(shè)A = a,b,c，R是A上的二元關(guān)系， R = (a,a), (b,b), (a,b), (a,c), (c,a)， 問：R是自反的嗎？是反自反的嗎？是對稱的嗎？是反對稱的嗎？是可傳遞的嗎？答案：n 由于cA，而(c,c) ，所以R不是自反的。 ×n 由于(a,a)R，(b,b)R，所以R不是反自反的。 ×n

11、由于(a,b)R，而(b,a) ，所以R不是對稱的。 ×n 由于(a,c)R，且(c,a)R，所以R不是反對稱的。 ×n 由于(c,a)R，且(a,c)R，但(c,c) ，所以R不是可傳遞的。 ×32. n 設(shè)A=1,2,3，分析A上的下述5個關(guān)系具有哪些性質(zhì)：n L=<1,1>,<1,2>,<2,1>,<2,2>,<3,3>n N=<1,3>,<2,3>n S=<1,2>,<2,1>,<1,3>n G=<1,1>,<1,2&g

12、t;,<2,3>答案：33. 設(shè)A = a, b, c, d，A上的關(guān)系，R = (a, b), (b, a), (b, c), (c, d) 求r(R)、s(R)、t(R)答案：34. A=a,b,c, R=(a,b),(b,c),(c,a)，求r(R), S(R)和t(R)答案：35. A=1,2,3,4，R=(1,1),(1,2),(1,4),(2,1),(2,2),(3,3),(4,1),(4,4),判斷R是否是等價的。答案：36. 判斷下列關(guān)系是否為等價關(guān)系？(1) A=a,b,c,d， R=(a,a),(b,a),(b,b),(c,c),(d,d),(d,c)(2) A

13、=1,2,3,4， R=(1,1),(1,2),(1,3),(2,1),(2,2),(3,1),(2,3),(3,3),(4,4),(3,2)答案：（1）×（2）37. A=1,2,3,4在冪集(A)上定義的二元關(guān)系如下：R=(S,T)|S,T(A)，|S|=|T|，寫出商集(A)/R。答案：解：首先求(A)。(A)=Ø, 1,2,3,4 , 1,2,1,3 ,1,4 ,2,3 ,2,4 ,3,4, 1,2,3 ,1,2,4 ,1,3,4 ,2,3,4 , 1,2,3,4 共16個元素！38. 設(shè)集合X=2166，243，375，648，455X中的關(guān)系R為：R=(x,y)

14、|x,yX，并且x和y中有相同數(shù)字問：R是不是相容關(guān)系？答案：39. A = 1，2，3，4，5，6，8，10，12，16，24，R是A上的整除關(guān)系，請畫出的哈斯圖。答案：40. 已知偏序集<A,R>的哈斯圖如圖所示, 試求出集合A和關(guān)系R的表達式.  求 A 的極小元、最小元、極大元、最大元. 設(shè) Bb,c,d, 求 B 的下界、上界、最大下界、最小上界.答案：極小元：a, b, c, g；極大元：a, f, h；沒有最小元與最大元.B的下界和最大下界都不存在, 上界有d 和 f, 最小上界為 d.41. 以下關(guān)系矩陣所代表的關(guān)系是什么關(guān)系？答案：相容關(guān)系42. 設(shè)集合

15、A = 1，2，3，4，5，6，8，10，12，16，24，R是A上的整除關(guān)系，請問關(guān)系R是否是偏序關(guān)系？是否是全序關(guān)系？畫出的哈斯圖，并根據(jù)圖求集合A的極大極小元、最大最小元，設(shè)B=2，3，4，求集合B的上界、最小上界、下界、最大下界。答案：是偏序關(guān)系，不是全序關(guān)系。A的極大元：24,16,10A的極小元：1A的最大元：沒有A的最小元：1B的上界：12,24B的最小上界：12B的下界：1B的最大下界：143. 找出如下哈斯圖中的子集a,b,c、j,h和a,c,d,f的上界和下界。答案：n a,b,c 上界：e,f,j,h 下界：an j,h 上界：無 下界：f,d,e,b,c,an a,c,

16、d,f 上界：f,j,h 下界：a44. 判斷下列關(guān)系是否是映射？是否是單射？是否是滿射？答案：映射（非單射、非滿射）、映射（滿射）映射（單射）、不是映射45. X=x1,x2,x3, Y=y1,y2, Z=z1,z2 f:XY，g:YZ，求h= gf答案：46. 下列哪些關(guān)系可以構(gòu)成函數(shù)（映射）？a. f=(x,y)|x,yN, x+y<10b. f=(x,y)|x,yR, x2=y答案：能不能47. 判斷下列函數(shù)是單射、滿射或雙射？a. f:NN, f(x)=x+2;b. f:NN, f(x)=x (mod 2);c. f:N(N), f(x)=x;答案：單射什么都不是單射48. f

17、-1f = ？，ff-1= ？答案：f-1f =IA，ff-1= IB49. 構(gòu)造下列函數(shù)的反函數(shù)：1.f(x)=sinx2.f(x)=x2 , x(-，0)3.A=1,2,3,B=a,b,c,f:AB, f=(1,a),(2,c),(3,b)答案：f-1(x)=arcsinxf-1(x)=-x1/2f-1=(a,1),(c,2),(b,3)50. 答案：51. 已知x=a,b,c ,Y=1,2,3,4 f:XY如圖所示, 試構(gòu)造函數(shù)g:YX,使得g·f=Ix答案：g=(1,a),(2,c),(3,b),(4,a)52. 請給出圖中各點的度數(shù)，以及圖的最大度數(shù)和最小度數(shù)。答案：d(v

18、1)=4, d(v2)=4, d(v3)=2, d(v4)=1, d(v5)=3D(G)=4, d(G)=153. 請給出圖中各點的出度和入，以及圖的最大出度和最小入度。答案：d+(a)=4, d-(a)=1, d(a)=5,d+(b)=0, d-(b)=3, d(b)=3,D+(D)=4, d+(D)=0, D-(D)=3, d-(D)=1, D(D)=5, d(D)=3. 54. (3,3,3,4), (2,3,4,6,8)能成為圖的度數(shù)序列嗎?答案：不可能. 它們都有奇數(shù)個奇數(shù).55. 已知圖G有10條邊, 4個3度頂點, 其余頂點的度數(shù)均小于等于2, 問G至少有多少個頂點?答案：設(shè)G有

19、n個頂點. 由握手定理, 4´3+2´(n-4)³2´10解得 n³856. 下面無向圖中有幾個頂點？(1) 16條邊，每個頂點都是2度頂點(2) 21條邊，3個4度頂點，其余的都是3度頂點(3) 35條邊，每個頂點的度數(shù)至少為3的圖最多有幾個頂點？答案：57. 確定下列各圖的出度、入度和度數(shù)答案：58. 判斷下列圖是否同構(gòu)答案：是是不是是59. 下圖中，1. 寫出a,d,e的導(dǎo)出子圖2. 畫出它的一個生成子圖3. 邊集e4,e7,e6的導(dǎo)出子圖答案：60. 試畫出以下兩個圖的并圖、交圖和環(huán)和。答案：61. 判斷下列各圖是否是連通圖：答案：是、不是62. 指出下列有向圖的連通性答案：強連通圖單向連通圖弱連通圖強連通圖單向連通圖弱連通圖63. 求下列圖的強連通分支答案：64. （1）e5、e2 、e3、e6、e4是否是下圖的邊割集？（2）v5、v2 、v4、v3、v1 、v2、v2 、v3是否是下圖的點割集？答案：（1）是、是、是、否（2）是、是、是、否、否65. 求出下圖的全部割點和橋答案：66. 下列圖是否是樹？如果是，找出樹的分枝結(jié)點和樹葉。答案：不是、是分枝結(jié)點：e,f樹葉：a, b, c, d, g, h67. 設(shè)一棵樹T有2個度數(shù)為2的結(jié)點，1個度數(shù)為3的結(jié)點，3個度數(shù)為4的結(jié)點，求T有幾片樹葉。答案：68. 已知無