(完整PPT)离散数学教程与范例课件.ppt

1、 有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人，因此要进

2、行100场比赛方可决出优胜者。土耳其商人和帽子的故事这是著名物理学家爱因斯坦出过的一道题。一个土耳其商人，想找一个十分聪明的助手协助他经商，有两个人前来应聘，这个商人为了试一试哪一个聪明些，就把两个人带进一间漆黑的屋子里，他打开电灯后：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的。现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在头上，在我开灯后，请你们尽快的说出自己头上戴的帽子是什么颜色的。”说完之后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把电灯打开，这时，那两个有应试者看到商人头上戴的是一顶红帽子，过了一会儿，其

3、中一个人便喊到：“我戴的是黑帽子。”请问这个人猜得对吗？是怎么推导出来的？聪明的囚徒古希腊有个国王，对处死囚徒的方法作了两种规定：一种是砍头，一种是绞刑。并他自恃聪明的做出一种规定：囚徒可以说一句话，并且这句话是马上可以验证其真假。如果囚徒说的是真话，那么处以绞刑，如果囚徒说的是假话，那么处以砍头。许多囚徒或者是因为说了假话而被砍头或者因为说了真话而被处以绞刑。有一位极其聪明的囚徒，当轮到他来选择处死方法时，他说出一句巧妙的话，结果使这个国王按照哪种方法处死他，都违背自己的决定，只得将他放了。试问：这囚徒说的是句什么话？哥尼斯堡城位于普雷格尔河畔，河中有两个岛，七哥尼斯堡城位于普雷格尔河畔，河

4、中有两个岛，七座桥使两个河心岛及两岸彼此相连。十八世纪的城中居座桥使两个河心岛及两岸彼此相连。十八世纪的城中居民热衷于这样一个问题：民热衷于这样一个问题：游人从四块陆地中的任何一地出发，能否找到一条路线，通过每桥一次且仅一次，最后返回原地？七桥问题欧拉对七桥问题的解欧拉对七桥问题的解 17361736年，著名数学家欧拉研究了七桥问题，他将这个年，著名数学家欧拉研究了七桥问题，他将这个问题用问题用结点结点和弧和弧边边组成的组成的图图来表示，问题归结为从图来表示，问题归结为从图中任一结点出发，中任一结点出发，经过每边一次且仅一次的回路经过每边一次且仅一次的回路是否是否存在？他找到了存在这样一条回路

5、的充分必要条件，存在？他找到了存在这样一条回路的充分必要条件，并由此判断并由此判断七桥问题无解而结束了而结束了哥尼斯堡城民的烦哥尼斯堡城民的烦恼。恼。同构同构 任何一張平面地圖，如果相鄰的兩個國家，必須塗上不同的顏色以便劃清邊界，則至多只要四種顏色就搞定了，不管這張地圖有多麼奇特複雜。四色问题發現者 這是在西元1852年，由畢業於英國倫敦大學的弗朗西斯(Francis Guthrie)發現的。當時他正在畫英國各郡的地圖，而發現了這個有趣的現象。格里斯覺得這其中一定有什麼奧妙，於是便寫信告訴他那數學很好的哥哥佛德雷克(Frederick Guthrie)。佛德雷克百思不得其解，又求教於他的老師-

6、數學家摩根(Morgan)。摩根也無法確定這個說法對不對，於是又寫信給他的好朋友哈彌爾頓(Hamilton)，希望他要嘛就證明出這個說法是正確的，要不就舉一個反例，建構出一張需要5 種顏色的地圖來。大師級的哈彌爾頓耗了13年心血，仍一籌莫展，抱憾而逝。公開徵答 1878年，英國數學家Cayley 將上述問題曝光取名為四色猜想(因為還不確定對不對，所以說是猜想)，公開徵求解答。問題一傳出後，馬上就有了回應。1879年和1880年，Kempe 和Tait 分別發表論文證明了四色問題。轟動一時的熱度終於平息。不料事隔11年後，一個名叫Heawood 的年輕人指出了Kempe 證明中的錯誤，並利用Ke

