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

系 专业 年级 班级 学号 姓名 装订线泉州师院2009-2010学年度第一学期2008级计算机离散数学期中试卷题 序一二三四五 总分成 绩签 名得 分评卷人一、单项选择题:（20%，每空2分） 1设A=a,a，下列命题错误的是（ B ）。AaP(A) BaP(A)CaP(A) DaP(A)2、假定全集E1,2,3,4,5,6,7,8,9,10,A=3,4,5，B2,3,4,7,8,9，则AB的位串是（D）。A1000000001 B0011100000 C0111001110 D01111011103、下列文氏图阴影部分所表示的集合是( A )。A. (A-(BC)(BC)-A) B. (A-(BC)(BC)-A)C. (A-(BC)(BC)-A) D. (A-(BC)(BC)-A)4设p：你主修计算机科学，q：你是新生， r：你可以从校园网访问因特网。只有你主修计算机科学或不是新生，你才可以从校园网访问因特网。可符号化为( C )。 ArpqBrpq CrpqDrpq 5下列是两个命题变元p，q的极小项是（ A ）Apq BpqCppqDppq6、下列等值式不正确的是（ C ）A(x)A(x)AB(x)(BA(x)B(x)A(x)C(x)(A(x)B(x)(x)A(x)(x)B(x)D(x)(y)(A(x)B(y)( x)A(x)(y)B(y)7、若s=1,2,3,4，S上关系R的关系图为：则R具有（ B ）性质。A、自反性 B、自反性、对称性C、反自反性、反对称性 D、自反性、对称性、传递性8设A=a,b,c,d，A上的等价关系R=,IA，则对应于R的A的划分是（ D ）Aa,b,c,dBa,b,c,dCa,b,c,dDa,b,c,d 9、设A=1，2，3，则A上的二元关系有（ C ）个。 A. 23 B. 32 C. D. 10下列函数是双射的为（ A ），其中：I整数集，E偶数集， N自然数集，R实数集。A. f : IE , f (x) = 2x B. f : NNN, f (n) = C. f : RI , f (x) = x D. f :IN, f (x) = | x |得 分评卷人二填空题（20%，每题2分） 1集合的表示法有 列举法、描述法 。3令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为 pq 。4复合命题(pq)(pq)是_ 永真_式（永真式或永假式或可满足式）。5令谓词P(x,y)表示”x爱y”,个体域是全世界所有人的集合，用P(x,y)、量词和逻辑词符号化“所有人都爱某些人”： x$yP(x,y) 。6$xF(x)xG(x)的前束范式是 $yx F(y) G(x) 。7设A=a,b,c,d,下列左图所示关系矩阵所表示的关系R= , 。8、设某偏序集的哈斯图如下列右图，该偏序集的拓扑排序为 1,5,3,2,7,9,6,4,8 。9、设f：NN，且，则f(1,3,4,6= 1,2,3 。 10、给定函数f：SS,S=0,1,f(x)=x/2+1/4,f是_单射_(满射或单射或双射或都不是)。得 分评卷人三、计算题（20%，每题5分） 1、问A(BC)=(AB)(AC)吗？为什么？解：上式不成立。设A=1,2,3,B=2,3,4,C=3,4,5有：A(BC)= 1,2,32,5=1,2,3,5(AB)(AC)= 1,2,3,41,2,3,4,5=52、求公式(pq)r的标准析取范式，再根据标准析取范式求标准合取范式。解：(pq)r (pqr)(pqr) (pqr)(pqr)(pqr)(pqr) m1m3m5 m6m7M0M2M43、设A=a,b,c,d，其上关系R=，S=,，求（1）RS （2）R的对称闭包及传递闭包。 解：(1) RS=,(2) R的对称闭包S(R)= ，(3) R的传递闭包t(R)= ， 4、设，偏序集的Hass图为：求 A中最小元与最大元。 x2,x3,x4的极小元和极大元。 x2,x3的上界与下界。 x3,x4的上确界与下确界。解：A中无最小元，最大元为x1。 x2,x3,x4的极小元为x4，极大元为x2,x3。 x2,x3的上界为x1，下界为x4。 x3,x4的上确界为x3，下确界为x4。得 分评卷人四、证明题（20%，每题5分）1、设A、B是任意集合，证明： (A-B)(B-A)= (AB)-(AB) 证：=(AB)-(AB)=(AB) (AB)=(AB)(AB)=A(AB)B(AB)=ABBA=(A-B)(B-A)2、证明下列推理：前提：(pq) r, rs, sp结论：q3、设F，G是任意的关系，证明：(FG)-1= G-1F-14. 任何人如果他喜欢步行，他就不喜欢乘汽车，对于每个人或者喜欢乘汽车或者喜欢骑自行车，有的人不爱骑自行车，因而有的人不爱步行。逻辑推证此结论的有效性。 (设个体域是人类)Q(x)：x喜欢步行； S(x)：x喜欢乘汽车 ； R(x)：x喜欢骑自行车。前提：x(Q(x) S(x), x(S(x) R(x), $xR(x)结论：$xQ(x)得 分评卷人五、判断题（20%，每题2分）(在括号中写“对”或“错”)1、 gcd(21,7)的值为7，-2.3的值为-2。( 对 )2、 设A,B,C均为E的子集，则ABA(B-A)=A。( 错 ) 3、间接证明法可形式化地表示为：ABBA。( 对 )4、对每个最大项而言，只有与下标编码相同的赋值是成假赋值，其余都是成真赋值。（ 对）5、设个体域是整数集Z，则$xyz(x+y=z)的真值为1。（ 错 ）6、逻辑公式 (xF(x) $yG(y) $yG(y)不是永真式。（ 对）7、因为若R是A上的关系，且m,nN，则RmRn=Rm+n,所以RR-1=R0=IA