太原理工大学离散数学试题

发布时间:   来源:文档文库   
字号:
一、填空题
1设集合A,B,其中A{1,2,3},B={1,2},A-B__{3}__________________;
(A-(B___________________{3},{1,3},{2,3},{123}______.
2.设有限集合A,|A|=n,|(A×A|=_____2^(n^2_____________________.
3.设集合A={a,b},B={1,2},则从AB的所有映射是_______________________________________,其中双射的是__________________________.
4.已知命题公式G(PQRG的主析取范式是_________________________________________________________________________________________.
5.G是完全二叉树,G7个点,其中4个叶点,则G的总度数为__________,分枝点数为________________.
6AB为两个集合,A={1,2,4},B={3,4},则从AB_________________________;AB_________________________;AB_____________________.
7.R是集合A上的等价关系,则R所具有的关系的三个特性是__自反,对称,传递____________________,________________________,_______________________________.
8.设命题公式G(P(QR,则使公式G为真的解释有_______________________________________________________,__________________________.
9.设集合A{1,2,3,4},A上的关系R1={(1,4,(2,3,(3,2},R2={(2,1,(3,2,(4,3},
R1R2=________________________,R2R1=____________________________,R12=________________________.

10.设有限集A,B|A|=m,|B|=n,||(AB|=_____________________________.11A,B,R是三个集合,其中R是实数集,A={x|-1x1,xR},B={x|0x<2,xR},A-B=__________________________,B-A=__________________________,AB=__________________________,.
13.设集合A{2,3,4,5,6}RA上的整除,则R以集合形式(列举法记为__________________________________________________________________.
14.设一阶逻辑公式G=xP(xxQ(xG的前束范式是_______________________________.
15.G是具有8个顶点的树,则G中增加_________条边才能把G变成完全图。16.设谓词的定义域为{a,b},将表达式xR(xxS(x中量词消除,写成与之对应的命题公

式是__________________________________________________________________________.17.设集合A{1,2,3,4}A上的二元关系R{(1,1,(1,2,(2,3},S{(1,3,(2,3,(3,2}。则RS_____________________________________________________,R2______________________________________________________.
二、选择题
1设集合A={2,{a},3,4}B={{a},3,4,1}E为全集,则下列命题正确的是((A{2}A(B{a}A(C{{a}}BE(D{{a},1,3,4}B.
2设集合A={1,2,3},A上的关系R{(1,1,(2,2,(2,3,(3,2,(3,3},则R不具备(.(A自反性(B传递性(C对称性(D反对称性
3设半序集(A,关系≤的哈斯图如下所示,若A的子集B={2,3,4,5},则元素6B(
6
(A下界(B上界(C最小上界(D以上答案都不对
5
4下列语句中,(是命题。
43(A请把门关上(B地球外的星球上也有人
2(Cx+5>6(D下午有会吗?5I是如下一个解释:D{a,b},
P(a,aP(a,bP(b,aP(b,b

1010
1
则在解释I下取真值为1的公式是(.
(AxyP(x,y(BxyP(x,y(CxP(x,x(DxyP(x,y.
6.若供选择答案中的数值表示一个简单图中各个顶点的度,能画出图的是(.(A(1,2,2,3,4,5(B(1,2,3,4,5,5(C(1,1,1,2,3(D(2,3,3,4,5,6.
7.GH是一阶逻辑公式,P是一个谓词,GxP(x,HxP(x,则一阶逻辑公式GH(.(A恒真的(B恒假的(C可满足的(D前束范式.
8设命题公式G(PQHP(QP,则GH的关系是((AGH(BHG(CGH(D以上都不是.9A,B为集合,当(ABB.(AAB(BAB(CBA(DAB.
10设集合A={1,2,3,4},A上的关系R{(1,1,(2,3,(2,4,(3,4},R具有((A自反性(B传递性(C对称性(D以上答案都不对11下列关于集合的表示中正确的为((A{a}{a,b,c}(B{a}{a,b,c}(C{a,b,c}(D{a,b}{a,b,c}12命题xG(x取真值1的充分必要条件是(.
(A对任意xG(x都取真值1.(B有一个x0,使G(x0取真值1.(C有某些x,使G(x0取真值1.(D以上答案都不对.
13.G是连通平面图,有5个顶点,6个面,则G的边数是(.(A9(B5(C6(D11.
14.G5个顶点的完全图,则从G中删去(条边可以得到树.(A6(B5(C10(D4.

01
15.设图G的相邻矩阵为
1111111
0100
,则G的顶点数与边数分别为(.
1011

01010110
(A4,5(B5,6(C4,10(D5,8.
三、计算证明题
1.设集合A{1,2,3,4,6,8,9,12}R为整除关系。
(1画出半序集(A,R的哈斯图;
(2写出A的子集B={3,6,9,12}的上界,下界,最小上界,最大下界;(3写出A的最大元,最小元,极大元,极小元。
2.设集合A{1,2,3,4}A上的关系R{(x,y|x,yAxy},
(1画出R的关系图;(2写出R的关系矩阵.
3.R是实数集合,,,R上的三个映射,(x=x+3,(x=2x,(xx/4,试求复合
映射,,.4.I是如下一个解释:D={2,3},
a3
b2
f(23
f(32
P(2,20
P(2,30
P(3,21
P(3,31
试求(1P(a,f(aP(b,f(b;
(2xyP(y,x.
5.设集合A{1,2,4,6,8,12}RA上整除关系。
(1画出半序集(A,R的哈斯图;
(2写出A的最大元,最小元,极大元,极小元;
(3写出A的子集B={4,6,8,12}的上界,下界,最小上界,最大下界.6.设命题公式G=(PQ(Q(PR,G的主析取范式。
7.(9设一阶逻辑公式:G=(xP(xyQ(yxR(x,把G化成前束范式.9.R是集合A={a,b,c,d}.RA上的二元关系,R={(a,b,(b,a,(b,c,(c,d},
(1求出r(R,s(R,t(R(2画出r(R,s(R,t(R的关系图.
11.通过求主析取范式判断下列命题公式是否等价:
(1G=(PQ(PQR
(2H=(P(QR(Q(PR
13.RS是集合A{a,b,c,d}上的关系,其中R{(a,a,(a,c,(b,c,(c,d},
S{(a,b,(b,c,(b,d,(d,d}.(1试写出RS的关系矩阵;(2计算RS,RS,R1,S1R1.




四、证明题
1.利用形式演绎法证明:{PQ,RS,PR}蕴涵QS2.A,B为任意集合,证明:(A-B-C=A-(BC.
3.(本题10利用形式演绎法证明:{AB,CB,CD}蕴涵AD4.(本题10A,B为两个任意集合,求证:
A(AB=(ABB.
参考答案
一、填空题
1.{3};{{3},{1,3},{2,3},{1,2,3}}.2.2n.
2
3.1={(a,1,(b,1},2={(a,2,(b,2},3={(a,1,(b,2},4={(a,2,(b,1};3,4.4.(PQR.5.12,3.
6.{4},{1,2,3,4},{1,2}.7.自反性;对称性;传递性.8.(1,0,0,(1,0,1,(1,1,0.
9.{(1,3,(2,2,(3,1};{(2,4,(3,3,(4,2};{(2,2,(3,3}.10.2mn.
11.{x|-1x<0,xR};{x|1R};{x|0x1,xR}.12.12;6.
13.{(2,2,(2,4,(2,6,(3,3,(3,6,(4,4,(5,5,(6,6}.14.x(P(xQ(x.15.21.
16.(R(aR(b(S(aS(b.17.{(1,3,(2,2};{(1,1,(1,2,(1,3}.二、选择题
1.C.2.D.3.B.4.B.5.D.6.C.7.C.
8.A.9.D.10.B.11.B.13.A.14.A.15.D三、计算证明题

1.(1
8
4
12
6
2
1
3
9

(2B无上界,也无最小上界。下界1,3;最大下界是3.(3A无最大元,最小元是1,极大元8,12,90+;极小元是1.2.R={(1,1,(2,1,(2,2,(3,1,(3,2,(3,3,(4,1,(4,2,(4,3,(4,4}.
(1
1

4
2
3

11
(2MR
11000100

110

111
3.(1((x(x+32x+32x+3.
(2((x(x+3(x+3+3x+6,(3((x(x+3x/4+3,(4((x(x/42x/4=x/2,
(5•(+32x/4+3x/2+3.4.(1P(a,f(aP(b,f(b=P(3,f(3P(2,f(2

=P(3,2P(2,3=10=0.
(2xyP(y,x=x(P(2,xP(3,x

=(P(2,2P(3,2(P(2,3P(3,3=(01(01=1=1.
84
126
1
5.(1
2
1



(2无最大元,最小元1,极大元8,12;极小元是1.(3B无上界,无最小上界。下界1,2;最大下界2.6.G=(PQ(Q(PR
=(PQ(Q(PR=(PQ(Q(PR=(PQ(QP(QR
=(PQR(PQR(PQR(PQR(PQR(PQR=(PQR(PQR(PQR(PQR(PQR=m3m4m5m6m7=(3,4,5,6,7.
7.G=(xP(xyQ(yxR(x
=(xP(xyQ(yxR(x=(xP(xyQ(yxR(x=(xP(xyQ(yzR(z=xyz((P(xQ(yR(z
9.(1r(RRIA{(a,b,(b,a,(b,c,(c,d,(a,a,(b,b,(c,c,(d,d},
s(RRR1{(a,b,(b,a,(b,c,(c,b(c,d,(d,c},

t(RRR2R3R4{(a,a,(a,b,(a,c,(a,d,(b,a,(b,b,(b,c,(b,d,(c,d}(2关系图:
ab
r(R
dc
ab
s(R
d
ab
t(R
dc

c
11.G(PQ(PQR
(PQR(PQR(PQRm6m7m3

(3,6,7
H=(P(QR(Q(PR(PQ(QR(PQR
(PQR(PQR(PQR(PQR(PQR(PQR(PQR(PQRm6m3m7(3,6,7
G,H的主析取范式相同,所以G=H.
1010100
13.(1M0
010
01R
001M
0S00000000

000(2RS{(a,b,(c,d},
RS{(a,a,(a,b,(a,c,(b,c,(b,d,(c,d,(d,d},R
1{(a,a,(c,a,(c,b,(d,c},
S
1R
1{(b,a,(d,c}.
证明题
1.证明:{PQ,RS,PR}蕴涵QS
(1PRP(2RPQ(1(3PQP(4RQQ(2(3(5QRQ(4(6RSP(7QSQ(5(6(8QS

Q(7
2.证明:(A-B-C=(A~B~C=A(~B~C=A~(BC

=A-(BC
0
1
0

1


3.证明:{AB,CB,CD}蕴涵AD
(1A


D(附加PQ(1(2PQ(4Q(3(5PQ(6(7D(1(8
(2AB(3B

(4CB(5BC(6C


(7CD(8D

(9AD
所以{AB,CB,CD}蕴涵AD.4.证明:A(AB
=A~(ABA(~A~B(A~A(A~B(A~B(A~BAB(ABB
=(AB~B=(A~B(B~B=(A~B=AB
所以:A(AB=(ABB.

本文来源:https://www.2haoxitong.net/k/doc/128af48e80c758f5f61fb7360b4c2e3f57272595.html

《太原理工大学离散数学试题.doc》
将本文的Word文档下载到电脑,方便收藏和打印
推荐度:
点击下载文档

文档为doc格式