7、mpe 的方法證明出若用5 種顏色就保證一定能區分出地圖上相鄰的區域。雖然四色問題未被破解，但是至此算是邁出了一大步。而另一方面，Tait 的論文亦被陸陸續續發現多處錯誤，甚至最後一個錯誤是一直到1946年才被發現的。從這裡我們可看出這些人的研究精神是多麼可敬，被發現錯誤的東西並未被棄之如敝屣般丟在一旁，仍舊不斷有人去研究它，甚至是在事隔半個多世紀之後。當然這兩篇錯誤的論文在數學上仍然有其貢獻，不可小覷。解題花絮 一番風風雨雨下來，四色問題更加受到矚目了。由於Heawood 的五色定理的證明並不難，因此就有許多人也小看了四色問題的難度。最有趣的是以下這個例子。1902年秋天，閔可夫斯基教授(H

8、ermann Minkowsky，1864-1909，愛因斯坦的數學導師)在上拓樸學的課堂上就當著學生面前說：四色問題之所以尚未被解決是因為世界上第一流的數學家都還沒空去研究它。而且興之所至，當場就證了起來；但是寫了好幾個黑板，卻依舊未能得證。接下來幾個星期的課，他繼續證下去，課一堂一堂地過去了，他如身陷泥沼，仍舊無法證明出來。他終於投降，承認自己也無能為力了。就在這個時候，天空正好霹靂一聲巨響，他感嘆地說：上帝在責備我的狂妄！然後就繼續上他的拓樸課了。离散数学是现代数学的一个重要离散数学是现代数学的一个重要分支，是计算机科学与技术的基分支，是计算机科学与技术的基础理论的核心课程之一。离散数础

9、理论的核心课程之一。离散数学与计算机科学中的数据结构、学与计算机科学中的数据结构、操作系统、编译理论、算法分析、操作系统、编译理论、算法分析、逻辑设计、系统结构、机器定理逻辑设计、系统结构、机器定理证明等课程息息相关。证明等课程息息相关。基本内容包括数理逻辑、集合论、基本内容包括数理逻辑、集合论、代数系统、图论等几大部分。代数系统、图论等几大部分。绪绪言言离散数学 离散数学(Discrete Mathematics)：研究离散结构的数学分科。-辞海79年版,P355用一组基本的指令来编制一个计算机程序，非常类似于从一组公理来构造一个数学证明。-D.E.Knuth(克纽斯)1974年Turing

10、奖获得者。离散数学离散数学 左孝凌等左孝凌等 上海科技文献出版社上海科技文献出版社离散数学离散数学 耿素云等耿素云等 清华大学出版社清华大学出版社离散数学离散数学 方世昌主编方世昌主编 西安电子科大出版社西安电子科大出版社Discrete Mathematics Structures Bemard Kolman Robert C.Busby Sharon Ross Prentice-Hall International,Inc.1997.11 (英文原版影印英文原版影印)清华大学出版社清华大学出版社参参考考书书目目离散数学是培养抽象思维和逻辑推理的学科，因此要重视基本概念的学习，一定要认真研读

11、教材，特别要从实例和习题中搞清众多概念的涵义。适当多做习题，至少要按时完成作业，强迫自己通过特定条件下运用所学的概念和理论，才能真正掌握和理解它们，提高分析和解决问题的能力。与教材配套的习题解答是离散数学的初学者必备的参考书，钻研习题解答，从中领会典型问题的解题方法。不会求解的作业题，可以看习题解答，但务求读懂，决不可一抄了事，养成依赖习惯，白白浪费宝贵的时光！学学习习方方法法建建议议手机（关机）手机（关机）作业（及时）作业（及时）考试（改革）考试（改革）约约法法三三章章2022-7-302022-7-30第一篇 预备知识第2章 计数问题2022-7-302022-7-302.0 内容提要容斥

12、原理与鸽笼原理容斥原理与鸽笼原理3离散概率离散概率4乘法原理和加法原理乘法原理和加法原理1排列与组合排列与组合2递归关系递归关系5电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程离离 散散 数数 学学电子科技大学电子科技大学计算机科学与工程学院计算机科学与工程学院示示 范范 性性 软软 件件 学学 院院20222022年年7 7月月3030日星期六日星期六2022-7-302022-7-302.1 本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1乘法原理和加乘法原理和加法原理法原理2 2排列组合的计排列组合的计算算 3 3利用容斥原理利用容斥原理计算有限

13、集合的计算有限集合的交与并交与并 31 1 离散概率离散概率2 2 离散概念的计离散概念的计 算公式及性质算公式及性质 21 1 鸽笼原理鸽笼原理2 2 鸽笼原理的简鸽笼原理的简单应用单应用3 3 递归关系递归关系4 4 递归关系的建递归关系的建立和计算立和计算 2022-7-302022-7-30表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.752022-7-302022-7-302.2.1 乘法原理 如果一些工作需

