华东理工,离散数学作业

离散数学作业及答案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、“我正在说谎。

”是个悖论。

（ √ ）2、“如果天气好，那么我去放风筝。

”是个原子命题。

（ ⨯ ）3、“如果35>，那么小布什将连任美国总统。

”这个命题的真值为“T ”。

（ √ ）4、T Q P P Q ⇔∧⌝∧→)()(。

（ ⨯ ） 5、)()(Q P P P Q P ⌝→→⌝⇔→→ （ √ ） 6、Q P Q P ⌝∧⌝⇒→⌝)(（ ⨯ ） 7、)(R Q P ∨→⌝∧⌝是个命题公式。

（ ⨯ ） 8、)()()()(Q P Q P Q P Q P ∧⌝∨⌝∧⇔∧⌝∨⌝∧（ √ ）二、试把原子命题表示为R Q P ,,等，然后用符号形式写出下列命题。

1、你不能既要熊掌又要鱼；解：P ：你要熊掌，Q ：你要鱼，则有)(Q P ∧⌝； 2、仅当你走我将留下；解：P ：你走，Q ：我留下，则有P Q →；3、今晚8：00钟CCTV-6或者播放电影“飞侠小白龙”，或者播放“天下无贼”；解：P ：今晚8：00CCTV —6播放电影“飞侠小白龙”，Q ：今晚8：00CCTV —6播放电影“天下无贼”，则有Q P ∨；4、假如明天不下雨，我们就去森林公园烧烤，否则就在家里上网或者看书。

解：P ：明天下雨，Q ：我们去森林公元烧烤，R ：我们在家里上网，S ：我们在家里看书，则有))(()(S R P Q P ∨→∧→⌝；5、如果你来了，那么他唱不唱歌将视你是否伴奏而定。

解：P ：如果你来了，Q ：他唱歌，R ：你伴奏，则有)(R Q P ↔→三、化简以下各式1、)()(C B A C B A ⌝∧∧∨∧∧解：原式B A T B A C C B A ∧⇔∧∧⇔⌝∨∧∧⇔)()()(； 2、R P Q Q P ∧→⌝↔→⌝))()((解：原式R R T R P Q Q P ⇔∧⇔∧∨↔∨⇔))()((； 3、)()()(Q P Q P Q P ⌝∧⌝∨∧⌝∨∧解：原式)()())((Q P Q Q P Q P P ⌝∧⌝∨⇔⌝∧⌝∨∧⌝∨⇔Q P Q P Q Q P Q →⇔∨⌝⇔⌝∨∧⌝∨⇔)()(四、求下列命题公式的主析取范式、主合取范式1、)()(Q P Q P ⌝↔→⌝∨⌝；解：原式))()(()(P Q Q P Q P →⌝∧⌝→∨⌝∨⌝⌝⇔))()(())()(()(P Q Q P T P Q Q P Q P ∨∨⌝∨⌝⌝∧⇔∨∧⌝∨⌝∨⌝∨⌝⌝⇔ ∏⇔⇔∨⇔∨∨∧∨∨⇔∨∨∧⇔000)()())()(M Q P P Q Q P Q P P Q Q P∑⇔3,2,1即主析取范式、主合取范式分别为∏、∑3,2,12、))((P Q P P →∧→；解：原式T T T P Q P P P P Q P P ⇔∧⇔∨⌝∨⌝∧∨⌝⇔∨⌝∧∨⌝⇔)()())((∑⇔3,2,1,0即为主析取范式，且无主合取范式；3、)()(Q P P Q ∧⌝∧→；解：原式F F Q P P Q P Q Q P P Q ∨⇔∧⌝∧∨∧⌝∧⌝⇔∧⌝∧∨⌝⇔)()()()(∏⇔⇔3,2,1,0F 即为主合取范式，且无主析取范式。

离散数学大作业题目赋权图的最小生成树算法学院班级学生姓名学号指导老师赋权图的最小生成树算法摘要一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点并且有保持图联通的最少的边问题就是最小生成树问题。

许多应用问题都是一个求无向连通图的最小生成树问题。

例如寻找在城市之间铺设光缆的最好方案问题等等。

解决权值最小生成树问题的方法有很多种，如Prim 算法、Kruskal算法等等都是很好的方法。

本文中使用了kruskal算法（避圈法）实现寻找赋权图的最小生成树问题。

概述离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。

它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。

通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。

随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。

离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。

由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。

离散数学是传统的逻辑学，集合论（包括函数），数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数（包括代数系统，群、环、域等），布尔代数，计算模型（语言与自动机）等汇集起来的一门综合学科。

离散数学作业-离散数学专业班级学号姓名第一章命题逻辑的基本概念一、单选题1．下列语句中不是命题的有（）.a9+5？12b。

1+3=5c。

1g是我电脑的主频吗？d、我想努力学习。

2.以下陈述是正确的，命题是（）a.1+2=5当且仅当2是偶数b.如果1+2=3，则2是奇数c.如果1+2=5，则2是奇数d.你上网了吗？3.设命题公式?p()? （q？R），然后让公式取P，q和R的值，真值为1，这些值为(b)0,0,1(c)0,1,0(d)1,0,0（a） 0,0,04。

命题公式（P？Q）？Q是（）(a)矛盾式(b)仅可满足式(c)重言式(d)合取范式5.设p:我将去市里,q：我有时间．“我只有在有时间的时候才会去城里”这个命题被符号化为（）(a)q?p(b)p?q(c)p?q(d)?p??q6．设p：我听课,q：我看小说.“我不能一边听课，一边看小说”的符号为（）a.p??q；b.?p?q；c.?q??p；d.?(p?q)二、判断下列语句是否是命题，若是命题是复合命题则请将其符号化（1）中国有四大发明。

（2）2是有理数。

（3）“请进！”（4）刘红和魏欣是同学。

（5） a+b（6）如果买不到飞机票，我哪儿也不去。

（8）侈而惰者贫，而力而俭者富。

（韩非：《韩非子?显学》）（9）火星上有生命。

（10）这朵玫瑰多美啊！二、将下列命题符号化，其中p:2<1,q:3<2（1）只要2<1，就有3<2。

（2）如果2<1，则3?2。

（3）只有2<1，才有3?2。

（4）除非2<1，才有3?2。

（5）除非2<1，否则3?2。

（6）2<1仅当3<2。

-1-离散数学专业班级学号姓名三、将下列命题符号化（1）小李只能从篮子里拿一个苹果或一个梨。

（2）王东出生于1992年或1993年。

四、设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。

（1）p∨(q∧r)（2）（p?r）∧(q∨s)（3）（？p∧?Q∧r） ?？（p∧Q∧r）（4）r∧（s）→（p∧?q）五、用真值表判断下列公式的类型：(1)p∧(p→q)∧(p→?q)(2)(p∧r)?(?p∧?q)(2)((p→q)∧(q→r))→(p→r)-2--离散数学专业班级学号姓名第二章命题逻辑等值演算一、填空（1）给定两个命题公式a，b，若，则称a和b时等值的，记作a?b．（2）德摩根定律是：。