最新电大离散数学作业5答案(图论部分)

电大离散数学作业答案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） 错误。

(精华版)国家开放大学电大本科《离散数学》网络课形考网考作业及答案(精华版)国家开放大学电大本科《离散数学》网络课形考网考作业及答案 100%通过考试说明：2020年秋期电大把该网络课纳入到“国开平台”进行考核，该课程共有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的（）闭包．选择一项：B. 对称题目4 设集合A={1, 2, 3}，B={3, 4, 5}，C={5, 6, 7}，则A∪B–C=( )．选择一项：D. {1, 2, 3, 4} 题目5 如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个．选择一项：C. 2 题目6 集合A={1, 2, 3, 4}上的关系R={<x，y>|x=y且x, y∈A}，则R的性质为（）．选择一项：D. 传递的题目7 若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( )．选择一项：题目8 设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为（）．选择一项：C. 8 题目9 设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为 ( )．选择一项：B. 无、2、无、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 =（）．选择一项：D. 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是（）．选择一项：C. 汉密尔顿图题目2 已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为( )．选择一项：D. 5 题目3 设无向图G的邻接矩阵为则G的边数为( )．选择一项：A. 7 题目4 如图一所示，以下说法正确的是 ( ) ．选择一项：C. {(d, e)}是边割集题目5 以下结论正确的是( )．选择一项：C. 树的每条边都是割边题目6 若G是一个欧拉图，则G一定是( )．选择一项：B. 连通图题目7 设图G＝<V, E>，v∈V，则下列结论成立的是 ( ) ．选择一项：题目8 图G如图三所示，以下说法正确的是 ( )．选择一项：C. {b, c}是点割集题目9 设有向图（a）、（b）、（c）与（d）如图五所示，则下列结论成立的是( )．选择一项：A. （a）是强连通的题目10 设有向图（a）、（b）、（c）与（d）如图六所示，则下列结论成立的是( )．选择一项：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 前提条件的有效结论是( )．选择一项：B. ┐Q 题目7 命题公式(P∨Q)→R的析取范式是 ( )．选择一项：D. (┐P∧┐Q)∨R 题目8 下列等价公式成立的为( )．选择一项：题目9 下列等价公式成立的为( )．选择一项：题目10 下列公式中 ( )为永真式．选择一项：C. ┐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%）附：元宇宙（新兴概念、新型虚实相融的互联网应用和社会形态）元宇宙（Metaverse）是整合了多种新技术而产生的新型虚实相融的互联网应用和社会形态，通过利用科技手段进行链接与创造的，与现实世界映射与交互的虚拟世界，具备新型社会体系的数字生活空间。

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

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

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

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

一、填空题1．图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，那么G的边数是 15 ．2．设给定图G(如右由图所示)，那么图G的点割集是 {f} ．3．设G是一个图，结点集合为V，边集合为E，那么 G的结点度数之和等于边数的两倍．4．无向图G存在欧拉回路，当且仅当G连通且等于出度． 5．设G=是具有n个结点的简单图，假设在G中每一对结点度数之和大于等于 n-1 ，那么在G 中存在一条汉密尔顿路．6．假设图G=中具有一条汉密尔顿回路，那么对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，那么S中结点数|S|与W满足的关系式为 W(G-V1) ??V1? ．7．设完全图Kn有n个结点(n?2)，m条边，当 n为奇数时，Kn中存在欧拉回路．8．结点数v与边数e满足 e=v-1 关系的无向连通图就是树． 9．设图G是有6个结点的连通图，结点的总度数为18，那么可从G中删去 4 条边后使之变成树．10．设正那么5叉树的树叶数为17，那么分支数为i = 5 ．1★形成性考核作业★二、判断说明题〔判断以下各题，并说明理由．〕1．如果图G是无向图，且其结点度数均为偶数，那么图G存在一条欧拉回路．． (1) 不正确，缺了一个条件，图G应该是连通图，可以找出一个反例，比方图G是一个有孤立结点的图。