14、要t步完成，第一步有n1种不同的选择，第二步有n2种不同的选择，第t步有nt种不同的选择，那么完成这项工作所有可能的选择种数为：tnnn212022-7-302022-7-30例2.2.2 Melissa病毒1990年，一种名叫Melissa的病毒利用侵吞系统资源的方法来破坏计算机系统，通过以含恶意宏的字处理文档为附件的电子邮件传播。当字处理文档被打开时，宏从用户的地址本中找出前50个地址，并将病毒转发给他们。用户接收到这些被转发的附件并将字处理文档打开后，病毒会自动继续转发，不断往复扩散。病毒非常快速地转发邮件，将被转发的邮件临时存储在某个磁盘上，当磁盘占满后，系统将会死锁甚至崩溃。问经过四

15、次转发，共有多少个接收者？解解 根据根据MelissaMelissa病毒的扩散原理，经过四次转发，病毒的扩散原理，经过四次转发，共有共有50505050505050+5050+50505050+5050+5050+50+150+50+1=6377551=6377551个接收者。个接收者。2022-7-302022-7-30例2.2.3在一幅数字图像中，若每个像素点用8位进行编码，问每个点有多少种不同的取值。分析 用8位进行编码可分为8个步骤：选择第一位，选择第二位，选择第八位。每一个位有两种选择，故根据乘法原理，8位编码共有22222222=28=256种取值。解 每个点有256(=28)种不

16、同的取值。2022-7-302022-7-302.2.2 加法原理 假定X1,X2,Xt均为集合，第i个集合Xi有ni个元素。如X1,X2,Xt为两两不相交的集合，则可以从X1,X2,Xt中选出的元素总数为：n1+n2+nt。2022-7-302022-7-30例2.2.4由Alice、Ben、Connie、Dolph、Egbert和Francisco六个人组成的委员会，要选出一个主席、一个秘书和一个出纳员。（1）共有多少种选法？（2）若主席必须从Alice和Ben种选出，共有多少种选法？（3）若Egbert必须有职位，共有多少种选法？（4）若Dolph和Francisco都有职位，共有多少种

17、选法？2022-7-302022-7-30例2.2.4 解（1）根据乘法原理，可能的选法种数为654=120；（2）法一 根据题意，确定职位可分为3个步骤：确定主席有2种选择；主席选定后，秘书有5个人选；主席和秘书都选定后，出纳有4个人选。根据乘法原理，可能的选法种数为254=40；2022-7-302022-7-30例2.2.4 解(续)法二 若Alice被选为主席，共有54=20种方法确定其他职位；若Ben为主席，同样有20种方法确定其他职位。由于两种选法得到的集合不相交，所以根据加法原理，共有2020=40种选法；2022-7-302022-7-30例2.2.4 解(续)(3)法一 将确

18、定职位分为3步：确定Egbert的职位,有3种方法；确定余下的较高职位人选,有5个人选；确定最后一个职位的人选,有4个人选。根据乘法原理，共有354=60种选法；2022-7-302022-7-30例2.2.4 解(续)法二 根据(1)的结论，如果Egbert为主席，有20种方法确定余下的职位；若Egbert为秘书，有20种方法确定余下的职位；若Egbert为出纳员，也有20种方法确定余下的职位。由于三种选法得到的集合不相交，根据加法原理，共有202020=60种选法；2022-7-302022-7-30例2.2.4 解(续)（4）将给Dolph、Francisco和另一个人指定职位分为3步：

19、给Dolph指定职位，有3个职位可选；给Francisco指定职位，有2个职位可选；确定最后一个职位的人选，有4个人选。根据乘法原理，共有324=24种选法。2022-7-302022-7-302.3 排列与组合 Zeke、Yung、Xeno和Wilma四个候选人竞选同一职位。为了使选票上人名的次序不对投票者产生影响，有必要将每一种可能的人名次序打印在选票上。会有多少种不同的选票呢？从某个集合中有序的选取若干个元素的问题，称为排列问题。2022-7-302022-7-302.3.1 排列问题定义2.3.1 从含n个不同元素的集合S中有序选取的r个元素叫做S的一个，不同的排列总数记为P(n,r)

