《离散数学复习题及答案谷风书屋》由会员分享，可在线阅读，更多相关《离散数学复习题及答案谷风书屋（25页珍藏版）》请在金锄头文库上搜索。
1、1. 写出命题公式 （P （P Q）的真值表。答案：2.证明 答案：3. 证明以下蕴涵关系成立： 答案：4. 写出下列式子的主析取范式：答案：5. 构造下列推理的论证：pq, pr, 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. 请将下列命题符号化：存在着不是有理数的实数。答案：令 Q ( x )：x 是有理数 R ( x )：x 是实数
2、9. 请将下列命题符号化：尽管有人聪明，但并非一切人都聪明。答案：令M(x)：x 是人 C(x)：x 是聪明的 则上述命题符号化为10. 请将下列命题符号化：对于所有的正实数x,y，都有x+yx。答案：令P(x):x是正实数 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):x对y过敏13. 求的对偶式:答案：14. 求下列谓词公式的前束范式：答案：15. 证明：答案：16. 用反证
3、法证明：x(P(x)Q(x) , xP(x) xQ(x)答案：17. 证明：前提： x(C(x)W(x)R(x), $x(C(x)Q(x).结论： $x(Q(x)R(x).答案：n (1) $x(C(x)Q(x) 前提引入n (2) C(a)Q(a) (1)ESn (3) C(a) (2)化简规则n (4) x(C(x)W(x)R(x) 前提引入n (5) C(a)W(a)R(a) (4)USn (6) W(a)R(a) (3)(5)假言推理n (7) R(a) (6)化简规则n (8) Q(a) (2)化简规则n (9) R(a)Q(a) (7)(8)合取引入规则n (10) $x(Q(x)
4、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,4txs)n (3) x|xNt(t整除2xt)答案：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. 一个学校有507，292，312和344个学生分别选择了A,B,C,D四门课程。有1
5、4人选了A和B，213人选了A和D，211人选了B和C ，43人选了C和D。没有学生同时选择A和C，也没有学生同时选择B和D。问共有多少学生在这四门课程中选了课？答案：解：画文氏图280+87+38+88 + 14+211+213+43=97422. 分别求下列集合的幂集(1) (2) (3)1,1答案：n 解:(1) ()= 空集的幂集的基数为1n (2) ()=, 幂集的基数为2n (3) (1,1)=,1,1,1,1 23. A=0,1,B=1,2,C=3,4,5,求AB, BA, ABC, A2, C2 .答案：n AB=(0,1),(0,2),(1,1),(1,2)n BA=(1,0
6、),(2,0),(1,1),(2,1)n ABC= (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. 设A=1,2,3, 4,5, 6,7,8,下列选项正确的是（C）n A. 1A B. 1,2,3 A C. 4,5 A D
7、. A n 2. 设A=x|x3 x=0, B=x|x2 40,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. 求关系的定义域和值域：n 设A = 2，4，6，8，R是A上的小于关系，即当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. 设A = a, b, c, d ,求A上的恒等关系。答案：IA= (a, a), (
8、b, b), (c, c), (d, d)。27. 设A = 1,2,3,4,5, R是A上的小于等于关系, 即当a b时, (a, b) R。求R的关系矩阵和关系图。答案：解:易知A上的小于等于关系为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)其关系矩阵为28. X=a,b,c，Y=1,2， 关系R=(a,1),(b,2),(c,1) S=(a,1),(b,1),(c,1)求RS、RS和R的补答案：29. 设A=1，2，3，B =a, b, c, d
9、,C =x, y, z，R是A到B的二元关系，R = (1, a), (1, b), (2, b), (3, c)，S是B到C的二元关系，S = (a, x), (b, x), (b, y), (b, z)。求复合关系RS的关系矩阵.答案：30. 答案：31. 设A = a,b,c，R是A上的二元关系， 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 由于(a,b)R，而(b,
10、a) ，所以R不是对称的。 n 由于(a,c)R，且(c,a)R，所以R不是反对称的。 n 由于(c,a)R，且(a,c)R，但(c,c) ，所以R不是可传递的。 32. n 设A=1,2,3，分析A上的下述5个关系具有哪些性质：n L=,n N=,n S=,n G=,答案：33. 设A = a, b, c, d，A上的关系，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,
11、4),(2,1),(2,2),(3,3),(4,1),(4,4),判断R是否是等价的。答案：36. 判断下列关系是否为等价关系？(1) A=a,b,c,d， R=(a,a),(b,a),(b,b),(c,c),(d,d),(d,c)(2) A=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)上定义的二元关系如下：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. 设集合X=2166，243，375，648，455X中的关系R为：R=(x,y)|x,yX，并且x和y中有相同数字问：R是不是相容关系？答案：39. A = 1，2，3，4，5，6，8，10，12，16，24
