五、证明题
1．试证明集合等式：A? (B?C)=(A?B) ? (A?C)．
2．试证明集合等式A? (B?C)=(A?B) ? (A?C)．
3．设R是集合A上的对称关系和传递关系，试证明：若对任意a?A，存在b?A，使得?R，则R是等价关系．
4．若非空集合A上的二元关系R和S是偏序关系，试证明：R?S也是A上的偏序关系．
参考解答
一、单项选择题
1．A 2．B 3．C 4．B 5．C 6．A 7．B
9．B 10．C 11．C 12．B 13．B
二、填空题 1．2n
2．{?,{a,b},{a},{b }}
3．{<2, 2>，<2, 3>，<3, 2>}，<3, 3>
?114．?0??000? ?110???? 5．{,
7．{<1, 1>, <2, 2>}
8．{<1, a >, <2, b >}，{<1, b >, <2, a >}
9．8
三、判断说明题（判断下列各题，并说明理由．） 1．解：错．
设A={1, 2}，B={1}，C={2}，则A∪B=A∪C，但B?C． 2．解：成立．
因为R1和R2是A上的自反关系，即IA?R1，IA?R2。
由逆关系定义和IR-A?1，得IA? R11；
由IA?R1，IA?R2，得IA? R1∪R2，IA? R1?R2。
所以，R-11、R1∪R2、R1?R2是自反的。
3．解：正确．
对于集合A的任意元素x，均有
按照最小元的定义，在集合A中不存在最
26
8．B 小元．
4．解：错误．
集合A的最大元不存在，a是极大元．
5．解：正确．
设x1，x2为自然数且x1?x2，则有f(x1)= x1+6? x2+6= f(x2)，故f为单射．
四、计算题
1．解：（1）B?A={a, b, c}?{b, d, e}={ b } （2）A?B={a, b, c}?{b, d, e}={a, b, c, d, e } （3）A－B={a, b, c}－{b, d, e}={a, c}
（4）B?A= A?B－B?A={a, b, c, d, e }－{ b }={a, c, d, e }
2．解：（1）（A?B）={{a, b}, 2}
（2）（A∪B）={{a, b}, 1, 2, a, b, {1}}
（3）（A∪B）?（A∩B）={{a, b}, 2, a, b, {1}} 3．解：（1）A?B ={{1},{2}}
（2）A∩B ={1,2} （3）A×B={<{1},1>，<{1},2>，<{1},{1,2}>，<{2},1>，<{2},2>，
<{2},{1,2}>，<1,1>，<1,2>，<1, {1,2}>，<2,1>，<2,2>,
<2, {1,2}>}
4．解：R=?,
S={<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>}
R?S=?，
R-1=?， S-1= S， r(R)=IA．
5．解：（1）R=I?{<1,2>, <1,3>, ?, <1,12> , <2,4>, <2,6>, <2,8>, <2,10>, <2,12>, <3,6>, <3,9> , <3,12>, <4,8>, <4,12>, <5,10>, <6,12>} （2）关系R的哈斯图如图四
（3）集合B没有最大元，最小元是：2 6．解：R＝{, ,
10 8 4 5 2 12 6 3 9 7 11
1 图四：关系R的哈斯图
?1?0MR???0??0000011000?0?? 0??1?R2 = {, ,
7．解：（1）R={<1,1>,<2,2>,<3,3>,<4,4>, <1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>}
（2）关系图如图五
（3）因为<1,1>,<2,2>,<3,3>,<4,4>均属于R，
27
? 4 2 1 ? 3 ? ? 图五
即A的每个元素构成的有序对均在R中，故R在 A上是自反的。
因有<2,3>与<3,4>属于R，但<2,4>不属于R， 所以R在A上不是传递的。
五、证明题
1．证明：设，若x∈A? (B?C)，则x∈A或x∈B?C，
即 x∈A或x∈B 且 x∈A或x∈C． 即x∈A?B 且 x∈A?C ， 即 x∈T=(A?B) ? (A?C)，
所以A? (B?C)? (A?B) ? (A?C)．
反之，若x∈(A?B) ? (A?C)，则x∈A?B 且 x∈A?C， 即x∈A或x∈B 且 x∈A或x∈C，
即x∈A或x∈B?C， 即x∈A? (B?C)，
所以(A?B) ? (A?C)? A? (B?C)． 因此．A? (B?C)=(A?B) ? (A?C)．
2．证明：设S=A∩(B∪C)，T=(A∩B)∪(A∩C)， 若x∈S，则x∈A且x∈B∪C，即 x∈A且x∈B 或 x∈A且x∈C，
也即x∈A∩B 或 x∈A∩C ，即 x∈T，所以S?T． 反之，若x∈T，则x∈A∩B 或 x∈A∩C， 即x∈A且x∈B 或 x∈A且x∈C
也即x∈A且x∈B∪C，即x∈S，所以T?S． 因此T=S．
3．设R是集合A上的对称关系和传递关系，试证明：若对任意a?A，存在b?A，使得?R，则R是等价关系．
证明：已知R是对称关系和传递关系，只需证明R是自反关系． ?a?A，?b?A，使得?R，因为R是对称的，故
由元素a的任意性，知R是自反的． 所以，R是等价关系．
4．若非空集合A上的二元关系R和S是偏序关系，试证明：R?S也是A上的偏序关系．
证明：.① ?x?A,?x,x??R,?x,x??S??x,x??R?S，所以R?S有自反性； ②?x,y?A,因为R，S是反对称的，
?x,y?R?S??y,x?R?S?(?x,y??R??x,y??S)?(?y,x??R??y,x??S)?(?x,y??R??y,x??R)?(?x,y??S??y,x??S)?x?y?y?x?x?y所以，R?S有反对称性．
③ ?x,y,z?A，因为R，S是传递的， ?x,y??R?S??y,z??R?S
??x,y??R??x,y??S??y,z??R??y,z??S ??x,y??R??y,z??R??x,y??S??y,z??S ??x,z??R??x,z??S??x,z??R?S
28
所以，R?S有传递性． 总之，R是偏序关系．
离散数学（本）2016年3月份试题
一、单项选择题（每小题3分，本题共15分）
1．设A={1, 3, 5, 7｝，B={2, 4, 6}，A到B的关系R={
C. {<1, 2>, <3, 4>, <5, 6>} D. {<1, 3>, <3, 3>, <5, 3>, <7, 3>} 2．若集合A＝{a, b, c}，则下列表述不正确的是( )． A．? ?A B．a?A
C．{a}?A D．{a, b, c}?A
3．设A（x）：x是学生，B（x）：x是大学生，则命题“不是所有的学生都是大学生”可符号化为（ ）．
A．┐(?x)(A(x)∧B(x)) B．(?x)(A(x)∧B(x)) C．┐(?x)(A(x)∧┐B(x)) D．┐(?x)(A(x) →B(x))
4．设G为连通无向图，则（ ）时，G中存在欧拉回路．
A．G不存在奇数度数的结点 B．G存在偶数度数的结点 C．G存在一个奇数度数的结点 D．G存在两个奇数度数的结点 5．n阶无向完全图Kn的边数是（ ）．
A. n(n-1), B. n(n-1)/2 C. n-1 D. n(n-1)
二、填空题（每小题3分，本题共15分）
6．设集合A={1, 2, 3}，B={2, 3, 4}，C={3, 4, 5}，则A∪(C?B )等于 ． 7．设A={a, b}，B={1, 2}，C={a, b}，从A到B的函数f={,
8．对于任意的无向图，其所有结点的度数之和等于该图的边数的 ． 9．设G是具有n个结点m条边k个面的连通平面图，则n+k ?2等于 ． 10．设个体域D＝{1, 2, 3, 4}，A(x)为“x等于4”，则谓词公式(?x)A(x)真值为 ．
三、逻辑公式翻译（每小题6分，本题共12分）
11．将语句“如果小王来学校，则他会参加比赛．”翻译成命题公式． 12．将语句“今天天晴，昨天下雨．”翻译成命题公式．
四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）
13．设A={1，2，3 }，R={<1，1 >, <1，2 >，<2，1 >, <3，3 >}，则R是等价关系． 14．(?x)P(x)∧Q(y)→R(x)中量词?的辖域为P(x)∧Q(y)． 五．计算题（每小题12分，本题共36分） 15．设集合A={a, b, c}，B={{a, b }, b}，试计算 （1）A?B； （2）A ? B； （3）A×B．
16．设G=
29
（1）给出G的图形表示； （2）写出其邻接矩阵； （3）求出每个结点的度数； （4）画出其补图的图形．
17．试利用Kruskal算法求出如下所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树的权．
v1 ? 2 v6 ? 7
5 ? v5
1
1 9 6 ? v2 5 4 ? v3
2 ? v4
3
六、证明题（本题共8分）
18．试证明：┐┐(P?Q)∧┐R ∧（Q?R）? ┐P．
30
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库离散数学(本)2016年10月份试题(6)在线全文阅读。
相关推荐：