20、。如果r=n，则称这个排列为S的一个，简称为S的排列。显然，2022-7-302022-7-30例2.3.1从含3个不同元素的集合S中有序选取2个元素的排列总数。解 从含3个元素的不同集合S中有序选取2个元素的排列总数为6种。如果将这3个元素记为A、B和C，则6个排列为AB,AC,BA,BC,CB,CA。2022-7-302022-7-30定理2.3.1对满足rn的正整数n和r有P(n,r)n(n1)(n(r1)第r位第第r-1r-1位位第第3 3位位第第2 2位位第第1 1位位nn-1n-2 n-(r-2)图2.3.1n-(r-1)n-(r-1)2022-7-302022-7-30推论2.3

21、.2n个不同元素的排列共有n！种，其中 n!n(n1)2 12022-7-302022-7-30例2.3.2 A,B,C,D,E,F组成的排列中，（1）有多少含有DEF的子串？（2）三个字母D、E和F相连的有多少种？解(1)将DEF看成一个对象，根据推论2.3.2，满足条件的排列为A,B,C,DEF的全排列，共有4！=24种；（2）根据题意，满足该条件的排列分为两步：第一步确定D,E和F三个字母的全排列，有3！种排列，第二步将已排序的D,E和F看成一个整体，与A,B和C共4个元素构造出A,B,C,D,E,F的全排列，有4！种排列。又根据乘法原理，满足条件的排列总数有3！4！=144。2022-

22、7-302022-7-30例2.3.36个人围坐在圆桌上，有多少种不同的坐法？通过转圈得到的坐法视为同一种坐法。解 6个人围坐在圆桌上，有120种不同的坐法。图图2.3.2AEFBDC2022-7-302022-7-30定理2.3.3含n个不同元素的集合的环形r-排列数Pc(n,r)是 。(2.3.3)cP(n,r)n!P(n,r)=rr(nr)!2022-7-302022-7-30例2.3.4求满足下列条件的排列数。(1)10个男孩和5个女孩站成一排，无两个女孩相邻。(2)10个男孩和5个女孩站成一圆圈，无两个女孩相邻.解(1)根据推论2.3.2，10个男孩的全排列为10!，5个女孩插入到1

23、0个男孩形成的11个空格中的插入方法数为P(11,5)。根据乘法原理，10个男孩和5个女孩站成一排，没有两个女孩相邻的排列数为：10!P(11,5)=（10!11!)/6!。2022-7-302022-7-30例2.3.4 解（续）（2）根据定理2.3.3，10个男孩站成一个圆圈的环排列数为9！，5个女孩插入到10男孩形成的10个空中的插入方法数为P(10,5)。根据乘法原理，10个男孩和5个女孩站成一个圆圈，没有两个女孩相邻的排列法为：2022-7-302022-7-302.3.2 组合问题定义2.3.2 从含有n个不同元素的集合S中无序选取的r个元素叫做S的一个r-组合，不同的组合总数记为

24、C(n,r)。2022-7-302022-7-30定理2.3.4对满足0m)个鸽笼，则存在一个鸽笼至少住进 +1只鸽子。这里，表示小于等于x的最大整数。mn1x 2022-7-302022-7-30例2.4.6如果一个图书馆里30本离散数学书共有12003页，那么必然有一本离散数学书至少有401页。证明 设页是鸽子，离散数学书是鸽笼，把每页分配到它所出现的离散数学书中，根据定理2.4.5，则存在一个鸽笼至少住进即结论得证。401130/)112003(2022-7-302022-7-302.5 离散概率简介概率(Probability)是17世纪为分析博弈游戏而发展起来的学科，最初计算概率仅有

25、计数一种方法。本节主要介绍离散概率的基本概率、基本性质和概率计算的简单例子。2022-7-302022-7-302.5.1 基本概念问题：掷出一个各面同性的骰子，求掷出偶数的概率。其中“各面同性”是指当骰子掷出时，各个面出现的机会均等。定义2.5.1 能生成结果的过程称为实验(experiment)；实验的结果或结果的组合称为事件(event)，包含所有可能结果的事件称为样本空间(sample space)。假如骰子的六个面分别标记为假如骰子的六个面分别标记为1,2,3,4,5,61,2,3,4,5,6，当掷出一个骰子时，一定能掷出当掷出一个骰子时，一定能掷出6 6种结果中的一种，种结果中的一

26、种，我们称我们称掷出骰子的过程为掷出骰子的过程为，掷出的结果掷出的结果(假如假如掷出掷出2)2)或或结果的组合结果的组合(假如掷出两个骰子，一个掷假如掷出两个骰子，一个掷出出1 1，一个掷出，一个掷出3)3)称为称为，当掷出一个骰子时得当掷出一个骰子时得到的到的6 6种可能种可能1,2,3,4,5,61,2,3,4,5,6称为称为。2022-7-302022-7-30例2.5.1请举例说明下列实验可能发生的事件，并列出其样本空间。（1）掷出一个六个面的骰子；（2）从1000个微处理器中随机抽取5个；（3）在北京人民医院选取一个婴儿。2022-7-302022-7-30例2.5.1 可能发生的事

