离散数学形成性考核作业7答案教程文件

电大离散数学作业答案3-7合集离散数学作业3离散数学集合论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。

本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业。

要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年11月7日前完成并上交任课教师（不收电子稿）。

并在03任务界面下方点击“保存”和“交卷”按钮，完成并上交任课教师。

一、填空题1．设集合{1,2,3},{1,2}A B ==，则P(A)-P(B )= {{3}，{1,3}，{2,3}，{1,2,3}} ，A ⨯ B= {<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3.2>} ．2．设集合A 有10个元素，那么A 的幂集合P(A)的元素个数为 1024．3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R 是A 到B 的二元关系，},,{B A y x B y A x y x R ⋂∈∈∈><=且且 则R 的有序对集合为 {<2, 2>，<2, 3>，<3, 2>}，<3,3> ．4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}， A 到B 的二元关系R ＝},,2,{B y A x x y y x ∈∈=>< 那么R －1＝ {<6,3>,<8,4>} 5．设集合A=｛a, b, c, d ｝，A 上的二元关系R={<a, b>, <b, a>, <b, c>, <c, d>}，则R 具有的性质是 没有任何性质 ．6．设集合A=｛a, b, c, d ｝，A 上的二元关系R={<a, a >, <b, b>, <b, c>, <c, d>}，若在R 中再增加两个元素 {<c,b>,<d,c>} ，则新得到的关系就具有对称性．7．如果R 1和R 2是A 上的自反关系，则R 1∪R 2，R 1∩R 2，R 1-R 2中自反关系有 2 个．8．设A={1, 2}上的二元关系为R={<x, y>|x A ，y A, x+y =10}，则R 的自反闭包为 {<1,1>,<2,2>} ．9．设R 是集合A 上的等价关系，且1 , 2 , 3是A 中的元素，则R 中至少包含 <1,1>,<2,2>,<3,3> 等元素．姓 名： 学 号： 得 分： 教师签名：10．设A ={1，2}，B ={a ，b }，C ={3，4，5}，从A 到B 的函数f ={<1, a >, <2, b >}，从B 到C 的函数g ={< a ，4>, < b ，3>}，则Ran(g ︒ f )= {3,4} ．二、判断说明题（判断下列各题，并说明理由．）1．若集合A = {1，2，3}上的二元关系R={<1, 1>，<2, 2>，<1, 2>}，则 (1) R 是自反的关系； (2) R 是对称的关系．（1） 错误。

第七章部分课后习题参考答案7.列出集合A={2,3,4}上的恒等关系I A,全域关系E A,小于或等于关系L A,整除关系D A.={<2，2>,<3,3>,<4,4>}解：IA={<2,2>,<2,3>,<2,4>,<3,4>,<4,4>,<3,2>,<3,3>,<4,2>,<4,3>}EA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>}LAD={<2,4>}A13.设A={<1,2>,<2,4>,<3,3>}B={<1,3>,<2,4>,<4,2>}求A⋃B,A⋂B, domA, domB, dom(A⋃B), ranA, ranB, ran(A⋂B ), fld(A-B).解：A⋃B={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}A⋂B={<2,4>}domA={1,2,3}domB={1,2,4}dom(A∨B)={1,2,3,4}ranA={2,3,4}ranB={2,3,4}ran(A ⋂B)={4} fld R=dom R ⋃ran RA-B={<1,2>,<3,3>}，fld(A-B)={1,2,3} 14.设R={<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>}求R R, R -1, R ↑{0,1,}, R[{1,2}]解：R R={<0,2>,<0,3>,<1,3>}R -1,={<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>}R ↑{0,1}={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>} R[{1,2}]=ran(R ↑{1,2})={2,3}16．设A={a,b,c,d}，1R ，2R 为A 上的关系，其中1R ={},,,,,a a a b b d{}2,,,,,,,R a d b c b d c b=求23122112,,,R R R R R R 。

三一文库（）*电大考试*电大离散数学数理逻辑部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。

本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。

要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月19日前完成并上交任课教师（不收电子稿）。

并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。

