计算机《离散数学》期中试卷答案

1、名姓号%学级、JI班级年彳1业,专系泉州师院2009-2010学年度第一学期2008级计算机离散数学期中试卷题序一二三四五总分成绩得分评卷人签名签名一、单项选择题：(20%每空2分)1 .设A=a,a,下列命题错误的是(B )。A. a P(A) B . a P(A)C. a P(A) D . a P(A)2、假定全集 E= 1,2,3,4,5,6,7,8,9,10,A=3,4,5, B= 2,3,4,7,8,9,则 AU B的位串是(D )。A. 01 B . 0011100000 C . 00 D3、下列文氏图阴影部分所表示的集合是(A )。A. (A-(BUC)U (BUC)-A)B.

2、(A-(BAC)U (BAC)-A)C. (A-(BAC)U (BUC)-A)D. (A-(BUC)U (BAC)-A)4.设p：你主修计算机科学，q：你是新生，r :你可以从校园网访问因特网。只有 你主修计算机科学或不是新生，你才可以从校园网访问因特网。可符号化为 (C )。00A. r f pVqC. r 一 p V q5.下列是两个命题变元A. n pA qC. p An p A q6、下列等值式不正确的是B. r f pA qD. r-pV qp, q的极小项是(A )A.x)A ( x) n AB. ( x)(B-A(x)B-( x)A(x)C. ( x)(A(x) A B(x)(

3、x)A(x) A ( x)B(x)D. (x)(y)(A(x) - B(y)( x)A(x) 一( y)B(y)7、若$=1,2,3,4, S上关系R的关系图为：则R具有(B )性质。A自反性B、自反性、对称性C反自反性、反又称性D、自反性、对称性、传递性8.设 A=a,b,c,d, A上的等价关系 R=, U I a,则对应于R的A的划分是(D )A. a,b,c,dB. a,b,c,dC a,b,c,dD. a,b,c,d9、设A=1 , 2, 3,则A上的二元关系有(C )个。323 3。2 2A. 2 B. 3 C. 2D. 310.下列函数是双射的为(A )，其中：I整数集，E偶数集

4、，N 自然数集,R实数集A. f : IE , f (x) = 2x B. f : NNN, f (n) = C. f : RI , f (x) = x D. f :I.填空题(20%每题2分)1.集合的表示法有列举法、描述法得分评卷人N, f (x) = | x |O12、设Ai 0, 7 ,i1,2,3,，则 Aii 10 3.令p：今天下雪了， q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化4.复合命题(p q) V ( p q)是 永真 式(永真式或永假式或可满足射或都不是)。三、计算题(20%每题5分)1、问 AU (B C)=(A U B) (AU C)吗为什么解：上式不成

5、立。设 A=1,2,3,B=2,3,4,C=3,4,5有：AU(BC)= 1,2,3 U2,5=1,2,3,5(A U B) (AU C)= 1,2,3,41,2,3,4,5=55.令谓词P(x,y)表示“ x爱y”，个体域是全世界所有人的集合，用 P(x,y)、量词和逻辑词符号化“所有人都爱某些人”x yP(x,y)xF(x) xG(x)的前束范式是y x F(y)G(x)7 . 设 A=a,b,c,d, 下列左图所示关系矩阵所表示的关系R= ,1MR 08、设某偏序集的哈斯图如下列右图，该偏序集的拓扑排序为1,5,3,2,7,9,6,4,89、设 f : NR N,且 f (x)1,当x为

6、奇数二当 X为偶数则 f(1,3,4,6= 1,232、求公式(p A q) V r的标准析取范式，再根据标准析取范式求标准合取范式。解：(p A q) V r(p q r) (p q r) ( p(p q r) (p q r) (p qr)mm3 m5m6mMA MA Mq r)得分评卷人10、给定函数f: Sf S,S=0,1,f(x)=x/2+1/4,f是 单射(满射或单射或双A中无最小元，最大元为 xlox 2,X3,X4的极小元为x4 ,极大元为x2,x3。x 2,x3的上界为x1 ,下界为x4。x 3,x4的上确界为x3,下确界为x4。3、设 A=a,b,c,d,其上关系 R= ,

7、 , , S=,求(1) R S(2) R的对称闭包及传递闭包。得分评卷人得分评卷人R S=,(2)R 的对称闭包 S(R)= , , , , R 的传递闭包 t(R)= , , , B)四、证明题(20%每题5分)1、设A、B是任意集合，证明： (A-B) U(B-A尸(A U B)-(A证：=(A U B)-(A A B)=(A u B) n (A n B)=(A U B) n (A U B)=An (A U B) U Bn (A U B)=An bu Bn a=(A-B) U(B-A)4、设 A xi,x2,x3, x4, 4,偏序集求A中最小元与最大元。x 2,*34的极小元和极大元。

8、x 2,x3的上界与下界。x 3,x4的上确界与下确界。解：A, R 的Hass图为:2、证明下列推理:前提：(p q)r, rs,结论：q(pq) r前提引入(2)rs前提引入(pq) s(1)(2)假言二段论(4) sp前提引入(5)P(2)化简(6) s(2)化简(7) (Pq)(3)(6)拒取式(8) Pq置换(9) q(5)(8)析取三段论3、设F, G是任意的关系，证明：(FG)-1= G-1 F-1证：任取 x, yX, y(F G)y, XF Gt( y,t F t, X G) t( t, yF 1X, tG 1)t(X,tG 1t, yF 1)1 u 1X, y G F前提引

9、入(1) ES规则前提引入(3)US规则(2)(4)析取三段论前提引入(6)US规则拒取式(8)EG规则欢骑自行车，有的人不爱骑自行车，因而有的人不爱步行。逻辑推证此结论的有效性。(设个体域是人类)Q(x) ： X喜欢步行；S(x) ： X喜欢乘汽车； R(x) : X喜欢骑自行车。前提：x(Q(x)S(x), x(S(x) R(x), x R(x)结论：x Q(x)证： X R(x) R(a) x(S(x) R(x) S(a) R(a)(5)S(a)(6) x(Q(x) S(x)(7)Q(a) S(a) Q(a)(9) x Q(x)4.任何人如果他喜欢步行，他就不喜欢乘汽车，对于每个人或者喜欢乘汽车或者喜得分评卷人五、判断题（20%每题2分）（在括号中写“对”或“错”）1、gcd（21,7）的值为7, 的值为-2。（ 对 ）2、设A,B,C均为E的子集，则A B AU （B-A尸A。（ 错）3、间接证明法可形式化地表示为：A-BB- A。（ 对 ）4、对每个最大项而言，只有与下标编码相同的赋值是成假赋值，其余都是成真赋值。（对）5、设个体域是整数集Z,则 x y z（x+y=z）的真值为1。（错 ）6、逻辑公式（xF（x） yG（y）yG（y）不是永真式。（对 ）7、因为若R是A上的关系，且 m,n N,则Rf R=RTn,所以R R1=R=IA.（错