离散数学图论答案离散数学图论答案【篇⼀：离散数学图论习题】综合练习⼀、单项选择题1．设l是n阶⽆向图g上的⼀条通路，则下⾯命题为假的是( )． (a) l可以不是简单路径，⽽是基本路径 (b) l可以既是简单路径,⼜是基本路径 (c) l可以既不是简单路径，⼜不是基本路径 (d) l可以是简单路径，⽽不是基本路径答案：a2．下列定义正确的是( )．(a) 含平⾏边或环的图称为多重图(b) 不含平⾏边或环的图称为简单图 (c) 含平⾏边和环的图称为多重图(d) 不含平⾏边和环的图称为简单图答案：d3．以下结论正确是 ( )．(a) 仅有⼀个孤⽴结点构成的图是零图 (b) ⽆向完全图kn每个结点的度数是n (c) 有n(n1)个孤⽴结点构成的图是平凡图(d) 图中的基本回路都是简单回路答案：d4．下列数组中，不能构成⽆向图的度数列的数组是( )． (a)(1,1,1,2,3) (b) (1,2,3,4,5) (c) (2,2,2,2,2) (d) (1,3,3,3) 答案：b5．下列数组能构成简单图的是( )． (a) (0,1,2,3)(b) (2,3,3,3)(c) (3,3,3,3)(d) (4,2,3,3) 答案：c6．⽆向完全图k3的不同构的⽣成⼦图的个数为（）． (a) 6 (b)5(c) 4 (d) 3 答案：c7．n阶⽆向完全图kn中的边数为（）．(a)n(n?1)n(n?1)(b) (c) n (d)n(n+1) 22答案：b8．以下命题正确的是( )．(a) n(n?1)阶完全图kn都是欧拉图(b) n(n?1)阶完全图kn都是哈密顿图(c) 连通且满⾜m=n－1的图v,e(?v?=n,?e?=m)是树 (d) n(n?5)阶完全图kn都是平⾯图答案：c10．下列结论不正确是( )．(a) ⽆向连通图g是欧拉图的充分必要条件是g不含奇数度结点(b) ⽆向连通图g有欧拉路的充分必要条件是g最多有两个奇数度结点 (c) 有向连通图d是欧拉图的充分必要条件是d的每个结点的⼊度等于出度(d) 有向连通图d有有向欧拉路的充分必要条件是除两个结点外，每个结点的⼊度等1于出度答案：d11．⽆向完全图k4是（）．（a）欧拉图（b）哈密顿图（c）树答案：b12．有4个结点的⾮同构的⽆向树有 ( )个．(a) 2 (b) 3(c) 4(d) 5 答案：a13．设g是有n个结点，m条边的连通图，必须删去g的( )条边，才能确定g的⼀棵⽣成树．(a) m?n?1 (b) n?m (c) m?n?1 (d) n?m?1 答案：a14．设g是有6个结点的完全图，从g中删去( )条边，则得到树． (a) 6 (b) 9 (c) 10 (d) 15 答案：c⼆、填空题1．数组{1，2，3，4，4}是⼀个能构成⽆向简单图的度数序列，此命题的真值是 . 答案：02．⽆向完全图k3的所有⾮同构⽣成⼦图有个．答案：43．设图g??v,e?，其中?v??n,?e??m．则图g是树当且仅当g是连通的，且m?．答案：n－14．连通图g是欧拉图的充分必要条件是答案：图g⽆奇数度结点 5．连通⽆向图g有6个顶点9条边，从g中删去g的⼀棵⽣成树t．答案：46．⽆向图g为欧拉图，当且仅当g是连通的，且g中⽆答案：奇数度7．设图g??v,e?是简单图，若图中每对结点的度数之和，则g⼀定是哈密顿图．答案：?8．如图1所⽰带权图中最⼩⽣成树的权是．答案：12三、化简解答题1．设⽆向图g＝v,e，v={v1，v2，v3，v4，v5，v6}， e={( v1，v2), ( v2，v2), ( v4，v5), ( v3，v4), ( v1，v3),( v3，v1), ( v2，v4)}． (1) 画出图g的图形；2图15图22(2) 写出结点v2, v4，v6的度数； (3) 判断图g是简单图还是多重图．解：(1) 图g的图形如图5所⽰．(2) deg(v2)?4,deg(v4)?3,deg(v6)?0．(3) 图g是多重图．作图如图2. 2．设图g＝v，e，其中v＝{a,b,c,d,e}, e={(a,b),(b,c),(c,d), (a,e)}试作出图g的图形，并指出图g是简单图还是多重图？是连通图吗？说明理由.b e解：图g如图8所⽰．. 图g中既⽆环，也⽆平⾏边，是简单图． cd 图g是连通图．g中任意两点都连通.图3所以，图g有9个结点．作图如图3．四、计算题1．设简单连通⽆向图g有12条边，g中有2个1度结点，2个2度结点，3个4度结点，其余结点度数为3．求g中有多少个结点．试作⼀个满⾜该条件的简单⽆向图．解：设图g有x个结点，由握⼿定理2?1+2?2+3?4+3?（x?2?2?3）＝12?23x?24?21?18?27x＝9 故图g有9个结点．图4满⾜该条件的简单⽆向图如图4所⽰2．设图g(如图5表⽰)是6个结点a,b,c, d,e,f的图，试求，图g的最⼩⽣成树，并计算它的权．c 解：构造连通⽆圈的图，即最⼩⽣成树，⽤克鲁斯克尔算法：第⼀步：取ab＝1；第⼆步：取af=4第三步：取fe＝3；第四步：取ad=9图5 第五步：取bc=23如图6．权为1+4+3+9+23=403．⼀棵树t有两个2度顶点，1个3度顶点；3个4问它有⼏⽚树叶？解：设t有n顶点，则有n－1条边．t中有2个 2度顶点，1个3度顶点，3个4度顶点，其余n－2－1-3个1度顶点．五、证明题1．若⽆向图g中只有两个奇数度结点，则这两个结点⼀定是连通的．证：⽤反证法．设g中的两个奇数度结点分别为u和v．假若u和v不连通．即它们之间⽆任何通路，则g⾄少有两个连通分⽀g1，g2，且u和v分别属于g1和g2，于是g1和g2各含有⼀个奇数度结点．这与握⼿定理的推论⽭盾．因⽽u和v⼀定是连通的．3【篇⼆：离散数学图论练习题】题1、设g是⼀个哈密尔顿图，则g⼀定是()。