27、件举例如下：（1）掷出一个六个面的骰子，得到的点数是4；（2）从1000个微处理器中随机抽取5个，没有发现次品；（3）在北京人民医院选取了一个女婴。各实验的样本空间为：（1）1,2,3,4,5,6；（2）从1000个微处理器中选取5个的所有组合；（3）北京人民医院的所有婴儿。2022-7-302022-7-30定义2.5.2有限样本空间S中的事件E的概率P(E)定义为：。(2.5.1)其中|E|,|S|分别表示集合E和S的基数。EP(E)S2022-7-302022-7-30例2.5.2掷出一个各面同性的骰子，求掷出偶数的概率。解 设掷出偶数这个事件为E，样本空间为S，则根据题意|E|=3,|

28、S|=6。代入式(2.5.1)，得P(E)=3/6=1/2。2022-7-302022-7-30例2.5.3掷出两个各面同性的骰子，求点数之和为10的概率。解 设点数之和为10这个事件为E，样本空间为S，则根据题意|E|=3,|S|=36。代入式(2.5.1)，得P(E)=3/36=1/12。2022-7-302022-7-30例2.5.4在福利彩票中，若彩民从152个数中选取的6个数与随机生成的中奖数字相同(不计顺序)，则可以赢得大奖。求一张彩票赢得大奖的概率。解 从52个数字中选取6个共有C(52,6)种选法，即|S|=C(52,6)，而得大奖的组合只有一种，即|E|=1，根据式(2.5.

29、1)，得：P(E)=1/C(52,6)=0.00000004。2022-7-302022-7-302.5.2 离散概率函数定义2.5.3 如果函数P将样本空间S的每一个结果x映射为实数P(x)，且对任意的xS，满足（1）0P(x)1；（2）。则称函数P是概率函数。x SP(x)1说明说明 条件条件(1)(1)保证一个结果的概率为非负数且不超过保证一个结果的概率为非负数且不超过1 1；条件条件(2)(2)保证所有结果的概率之和为保证所有结果的概率之和为1 1，即进行实验，即进行实验后，必出现某个结果。后，必出现某个结果。2022-7-302022-7-30例2.5.5一个一面较重的骰子，26以相

30、同的机会出现，1出现的机会是其他数字的3倍。试求出16的概率函数值。解 设P(2)=P(3)=P(4)=P(5)=P(6)=a，则P(1)=3a。又因为P(1)+P(2)+P(3)+P(4)+P(5)+P(6)=1，所以有5a3a=1，即a=1/8。从而P(2)=P(3)=P(4)=P(5)=P(6)=1/8，P(6)=3/8。2022-7-302022-7-30概率函数定义2.5.4 设E是一个事件，E的概率函数P(E)定义为 。在例2.5.5中，出现奇数点的概率则为P(1)+P(3)+P(5)=5/8。定理2.5.1 设E是一个事件，E的补的概率满足 。(2.5.2)x EP(E)P(x)

31、P(E)P E12022-7-302022-7-30例2.2.6 生日问题n个人中，求至少有两个人生日相同(同月同日不计年)的概率。假定出生在某天的概率均等，忽略2月29日。解 设E表示“至少两个人生日相同”，则 表示“没有两个人生日相同”，则 。从而 。n365364(365n1)PE365n365 364(365n1)P(E)1365事实上，事实上，随着天数随着天数n n的增加，至少两个人的增加，至少两个人生日相同的概率也随着增加生日相同的概率也随着增加，当，当n23n23时，时，至少有两个人生日相同的概率大于至少有两个人生日相同的概率大于1/21/2。E2022-7-302022-7-3

32、0两个事件并的概率定理2.5.2 设E1和E2是两个事件，则 P(E1E2)=P(E1)P(E2)P(E1E2)(2.5.3)如果E1E2=，即E1与E2为不相交的事件，则有下面的推论。推论2.5.3 设E1和E2是两个不相交的事件，则 P(E1E2)=P(E1)P(E2)(2.5.4)2022-7-302022-7-30例2.5.7掷出两个各面同性的骰子，得到“一对”(两个骰子点数相同)或点数和为6的概率是多少？解 设E1表示事件“一对”，E2表示事件“点数和为6”，则样本空间大小是36，事件E1的种数为6,即(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),事件E2的

