的最大元为a，最小元不存在．则集合Ad ? ?h 解：错误． ? ?e f a是极大元．集合A的最大元不存在， 图一 ：是否构成函数f，B={2, 4, 6, 8}，，判断下列关系f 4．设集合A={1, 2, 3, 4} ，并说明理由．BA? (2)f={<1, 6>, <3, 4>, <2, 2>}； (1) f={<1, 4>, <2, 2,>, <4, 6>, <1, 8>}； ．(3) f={<1, 8>, <2, 6>, <3, 4>, <4, 2,>}
B中没有元素与之对应。3属于A，在（1）不构成函数。因为对于 B中没有元素与之对应。4属于A，在（2）不构成函数。因为对于 中唯一的元素相对应。）构成函数。因为A中任意一个元素都有A（3 三、计算题 1．设，求：}45},C?{2,,},A?{14},B?{1,2,4?E{1,2,3,,5 ?B．； (4) A?B)- (B?A) (3) P(A)－P(C)(2) (AB)(1) (A??~C；
},5?{1,3{1,3,5} ?解：（1）(A?B)?~C={1} ?
??}}2,4{{2},{4},},,{1},{4{1,4}}?{,{(AP()?PC)? （ ） 3{{4}}?1},{1,
}4{2,,5?1?5421{,,,}{}= ?B）A－（B)B =(A?A4（ ）?2,4,5}-{1}={2,4,5} ，={12（）
2
★★ 形成性考核作业
B={1,2,{1,2}}2．设，试计算,1,2}， B．（3）A×（2）（A∩B）； 1（）（A?B）； ）1A? } 解：（ B ={1,2} （2）A∩ ，，<{2},2>2}>，<{2},1>（3）A×B={<{1},1>，<{1},2>，2}>，<1,1>，<1,2>，<1, {1,2}>，<2,1>，<2,2>,
<2, {1,2}>}
3．设A={1，2，3，4，5}，R={|x?A，y?A且x+y?4}，S={|x?A，-1-1，r(S)，s(R)R．，S ?x+y<0}，试求R，S，R?S，SR，y?A且 解：R={<1,1>,<1,2>,<1,3><2,1><2,2><3,1>} S=空集 R*S=空集 S*R=空集 -1={<1,1>,<2,1><3,1><1,2><2,2><1,3>} R
=空集S
r(S)={<1,1><2,2><3,3><4,4><5,5>}
s(R)={<1,1><1,2><1,3><2,1><2,2><3,1>}
4．设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}． (1) 写出关系R的表示式； (2 )画出关系R的哈斯图； (3) 求出集合B的最大元、最小元．
(1)
R={<1,1><1,2><1,3><1,4><1,5><1,6><1,7><1,8><2,2><2,4><2,6><2,8><3,3><3,6
><4,4><4,8><5,5><6,6><7,7><8,8>}
(2) 哈斯图如下：
-1
8 6 4
3 5 2 7
1
(3)集合B没有最大元，最小元是2
四、证明题
1．试证明集合等式：A? (B?C)=(A?B) ? (A?C)．
1．证明：设，若x∈A? (B?C)，则x∈A或x∈B?C， 即 x∈A或x∈B 且 x∈A或x∈C．
3
★作业 ★ 形成性考核
?C x∈A即x∈A?B 且 ，?C)?B) ? (A即 x∈T=(A (A?C)． (B?C)? (A?B) ，
??所以A C，x∈A?B C)，则x∈A?且 反之，若x∈(A?B) ? (A? C，A或x∈或x∈B 且 x∈ 即x∈A C，x∈B?即x∈A或 C)，A? (B?即x∈ C)．? (B? A?B) ? (A?C)?所以(A C)．? (A?A? (B?C)=(A?B) 因此． C)．? (A?A? (B?C)=(A?B) 2．试证明集合等式
x且x∈A∈， 若xS，则S=A∩(B∪C)，T=(A∩B)∪(A∩C)2．证明：设 ，x∈C或 x∈A且B∪C，即 x∈A且x∈B ∈ ?T．x∈T，所以S∩B 或 x∈A∩C ，即 也即x∈A ，∩C或 x∈A反之，若x∈T，则x∈A∩B C
∈且x x∈A或 即x∈A且x∈B ．?S∈S，所以T且x∈B∪C，即xA 也即x∈ T=S． 因此???B = ，，且试证明：若AAB = A则C 3．对任意三个集合A, B和C，? ． C
，B= A×CB,，b∈因为A×对于任意 ∈A×B，其中a∈A（1）C ?C因此BA×C,其中b ∈必有∈
CB= A×∈C，因为A×其中，∈A×C,a∈A，c（2）同理，对于任意B ?，因此C，其中c∈B必有∈A×BB=C 2）（）得有（1上的自也是集合A是集合A上的自反关系，则R∩S4．试证明：若R与S 反关系．S, ＞∈x,x＞∈R,＜A上的自反关系，则任意x∈A,＜x,x若R与S是集合
上的自A的任意元素，所以R∩S也是集合从而＜x,x＞∈R∩S,注意x是A 反关系．
姓
名： 学 号：
得 分： 教师签名： 4
★ 形成性考核作业 ★
离散数学作业5
离散数学图论部分形成性考核书面作业
本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。
要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月5日前完成并上交任课教师（不收电子稿）。并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。
一、填空题
1．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，
则G的边数是 15 ．
的点割集是，则图G)2．设给定图G(如右由图所示 ． {f}
，则，边集合为E3．设G是一个图，结点集合为V 等于边数的两倍． 度数之和 G的结点
． 等于出度 4．无向图G存在欧拉回路，当且仅当G连通且
中每一对结点度数之和个结点的简单图，若在G>是具有n<5．设G=V，E G中存在一条汉密尔顿路． ，则在 n-1 大于等于 的每个非空V, E>中具有一条汉密尔顿回路，则对于结点集6 ．若图G=K n为奇数 当个结点 中时，
7．设完全图K有n(n?2)，m条边， nn 关 存在欧拉回路．