《失散数学》题库与答案一、选择或填空（数理逻辑部分）1、以下哪些公式为永真包括式？( A )(1) Q=>Q→P (2) Q=>P→Q (3)P=>P→Q (4) P (P Q)=>P答：在第三章里面有公式（1）是附加律，（ 4）能够由第二章的包括等值式求出（注意与吸取律差异）2、以下公式中哪些是永真式？()(1)( ┐P Q)→(Q→R) (2)P →(Q→Q) (3)(P Q)→P (4)P→(P Q)答：（ 2），（3），（4）可用包括等值式证明3、设有以下公式，请问哪几个是永真蕴涵式?()(1)P=>P Q (2) P Q=>P (3) P Q=>P Q(4)P (P →Q)=>Q (5)(P→Q)=>P (6)P (P Q)=>P答：（2）是第三章的化简律，（3）近似附加律，（4）是假言推理，（ 3），（5），（6）都可以用包括等值式来证明出是永真包括式4、公式x((A(x)B(y，x))z C(y ，z)) D(x) 中，自由变元是 ( )，拘束变元是 ( )。

答： x,y, x,z（察看定义在公式x A 和 x A 中，称x为指导变元，A为量词的辖域。

在x A 和 x A 的辖域中， x 的所有出现都称为拘束出现，即称x 为拘束变元， A 中不是拘束出现的其他变项则称为自由变元。

于是A(x)、B(y，x)和 z C(y ，z) 中 y 为自由变元， x 和 z 为拘束变元，在 D(x) 中 x 为自由变元）5、判断以下语句可否是命题。

若是，给出命题的真值。

()(1)北京是中华人民共和国的国都。

(2)陕西师大是一座工厂。

(3)你喜欢唱歌吗？(4)若 7+8＞18，则三角形有 4 条边。

(5)前进！(6)给我一杯水吧！答：（1）是，T（2）是，F（3）不是（4）是，T（5）不是（6）不是（命题必定满足是陈述句，不能够是疑问句也许祈使句。

《离散数学》题库及答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？()(1)Q=>Q→P(2)Q=>P→Q(3)P=>P→Q(4)P(PQ)=>P答：（1），（4）2、下列公式中哪些是永真式？()(1)(┐PQ)→(Q→R)(2)P→(Q→Q)(3)(PQ)→P(4)P→(PQ)答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式()(1)P=>PQ(2)PQ=>P(3)PQ=>PQ(4)P(P→Q)=>Q(5)(P→Q)=>P(6)P(PQ)=>P答：（2），（3），（4），（5），（6）4、公式某((A(某)B(y，某))zC(y，z))D(某)中，自由变元是(变元是()。

答：某,y,某,z5、判断下列语句是不是命题。

若是，给出命题的真值。

((1)北京是中华人民共和国的首都。

(2)陕西师大是一座工厂。

)，约束)(3)你喜欢唱歌吗？(4)若7+8＞18，则三角形有4条边。

(5)前进！(6)给我一杯水吧！答：（1）是，T（2）是，F（3）不是（4）是，T（5）不是（6）不是6、命题“存在一些人是大学生”的否定是()，而命题“所有的人都是要死的”的否定是()。

答：所有人都不是大学生，有些人不会死7、设P：我生病，Q：我去学校，则下列命题可符号化为()。

