资源描述：
《2012年9月份考试离散数学第三次作业》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、2012年9月份考试离散数学第三次作业一、填空题（本大题共48分，共16小题，每小题3分）1.一公式为______之充分必要条件是其合取范式之每一合取项中均必同时包含一命题变元及其否定2.无向图G具有是生成树，当且仅当______的，若G为(n,m)连通图，要确定G的一棵生成树必删掉G的______条边。3.一个无向图的欧拉回路要求经过图中_______一次且仅一次，汉密顿图要求经过图中______一次且仅一次。4.设P：我生病，Q：我去学校（1）命题“我虽然生病但我仍去学校”符号化为______。（2）命题“只有生病的时候，我才不去学校”符号化为
2、______。（3）命题“如果我生病，那么我不去学校”符号化为______。5.设有33盏灯，拟公用一个电源，则至少需要5个插头的接线板数______。6.若H1∧H2∧…∧Hn是______，则称H1,H2,…Hn是相容的，若H1∧H2∧…∧Hn是______，则称H1,H2,…Hn是不相容的7.设f,g,h是N到N上的函数（N为自然数集合），f(n)=n+1;g(n)=2n;h(n)=0；则(fog)oh=______。8.K5的点连通度为______，边连通度为______。9.A={1，2，3，4，5，6，8，10，24，36}，R是A上的
3、整除关系。子B={1，2，3，4},那么B的上界是______；B的下界是______;B的上确界是____________；B的下确界为______10.命题公式P→Q∧R的对偶式为______11.设A={1,{2},φ}，则A的幂集有元素______个。12.设A={0,1,2,3}，B={4,6,7}，C={8,9,12,14}，R1是由A到B的关系，R2是由B到C原关系，分别定义为R1={<2,6>,<3,4>,<0,7>};R2={<4,8>,<4,12>,<6,12>,<7,14>}，则复合关系R1oR2为：______13.设A={
4、φ}，B={φ,{φ}}，则P(A)∩P(B)=______。14.给定个体域为整数域，若F(x):表示x是偶数，G(x):表示x是奇数；那么是一个______语句；而是一个______语句。15.设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度结点，该图有______个顶点。16.设T是一棵完全二元树，有15个结点，其中8个树叶结点，则T分枝结点数是______，T的所有结点度数之和是______。二、作图题（本大题共8分，共1小题，每小题8分）求下图所示带权图的最小生成树：三、简答题（本大题共4分，共1小题，每小题4分）判断下图是否欧
5、拉图，若是，找出一个欧拉回路。 四、分析题（本大题共10分，共2小题，每小题5分）1.设I是整数集，<，>，=，是I上的二元关系，分别表示小于、大于、等于、小于等于、大于等于，不等于。那么这些关系会满足什么性质？试填写下表：2.设集合A={1,2,3,4,5}上的二元关系R如下图，请判断R是否是A上的等价关系，若是，请说明理由并写出各元素的等价类，若不是，请说明理由。五、证明题（本大题共30分，共5小题，每小题6分）1.设G为群，证明e为G中的唯一幂等元。2.在命题逻辑中构造下面推理的证明。前提：p→s，q→r，ùr，p∨q结论：s3.案件涉及甲、
6、乙、丙、丁四个，根据已有的线索，已知：i.若甲、乙均未作案，则丙、丁也未作案ii.若丙、丁未作案，则甲、乙也未作案iii.若甲与乙同时作案，则丙与丁有一人且只有一人作案iv.若乙与丙同时作案，则甲与丁同时作案或同时未作案。办案人员由此的出结论：甲是作案者。这个结论是否正确，为什么4.设f1,f2都是从代数系统到代数系统的同态。设g是从A到B的一个映射，使得对任意a∈A，都有g(a)=f1(a)*f2(a)。证明：如果是一个可交换半群，那麽g是一个由代数系统到代数系统的同态。5.设R是集合A上的自反、传递的二元关系
7、，又设T也是A上的二元关系，且满足：∈T∈R∈R，求证：T是A上的等价关系。答案：一、填空题（48分，共16题，每小题3分）1.参考答案：永真式解题方案：评分标准：答案正确得满分，错误不得分2.参考答案：G是连通m-n+1解题方案：评分标准：3.参考答案：、每条边；每个顶点解题方案：评分标准：4.参考答案：（1）PÙQ(2)P↔ùQ(3)P®ùQ解题方案：评分标准：5.参考答案：8解题方案：评分标准：6.参考答案：可满足式永假式（或矛盾式）解题方案：评分标准：答案正确得满分，错误不得分7.参考答案：1解题方案：评分标准
8、：8.参考答案：（1）4（2）4解题方案：评分标准：9.参考答案：_24,36_1无1解题方案：评分标准：10.参考答案：
