《离散数学I》模拟试题

1、离散数学I模拟试题一、单选题（每小题 2 分，共 20 分）1 以下语句是命题的是（B ）。yX。每个自然数都是奇数。请爱护环境。你今天有空吗？设a是一赋值，a(p)=a(q)=l,a(r)=0,下列公式的值为真的是(BA.pA(qVr)C.(Lq)A(qip)B.(p-r)(rLq)oD (Lq).以下联结词的集合（-i,A,V,（D）不是完备-i,A,V4AA*,D.A,V下列结果成立的是A.A*B.rAA*C.A|=|A*5假下列自然语言的符号化表示中，(A)的值是真的。Vx3yG(x,y),其中 G(x,y)表示 xy=yVxVyF(x,y),F(x,y)x+y=y3xVyH(x,y)

2、,H(x,y)x+y=xVxVyM(x,y),其中 M(x,y)表示 xy=x)=D. rA| =|A*论域是正整数集合，以下式子错误的是(D )。V x-i A(x) |=| -i 3xA(x)V x(A(x)AB(x) |=| V xA(x) A V xB(x)C.3 x(A(x) VB(x) |=| 3 xA(x)V 3 xB(x)D.Vx(A(x)VB(x) |=| VxA(x)VVxB(x)下列式子(C ) 正确。A.xGxC.XxB. xGx,xD. XX,X&下列性质正确的是（D ）。 A.如果 AWB,BGC,贝ijAGCB.如果 AeB,则 AcCC.如果AqB,BeC,贝i

3、jD.如果 AeB,BqC,则AGC9下列说法错误的是（A ）。RR是反自反关系1自反关系的关系图每个结点都有一条闭路G是自反关系10.设 p、卩都是集合 A 到集合 B 的关系，则下列等式错误的是(B )o(pu 叮=pC|ic. (pc 叮=pC|T20 分)D. (pg)=g p1 B 2 B (题目改为公式真值为假的是)3D 4D 5A6.D 7. C & D 9. A 10.B二、 填空题(每小题 2 分，共 20 分)句子“只有小王爱唱歌，他才会弹钢琴。”中，把“小王爱唱歌”P，“小王会弹钢琴”形式化为命题符q，则句子形式化为公式。公式r(rp/rq)/(rp/q)/t 的对偶是。

4、公式VxA(x)3xB(x)的前束范式是。公式VxA(x)VB(y)中，V量词的辖域是,自由变是。集合a,a,b的基数是,幕集是=7.,6.A=1,3,5, B=2,3,4,U=0,l,2,3,4,5,6,(AUB-AnB)=7.,7.A=a,b,c, B=x,y,z, C=1,2,3, Rl=,R2=, R10 R2=8.设集合A=0丄3上的关系p=,贝ij自反闭包r(p)=,对称闭包s(p)=o9 .集合 A=a,b,c , A 的一个划分a,b,c定义的 A 之上的等价关系 是 10.以下哈斯图所对应的序关系是。OCo bO a二、填空题(20 分)1.qp2.-(-pV-q)A(pVq

5、)Af3.3.A(x),y4.2,a,a,b,a,a,b5.0,3,66.,8.,9.,三、计算题（30分）1.(6分)用等值演算法计算命题公式(Tq)的析取范式和主析取范式。2.(7 分)设 A=1,2,3,4,A 上的关系 R=|a,beA且 a=b%R的关系图，写出其关系矩阵；Rt(R)o3.(7 分)令乂=1,2,3,Y=a,b,c,XY的关系？XY的映射？XY要求写出分析、计算过程。4.(6 分)集合 A=1,2,3,4,6,8,12,24,A p=|x,yeA 且 yx整除, B=2,3,4,画出哈斯图；B的极大元、极小元、最大元、最小元、上界、下界、最小上界、最大下界。5.(4分

6、)设人=1,2,3,4,f:A-A,fAf构造一个函g:AA,g2(x)=g(x)o三、计算题(30 分)1.倒数第二步可以算做析取范式；最后一步既是析取范式也是主析取范式。2.(1)R=,(2)沃夏尔算法得t(R)=R。没有增加序偶，原关系具有传递性3.(1)29(2)33(3)单射：3!=6满射：6双射4.(1)(2) B 的极大兀：3, 4；极小兀：2, 3；最大兀：无；最小兀：无； 上界：12, 24；下界：1；最小上界：12；最大下界：1。5.、g都有多个解。匸,g=IA,或 g 可以是有传递性的任何函数，例如 g=,四、证明题(20分)(6A-(B-C)|=|(A-B)f(A-C)

7、(6分)ABAcBAUB=B(6分)(8 R是集合 A上的关系。令 S=(a,b)|3ceA,(a,c)eRH(c,b)Ro ffiR是S也是等价关系。四、 证明题(20 分)aa(A)=0a(A)=la(B-C)=l当 a(A)=0时，aAB)=aAC)=l,所以 a(A-B)(AC)1。a (A)=l 且 a(BC)=l 时，有 a (B) = 0 或 a (B)=l 且 a (C)=la (A)= 1 且 a(B) = 0 时，a (A-B) = 0, a (AB)(AC)= 1。a (A)=l 且 a(B)=l 且 a(C)=l 时，a (A-B)= a (A-C)=l,所以 a (A

8、-B)f (A-C)= 1。 因此 A(B-C)|= (A-B)-(A-C)。当赋值 a 使右式为真时，为证 a (A-B)-(Af C)= 1 时有 a (A-(B-C)= 1,等价于证 a (A(B-C) = 0时有 a (AB)(A-C) = 0。a(Af(BC) = 0 时,a(A)=l 月.a(BC)=0,即 a (A)=l 且 a (B)= 1 且 a (C) = 0o 此时 a (AB)=l, a(AC) = 0,所以 a (A-B)(AC) = 0。因此(A-B)f (A-C)|=A(B-C)。 因此 A(B-C)|=| (AB)-(A-C)。(1)ABAUB=BoAUB=B

9、AUBB BAUBxWB,xWAUB,BAUBo xGAUB,有 xWA 或 xWB。因为 AB,所以 xGA 时有 xB。所以 AUBB。 所以 AUB=B(2)证 AUB=B 时有 AB对任意 xGA,山 U 定义有 xGAUBo 因为 AUB=B,所以 xB。所以 AB =(1)xGA,R有自反性，所以WRS定义知GC=S设S,cA,使WR 且WR。因为 RUWR且WR,则S,所以 S 有对称性。设S且设S,S的定义知 cA,使ER 且eR,d,使WR月.WR。因为 R 有传递性，所以eR R.eR。贝 IJGS =所以 S 有 传递性。五、综合题(10分)FND提、结论和证明过程。“家。”五、综合题