33、种数为5，即(1,5),(2,4),(3,3),(4,2),(5,1)。E1E2的种数为1。2022-7-302022-7-30例2.5.7 解（续）从而 P(E1)=1/6,P(E2)=5/36,P(E1E2)=1/36。根据式(2.5.3)，有 P(E1E2)=1/65/361/36=5/18。即得到“一对”或点数和为6的概率是5/18。2022-7-302022-7-302.6 递归关系递归关系可用于解决一些特定的计数问题。递归关系是序列中第n个元素与它相邻前若干个元素之间的关系。例如第一个数是5；2、将前一项加3得到后一项。5,8,11,14,递归关系递归关系2022-7-302022

34、-7-30定义2.6.1对序列a0,a1,a2,an-1,，用a0,a1,a2,an-1中的某些项表示an的等式称为递归关系(recurrence relation)。显示地给出序列a0,a1,a2,的有限项的值，称为初始条件(initial condition)。显然，递归关系和确定的初始条件一起，才能确定一个序列。2022-7-302022-7-30例2.6.1某人投资1000元，每年可收益12。An表示他在第n年末的总资产。求出定义序列An的递归关系和初始条件。解 序列An的递归关系和初始条件分别为：An=An-10.12An-1=1.12 An-1,n1,A0=10002022-7-3

35、02022-7-30例2.6.2Sn表示不含子串“111”的n位字符串的个数。求出序列Sn的递归关系和初始条件。解 序列Sn的递归关系和初始条件分别为：Sn=Sn-1Sn-2 Sn-3，n4,S1=2,S2=4,S3=7。2022-7-302022-7-302.7 计数问题的应用例2.7.1 7个科学工作者从事一项机密的技术研究，他们的工作室装有电子锁，每位科学工作者都有打开电子锁用的“钥匙”。为了安全起见，必须有4位在场时才能打开大门。试问该电子锁至少应具备多少个特征？每位科学工作者的“钥匙”至少应有多少种特征？解 为了使任意3个人在场时至少缺少一个特征而打不开门，该电子锁至少应具备C(7,

36、3)=35种特征；每个科学工作者的“钥匙”至少要有C(6,3)=20种特征。2022-7-302022-7-30例2.7.2某一制造铁盘的工厂，由于设备和技术的原因只能将生产盘子的重量控制在a克到（a+0.1）克之间。现需要制成重量相差不超过0.005克的两铁盘来配制一架天平，问该工厂至少要生产多少铁盘才能得到一对符合要求的铁盘。2022-7-302022-7-30例2.7.2 解将铁盘按重量分类，所有a克到a+0.005克的分为第一类；a+0.005克到a+0.01克的分为一类；a+0.01克到a+0.015克的又为一类，.，最后，a+0.095克到a+0.1克为一类，共计20类，由鸽笼原理

37、知，若该工厂生产21个铁盘，那么就能得知有两个铁盘属于同一类，因而它们之间的重量差将不超过0.005克。2022-7-302022-7-30例2.7.3 Fibonacci数列假定一对新出生的兔子一个月又成熟，并且再过一个月开始生出一对小兔子。按此规律，在没有兔子死亡的情形下，一对初生的兔子，一年可以繁殖成多少队兔子？解 因为Fn=Fn-1+Fn-2，所以根据迭代法，有F12=F11+F10=2F10+F9=3F9+2F8 =5F8+3F7=8F7+5F6 =89F2+55F1=89+55=143。2022-7-302022-7-30例2.7.4计算下面算法中基本操作的次数算法 输入：s1,s

38、2,sn和序列的长度。输出：s1,s2,sn，按非递减顺序排列。2022-7-302022-7-30例2.7.4（续）1.selection_sorts(s,n)2./基本情况3.if(n=1)4.return5./找到最大的元素6.max_index=1/初始时认为s1是最大的元素7.for i=2 to n8.if(sismax_index)/比较得到较大的元素，并更新最大元素9.max_index=i 10./将最大的元素移至序列尾11.swap(sn,smax_index)12.selection_sort(s,n-1)13.2022-7-302022-7-30例2.7.4 解设计算n