(1)只有在生病时，我才不去学校(2)若我生病，则我不去学校(3)当且仅当我生病时，我才不去学校(4)若我不生病，则我一定去学校答：（1）QP（2）PQ（3）PQ（4）PQ8、设个体域为整数集，则下列公式的意义是()。

(1)某y(某+y=0)(2)y某(某+y=0)答：（1）对任一整数某存在整数y满足某+y=0（2）存在整数y对任一整数某满足某+y=09、设全体域D是正整数集合，确定下列命题的真值：(1)某y(某y=y)()(2)某y(某+y=y)()(3)某y(某+y=某)()(4)某y(y=2某)()答：（1）F（2）F（3）F（4）T10、设谓词P(某)：某是奇数，Q(某)：某是偶数，谓词公式某(P(某)Q(某))在哪个个体域中为真()2(1)自然数(2)实数(3)复数(4)(1)--(3)均成立答：（1）11、命题“2是偶数或-3是负数”的否定是（）。

离散数学第5次作业参考答案一、(每问5分，共10分)设S Q Q =⨯，Q 是有理数集，*为S 上的二元运算，,,,a b x y S ∀<><>∈有：,*,,a b x y ax ay b <><>=<+>(1) *运算在S 上是否可交换、可结合？是否为幂等？ (2) *运算是否有单位元、零元？如果有，请指出，并求出S 中所有可逆元素的逆元。

. 解：(1) 因为,*,,a b x y ax ay b <><>=<+>， 而,*,,x y a b xa xb y <><>=<+>，所以，不具有交换律。

对任意的,,,,,a b x y w t S <><><>∈，有(,*,)*,,a b x y w t axw axt ay b <><><>=<++>，且 ,*(,*,),a b x y w t axw axt ay b <><><>=<++>。

因此，满足结合律。

因为2,*,,,a b a b a ab b a b <><>=<+>≠<>，所以不是幂等的。

(2)因为没有交换律，所以要求单位元，需要先求出左单位元，右单位元，当左单位元和右单位元相等的时候，那么就称为单位元。

零元也是一样，没有交换律，就要先求出左零元和右零元，如果左右零元相等，就叫做零元。

求零元：假设左零元为<a , b >.那么根据左零元的定义，对任意的,x y S <>∈，有,*,,,a b x y ax ay b a b ax a ay b b<><>=<+>=<>⇒=+=且，由于对任意的,x y <>都成立，所以左零元为0,,b b Q <>∈.但是,*0,0,x y b bx y <><>=<+>，对任意的,x y <>，显然0,0,bx y b <+>≠<>，因此，0,b <>不是右零元。

第五章习 题1． 解：4个顶点的所有非同构连通图如下图所示：2． 解：图G 是1-可着色的当且仅当G 是空图。

3． 解：(1)设w 为分图个数，由公式m ≤12(n −w )(n −w +1)知，w=3时，m ≤12(6−3)(6−3+1)=6。

所以分图个数w>2时，边数不能超过6条。

现在有7条边，所以分图个数不超过2。

(2)由一个孤立顶点和一个K n-1组成的图。

4． 解： 以所有二位三进制数作为顶点，在这顶点集{aa,ab,ac,ba,bb,bc,ca,cb,cc}中，若顶点u 的后一个字母与顶点v 的前一个字母相同，则u 到v 有一个弧。

这样所得图如下图所示，其中e 0=aaa,e 1=aab,e 2=aac,e 3=aba,e 4=abb,e 5=abc,e 6=aca,e 7=acb,e 8=acc,e 9=baa, e 10=bab,e 11=bac,e 12=bba,e 13=bbb,e 14=bbc,e 15=bca,e 16=bcb,e 17=bcc,e 18=caa,e 19=cab, e 20=cac,e 21=cba,e 22=cbb,e 23=cbc,e 24=cca,e 25=ccb,e 26=ccc 。

此图有一条欧拉回路:（e 0,e 1,e 3,e 11,e 7,e 21,e 10,e 4,e 14,e 16,e 22,e 13,e 12,e 9,e 2,e 8,e 26,e 25, e 23,e 15,e 20,e 6,e 19,e 5,e 17,e 24,e。

5． 解：(a) 邻接矩阵为A=[0 1 0 10 0 1 10 1 0 10 1 0 0]；(b) A (2)=[0 1 1 10 2 0 10 1 1 10 0 1 1]，A (3)=[0 2 1 20 1 2 20 2 1 20 2 0 1]，A (4)=[0 3 2 30 4 1 30 3 2 30 1 2 2];由A ，A (2)，A (3)，A (4)可知从v 1到v 4长度为1，2，3，4的路径分别为1，1，2，3条。