离散数学教程与范例

有101个人参加乒乓球淘汰赛（每一轮比赛在参加人数是奇数时，让一人轮空），共需进行多少场比赛方可决出优胜者（一场比赛指两人的一次对垒）@淘汰赛解（一）第一轮50场，剩50名优胜者1名轮空第二轮25场，剩25名优胜者1名轮空第三轮13场，剩13名优胜者第四轮6场，剩6名优胜者1名轮空第五轮3场，剩3名优胜者1名轮空第六轮2场，剩2名优胜者第七轮1场，剩1名优胜者共计50+25+13+6+3+2+1=100场解（二）用一一对应技术一场比赛对应一个被淘汰者，反之也真，那么比赛场数与被淘汰者人数是相等的。由于优胜者只有一人，全部被淘汰者是100人，因此要进行100场比赛方可决出优胜者。土耳其商人和帽子的故事这是著名物理学家爱因斯坦出过的一道题。一个土耳其商人，想找一个十分聪明的助手协助他经商，有两个人前来应聘，这个商人为了试一试哪一个聪明些，就把两个人带进一间漆黑的屋子里，他打开电灯后：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的。现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在头上，在我开灯后，请你们尽快的说出自己头上戴的帽子是什么颜色的。”说完之后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把电灯打开，这时，那两个有应试者看到商人头上戴的是一顶红帽子，过了一会儿，其中一个人便喊到：“我戴的是黑帽子。”请问这个人猜得对吗？是怎么推导出来的？聪明的囚徒古希腊有个国王，对处死囚徒的方法作了两种规定：一种是砍头，一种是绞刑。并他自恃聪明的做出一种规定：囚徒可以说一句话，并且这句话是马上可以验证其真假。如果囚徒说的是真话，那么处以绞刑，如果囚徒说的是假话，那么处以砍头。许多囚徒或者是因为说了假话而被砍头或者因为说了真话而被处以绞刑。有一位极其聪明的囚徒，当轮到他来选择处死方法时，他说出一句巧妙的话，结果使这个国王按照哪种方法处死他，都违背自己的决定，只得将他放了。试问：这囚徒说的是句什么话？哥尼斯堡城位于普雷格尔河畔，河中有两个岛，七座桥使两个河心岛及两岸彼此相连。十八世纪的城中居民热衷于这样一个问题：游人从四块陆地中的任何一地出发，能否找到一条路线，通过每桥一次且仅一次，最后返回原地？七桥问题欧拉对七桥问题的解1736年，著名数学家欧拉研究了七桥问题，他将这个问题用结点和弧边组成的图来表示，问题归结为从图中任一结点出发，经过每边一次且仅一次的回路是否存在？他找到了存在这样一条回路的充分必要条件，并由此判断七桥问题无解而结束了哥尼斯堡城民的烦恼。同构任何一張平面地圖，如果相鄰的兩個國家，必須塗上不同的顏色以便劃清邊界，則至多只要四種顏色就搞定了，不管這張地圖有多麼奇特複雜。四色问题發現者這是在西元1852年，由畢業於英國倫敦大學的弗朗西斯(FrancisGuthrie)發現的。當時他正在畫英國各郡的地圖，而發現了這個有趣的現象。格里斯覺得這其中一定有什麼奧妙，於是便寫信告訴他那數學很好的哥哥佛德雷克(FrederickGuthrie)。佛德雷克百思不得其解，又求教於他的老師----數學家摩根(Morgan)。摩根也無法確定這個說法對不對，於是又寫信給他的好朋友哈彌爾頓(Hamilton)，希望他要嘛就證明出這個說法是正確的，要不就舉一個反例，建構出一張需要5種顏色的地圖來。大師級的哈彌爾頓耗了13年心血，仍一籌莫展，抱憾而逝。公開徵答1878年，英國數學家Cayley將上述問題曝光取名為「四色猜想」(因為還不確定對不對，所以說是猜想)，公開徵求解答。問題一傳出後，馬上就有了回應。1879年和1880年，Kempe和Tait分別發表論文證明了四色問題。轟動一時的熱度終於平息。不料事隔11年後，一個名叫Heawood的年輕人指出了Kempe證明中的錯誤，並利用Kempe的方法證明出若用5種顏色就保證一定能區分出地圖上相鄰的區域。雖然四色問題未被破解，但是至此算是邁出了一大步。而另一方面，Tait的論文亦被陸陸續續發現多處錯誤，甚至最後一個錯誤是一直到1946年才被發現的。從這裡我們可看出這些人的研究精神是多麼可敬，被發現錯誤的東西並未被棄之如敝屣般丟在一旁，仍舊不斷有人去研究它，甚至是在事隔半個多世紀之後。當然這兩篇錯誤的論文在數學上仍然有其貢獻，不可小覷。解題花絮一番風風雨雨下來，四色問題更加受到矚目了。由於Heawood的「五色定理」的證明並不難，因此就有許多人也小看了「四色問題」的難度。最有趣的是以下這個例子。1902年秋天，閔可夫斯基教授(HermannMinkowsky，1864-1909，愛因斯坦的數學導師)在上拓樸學的課堂上就當著學生面前說：「四色問題之所以尚未被解決是因為世界上第一流的數學家都還沒空去研究它。」而且興之所至，當場就證了起來；但是寫了好幾個黑板，卻依舊未能得證。接下來幾個星期的課，他繼續證下去，課一堂一堂地過去了，他如身陷泥沼，仍舊無法證明出來。他終於投降，承認自己也無能為力了。就在這個時候，天空正好霹靂一聲巨響，他感嘆地說：「上帝在責備我的狂妄！」然後就繼續上他的拓樸課了。离散数学是现代数学的一个重要分支，是计算机科学与技术的基础理论的核心课程之一。离散数学与计算机科学中的数据结构、操作系统、编译理论、算法分析、逻辑设计、系统结构、机器定理证明等课程息息相关。基本内容包括数理逻辑、集合论、代数系统、图论等几大部分。绪言离散数学离散数学(DiscreteMathematics)：研究离散结构的数学分科。--《辞海》79年版,P355用一组基本的指令来编制一个计算机程序，非常类似于从一组公理来构造一个数学证明。--D.E.Knuth(克纽斯)1974年Turing奖获得者。离散数学左孝凌等上海科技文献出版社离散数学耿素云等清华大学出版社离散数学方世昌主编西安电子科大出版社DiscreteMathematicsStructuresBemardKolmanRobertC.BusbySharonRossPrentice-HallInternational,Inc.1997.11(英文原版影印)清华大学出版社参考书目离散数学是培养抽象思维和逻辑推理的学科，因此要重视基本概念的学习，一定要认真研读教材，特别要从实例和习题中搞清众多概念的涵义。适当多做习题，至少要按时完成作业，强迫自己通过特定条件下运用所学的概念和理论，才能真正掌握和理解它们，提高分析和解决问题的能力。与教材配套的习题解答是离散数学的初学者必备的参考书，钻研习题解答，从中领会典型问题的解题方法。不会求解的作业题，可以看习题解答，但务求读懂，决不可一抄了事，养成依赖习惯，白白浪费宝贵的时光！学习方法建议手机（关机）作业（及时）考试（改革）约法三章2020/6/14第一篇预备知识第2章计数问题2020/6/142.0内容提要容斥原理与鸽笼原理3离散概率4乘法原理和加法原理1排列与组合2递归关系5电子科技大学离散数学课程组——国家精品课程离散数学电子科技大学计算机科学与工程学院示范性软件学院2020年6月14日星期日2020/6/142.1本章学习要求重点掌握一般掌握了解11乘法原理和加法原理2排列组合的计算3利用容斥原理计算有限集合的交与并31离散概率2离散概念的计算公式及性质21鸽笼原理2鸽笼原理的简单应用3递归关系4递归关系的建立和计算2020/6/14表2.2.1开胃食品主食饮料种类价格(元)种类价格种类价格玉米片(Co)2.15汉堡(H)3.25茶水(T)0.70色拉(Sa)1.90三明治(S)3.65牛奶(M)0.85鱼排(F)3.15可乐(C)0.75啤酒(B)0.752020/6/142.2.1乘法原理如果一些工作需要t步完成，第一步有n1种不同的选择，第二步有n2种不同的选择，…，第t步有nt种不同的选择，那么完成这项工作所有可能的选择种数为：tnnn212020/6/14例2.2.2Melissa病毒1990年，一种名叫Melissa的病毒利用侵吞系统资源的方法来破坏计算机系统，通过以含恶意宏的字处理文档为附件的电子邮件传播。当字处理文档被打开时，宏从用户的地址本中找出前50个地址，并将病毒转发给他们。用户接收到这些被转发的附件并将字处理文档打开后，病毒会自动继续转发，不断往复扩散。病毒非常快速地转发邮件，将被转发的邮件临时存储在某个磁盘上，当磁盘占满后，系统将会死锁甚至崩溃。问经过四次转发，共有多少个接收者？解根据Melissa病毒的扩散原理，经过四次转发，共有50×50×50×50+50×50×50+50×50+50+1=6377551个接收者。2020/6/14例2.2.3在一幅数字图像中，若每个像素点用8位进行编码，问每个点有多少种不同的取值。分析用8位进行编码可分为8个步骤：选择第一位，选择第二位，…，选择第八位。每一个位有两种选择，故根据乘法原理，8位编码共有2×2×2×2×2×2×2×2=28=256种取值。解每个点有256(=28)种不同的取值。2020/6/142.2.2加法原理假定X1,X2,…,Xt均为集合，第i个集合Xi有ni个元素。如{X1,X2,…,Xt}为两两不相交的集合，则可以从X1,X2,…,Xt中选出的元素总数为：n1+n2+…+nt。即集合X1∪X2∪…∪Xt含有n1+n2+…+nt个元素。2020/6/14例2.2.4由Alice、Ben、Connie、Dolph、Egbert和Francisco六个人组成的委员会，要选出一个主席、一个秘书和一个出纳员。（1）共有多少种选法？（2）若主席必须从Alice和Ben种选出，共有多少种选法？（3）若Egbert必须有职位，共有多少种选法？（4）若Dolph和Francisco都有职位，共有多少种选法？2020/6/14例2.2.4解（1）根据乘法原理，可能的选法种数为6×5×4=120；（2）[法一]根据题意，确定职位可分为3个步骤：确定主席有2种选择；主席选定后，秘书有5个人选；主席和秘书都选定后，出纳有4个人选。根据乘法原理，可能的选法种数为2×5×4=40；2020/6/14例2.2.4解(续)[法二]若Alice被选为主席，共有5×4=20种方法确定其他职位；若Ben为主席，同样有20种方法确定其他职位。由于两种选法得到的集合不相交，所以根据加法原理，共有20＋20=40种选法；2020/6/14例2.2.4解(续)(3)[法一]将确定职位分为3步：确定Egbert的职位,有3种方法；确定余下的较高职位人选,有5个人选；确定最后一个职位的人选,有4个人选。根据乘法原理，共有3×5×4=60种选法；2020/6/14例2.2.4解(续)[法二]根据(1)的结论，如果Egbert为主席，有20种方法确定余下的职位；若Egbert为秘书，有20种方法确定余下的职位；若Egbert为出纳员，也有20种方法确定余下的职位。由于三种选法得到的集合不相交，根据加法原理，共有20＋20＋20=60种选法；2020/6/14例2.2.4解(续)（4）将给Dolph、Francisco和另一个人指定职位分为3步：给Dolph指定职位，有3个职位可选；给Francisco指定职位，有2个职位可选；确定最后一个职位的人选，有4个人选。根据乘法原理，共有3×2×4=24种选法。2020/6/142.3排列与组合Zeke、Yung、Xeno和Wilma四个候选人竞选同一职位。为了使选票上人名的次序不对投票者产生影响，有必要将每一种可能的人名次序打印在选票上。会有多少种不同的选票呢？从某个集合中有序的选取若干个元素的问题，称为排列问题。2020/6/142.3.1排列问题定义2.3.1从含n个不同元素的集合S中有序选取的r个元素叫做S的一个r-排列，不同的排列总数记为P(n,r)。如果r=n，则称这个排列为S的一个全排列，简称为S的排列。显然，当rn时，P(n,r)=0。2020/6/14例2.3.1从含3个不同元素的集合S中有序选取2个元素的排列总数