一、填空题1．命题公式()→∨的真值是 1 ．P Q P2．设P：他生病了，Q：他出差了．R：我同意他不参加学习.则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为P∨Q→R．3．含有三个命题变项P，Q，R的命题公式P∧Q的主析取范式是(P∧Q∧┐R)∨(P∧Q∧R)．4．设P(x)：x是人，Q(x)：x去上课，则命题“有人去上课．”可符号化为∃x ( P ( x) ∧Q ( x))．5．设个体域D＝{a, b},那么谓词公式)xA∀∨∃消去量词后的等值式为(A(a)∨A(b))xyB()(y∨(B(a) ∧B(b))．6．设个体域D＝{1, 2, 3}，A(x)为“x大于3”，则谓词公式(∃x)A(x) 的真值为0 ．7．谓词命题公式(∀x)((A(x)∧B(x)) ∨C(y))中的自由变元为y ．8．谓词命题公式(∀x)(P(x) →Q(x) ∨R(x，y))中的约束变元为x ．三、公式翻译题1．请将语句“今天是天晴”翻译成命题公式．解：设P：今天是天晴则该语句符号化为P2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式．设P：小王去旅游，Q：小李也去旅游则该语句符号化为P∧Q3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式．解：设P：明天天下雪Q：我就去滑雪则该语句符号化为P→Q4．请将语句“他去旅游，仅当他有时间．”翻译成命题公式．解：设P：他去旅游Q：他有时间则该语句符号化为P→Q5．请将语句“有人不去工作”翻译成谓词公式．解：设P(x)：x是人Q(x)：x不去工作则谓词公式为(∃x)(P(x)∧Q(x))6．请将语句“所有人都努力工作．”翻译成谓词公式．解：设P(x)：x是人Q(x)：x努力工作则谓词公式为(∀x)(P(x)→Q(x))四、判断说明题（判断下列各题，并说明理由．）1．命题公式⌝P∧P的真值是1．不正确，┐P∧P的真值是0，它是一个永假式，命题公式中的否定律就是┐P∧P=F2．命题公式⌝P∧(P→⌝Q)∨P为永真式．正确可以化简┐P∧（P→┐Q）∨P=┐P∧（┐P∨┐Q）∨P=┐P∨P=1，所以它是永真式当然方法二是用真值表3．谓词公式))xP∀xyG→∀是永真式．y∃→x,)(xP((x)(正确∀x P(x)→(∃y G(x,y)→∀xP(x))=∀x P(x)→(┐∃y G(x,y)∨∀xP(x))=∀x P(x)→(∀y(┐G(x,y))∨∀xP(x))=┐∀x P(x)∨(∀y(┐G(x,y))∨∀xP(x))=┐∀x P(x)∨∀y(┐G(x,y))∨∀xP(x)=┐∀x P(x) ∨∀xP(x)∨∀y(┐G(x,y))=1∨∀y(┐G(x,y))=1所以该式是永真式4．下面的推理是否正确，请给予说明．(1) (∀x)A(x)→ B(x) 前提引入。

第7章习题答案1．f（x）=2|x|+1是从整数集合到正整数集合的函数，它的值域是什么？解：它的值域是正奇数集合。

2．试问下列关系中哪个能构成函数？（1）{〈x，y〉|x，y∈N，x+y<10}（2）{〈x，y〉|x，y∈R，y=x2}（3）{〈x，y〉|x，y∈R，y2=x}解；（1）、（3）不满足函数的定义，只有（2）是函数。

3．下列集合能够定义函数吗？如果能，求出它们的定义域和值域。

（1）{〈1,〈2,3〉〉,〈2,〈3,4〉〉,〈3,〈1,4〉〉,〈4,〈1,4〉〉}（2）{〈1,〈2,3〉〉,〈2,〈3,4〉〉,〈3,〈3,2〉〉}（3）{〈1,〈2,3〉〉,〈2,〈3,4〉〉,〈1,〈2,4〉〉}（4）{〈1,〈2,3〉〉,〈2,〈2,3〉〉,〈3,〈2,3〉〉}解：(1)、(2)、(4)定义的是函数。

(1)的定义域是{1,2,3,4},值域是{〈2,3〉,〈3,4〉,〈1,4〉}(2)的定义域是{1,2,3},值域是{〈2,3〉,〈3,4〉,〈3,2〉}(4)的定义域是{1,2,3},值域是{〈2,3〉}4．设f，g都是函数，并且有f⊆g和dom（g）=dom（f），证明f=g证明：假设f≠g，因为f⊆g和dom（g）=dom（f），则存在x1∈dom（g）和dom（f），使得〈x1,y1〉∈g但〈x1,y1〉∉f，因为f是函数，在定义域上处处有定义，所以必存在y2，使得〈x1,y2〉∈f，由f⊆g得〈x1,y2〉∈g，这与g是函数满足单值性矛盾。

故假设错误，必有f=g。

6．设X={0，1，2}，求出X X中的如下函数（1） f2（x）=f（x）（2） f2（x）=x（3） f3（x）=x解：（1）有10个函数，分别是：f1（x）={〈0,0〉,〈1,0〉,〈2,0〉}f2（x）={〈0,1〉,〈1,1〉,〈2,1〉}f3（x）={〈0,2〉,〈1,2〉,〈2,2〉}f4（x）={〈0,1〉,〈1,1〉,〈2,2〉}f5（x）={〈0,2〉,〈1,1〉,〈2,2〉}f6（x）={〈0,0〉,〈1,0〉,〈2,2〉}f7（x）={〈0,0〉,〈1,2〉,〈2,2〉}f8（x）={〈0,0〉,〈1,1〉,〈2,0〉}f9（x）={〈0,0〉,〈1,1〉,〈2,1〉}f10（x）={〈0,0〉,〈1,1〉,〈2,2〉}（2）有4个函数，分别是：f1（x）={〈0,0〉,〈1,1〉,〈2,2〉}f2（x）={〈0,0〉,〈1,2〉,〈2,1〉}f3（x）={〈0,2〉,〈1,1〉,〈2,0〉}f4（x）={〈0,1〉,〈1,0〉,〈2,2〉}（3）有3个函数，分别是：f 1（x ）={〈0,0〉,〈1,1〉,〈2,2〉}f 2（x ）={〈0,1〉,〈1,2〉,〈2,0〉}f 3（x ）={〈0,2〉,〈1,0〉,〈2,1〉}8．设f,g,h 是N → N 的函数, 其中N 是自然数集合，f(n)＝n ＋1, g(n)＝2n,⎩⎨⎧=是奇数若是偶数若n n n h 10)(试确定：f f ，f g ，g h ，h g 及(f g) h 。

国家开放大学电大本科《离散数学》网络课形考网考作业及答案国家开放大学电大本科《离散数学》网络课形考网考作业及答案100%通过考试说明：2022年秋期电大把该网络课纳入到“国开平台”进行考核，该课程共有5个形考任务，针对该门课程，本人汇总了该科所有的题，形成一个完整的标准题库，并且以后会不断更新，对考生的复习、作业和考试起着非常重要的作用，会给您节省大量的时间。

做考题时，利用本文档中的查找工具，把考题中的关键字输到查找工具的查找内容框内，就可迅速查找到该题答案。

本文库还有其他网核及教学考一体化答案，敬请查看。

课程总成绩=形成性考核×30%+终结性考试×70%形考任务1单项选择题题目1若集合A＝{a，{a}，{1，2}}，则下列表述正确的是（）．选择一项：题目2若集合A＝{2，a，{a}，4}，则下列表述正确的是()．选择一项：题目3设集合A={1,2,3,4}上的二元关系R={<1,1>，<2,2>，<2,3>，<4,4>}，S={<1,1>，<2,2>，<2,3>，<3,2>，<4,4>}，则S是R的（）闭包．选择一项：A.传递B.对称C.自反和传递D.自反题目4设集合A={1,2,3}，B={3,4,5}，C={5,6,7}，则A∪B–C=()．选择一项：A.{1,2,3,5}B.{4,5,6,7}C.{2,3,4,5}D.{1,2,3,4}题目5如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个．选择一项：A.1B.3C.2D.0题目6集合A={1,2,3,4}上的关系R={<x，y>|x=y且x,y∈A}，则R的性质为（）．选择一项：A.不是对称的B.反自反C.不是自反的D.传递的题目7若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是()．选择一项：题目8设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为（）．选择一项：A.3B.2C.8D.6题目9设A={1,2,3,4,5,6,7,8}，R是A上的整除关系，B={2,4,6}，则集合B的最大元、最小元、上界、下界依次为()．选择一项：A.6、2、6、2B.无、2、无、2C.8、1、6、1D.8、2、8、2题目10设集合A={1,2,3}上的函数分别为：f={<1,2>，<2,1>，<3,3>}，g={<1,3>，<2,2>，<3,2>}，h={<1,3>，<2,1>，<3,1>}，则h=（）．选择一项：A.f◦fB.g◦fC.g◦gD.f◦g判断题题目11设A={1,2}上的二元关系为R={<x,y>|xA，yA,x+y=10}，则R的自反闭包为{<1,1>,<2,2>}．（）选择一项：对错题目12空集的幂集是空集．（）选择一项：对错题目13设A={a,b}，B={1,2}，C={a,b}，从A到B的函数f={<a,1>,<b,2>}，从B到C的函数g={<1,b>,<2,a>}，则g°f={<1，2>,<2，1>}．（）选择一项：对错题目14设集合A={1,2,3,4}，B={2,4,6,8}，下列关系f={<1,8>,<2,6>,<3,4>,<4,2,>}可以构成函数f：．（）选择一项：对错题目15设集合A={1,2,3}，B={2,3,4}，C={3,4,5}，则A∩(C-B)={1,2,3,5}．（）选择一项：对错题目16如果R1和R2是A上的自反关系，则、R1∪R2、R1∩R2是自反的．（）选择一项：对错题目17设集合A=｛a,b,c,d｝，A上的二元关系R={<a,b>,<b,a>,<b,c>,<c,d>}，则R具有反自反性质．（）选择一项：对错题目18设集合A={1,2,3}，B={1,2}，则P(A)-P(B)={{3},{1,3},{2,3},{1,2,3}}．（）选择一项：对错题目19若集合A={1，2，3}上的二元关系R={<1,1>，<1,2>，<3,3>}，则R是对称的关系．（）选择一项：对错题目20设集合A={1,2,3,4}，B={6,8,12}，A到B的二元关系R＝那么R－1＝{<6,3>，<8,4>}．（）选择一项：对错形考任务2单项选择题题目1无向完全图K4是（）．选择一项：A.树B.欧拉图C.汉密尔顿图D.非平面图题目2已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为()．选择一项：A.4B.8C.3D.5题目3设无向图G的邻接矩阵为则G的边数为()．选择一项：A.7B.14C.6D.1题目4如图一所示，以下说法正确的是()．选择一项：A.{(a,e),(b,c)}是边割集B.{(a,e)}是边割集C.{(d,e)}是边割集D.{(a,e)}是割边题目5以下结论正确的是()．选择一项：A.有n个结点n－1条边的无向图都是树B.无向完全图都是平面图C.树的每条边都是割边D.无向完全图都是欧拉图题目6若G是一个欧拉图，则G一定是()．选择一项：A.汉密尔顿图B.连通图C.平面图D.对偶图题目7设图G＝<V,E>，v∈V，则下列结论成立的是()．选择一项：题目8图G如图三所示，以下说法正确的是()．选择一项：A.{b,d}是点割集B.{c}是点割集C.{b,c}是点割集D.a是割点题目9设有向图（a）、（b）、（c）与（d）如图五所示，则下列结论成立的是()．选择一项：A.（a）是强连通的B.（d）是强连通的C.（c）是强连通的D.（b）是强连通的题目10设有向图（a）、（b）、（c）与（d）如图六所示，则下列结论成立的是()．选择一项：A.（b）只是弱连通的B.（c）只是弱连通的C.（a）只是弱连通的D.（d）只是弱连通的判断题题目11设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去4条边后使之变成树．()选择一项：对错题目12汉密尔顿图一定是欧拉图．()选择一项：对错题目13设连通平面图G的结点数为5，边数为6，则面数为4．()选择一项：对错题目14设G是一个有7个结点16条边的连通图，则G为平面图．()选择一项：对错题目15如图八所示的图G存在一条欧拉回路．()选择一项：对错题目16设图G如图七所示，则图G的点割集是{f}．()选择一项：对错题目17设G是一个图，结点集合为V，边集合为E，则()选择一项：对错题目18设图G是有5个结点的连通图，结点度数总和为10，则可从G中删去6条边后使之变成树．()选择一项：对错题目19如图九所示的图G不是欧拉图而是汉密尔顿图．()选择一项：对错题目20若图G=<V,E>，其中V={a,b,c,d}，E={(a,b),(a,d),(b,c),(b,d)}，则该图中的割边为(b,c)．()选择一项：对错形考任务3单项选择题题目1命题公式的主合取范式是()．选择一项：题目2设P：我将去打球，Q：我有时间．命题“我将去打球，仅当我有时间时”符号化为()．选择一项：题目3命题公式的主析取范式是()．选择一项：题目4下列公式成立的为()．选择一项：题目5设A（x）：x是书，B（x）：x是数学书，则命题“不是所有书都是数学书”可符号化为（）．选择一项：题目6前提条件的有效结论是()．选择一项：A.QB.┐QC.PD.┐P题目7命题公式(P∨Q)→R的析取范式是()．选择一项：A.(P∨Q)∨RB.┐(P∨Q)∨RC.(P∧Q)∨RD.(┐P∧┐Q)∨R题目8下列等价公式成立的为()．选择一项：题目9下列等价公式成立的为()．选择一项：题目10下列公式中()为永真式．选择一项：A.┐A∧┐B↔┐(A∧B)B.┐A∧┐B↔A∨BC.┐A∧┐B↔┐(A∨B)D.┐A∧┐B↔┐A∨┐B判断题题目11设个体域D＝{1,2,3}，A(x)为“x小于3”，则谓词公式(∃x)A(x)的真值为T．()选择一项：对错题目12设P：小王来学校，Q：他会参加比赛．那么命题“如果小王来学校，则他会参加比赛”符号化的结果为P→Q．()选择一项：对错题目13下面的推理是否正确．()(1)(∀x)A(x)→B(x)前提引入(2)A(y)→B(y)US(1)选择一项：对错题目14含有三个命题变项P，Q，R的命题公式P∧Q的主析取范式(P∧Q∧R)∨(P∧Q∧┐R)．()选择一项：对错题目15命题公式P→(Q∨P)的真值是T．()选择一项：对错题目16命题公式┐P∧P的真值是T．()选择一项：对错题目17谓词公式┐(∀x)P(x)(∃x)┐P(x)成立．()选择一项：对错题目18命题公式┐(P→Q)的主析取范式是P∨┐Q．()选择一项：对错题目19设个体域D＝{a,b}，则谓词公式(∀x)(A(x)∧B(x))消去量词后的等值式为(A(a)∧B(a))∧(A(b)∧B(b))．()选择一项：对错题目20设个体域D＝{a,b},那么谓词公式(∃x)A(x)∨(∀y)B(y)消去量词后的等值式为A(a)∨B(b)．()选择一项：对错形考任务4要求：学生提交作业有以下三种方式可供选择：1.可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅．2.在线提交word文档.3.自备答题纸张，将答题过程手工书写，并拍照上传形考任务5网上学习行为（学生无需提交作业，占形考总分的10%）。

第7章习题解答(1),(2),⑶，⑸都能组成无向图的度数列,其中除⑸外又都能组成无向简单图的度数列.分析1°非负整数列〃詔2,…，血能组成无向图的度数列当且仅当f川为r-1偶数，即心,〃2,…，〃”中的奇数为偶数个.(1),(2),(3),⑸中别离有4个,0个,4个,4个奇数，所以，它们都能组成无向图的度数列，固然，所对应的无向图极可能是非简单图•而(4)中有3个奇数，因此它不能组成无向图度数列.不然就违背了握手定理的推论.2°⑸虽然能组成无向图的度数列，但不能组成无向简单度数列.不然，若存在无向简单图G,以1,3,3,3为度数列,不妨设G中极点为儿宀宀宀，且〃(片)=1, 于是〃(”2)= d(y3) = J(v4) = 3.而儿只能与v2,v3»v4之一相邻,设片与冬相邻，这样一来，除冬能达到3度外，耳宀都达不到3度,这是矛盾的.在图所示的4个图中,(1)以1为度数列，⑵以2为度数列，⑶以3为度数列,(4) 以4为度数列(非简单图).⑴ (2)(3) (4)困7.5设有几简单图D以2, 2, 3, 3为度数列，对应的极点别离为y r v2,v3,v4,由于J(v) = J+(v) + ^-(v),所示，d\v l)-d-(v i) = 2-0 = Zd+(v2) = d(v2)-d-(v2)= 2-0 = 2,J*(V3)=d(v3)-d-(v3) = 3-2 = l,J+(v4)= 〃(勺)一旷(勺)= 3-3 = 0 由此可知,D的出度列为2,2, 1,0,且知足工(广化)=》旷(勺).请读者画出一个有向图.以2, 2, 3, 3为度数列，且以0,0, 2, 3为入度列，以2, 2, 1, 0为出度列.D的入度列不可能为1,1,1, 1.不然，必有出度列为2, 2, 2,2(因为J(v) = J*(v) + J-(v)),)此时，入度列元素之和为4,不等于出度列元素之和8,这违背握手定理.类似地讨论可知，1, 1, 1, 1也不能为D的出席列.不能.N阶无向简单图的最大度厶＜/7-1,而这里的n个正整数彼此不同, 因此这n个数不能组成无向简单图的度数列，不然所得图的最大度大于n,这与最大度应该小于等于n-1矛盾.(1) 16个极点.图中边数加= 16,设图中的极点数为〃.按照握手定理可知2m = 32 =》〃(片)=Inr-I所以，n = 16.(2)13个极点.图中边数也= 21,设3度极点个数为x,由握手定理有2in = 42 = 3 x 4 + 3x由此方程解出x = 10.于是图中极点数71 = 3+10 = 13.(3)III握手定理及各极点度数均相同，寻觅方程2x24 = nk的非负整数解，这里不会出现儿k均为奇数的惜况.其中“为阶级，即极点数，£为度数共可取得下面10种情况.①个极点,度数为48.此图必然是由一个极点的24个环组成,固然为非简单图.②2个极点，每一个极点的度数均为24.这样的图有多种非同构的情况，必然为非简单图.③3个极点，每一个极点的度数均为16.所地应的图也都是非简单图.④4个极点，每一个极点的度数均为12.所对应的图也都是非简单图.⑤6个极点，每一个极点的度数均为8,所对应的图也都是非简单图.⑥个极点，每一个极点的度数均为6.所对应的非同构的图中有简单图，也有非简单图.⑦12个极点，每一个极点的度数均为4.所对应的非同构的图中有简单图, 也有非简单图.⑧16个极点，每一个极点的度数均为3,所对应的非同构的图中有简单图，也有非简单图.⑨24个极点，每一个极点的度数均为2.所对应的非同构的图中有简单图，也有非简单图.⑩48个极点，每一个极点的度数均为1,所对应的图是唯一的，即由24个K,■ 组成的简单图.分析由于n阶无向简单图G A(G)<«-1,的以①所对应的图不可能有简单图•⑥-⑨既有简单图，也有非简单图，读者可以画出若干个非同构的图，而⑩只能为简单图.设G为n阶图，由握手定理可知70 = 2 x 35 =》〃(*]) n 3n,所以,这里，匕」为不大于兀的最大整数，例如[_2」=2丄2.5」=2,斤」=23.由于3(G) = n-l,说明G中任何极点v的度数J(v) > J(G) = /7-1,可是由于G为简单图，因此△(G)S-1,这乂使得J(v) < n -1,于是1,也就是说,G中每一个极点的度数都是幵-1,因此应有△(G)S-1.于是G为("-1)阶正则图，即G为n阶完全图K”.由G的补图7的概念可知，GUG为K”，由于n为奇数，所以，K”中各项极点的度数//-1为偶数•对于任意的卩e卩(G),应有v e V(G),且百度文库•好好学习.天天向上（V）_ d G（y） = C I K K（V）=办一1其中d G(v)表示V在G中的度数，J- (v)表示「在E中的度数.曲于n -1为偶数,所以，与4(叭同为奇数或同为偶数，因此若G有r个奇度极点，则7也有r个奇度极点.由于£>匸ZX所以，m <m.而n阶有向简单图中，边数/n<n(n-l),所以，应n(n -1) = m < m < n(n一1)这就致使川=n(n-l),这说明D为n阶完全图，且D =D.图给岀了心的18个非同构的子图,其中有11个生成子图(8-18),其中连通的有6个11, 12, 13, 14, 16,17).图中,n, m别离为极点数和边数.K-有11个生成子图，在图中，它们别离如图8-18所示•要判断它们肖中哪些是自补图，首先要知道同构图的性质，设G与G?的极点数和边数•若q = G2, 则= n2且m x = m2・£7.6百度文库•好好学习.天天向上(8)的补图为(14) = K,,它们的边数不同，所以，不可能同构.因此⑻与(14) 均不是自补图类似地，(9)的补图为(13),它们也非同构，因此它们也都不是自补图.(10)与(12)互为补图，它们非同构，因此它们都不是自补图.(15)与(17)互为补图，它们非同构，所以，它们都不是自补图.类似地，(16)与(18)互为补图且非同构，所以，它们也都不是自补图.而(11)与自己的补图同构,所以，(11)是自补图.3阶有向完全图共有20个非同构的子图，见图所示，其中(5)-(20)为生成子图，生成子图中(8), (13), (16), (19)均为自补图.分析在图所示的生成子图中，(5)与(11)互为补图，(6)与(10)互为补图，(7)与(9)互为补图,(⑵与(14)互为补图,(15)与(17)互为补图,(18)与(20) 互为补图，以上互为补图的两个图边数均不相同，所以，它们都不是自补图.而(8), (13), (16), (19)4个图都与自己的补图同构，所以，它们都是自补图.不能.分析在同构的意义下，G P G2,G3都中心的子图，而且都是成子图.而心的两条边的主成子图中，只有两个是非同构的，见图中(10)与(15)所示.山鸽巢原理可知，G r G2,G3中至少有两个是同构的，因此它们不可能彼此都非同构.鸽巢原理川只鸽飞进H个鸽巢，其中心2,则至少存在一巢飞入至少[口只n鸽子.这里「刃表示不小于X的最小整数.例如,⑵=2,「2.5] = 3.7. 14 G是唯一的，即便G是简单图也不唯一.百度文库-好好学习.天天向上分析 山握手定理可知2也=3从乂山给的条件得联立议程组 2m = 3/2<2〃 一 3 = m.解出” =6,加= 9.6个极点,9条边，每一个极点的度数都是3的图有多种非同 构的情况，其中有多个非简单图(带平行边或环)，有两个非同构的简单图，在图的事实，设GG 都是n 阶简单图，则G, =G 2当且仅当石三房，其中瓦，不别离 为G 与62的补图.知足要求的简单图都是6阶9条边的3正则图，因此它们的补 图都为6阶6条边的2正则图(即每一个极点度数都是2).而心的所有生成子图 中,6条边2正则的非同构的图只有两个，见图中(3), (4)所示的图，其中(3)为(1) 的补图，⑷为⑵的补图，知足要求的非同构的简单图只有两个.但知足要求的非同简单图有多个非同构的，读者可自己画出多个来.将心的极点标定顺序，讨论片所关联的边.由鸽巢原理(见 题)，与片关联 的5条边中至少有3条边颜色相同，不妨设存在3条红色边,见图中(1)所示(用 实线表示红色的边)并设它们关联另外3个极点别离为V 2,V 4,V 6.若”2，^，%组成 的心中还有红色边，比如边(v 2,v 4)为红色，则v,,v 2,v 4组成的©为红色心，见 图中⑵所示.若v 2,v 4,v 6组中(1), (2)给出了这两个非同构的简单图.知足条件的非同构的简单图只有图 中，(1),⑵所示的图，⑴与⑵所示的图，⑴ 与(2)是非同构的.注意在(1)中不存在3个彼此相邻的极点, 而在(2)中存在3个彼此相邻的极点，因此(1) 图与(2)图非同构.下面分析知足条件的简单 图只有两个是非同构的•首先注意到(1)中与 (2)中图都是心的生成子图，而且还有这样£ 7.8百度文库•好好学习.天天向上成的心各边都是蓝色(用虚线表示)，则V2,V4,V6组成的&为蓝色的.(1> ⑵(3)困7.9在图所示的3个图中，（1）为强连通图，（2）为单向连通图，但不是强连通的，（3）是弱连通的，不是单向连通的，更不是强连通的.分析在（1）中任何两个极点之间都有通路，即任何两个极点都是彼此可达的，因此它是强连能的.（2）中c不可达任何极点，因此它不是强连通的，但任两个极点存在一个极点可达另外一个极点，所以，它是单向可达的.（3）中“,c彼此均不可达，因此它不是单向连通的，更不是强连通的.判断有向图的连通性有下面的两个判别法.1°有向图D是强连通的当且仅当D中存在通过每一个极点至少一次的回路.2°有向图D是单向连通的当且仅当D中存在通过每一个极点至少一次的通路.（1）中“仇为通过每一个极点一次的回路，所以，它是强连能的.⑵中为通过每一个极点的通路，所以，它是单向连通的，但没有通过每一个极点的回路，所以，它不是强连通的.（3）中无通过每一个极点的回路，也无通过每一个极点的通路，所以，它只能是弱连通的.G-E的连通分支必然为2,而G-V的连通分支数是不肯定的.百度文库-好好学习.天天向上分析 设E 为连通图G 的边割集，则G-E 的连通分支数p(G - E ) = 2,不可 能大于2.不然，比如“(G -E ) = 3,则G-E 由3个小图G,,G 2,G 3组成，且E 中边 的两个端点分属于两个不同的小图.设E”中的边的两个端点一个在G 中，另一 个在G?中，则E「uE ,易知〃(G-£”)= 2,这与F 为边割集矛盾，所以， p(G-E ) = 2.但p(G-V )不是定数，固然它大于等于2,在图中，"=｛“」，｝为⑴的点割集, /XG-V ) = 2,其中G 为⑴中图.V =(v ｝为⑵中图的点割集，且卩为割点, “(G -V) = 4,其中G 为⑵中图.解此题，只要求岀D 的邻接矩阵的前4次幕即可.D 中长度为4的通路数为屮中元素之和，等于15,其中对角线上元素之和为3,即D 中长度为3的回路数为3. b 到6的长度为4的通路数等于尿：＞ =2.分析 用邻接矩阵的幕求有向图D 中的通路数和回路数应该注意以下儿点: 1°这里所谈通路或回路是概念意义下的，不是同构意义下的.比如，不同始 点(终点)的回路'o 1 1 0 1 0 0・ 0 A =0 1 0 10 0 0 0'1 1 1 1 ■1 1 0 1=0 1 1 10 0 0 1_"1 0 1 0 1 1 1・A 2=1 0 0 10 0 0 1'1 2 1 2~1 1 1 1A 4=1 1 0 10 0 0 1 (2)百度文库•好好学习.天天向上2°这里的通路或回路不但有低级的、简单的，还有复杂的.例/lO, v l,v2,v1,v2,v1是一条长为4的复杂回路.3°回路仍然看成是通路的特殊情况.读者可利用求D中长度为2和3的通路和回路数.答案A:④.分析G中有皿个k度极点，有(// - N k)个伙+1)度极点，由握手定理可知工J(v z) = k-N k + 伙 +1)(/7 一NJ = 2m=> Nk = n{k + 1) —2n.答案A:②；B:③.分析在图中，图(1)与它的补同构，再没有与图(1)非同构的自补图了，所以非同构的无向的4阶自补图只有1个.图(2)与它的补同构，图(3)与它的补也同构，而图(2)与图(3)不同构，再没有与(2), (3)非同构的自补图了，所以，非同械的5阶自补图有2个.(1)⑵⑶困7.12答案A:④；B:③；C:④；D:©.分析(1)中存在通过每一个极点的回路，如很/1力0.. (2)中存在通过每一个极点的通路，但无回路.(3)中无通过每一个极点至少一次的通路,其实，两个极点互不可达.(4)中有通过每一个极点至少一次的通路，但无回路，负Mcbd为通过每一个极点的通路•(5)中存在通过每一个极点至少一次的回路，如aedbcdba(6)中也存在通过每一个极点的回路，如baebdcb. ill题可知，(1), (5), (6)是强连通的,(1), (2), (4), (5), (6)是单向连能的，(2), (4)是非强连通的单向连通图.注意，强连通图必为单向连通图.6个图中，只有(3)既不是强连通的，也不是连通的，它只是弱连通图.在⑶中，从&到b无通路，所以d,<a y b>= 00,而方到a有唯一的通路加，所以〃<百度文库-好好学习.天天向上b.a >= 1 ・答案A:①；B:⑥（十）C:②；D:④.分析用Dijkstra标号法，将计算机结果列在表中.表中第x列最后标定回表示b到x的最短路径的权为y,且在b到x的最短路径上,Z邻接到x,即x的前驱元为乙曲表可知,a的前驱元为c （即a邻接到c）, c的前驱元为b,所以,b到a的最短路径为仇其权为4.类似地计论可知,b到c的最短路径为be,其权为到d的最短路径为bceg〃，其权为到e的最短路径为bee,其权为7.答案A:⑧；B:⑩C:③；D:③和④.分析按求最先、最晚完成时间的公式，先求各极点的最先完成时间，再求最晚完成时间，最后求缓冲时间。

第七章习题答案2. 试问下列关系中哪个能构成函数：(1){< x1, x2 > | x1, x2∈N, x1 + x2 <10}(2){< x, y > | x, y∈R, y = x2}(3){< x, y > | x, y∈R, y2 = x}解只有(2)满足单值性，能构成函数。

6. 设X = {0, 1, 2}，求出X X中的如下函数：(1)f2(x) = f (x)(2)f2(x) = x(3)f3(x) = x解(1) 任取y∈ran( f )，则有x∈X使得f (x) = y，因而f (y) = f2(x) = f (x) = y若ran( f ) = {0}，则f1 = {< 0, 0 >,< 1, 0 >,< 2, 0 >}。

若ran( f ) = {1}，则f2 = {< 0, 1 >,< 1, 1 >,< 2, 1 >}。

若ran( f ) = {2}，则f3 = {< 0, 2 >,< 1, 2 >,< 2, 2 >}。

若ran( f ) = {0, 1}，则有两个函数f4 = {< 0, 0 >,< 1, 1 >,< 2, 0 >}和f5 = {< 0, 0 >,< 1, 1 >,< 2, 1 >}。

若ran( f ) = {0, 2}，则有两个函数f6 = {< 0, 0 >,< 1, 0 >,< 2, 2 >}和f7 = {< 0, 0 >,< 1, 2 >,< 2, 2 >}。

若ran( f ) = {1, 2}，则有两个函数f8 = {< 0, 1 >,< 1, 1 >,< 2, 2 >}和f9 = {< 0, 2 >,< 1, 1 >,< 2, 2 >}。

2017年11月上交的离散数学形考任务一本课程的教学内容分为三个单元，其中第三单元的名称是（A ）．选择一项：A. 数理逻辑B. 集合论C. 图论D. 谓词逻辑题目2答案已保存满分10.00标记题目题干本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合，其中第2章关系与函数中的第3个知识点的名称是（D ）．选择一项：A. 函数B. 关系的概念及其运算C. 关系的性质与闭包运算D. 几个重要关系题目3答案已保存满分10.00标记题目题干本课程所有教学内容的电视视频讲解集中在VOD点播版块中，VOD点播版块中共有（B）讲．选择一项：A. 18B. 20C. 19D. 17题目4答案已保存满分10.00标记题目题干本课程安排了7次形成性考核作业，第3次形成性考核作业的名称是（ C）．选择一项：A. 集合恒等式与等价关系的判定B. 图论部分书面作业C. 集合论部分书面作业D. 网上学习问答题目5答案已保存满分10.00标记题目题干课程学习平台左侧第1个版块名称是：（C）．选择一项：A. 课程导学B. 课程公告C. 课程信息D. 使用帮助题目6答案已保存满分10.00标记题目题干课程学习平台右侧第5个版块名称是：（D）．选择一项：A. 典型例题B. 视频课堂C. VOD点播D. 常见问题题目7答案已保存满分10.00标记题目题干“教学活动资料”版块是课程学习平台右侧的第（ A ）个版块．选择一项：A. 6B. 7C. 8D. 9题目8答案已保存满分10.00标记题目题干课程学习平台中“课程复习”版块下，放有本课程历年考试试卷的栏目名称是：（D ）．选择一项：A. 复习指导B. 视频C. 课件D. 自测请您按照课程导学与章节导学中安排学习进度、学习目标和学习方法设计自己的学习计划，学习计划应该包括：课程性质和目标（参考教学大纲）、学习内容、考核方式，以及自己的学习安排，字数要求在100—500字．完成后在下列文本框中提交．解答：学习计划学习离散数学任务目标：其一是通过学习离散数学，使学生了解和掌握在后续课程中要直接用到的一些数学概念和基本原理，掌握计算机中常用的科学论证方法，为后续课程的学习奠定一个良好的数学基础；其二是在离散数学的学习过程中，培养自学能力、抽象思维能力和逻辑推理能力，解决实际问题的能力，以提高专业理论水平。

离散数学数理逻辑部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。

本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。

要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师（不收电子稿）。

并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。

一、填空题1．命题公式()→∨的真值是1或T ．P Q P2．设P：他生病了，Q：他出差了．R：我同意他不参加学习.则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为（P∨Q）→R ．3．含有三个命题变项P，Q，R的命题公式P∧Q的主析取范式是(P∧Q∧R)∨(P∧Q∧⌝R)．4．设P(x)：x是人，Q(x)：x去上课，则命题“有人去上课．”可符号化为∃x(P(x) ∧Q(x)) ．5．设个体域D＝{a, b},那么谓词公式)xA∀∃消去量词后的等值式为∨x(yB)(y(A(a)∨A(b))∨((B(a)∧B(b)) ．6．设个体域D＝{1, 2, 3}，A(x)为“x大于3”，则谓词公式(∃x)A(x) 的真值为0(F) ．7．谓词命题公式(∀x)((A(x)∧B(x)) ∨C(y))中的自由变元为y ．8．谓词命题公式(∀x)(P(x) →Q(x) ∨R(x，y))中的约束变元为x ．三、公式翻译题1．请将语句“今天是天晴”翻译成命题公式．设P：今天是晴天。

则P2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式．设P：小王去旅游。

Q：小李去旅游。

则P∧Q3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式．设P：明天下雪。

失散数学作业3姓名：学号：得分：教师署名：失散数学会合论部分形成性查核书面作业本课程形成性查核书面作业共 3 次，内容主要分别是会合论部分、图论部分、数理逻辑部分的综合练习，基本上是依据考试的题型（除单项选择题外）安排演习题目，目的是经过综合性书面作业，使同学自己查验学习成就，找出掌握的单薄知识点，要点复习，争取赶快掌握。

本次形考书面作业是第一次作业，大家要仔细实时地达成会合论部分的综合练习作业。

要求：将此作业用A4 纸打印出来，手工书写答题，笔迹工整，解答题要有解答过程，要求 2018 年 11 月 7 日前达成并上交任课教师（不收电子稿）。

并在 03 任务界面下方点击“保留”和“交卷”按钮，达成并上交任课教师。

一、填空题1．设会合A{1, 2, 3}, B { 1, 2} ，则P(A)- P(B )={{1,2},{2,3},{1,3},{1,2,3}}，A B={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} ．2．设会合 A 有 10 个元素，那么 A 的幂会合 P(A)的元素个数为 1024．3．设会合 A={0, 1, 2, 3} ， B={2, 3, 4, 5} ， R 是 A 到 B 的二元关系，R { x, y x A且y B且x, y A B}则 R 的有序对会合为 {<2,2>,<2,3>,<3,2>,<3,3>} ．4．设会合 A={1, 2, 3, 4 } ，B={6, 8, 12} ，A 到 B 的二元关系R＝{x, y y 2 x, x A, y B}那么 R－1＝{<6,3>,<8,4>}5．设会合 A=｛a,b,c,d｝， A 上的二元关系 R={< a, b>, <b, a>, <b, c>, <c, d>} ，则 R 拥有的性质是反自反性．6．设会合 A=｛a,b,c,d｝， A 上的二元关系 R={< a, a>, <b, b>, <b, c>, <c, d>} ，若在 R 中再增添两个元素 <c, b>, <d, c>，则新获得的关系就拥有对称性．7．假如 R1和 R2是 A 上的自反关系，则 R1∪R2，R1∩R2，R1- R2中自反关系有 2个．8．设 A={1,2} 上的二元关系为 R={< x,y>|x A，y A,x+y=10} ，则 R 的自反闭包为 {<1,1>,<2,2>} ．9．设 R 是会合 A 上的等价关系，且 1 , 2 , 3 是 A 中的元素，则 R 中起码包括<1,1>,<2,2>,<3,3>等元素．10．设会合 A={1, 2} ，B={ a, b} ，那么会合 A 到 B 的双射函数是{<1,a>,<2,b>} 或{<1,b>,<2,a>} ．二、判断说明题（判断以下各题，并说明原因．）1．若会合 A = {1 ，2，3} 上的二元关系 R={<1, 1> ，<2, 2>，<1, 2>} ，则(1) R 是自反的关系；(2) R 是对称的关系．解： (1) 结论不建立．由于关系 R 要成为自反的，此中缺乏元素<3, 3>．(2)结论不建立．由于关系 R 中缺乏元素 <2, 1>．2．假如 R1和 R2是 A 上的自反关系，判断结论：“的” 能否建立？并说明原因．解：结论建立．由于 R1和 R2是 A 上的自反关系，即 I A R1，I A 由逆关系定义和 I A R1，得 I A R1-1；由 I A R1，I A R2，得 I A R1∪R2，I A R1 R2．所以， R1-1、R1∪ R2、R1 R2是自反的．3．若偏序集<A，R>的哈斯图如图一所示，则会合 A 的最大元为 a，最小元不存在．错误，依据定义，图中不存在最大元和最小元。

离散数学作业7离散数学图论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。

本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。

要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成并上交任课教师（不收电子稿）。

并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。

一、单项选择题1．设图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101010010000011100000100，则G 的边数为( D )．A ．5B ．6C ．3D ．4 2．设图G ＝<V ,E >，则下列结论成立的是 ( C )． A ．deg(V )=2∣E ∣ B ．deg(V )=∣E ∣ C ．E v Vv 2)deg(=∑∈ D ．E v Vv =∑∈)deg(3．设有向图（a ）、（b ）、（c ）与（d ）如下图所示，则下列结论成立的是( D )．A ．（a ）是强连通的B ．（b ）是强连通的C ．（c ）是强连通的D ．（d ）是强连通的 4．给定无向图G 如右图所示，下面给出的结 点集子集中，不是点割集的为（ B ）．A ．{b , d }B ．{d }姓 名： 学 号： 得 分： 教师签名：a b dc eο ο ο ο ο 4题图C ．{a , c }D ．{b , e }5．图G 如右图所示，以下说法正确的是 ( C ) ． A ．{(a , c )}是割边 B ．{(a , c )}是边割集 C ．{(b , c )}是边割集 D ．{(a, c ) ,(b, c )}是边割集6．无向图G 存在欧拉通路，当且仅当(D )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点7．若G 是一个欧拉图，则G 一定是( C )．A ．平面图B ．汉密尔顿图C ．连通图D ．对偶图8．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( A )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋29．设G 是有n 个结点，m 条边的连通图，必须删去G 的( A )条边，才能确定G 的一棵生成树．A ．1m n -+B ．m n -C ．1m n ++D ．1n m -+ 10．已知一棵无向树T 中有8个结点，4度，3度，2度的分支点各一个，T 的树叶数为（D ）．A ．8B ．5C ．4D ．3二、填空题1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ．2．设给定图G (如右由图所示)，则图G 的点割集是 {f,c} ．3．设G 是一个图，结点集合为V ，边集合为E ，则 G 的结点 度数 等于边数的两倍．4．设有向图D 为欧拉图，则图D 中每个结点的入度 等于出度 ． 5．设G=<V ，E >是具有n 个结点的简单图，若在G 中每一对结点度数之和大于等于 n-1 ，则在G 中存在一条汉密尔顿路．6．设无向图G ＝<V ，E >是汉密尔顿图，则V 的任意非空子集V 1，都有 W(G-V1) ≤∣V 1∣．7．设完全图K n 有n 个结点(n ≥2)，m 条边，当 当m=2n 时，K n 中存在欧拉回路．ο a οο οο b cde 5题图8．设图G=<V,E>，其中|V|=n，|E|=m．则图G是树当且仅当G是连通的，且m=2V-2 ．9．连通无向图G有6个顶点9条边，从G中删去4 条边才有可能得到G的一棵生成树T．10．设正则5叉树的树叶数为17，则分支数为i = 4 ．三、判断说明题（判断下列各题，并说明理由．）1．(1) 如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路．．(2) 图G1，(如下图所示) 是欧拉图．解：(1)错，图G是无向图，当且仅当G是连通的，且所有结点度数均为偶数，这里不能确定G图是否是连通的。

离散数学作业7离散数学图论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。

本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。

要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成并上交任课教师（不收电子稿）。

并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。

一、单项选择题1．设图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101010010000011100000100，则G 的边数为( D )． A ．5 B ．6 C ．3 D ．42．设图G ＝<V , E >，则下列结论成立的是 ( C )．A ．deg(V )=2∣E ∣B ．deg(V )=∣E ∣C ．E v V v 2)deg(=∑∈D ．E v Vv =∑∈)deg(3．设有向图（a ）、（b ）、（c ）与（d ）如下图所示，则下列结论成立的是( D )．A ．（a ）是强连通的B ．（b ）是强连通的C ．（c ）是强连通的D ．（d ）是强连通的4．给定无向图G 如右图所示，下面给出的结点集子集中，不是点割集的为（ B ）．A ．{b , d }B ．{d }C ．{a , c }D ．{b , e }5．图G 如右图所示，以下说法正确的是 ( C ) ．A ．{(a , c )}是割边B ．{(a , c )}是边割集C ．{(b , c )}是边割集D ．{(a, c ) ,(b, c )}是边割集6．无向图G 存在欧拉通路，当且仅当(D )．a b d c eο ο ο ο ο 4题图 ο a ο ο ο ο b c d e 5题图A ．G 中所有结点的度数全为偶数B ．G 中至多有两个奇数度结点C ．G 连通且所有结点的度数全为偶数D ．G 连通且至多有两个奇数度结点7．若G 是一个欧拉图，则G 一定是( C )．A ．平面图B ．汉密尔顿图C ．连通图D ．对偶图8．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( A )．A ．e －v ＋2B ．v ＋e －2C ．e －v －2D ．e ＋v ＋29．设G 是有n 个结点，m 条边的连通图，必须删去G 的( A )条边，才能确定G 的一棵生成树．A ．1m n -+B ．m n -C ．1m n ++D ．1n m -+10．已知一棵无向树T 中有8个结点，4度，3度，2度的分支点各一个，T 的树叶数为（D ）．A ．8B ．5C ．4D ．3二、填空题1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ．2．设给定图G (如右由图所示)，则图G 的点割集是{f,c} ．3．设G 是一个图，结点集合为V ，边集合为E ，则G 的结点 度数 等于边数的两倍．4．设有向图D 为欧拉图，则图D 中每个结点的入度 等于出度 ．5．设G=<V ，E >是具有n 个结点的简单图，若在G 中每一对结点度数之和大于等于 n-1 ，则在G 中存在一条汉密尔顿路．6．设无向图G ＝<V ，E >是汉密尔顿图，则V 的任意非空子集V 1，都有 W(G-V1) ≤∣V 1∣．7．设完全图K n 有n 个结点(n ≥2)，m 条边，当 当m=2n 时，K n 中存在欧拉回路．8．设图G =<V ,E >，其中|V |=n ，|E |=m ．则图G 是树当且仅当G 是连通的，且m = 2V-2 ．9．连通无向图G 有6个顶点9条边，从G 中删去 4 条边才有可能得到G 的一棵生成树T ．10．设正则5叉树的树叶数为17，则分支数为i = 4 ．三、判断说明题（判断下列各题，并说明理由．）1．(1) 如果图G 是无向图，且其结点度数均为偶数，则图G 存在一条欧拉回路．．(2) 图G 1，(如下图所示) 是欧拉图．解：(1)错，图G 是无向图，当且仅当G 是连通的，且所有结点度数均为偶数，这里不能确定G 图是否是连通的。

大学离散数学试卷七及答案一、选择题(每题2分，共20分)1．下列句子是命题的是[ D ]。

A ．禁止吸烟!B ．你带了衣服吗？C ．2x+3>8。

D ．小红是大学生。

2．对于公式),()),(),((z x G y x yH y x F x ∧∃→∀，下列说法正确的是[ C ]。

A ．y 是自由变元B ．x 是约束变元C ．z 是自由变元D ．∀x 的辖域是F(x ，y)3．命题公式q q p ∧→⌝)(的类型是[ B ]。

A ．重言式B ．矛盾式C ．非永真的可满足式D ．等价式4．A ＝｛a ，b ，c ｝上的二元关系如下所示，具有传递性的是[ A ]。

A ．{<a,a>}B ．{<b,c>,<a,b>}C ．{<a,b>,<b,a>}D ．{<b,a>，<a,c>，<c,b>}5．集合{－1，0，1}上的[ A ]运算为二元运算（满足封闭性）。

A ．乘法B ．除法C ．加法D ．减法6．P(S)是非空有限集合S 的幂集，则代数系统<P(S)，∪>中的零元是[ B ]。

A ．P(S)B ．SC ．ΦD ．{Φ}7．代数系统<G ，+>中，+是普通加法，以下选项[ B ]不是群。

A ．G 为有理数集合B ．G 为自然数集合C ．G 为整数集合D ．G 为实数集合8．无环有向图的关联矩阵中，每行中1的个数是[ C ]。

A ．边数的2倍B ．相关顶点的度C ．相关顶点的出度D ．相关顶点的入度9．6阶无向完全图的边数为[ A ]。

A ．15B ．30C ．0D ．1010．有向图的度数序列为(6,5,4,4,3)，入度序列为(2,3,1,4,2)，则以下选项[ C ]是正确的出度序列。

A ．(2,3,1,4,2)B ．(6,5,4,4,3)C ．(4,1,3,1,1)D ．(3,3,3,0,2)二、填空题(每题2分，共20分)1．公式∀xP(x)∨∃xF(x,y)的前束范式为 ∀x ∃z (P(x)∨F(z,y)) 。

2017年11月上交的离散数学形考任务一本课程的教学内容分为三个单元，其中第三单元的名称是（A ）．选择一项：A. 数理逻辑B. 集合论C. 图论D. 谓词逻辑题目2答案已保存满分10.00标记题目题干本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合，其中第2章关系与函数中的第3个知识点的名称是（D ）．选择一项：A. 函数B. 关系的概念及其运算C. 关系的性质与闭包运算D. 几个重要关系题目3答案已保存满分10.00标记题目题干本课程所有教学内容的电视视频讲解集中在VOD点播版块中，VOD点播版块中共有（B）讲．选择一项：A. 18B. 20C. 19D. 17题目4答案已保存满分10.00标记题目题干本课程安排了7次形成性考核作业，第3次形成性考核作业的名称是（ C）．选择一项：A. 集合恒等式与等价关系的判定B. 图论部分书面作业C. 集合论部分书面作业D. 网上学习问答题目5答案已保存满分10.00标记题目题干课程学习平台左侧第1个版块名称是：（C）．选择一项：A. 课程导学B. 课程公告C. 课程信息D. 使用帮助题目6答案已保存满分10.00标记题目题干课程学习平台右侧第5个版块名称是：（D）．选择一项：A. 典型例题B. 视频课堂C. VOD点播D. 常见问题题目7答案已保存满分10.00标记题目题干“教学活动资料”版块是课程学习平台右侧的第（ A ）个版块．选择一项：A. 6B. 7C. 8D. 9题目8答案已保存满分10.00标记题目题干课程学习平台中“课程复习”版块下，放有本课程历年考试试卷的栏目名称是：（D ）．选择一项：A. 复习指导B. 视频C. 课件D. 自测请您按照课程导学与章节导学中安排学习进度、学习目标和学习方法设计自己的学习计划，学习计划应该包括：课程性质和目标（参考教学大纲）、学习内容、考核方式，以及自己的学习安排，字数要求在100—500字．完成后在下列文本框中提交．解答：学习计划学习离散数学任务目标：其一是通过学习离散数学，使学生了解和掌握在后续课程中要直接用到的一些数学概念和基本原理，掌握计算机中常用的科学论证方法，为后续课程的学习奠定一个良好的数学基础；其二是在离散数学的学习过程中，培养自学能力、抽象思维能力和逻辑推理能力，解决实际问题的能力，以提高专业理论水平。

姓名：学号：得分：教师签名：离散数学作业7离散数学数理逻辑局部形成性查核书面作业本课程形成性查核书面作业共 3 次，内容主要别离是调集论局部、图论局部、数理逻辑局部的综合操练，底子上是按照测验的题型〔除单项选择题外〕安排练习标题问题，目的是通过综合性书面作业，使同学本身查验学习成果，找出掌握的薄弱常识点，重点复习，争取尽快掌握。

本次形考书面作业是第三次作业，大师要当真及时地完成数理逻辑局部的综合操练作业。

要求：将此作业用A4 纸打印出来，手工书写答题，笔迹工整，解答题要有解答过程，要求2021年12 月19日前完成并上交任课教师〔不收电子稿〕。

并在07 任务界面下方点击“保存〞和“交卷〞按钮，以便教师评分。

一、填空题1．命题公式P (Q P) 的真值是 1 ．2．设P：他生病了，Q：他出差了．R：我同意他不参加学习. 那么命题“如果他生病或出差了，我就同意他不参加学习〞符号化的成果为．(P Q) R3．含有三个命题变项P，Q，R 的命题公式P Q 的主析取范式是(P Q R) (P Q R) ．4．设P(x)：x 是人，Q(x)：x 去上课，那么命题“有人去上课．〞可符号化为( x)(P(x) →Q(x)) ．5．设个体域D＝{a, b},那么谓词公式xA( x) yB( y) 消去量词后的等值式为(A(a) A(b)) (B(a) B(b)) ．6．设个体域D＝{1, 2, 3} ，A(x) 为“x 大于3〞，那么谓词公式( x)A(x) 的真值为．7．谓词命题公式( x)((A(x) B(x)) C(y))中的自由变元为8．谓词命题公式( x)(P(x) Q(x) R(x，y))中的约束变元为．X ．三、公式翻译题1．请将语句“今天是天晴〞翻译成命题公式．1．解：设P：今天是天晴；那么P．2．请将语句“小王去旅游，小李也去旅游．〞翻译成命题公式．解：设P：小王去旅游，Q：小李去旅游，那么PQ．3．请将语句“如果明天天下雪，那么我就去滑雪〞翻译成命题公式．解：设P:明天天下雪。