39、个数排序的比较执行次数为bn，则该算法中的比较语句的执行次数的递归关系为：bn=bn-1+n 1，其初始条件为：b1=0。2022-7-302022-7-30例2.7.4 解（续）用迭代法求解该递归关系：bn=bn-1+n1=bn-2+n2+n-1 =bn-3+n3+n2+n1=b1+1+2+n3+n2+n1=0+1+2+n 3+n2+n1=n(n-1)/2。2022-7-302022-7-302.8 本章总结 1、乘法原理和加法原理的基本含义；2、r-排列，全排列，环形r排列，环排列，r-组合的基本概念，它们之间关系和相应的计算公式；3、容斥原理和鸽笼原理的基本概念及正确使用；4、实验、事件

40、、样本空间、概率函数的基本概念，离散概率的计算；5、递归关系、初始条件的概念、递归关系的建立和求解。2022-7-302022-7-30习题类型（1）基本概念题：涉及离散概率的基本概念；（2）计算题：涉及排列数与组合数的计算，利用容斥原理的计算，离散概率的计算和递归关系的建立与求解；（3）证明题：涉及对鸽笼原理的应用。2022-7-302022-7-30习题第44-45页2.6.8.11.14.19.20.21.24.26.27.http:/202.115.21.136:8080/lssx/离离 散散 数数 学学电子科技大学电子科技大学计算机科学与工程学院计算机科学与工程学院示示 范范 性性

41、软软 件件 学学 院院20222022年年7 7月月3030日星期六日星期六2022-7-30数理逻辑（Mathematical Logic）是研究演绎推理的一门学科，用数学的方法来研究推理的规律统称为数理逻辑。第二篇 数理逻辑2022-7-30主要研究内容：推理 着重于推理过程是否正确 着重于语句之间的关系 主要研究方法：数学的方法 就是引进一套符号体系的方法，所以数理逻辑又叫符号逻辑（Symbolic Logic）。第二篇 数理逻辑2022-7-30什么是数理逻辑？用数学的方法来研究推理的规律统称为数理逻辑。为什么要研究数理逻辑？程序算法数据 算法逻辑控制总结总结2022-7-30第二篇

42、数理逻辑命题逻辑命题逻辑 命题的基本概念命题的基本概念命题联结词命题联结词命题公式命题公式命题的范式命题的范式 主要研主要研 究内容究内容谓词逻辑谓词逻辑谓词的基本概念谓词的基本概念谓词公式谓词公式公式的标准型公式的标准型推理与证明技术推理与证明技术命题逻辑推理理论命题逻辑推理理论谓词逻辑推理理论谓词逻辑推理理论数学归纳法数学归纳法按定义证明法按定义证明法2022-7-30第三章 命题逻辑 命题逻辑也称命题演算，或语句逻辑。研究内容：（1）研究以命题为基本单位构成的前提和结论之间的可推导关系 （2）研究什么是命题？（3）研究如何表示命题？（4）研究如何由一组前提推导一些结论？2022-7-30

43、第三章 命题逻辑 命题逻辑的特征：在研究逻辑的形式时，我们把一个命题只分析到其中所含的命题成份为止，不再分析下去。不把一个简单命题再分析为非命题的集合，不把谓词和量词等非命题成份分析出来。2022-7-30第三章 命题逻辑集合的表示方法集合的表示方法2命题公式命题公式3命题范式命题范式4命题基本概念命题基本概念1命题联结词命题联结词22022-7-303.1 本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1、五种基本、五种基本联结词联结词2 2、2424个基本个基本的等价公式的等价公式3 3 掌握求命题掌握求命题范式的方法范式的方法3联结词完备集联结词完备集的理解和学习的理解和学习

44、2公式的代入规公式的代入规则和替换规则则和替换规则2022-7-303.2.1 命题定义3.2.1具有确切真值的陈述句称为命题,该命题可以取一个“值”，称为真值。真值只有“真”和“假”两种，分别用“”(或“”)和“”(或“”)表示。3.2 命题与命题联结词2022-7-30（1）太阳是圆的；（2）成都是一个旅游城市；（3）北京是中国的首都；（4）这个语句是假的；（5）1110；（6）+y；（7）我喜欢踢足球；（8）3能被2整除；（9）地球外的星球上也有人；（10）中国是世界上人口最多的国家；（11）今天是晴天；例3.2.1TTT/F非命题非命题T/FFT/FTTT非命题非命题2022-7-30

