2014年9月份考试离散数学第三次作业

2014年9月份考试离散数学第三次作业一、填空题（本大题共40分，共10小题，每小题4分）1.设P：我生病，Q：我去学校（1）命题“我虽然生病但我仍去学校”符号化为______。（2）命题“只有生病的时候，我才不去学校”符号化为______。（3）命题“如果我生病，那么我不去学校”符号化为______。2.某集合A上的二元关系R具有对称性，反对称性，自反性和传递性，此关系R是______，其关系矩阵是______3.设A={1,2},B={α，β，γ}，则AoB=______。4.设A={2,3,{2,3},φ}，则A-{{2,3}}=______。5.设A={1,{2},φ}，则A的幂集有元素______个。6.设A={1,2,3}，B={x,y}，f：AB，则不同的函数个数为______个。7.设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度结点，该图有______个顶点。8.集合A={1,2}，B={a,b,c,d}，C={c,d,e}，则A*(B-C)为______。9.求命题公式的主析取范式______。10.命题公式P→Q∧R的对偶式为______二、作图题（本大题共6分，共1小题，每小题6分）根据下列条件如果能则画出一个欧拉图，如果不能则说明理由。（1）偶数个顶点，偶数条边（2）奇数个顶点，奇数条边（3）偶数个顶点，奇数条边（4）奇数个顶点，偶数条边三、计算题（本大题共30分，共5小题，每小题6分）1.分别列出：广群、半群、独异点、群的概念2.判定下图是否能够一笔画，若不能，请说明为什么，若能，请标出路径。3.设S={1,2,3,4,6,12}，D为S上的整除关系，（1）试写出该关系并画出哈斯图；（2）设子集B={2,3,6}，试求B的最大元、最小元、极大元和极小元；（3）试求B的上界、上确界、下界和下确界。4.所有的有理数是实数，某些有理数是整数，因此某些实数是整数。1）请符号化该命题。2）使用谓词演算的推理论证，证明结论成立。5.画出满足下列条件的图来a）画一个有一条欧拉回路和一条汉密尔顿回路的图。b）画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。c）画一条没有一条欧拉回路，但有一条汉密尔顿回路的图。四、分析题（本大题共24分，共4小题，每小题6分）1.设I是整数集，，，=，是I上的二元关系，分别表示小于、大于、等于、小于等于、大于等于，不等于。那么这些关系会满足什么性质？试填写下表：2.求出下图的最小生成树，并计算出权。3.分析集合A={1，2，3}上的下述5个关系(1)R={,,,}(2)S={,,,,}(3)T={,,,}(4)空关系(5)全域关系判断上述关系是否为a)自反的b)对称的c)可传递的d)反对称的。4.一棵数有两个结点度数为2，一个结点度数为3，三个结点度数为4，问有几个度数为1的结点？答案：一、填空题（40分，共10题，每小题4分）1.参考答案：（1）PQ(2)P↔Q(3)PQ解题方案：评分标准：2.参考答案：恒等关系恒等矩阵解题方案：评分标准：答案正确得满分，错误不得分3.参考答案：{＜1,α＞,＜1,β＞,＜1,γ＞,＜2,α＞,＜2,β＞，＜2,γ＞}解题方案：评分标准：4.参考答案：{2,3,φ}解题方案：评分标准：5.参考答案：8解题方案：评分标准：6.参考答案：8解题方案：评分标准：7.参考答案：4解题方案：评分标准：8.参考答案：{1,a,1,b,2,a,2,b}解题方案：评分标准：9.参考答案：解题方案：评分标准：10.参考答案：P∧(Q∨R)解题方案：评分标准：二、作图题（6分，共1题，每小题6分）0.参考答案：（1）、（2）均可画出。依次如下：其中（3）（4）不能画出一个欧拉图，因此具有n个结点的连通图如果存在一条包含所有节点的回路，则该图至少有n条边。对于（3）（4）而言，则必然还有其余的边，使的图中存在奇数度结点，故它们没有欧拉回路，不能构成欧拉图。解题方案：评分标准：三、计算题（30分，共5题，每小题6分）1.参考答案：略解题方案：略评分标准：2.参考答案：可以一笔画（路径略）解题方案：评分标准：3.参考答案：（1）哈斯图为：（2）B的最大元为6，最小元为1，极大元为6，极小元为1.（3）B的上界为：6，12；上确界为6；下界为：1，下确界为1.解题方案：评分标准：4.参考答案：解题方案：评分标准：5.参考答案：解题方案：评分标准：四、分析题（24分，共4题，每小题6分）1.参考答案：解题方案：评分标准：2.参考答案：权=1+2+2+3+5=13解题方案：权=1+2+2+3+5=13评分标准：733.参考答案：（1）可传递的（2）自反、对称、可传递的（3）都不是（4）自反、对称和传递的（5）自反、对称、传递的解题方案：（1）可传递的（2）自反、对称、可传递的（3）都不是（4）自反、对称和传递的（5）自反、对称、传递的评分标准：222224.参考答案：设有x个度数为1的结点。则结点总数为：2+1+3+x=6+x;树的边树=结点数-1，故该树中边数为：5+x;因为：2e=Sdeg(vi)故：2(5+x)=2*2+1*3+3*4+xx=9解题方案：设有x个度数为1的结点。则结点总数为：2+1+3+x=6+x;树的边树=结点数-1，故该树中边数为：5+x;因为：2e=Sdeg(vi)故：2(5+x)=2*2+1*3+3*4+xx=9评分标准：334