下载文档原格式
离散数学作业及答案2011-2012学年第⼀学期离散数学作业及参考答案---信息安全10级5-1 1.利⽤素因⼦分解法求2545与360的最⼤公约数。
解：掌握两点：(1) 如何进⾏素因⼦分解从最⼩素数2的素数去除n。
(2) 求最⼤公约数的⽅法gcd(a,b) = p1min(a1,b1)p2min(a2,b2)pn min(an,bn)360=23325150902545=2030515091gcd(2545,360) =2030515090=52.求487与468的最⼩公倍数。
解：掌握两点：(1) 如何进⾏素因⼦分解从最⼩素数2的素数去除n。
(2) 求最⼩公倍数的⽅法lcm(a,b) = p1max(a1,b1)p2max(a2,b2)pn max(an,bn)ab=gcd(a, b)﹡lcm (a, b)487是质数，因此gcd(487,468)=1lcm(487,468)= (487*468)/1=487*468=2279163.设n是正整数，证明：6|n(n+1)(2n+1)证明：⽤数学归纳法：归纳基础：当n=1时，n(n+1)(2n+1)=1*2*3=6，6|6归纳假设：假设当n=m时，6|m(m+1)(2m+1)归纳推导：当n=m+1时，n(n+1)(2n+1)=(m+1)(m+1+1)[2(m+1)+1]=(m+1)(m+2)(2m+3)= m(m+1)(2m+3)+2(m+1)(2m+3)= m(m+1)(2m+1+2)+2(m+1)(2m+3)= m(m+1)(2m+1)+2 m(m+1)+ 2(m+1)(2m+3)= m(m+1)(2m+1)+ 2(m+1)(m+2m+3)= m(m+1)(2m+1)+ 2(m+1)(3m+3)= m(m+1)(2m+1)+ 6(m+1)2因为由假设6|m(m+1)(2m+1)成⽴。
⽽6|6(m+1)2所以6|m(m+1)(2m+1)+ 6(m+1)2故当n=m+1时，命题亦成⽴。
华理离散数学试题及答案一、单项选择题（每题2分，共10分）1. 在离散数学中，以下哪个概念是用来描述两个集合之间元素的对应关系的？A. 函数B. 映射C. 序列D. 集合答案：A2. 命题逻辑中，以下哪个符号表示逻辑“与”？A. ∧B. ∨C. →D. ¬答案：A3. 集合{1, 2, 3}和{3, 4, 5}的交集是什么？A. {1, 2}B. {3, 4}C. {3}D. {1, 2, 3, 4, 5}答案：C4. 以下哪个图是无向图？A. 有向图B. 无向图C. 完全图D. 部分图答案：B5. 在图论中，一个图的度是指什么？A. 顶点的数量B. 边的数量C. 顶点的度数D. 图的连通性答案：C二、填空题（每题2分，共10分）1. 在集合论中，空集用符号____表示。
答案：∅2. 如果A和B是两个集合，那么A和B的并集用符号____表示。
答案：A∪B3. 逻辑运算中的否定运算符用符号____表示。
答案：¬4. 在图论中，如果一个图的任意两个顶点都可以通过路径相连，则称这个图为____图。
答案：连通5. 一个有n个顶点的完全图，其边的数量为____。
答案：\(\frac{n(n-1)}{2}\)三、简答题（每题5分，共20分）1. 请解释什么是二元关系，并给出一个例子。
答案：二元关系是集合A和集合B之间的一种对应关系，它由有序对(a, b)组成，其中a属于A，b属于B。
例如，如果A是人名集合，B是年龄集合，那么“小于”就是一个二元关系。
2. 什么是归纳推理？请给出一个简单的例子。
答案：归纳推理是一种从特殊到一般的推理方法，它通过观察一系列具体实例来推断出一个普遍的结论。
例如，观察到太阳每天从东方升起，我们归纳出“太阳每天都会从东方升起”。
3. 什么是图的生成树？请简述其特点。
答案：图的生成树是包含图中所有顶点的子图，并且是一个树。
它的特点是没有环，并且任意两个顶点之间有且仅有一条路径。
离散数学作业答案文档编制序号：[KK8UY-LL9IO69-TTO6M3-MTOL89-FTT688]离散数学作业5离散数学图论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。
本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。
要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月5日前完成并上交任课教师（不收电子稿）。
并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。
一、填空题1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ．2．设给定图G (如右由图所示)，则图G 的点割集是 {f,c}．3．设G 是一个图，结点集合为V ，边集合为E ，则G 的结点 度数之和 等于边数的两倍．4．无向图G 存在欧拉回路，当且仅当G 连通且 所有结点的度数全为偶数 ．5．设G=<V ，E >是具有n 个结点的简单图，若在G 中每一对结点度数之和大于等于n-1 ，则在G 中存在一条汉密尔顿回路．6．若图G=<V , E>中具有一条汉密尔顿回路，则对于结点集V 的每个非空子集S ，在G 中删除S 中的所有结点得到的连通分支数为W ，则S 中结点数|S|与W 满足的关系式为 S W ．7．设完全图K n 有n 个结点(n 2)，m 条边，当n 为奇数时，K n 中存在欧拉回路．8．结点数v 与边数e 满足 e= v －1 关系的无向连通图就是树． 9．设图G 是有6个结点的连通图，结点的总度数为18，则可从G 中删去4 条边后使之变成树．姓 名： 学 号： 得 分： 教师签名：10．设正则5叉树的树叶数为17，则分支数为i = 4 ． 二、判断说明题（判断下列各题，并说明理由．）1．如果图G 是无向图，且其结点度数均为偶数，则图G 存在一条欧拉回路．．答：不正确，图G 是无向图，当且仅当G 是连通，且所有结点度数均为偶数，这里不能确定图G 是否是连通的。
离散数学作业（解答必须手写体上传，否则酌情扣分）1．设命题公式为⌝Q∧（P→Q）→⌝P。
（1）求此命题公式的真值表；答：解（1）真值表如下P Q ⌝Q P→Q ⌝Q∧（P→Q）⌝P⌝Q∧（P→Q）→⌝P0 0 1 1 1 1 10 1 0 1 0 1 11 0 1 0 0 0 11 1 0 1 0 0 1（2）求此命题公式的析取范式；答：⌝（⌝Q∧（⌝P∨Q））∨⌝P ⇔Q∨⌝（⌝P∨Q）∨⌝P ⇔ Q∨P∧⌝Q∨⌝P ⇔ P∨ Q∧⌝Q∨⌝P⇔P ∨1∨⌝P⇔P ∨⌝P ∨1⇔1⇔（⌝P∧⌝Q）∨（⌝P∧Q）∨（P∧⌝Q）∨（P∧Q）（主析取范式）（3）判断该命题公式的类型。
答：该命题公式重言式2．用直接证法证明前提：P∨Q，P→R，Q→S结论：S∨R证 (1)P∨Q P(2)⌝P→Q T(1)E(3) Q→S P(4)⌝P→S T(2,3)I(5)⌝ S → P T(4)E(6) P→R P(7)⌝ S →R T(5,6)I(8) S∨R T(7)E3．在一阶逻辑中构造下面推理的证明每个喜欢步行的人都不喜欢坐汽车。
每个人或者喜欢坐汽车或者喜欢骑自行车。
有的人不喜欢骑自行车。
因而有的人不喜欢步行。
令F(x)：x喜欢步行。
G(x)：x喜欢坐汽车。
H(x)：x喜欢骑自行车。
解前提：∀x（F（x）→⌝ G（x）），∀x（G（x）∨H（x）），∃ x⌝ H（x）。
结论：∃ x ⌝F（x）。
证 (1)∃ x ⌝H（x） P(2)⌝H（c） ES(1)(3)∀x（G（x）∨H（x）） P(4) G（c）∨H（c） US(3)(5) G（c） T(2，4)I(6)∀x（F（x）→⌝ G（x）） P(7)F（c）→⌝ G（c） US(6)(8)⌝ F（c） T(5,7)I(9)（∃x）⌝ F（x） EG(8)4．用直接证法证明：前提：（∀x）（C（x）→W（x）∧R（x）），（∃x）（C（x）∧Q（x））结论：（∃x）（Q（x）∧R（x））。
离散数学大作业题目赋权图的最小生成树算法学院班级学生姓名学号指导老师赋权图的最小生成树算法摘要一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点并且有保持图联通的最少的边问题就是最小生成树问题。
许多应用问题都是一个求无向连通图的最小生成树问题。
例如寻找在城市之间铺设光缆的最好方案问题等等。
解决权值最小生成树问题的方法有很多种，如Prim 算法、Kruskal算法等等都是很好的方法。
本文中使用了kruskal算法（避圈法）实现寻找赋权图的最小生成树问题。
概述离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。
它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。
通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。
随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。
离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。
由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。
离散数学是传统的逻辑学，集合论（包括函数），数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数（包括代数系统，群、环、域等），布尔代数，计算模型（语言与自动机）等汇集起来的一门综合学科。
离散数学习题及解答作业题与解答第⼀章19 (2)、(4) 、(6)21 (1)、(2) 、(3)19、(2)解答: (p→┐p)→┐q 真值表如下:所以公式(p→┐q)→┐q 为可满⾜式19、(4)解答: (p→q)→(┐q→┐p) 真值表如下:所以公式(p→q)→(┐q→┐p)为永真式19、(6)解答: ((p→q)∧(q→r))→(p→r) 真值表如下:所以公式((p→q)∧(q→r))→(p→r)为永真式21、(1)解答: ┐(┐p∧q)∨┐r 真值表如下:所以成假赋值为:01121、(2)解答: (┐q∨r)∧(p→q)真值表如下:所以成假赋值为:010,100,101,11021、(3)解答: (p→q)∧(┐(p∧r)∨p)真值表如下:所以成假赋值为:100,101第⼆章5、(1) (2) (3) 6、(1) (2) (3) 7、(1) (2) 8、(1) (2) (3) 5、求下列公式的主析取范式,并求成真赋值(1) (┐p→q)→(┐q∨p)┐(┐p→q) ∨(┐q∨p)┐(┐(┐p) ∨q) ∨(┐q∨p)(┐p ∧┐q) ∨(┐q∨p)(┐p ∧┐q) ∨(p ∧┐q)∨(p ∧q)所以00，10，11 为成真赋值。
(2) (┐p→q)∧(q∧r)(┐┐p∨q)∧(q∧r)(p∨q)∧(q∧r)(p∧q∧r)∨(q∧r)(p∧q∧r)∨(p∧q∧r)∨(┐p∧q∧r)(p∧q∧r)∨(┐p∧q∧r)m3∨m 7，所以011，111 为成真赋值。
(3) (p∨(q∧r))→(p∨q∨r)┐(p∨(q∧r))∨(p∨q∨r)(┐p∧(┐q∨┐r))∨(p∨q∨r)(┐p∧┐q)∨(┐p∧┐r)∨(p∨q∨r)(┐p∧┐q)∨((┐p∧┐r)∨(p∨q∨r))(┐p∧┐q)∨((┐p∨p∨q∨r)∧(┐r∨p∨q∨r) )(┐p∧┐q)∨(1∧1)(┐p∧┐q)∨11m0∨m1∨m 2∨m3∨m4∨m5∨m 6 ∨m 7，所以000, 001, 010, 011, 100, 101, 110, 111 为成真赋值。
离散数学作业4离散数学图论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容重要分别是集合论部分、图论部分、数理逻辑部分旳综合练习，基本上是按照考试旳题型（除单项选择题外）安排练习题目，目旳是通过综合性书面作业，使同学自己检查学习成果，找出掌握旳微弱知识点，重点复习，争取尽快掌握。
本次形考书面作业是第二次作业，大家要认真及时地完毕图论部分旳综合练习作业。
一、填空题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=<V，E>是具有n个结点旳简朴图，若在G中每一对结点度数之和不小于等于n-1 ，则在G中存在一条汉密尔顿路．6．若图G=<V, E>中具有一条汉密尔顿回路，则对于结点集V旳每个非空子集S，在G中删除S中旳所有结点得到旳连通分支数为W，则S中结点数|S|与W满足旳关系式为W(G-V1) ≤∣V1∣．7．设完全图n个结点(n≥2)，m条边，当n为奇数时，存在欧拉回路．8．结点数v与边数e满足e=v-1 关系旳无向连通图就是树．9．设图G是有6个结点旳连通图，结点旳总度数为18，则可从G中删去4 条边后使之变成树．10．设正则5叉树旳树叶数为17，则分支数为i = 5 ．二、判断阐明题（判断下列各题，并阐明理由．）1．假如图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路．．(1) 不对旳，缺了一种条件，图G应当是连通图，可以找出一种反例，例如图G是一种有孤立结点旳图。
2．如下图所示旳图G存在一条欧拉回路．(2) 不对旳，图中有奇数度结点，因此不存在是欧拉回路。
3．如下图所示旳图G不是欧拉图而是汉密尔顿图．G解：对旳由于图中结点a，b，d，f旳度数都为奇数，因此不是欧拉图。
考生答题情况作业名称：2017年秋季网上作业1 出卷人：SA 作业总分：100 通过分数：60 起止时间：2017/12/11 23:43:18 至2017/12/12 0:17:07 学员姓名：学员成绩：85 标准题总分：100 标准题得分：85 详细信息：题号:1 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:下列语句中是命题的为（）. A、上帝是万能的么？！B、X = 3. C、如果2+3＝23，那么雪是蓝色的. D、敬礼！标准答案:C 学员答案:C 本题得分:5题号:2 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:下列图形中是平面图的是（）. A、B、C、.D、（彼得森）图标准答案:B 学员答案:B 本题得分:5题号:3 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:若完全图是图的一个子图，则图的色数至少应为（）. A、2 B、3 C、4 D、5 标准答案:B 学员答案:B 本题得分:5题号:4 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:已知集合上偏序关系，其中属于的序偶有（）. A、B、和C、D、标准答案:B 学员答案:B 本题得分:5题号:5 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:集合上的二元关系、，下列选项中唯一正确的是（）. A、如果、都是对称的，那么也是对称的B、如果、都是反对称的，那么也是反对称的C、如果、都是传递的，那么也是传递的D、如果、都是自反的，那么也是自反的标准答案:D 学员答案:D 本题得分:5题号:6 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:对有限连通平面图，则其边数、点数、面数必满足的是（）. A、B、C、D、标准答案:C 学员答案:C 本题得分:5题号:7 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:一棵树中的任意两点之间相连的通路条数必为（）. A、2 B、3 C、1 D、5 标准答案:C 学员答案:C 本题得分:5题号:8 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:交换群是只须同时满足（）等特征的独异点. A、存在生成元B、存在零元C、存在幺元D、可交换性且中每个元素都有逆元标准答案:D 学员答案:D 本题得分:5题号:9 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:设：我去看电影;：我有时间，将命题“我去看电影，仅当我有时间.” 符号化为（）. A、B、C、D、标准答案:A 学员答案:A 本题得分:5题号:10 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:已知上偏序关系对应的，则的子集的极小元为（）. A、4 B、2 C、1 D、3 标准答案:C 学员答案:B 本题得分:0题号:11 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:与命题公式唯一不等价的选项是（）. A、B、C、D、标准答案:C 学员答案:C 本题得分:5题号:12 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:下列各式中，为永假式的是（）. A、B、C、D、标准答案:C 学员答案:C 本题得分:5题号:13 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:对代数系统，下列四个论述中正确的只有（）. A、若存在零元，则零元是唯一的B、若存在左幺元，则左幺元必是唯一的C、若同时存在左、右幺元，则左、右幺元必相等D、若一个元素存在左逆元，则它一定也存在右逆元标准答案:A 学员答案:D 本题得分:0题号:14 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:集合，为上的一个二元关系，则下列命题中（）为真. A、不是自反的B、不是反自反的C、不是传递的D、不是对称的标准答案:B 学员答案:B 本题得分:5题号:15 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:前提，，，下的结论是（）. A、B、C、D、标准答案:C 学员答案:C 本题得分:5题号:16 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:集合的幂集的幂集是（）. A、B、C、D、标准答案:D 学员答案:D 本题得分:5题号:17 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:平面图的点数与边数一定满足的关系式为（）. A、B、C、标准答案:C 学员答案:C 本题得分:5题号:18 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:设是非空集合上的二元关系，则的对称闭包（）. A、B、C、D、标准答案:D 学员答案:B 本题得分:0题号:19 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:前提，下的结论是（）. A、B、C、D、标准答案:A 学员答案:A 本题得分:5题号:20 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:下列图形中不是汉密尔顿图的是（）. A、B、C、D、（彼得森）图E、标准答案:D 学员答案:D 本题得分:5。