45、例3.2.1（续）（12）把门关上；（13）滚出去！（14）你要出去吗？（15）今天天气真好啊！非命题非命题非命题非命题非命题非命题非命题非命题注意：注意：一切没有判断内容的句子都不能作为命题一切没有判断内容的句子都不能作为命题，如命令，如命令句、感叹句、疑问句、祈使句、二义性的陈述句等。句、感叹句、疑问句、祈使句、二义性的陈述句等。2022-7-30命题一定是陈述句，但并非一切陈述句都是命题。命题的真值有时可明确给出，有时还需要依靠环境、条件、实际情况时间才能确定其真值。结论：结论：在数理逻辑中像在数理逻辑中像字母字母“x x”、“y y”、“z z”等字母总等字母总是表示是表示变量。变量。

46、约定：约定：2022-7-30下列语句是否是命题？并判断其真值结果？（1）四川不是一个国家；（2）3既是素数又是奇数；（3）张谦是大学生或是运动员；（4）如果周末天气晴朗，则我们将到郊外旅游；（5）2+2=4当且仅当雪是白的。例例3.2.23.2.22022-7-30一般来说，命题可分两种类型：1)原子命题(简单命题)：不能再分解为更为简单命题的命题。2)复合命题：可以分解为更为简单命题的命题。而且这些简单命题之间是通过如“或者”、“并且”、“不”、“如果.则.”、“当且仅当”等这样的关联词和标点符号复合而构成一个复合命题。命题的分类2022-7-301)今天天气很冷。2)今天天气很冷并且刮风

47、。3)今天天气很冷并且刮风，但室内暖和。例3.2.3 通常用通常用大写的带或不带下标的英文字母大写的带或不带下标的英文字母、.P.P、Q Q、R R、.A Ai i、B Bi i、C Ci i、.P.Pi i、Q Qi i、R Ri i、.等表示命题等表示命题2022-7-303.2.2 命题联结词设命题设命题P,QP,Q表示任意两个命题表示任意两个命题,则则最常见的命题联结词有：最常见的命题联结词有：联接词记号复合命题读法 记法真值结果 3.3.析取析取 P P或者或者Q QP P与与Q Q的析取的析取P P Q QP PQ=1Q=1P=1P=1或或Q=1Q=12.2.合取合取 P P并且并

48、且Q QP P与与Q Q的合取的合取PQPQPQPQ=1=1P=1P=1且且Q=1Q=11.1.否定否定 非非P PP P的否定的否定PPP=1P=1 P=0P=04.4.蕴涵蕴涵若若P,P,则则Q QP P蕴涵蕴涵Q QP PQQP PQ=0Q=0 P=1,Q=0P=1,Q=05.5.等价等价 P P当且仅当当且仅当Q QP P等价于等价于Q QP PQ QP PQ=1Q=1P P=1=1,Q=1Q=1或或P P=0=0,Q=0Q=0例如：命题例如：命题P P：2 2是素数；是素数；Q Q：北京是中国的首都：北京是中国的首都2022-7-30总结P QPPQPQPQPQ0 0100110 1

49、101101 0001001 1011112022-7-30说明1、联结词是句子与句子之间的联结，而非单纯的名词、形容词、数词等地联结；2、联结词是两个句子真值之间的联结，而非句子的具体含义的联结，两个句子之间可以无任何地内在联系；2022-7-30说明3、联结词与自然语言之间的对应并非一一对应；联结词自然语言既又、不仅而且、虽然但是、并且、和、与，等等；如P则Q、只要P就Q、P仅当Q、只有Q才P、除非Q否则P，等等等价、当且仅当、充分必要、等等；相容（可兼）的或2022-7-30符号化下列命题（1）四川不是人口最多的省份；（2）王超是一个德智体全面发展的好学生；（3）教室的灯不亮可能是灯管坏

50、了或者是停电了；（4）如果周末天气晴朗，那么学院将组织我们到石像湖春游；（5）两个三角形全等当且仅当三角形的三条边全部相等。例3.2.42022-7-30例3.2.4 解（1）设：四川是人口最多的省份。则命题（1）可表示为。（2）设：王超是一个思想品德好的学生；：王超是一个学习成绩好的学生；R：王超是一个体育成绩好的学生。则命题（2）可表示为R。（3）设：教室的灯不亮可能是灯管坏了 ：教室的灯不亮可能是停电了 则命题（3）可表示为。2022-7-30（4）设：周末天气晴朗；：学院将组织我们到石像湖春游。则命题（4）可表示为。（5）设：两个三角形全等；：三角形的三条边全部相等。则命题（5）可表示