1、离离 散散 数数 学学主讲教师：程主讲教师：程 虹虹电电 话：话：676261/21第一章第一章 绪绪 论论课课 程程 简简 介介教教 学学 大大 纲纲教教 学学 目目 教教 学学 要要 求求参参 考考 教教 材材考考 核核 方方 式式 说说 明明离离 散散 与与 连连 续续名名 人人 名名 言言 趣趣 味味 数数 学学土耳其商人和帽子故事土耳其商人和帽子故事 剪发师头由谁来理剪发师头由谁来理?聪聪 明明 囚囚 徒徒考考 试试 日日 程程 表表 安安 排排2/21课课 程程 简简 介介课程编号：课程编号：07ZB073116 课程性质：课程性质：必修必修 总课时：总课时：72课时课时 总学分：
2、总学分：4分分 开课学期：开课学期：第三学期第三学期 适用专业：适用专业：计算机科学与技术计算机科学与技术 先修课程：先修课程：高等数学，线性代数高等数学，线性代数，计算机导论，计算机导论后续课程：后续课程：数据结构及算法，数字逻辑数据结构及算法，数字逻辑课程地位：课程地位：学位课程，非常主要学位课程，非常主要 3/21 教教 学学 大大 纲纲离散数学研究离散量结构和相互间关系。其离散数学研究离散量结构和相互间关系。其研究对象普通是有限个或可数个元素。课程以培研究对象普通是有限个或可数个元素。课程以培养学生抽象思维和缜密概括能力为主要教学目标。养学生抽象思维和缜密概括能力为主要教学目标。课程内
3、容主要有：数理逻辑、集合论、二元关系、课程内容主要有：数理逻辑、集合论、二元关系、代数系统、图论、形式语言和自动机。离散数学代数系统、图论、形式语言和自动机。离散数学能够为学生学习计算机专业知识与技术，从事计能够为学生学习计算机专业知识与技术，从事计算机软、硬件开发和应用打下坚实基础。算机软、硬件开发和应用打下坚实基础。4/21 教教 学学 目目 1、了解离散数学研究内容以及它在计算机科学中地位、了解离散数学研究内容以及它在计算机科学中地位和作用。和作用。2、了解和掌握命题逻辑和谓词逻辑符号化和推导证实、了解和掌握命题逻辑和谓词逻辑符号化和推导证实方法。方法。3、了解和掌握集合与二元关系性质和
4、应用。、了解和掌握集合与二元关系性质和应用。4、掌握代数系统（群、半群、格、环、域，布尔代数、掌握代数系统（群、半群、格、环、域，布尔代数等）性质及主要应用。等）性质及主要应用。5、掌握惯用判别图和树方法。、掌握惯用判别图和树方法。5/21教教 学学 要要 求求1、了解命题逻辑和谓词逻辑异同点和联络，掌握基本概念和推理证实方法。、了解命题逻辑和谓词逻辑异同点和联络，掌握基本概念和推理证实方法。2、了解并掌握集合基本运算和性质及其计算机科学中应用。、了解并掌握集合基本运算和性质及其计算机科学中应用。3、了解二元关系和集合笛卡儿积，掌握关系运算和性质。、了解二元关系和集合笛卡儿积，掌握关系运算和性
5、质。4、了解函数定义，并掌握不一样种函数性质。、了解函数定义，并掌握不一样种函数性质。5、了解并掌握代数系统性质，掌握几个经典代数系统。、了解并掌握代数系统性质，掌握几个经典代数系统。6、了解图基本概念，掌握它存放表示，并了解最短路径和关键路径求法。、了解图基本概念，掌握它存放表示，并了解最短路径和关键路径求法。7、了解并掌握欧拉图和哈密尔顿图定义及判定方法。、了解并掌握欧拉图和哈密尔顿图定义及判定方法。8、了解树基本概念及树相关应用。、了解树基本概念及树相关应用。9、了解形式语言和有穷自动机。、了解形式语言和有穷自动机。10、能够针对所学知识点，对每章后习题做覆盖率到达、能够针对所学知识点，
6、对每章后习题做覆盖率到达60以上。以上。11、能够做题举一反三，尽可能使用各种方法去解题，锻炼独立思索能力。、能够做题举一反三，尽可能使用各种方法去解题，锻炼独立思索能力。12、能够从生活中、计算机课程学习中对应找到离散数学实际应用实例，进而加、能够从生活中、计算机课程学习中对应找到离散数学实际应用实例，进而加深了解和掌握相关知识点，并能提升学习趣味性和主动性。深了解和掌握相关知识点，并能提升学习趣味性和主动性。6/21参参 考考 教教 材材推荐教材：推荐教材：离散数学离散数学，第二版，左孝凌、刘永才等编著，上海科学技术文件出版社，第二版，左孝凌、刘永才等编著，上海科学技术文件出版社参考教材：
7、参考教材：1、离散数学离散数学，第三版，耿素云、屈婉玲等编，清华大学出版社，第三版，耿素云、屈婉玲等编，清华大学出版社 2、离散数学离散数学，刘学书、袁磊等编著，刘学书、袁磊等编著，武汉大学出版社武汉大学出版社3、离散数学导论离散数学导论，徐洁磐编，高等教育出版社徐洁磐编，高等教育出版社4、离散数学离散数学，陈莉、刘晓霞编著，高等教育出版社，陈莉、刘晓霞编著，高等教育出版社5、离散数学结构离散数学结构，第四版（影印版），第四版（影印版），Bernard Kolman等编，高等等编，高等教育出版社教育出版社6、离散数学离散数学，朱一清编著，朱一清编著，电子工业出版社电子工业出版社7、离散数学离散
8、数学，乔维声编，西安电子科技大学出版社，乔维声编，西安电子科技大学出版社8、离散数学离散数学，第四版，第四版，Richard Johnsonbaugh著，电子工业出版社著，电子工业出版社7/21 考考 核核 方方 式式 说说 明明1、考查方式：、考查方式：笔试（闭卷）2、笔试时间：、笔试时间：120分钟3、成绩组成：、成绩组成：结业考试成绩（占70%）,平时成绩(占30%，包含作业、提问、测验等)4、主要题型：、主要题型：本课程命题范围涵盖课程大部分章节。试题难易程度分为：较易占50%，中等难度占40%，较难占10%。在题型结构上，主要由选择题、填空题、判断题、画图题和计算（综合）题，其中客观
9、题（包含选择题、填空题、判断题等）占40%；主观题（包含画图题和计算（综合）题等）占60%。5、考评范围：、考评范围：第2章第11章8/21离离 散散 与与 连连 续续“离散数学离散数学”是研究离散数量关系和离散结构数是研究离散数量关系和离散结构数学模型数学分支统称。学模型数学分支统称。“离散离散”与与“连续连续”是数量关系中一对极为深刻是数量关系中一对极为深刻矛盾，它们之间对立与统一是数学发展主要动力矛盾，它们之间对立与统一是数学发展主要动力之一。之一。“离散离散”是是“连续连续”否定，即否定，即“不连续不连续”；“连续连续”则是指事物、数量一个属性，这种属则是指事物、数量一个属性，这种属性
10、使它们轻易被分割或结合，而且不会所以而丧性使它们轻易被分割或结合，而且不会所以而丧失它们原有本性。比如，实数是连续，整数则是失它们原有本性。比如，实数是连续，整数则是离散；马铃薯是离散，而马铃薯羹则是连续。离散；马铃薯是离散，而马铃薯羹则是连续。9/21近近50年来，数字电子计算机飞速发展与广泛应用，极年来，数字电子计算机飞速发展与广泛应用，极大地冲击了当代数学。因为数字电子计算机是一个离散结大地冲击了当代数学。因为数字电子计算机是一个离散结构，它只能处理离散或离散化了数量关系，所以，不论计构，它只能处理离散或离散化了数量关系，所以，不论计算机科学本身，还是与计算机科学及其应用亲密相关当代算机
11、科学本身，还是与计算机科学及其应用亲密相关当代科学研究领域，都面临这么一些问题：怎样高速、有效地科学研究领域，都面临这么一些问题：怎样高速、有效地处理离散对象和离散数量关系，怎样对离散结构建立离散处理离散对象和离散数量关系，怎样对离散结构建立离散数学模型，又怎样将已用连续数量关系建立起来数学模型数学模型，又怎样将已用连续数量关系建立起来数学模型离散化，从而可由计算机加以处理。于是，人们开始重新离散化，从而可由计算机加以处理。于是，人们开始重新认识离散数量关系研究意义，重新重视讨论离散数量关系认识离散数量关系研究意义，重新重视讨论离散数量关系数学分支，并取得新发展。离散数学学科出现和发展是上数学
12、分支，并取得新发展。离散数学学科出现和发展是上述事实逻辑结果。述事实逻辑结果。10/21名名 人人 名名 言言1、（绪论）宏伟乐队里缺乏不了乐器之王、（绪论）宏伟乐队里缺乏不了乐器之王钢琴，高耸钢琴，高耸入云数学大厦里也缺乏不了入云数学大厦里也缺乏不了“离散离散”（数学），（数学），“连续连续”和和“离散离散”像两支翅膀，像两支翅膀，它把人类从地上带向天堂！它把人类从地上带向天堂！“有有限限”与与“无穷无穷”象一把尖锐宝剑，它无往不胜，无坚不摧！象一把尖锐宝剑，它无往不胜，无坚不摧！2、学习数学吧！即便你还是一个孩童，学习它能培养你耐、学习数学吧！即便你还是一个孩童，学习它能培养你耐性，更能发
13、挥你思索力及创造力！性，更能发挥你思索力及创造力！3、(集合论技术集合论技术)连续形象：连续形象：“剪不停，理还乱，是离愁，恰剪不停，理还乱，是离愁，恰似一江春水向东流。似一江春水向东流。”南唐，李后主词南唐，李后主词4、离散形象：、离散形象：“枯藤老树昏鸦，小桥流水人家，古道西风枯藤老树昏鸦，小桥流水人家，古道西风瘦马，夕阳西下，断肠人在天涯。瘦马，夕阳西下，断肠人在天涯。”元元.马致远马致远5、(图论图论)“现在应该使用图概念渗透全部数学教学，图表示现在应该使用图概念渗透全部数学教学，图表示了一个系统可能状态以及连接这些状态算子。了一个系统可能状态以及连接这些状态算子。11/21 离散数学
14、趣味应用离散数学趣味应用1、土耳其商人和帽子故事、土耳其商人和帽子故事一个土耳其商人，想找一个十分聪明助手帮助他经商，有两一个土耳其商人，想找一个十分聪明助手帮助他经商，有两个人前来应聘，这个商人为了试一试哪一个聪明些，就把两个人个人前来应聘，这个商人为了试一试哪一个聪明些，就把两个人带进一间漆黑屋子里，他打开电灯后：带进一间漆黑屋子里，他打开电灯后：“这张桌子上有五顶帽子，这张桌子上有五顶帽子，两顶是红色，三顶是黑色。现在，我把灯关掉，而且把帽子摆位两顶是红色，三顶是黑色。现在，我把灯关掉，而且把帽子摆位置弄乱，然后我们三个人每人摸一顶帽子戴在头上，在我开灯后，置弄乱，然后我们三个人每人摸一
15、顶帽子戴在头上，在我开灯后，请你们尽快说出自己头上戴帽子是什么颜色。请你们尽快说出自己头上戴帽子是什么颜色。”说完之后，商人说完之后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下两顶帽子藏了起来，接着把电灯打开，这时，那两个有应试者下两顶帽子藏了起来，接着把电灯打开，这时，那两个有应试者看到商人头上戴是一顶红帽子，过了一会儿，其中一个人便喊到：看到商人头上戴是一顶红帽子，过了一会儿，其中一个人便喊到：“我戴是黑帽子。我戴是黑帽子。”请问这个人猜得对吗？是怎么推导出来？请问这个人猜得对吗？是怎么推导出来？答案分析答案分析1
16、2/212、剪发师头由谁来理、剪发师头由谁来理?在一个小镇上，有一个剪发师公开在一个小镇上，有一个剪发师公开宣告：他给而且只给小镇上全部不给宣告：他给而且只给小镇上全部不给自己剪发人剪发，现在要问自己剪发人剪发，现在要问:这位剪发这位剪发师头由谁来理师头由谁来理?答案分析答案分析13/213、聪、聪 明明 囚囚 徒徒古希腊有个国王，对处死囚徒方法作了两种要求：古希腊有个国王，对处死囚徒方法作了两种要求：一个是砍头，一个是绞刑。而且他自恃聪明做出一个要求：一个是砍头，一个是绞刑。而且他自恃聪明做出一个要求：囚徒能够说一句话，而且这句话是马上能够验证其真假。囚徒能够说一句话，而且这句话是马上能够验
17、证其真假。假如囚徒说是真话，那么处以绞刑，假如囚徒说是假话，假如囚徒说是真话，那么处以绞刑，假如囚徒说是假话，那么处以砍头。许多囚徒或者是因为说了假话而被砍头或那么处以砍头。许多囚徒或者是因为说了假话而被砍头或者因为说了真话而被处以绞刑。者因为说了真话而被处以绞刑。有一位极其聪明囚徒，当轮到他来选择处死方法时，有一位极其聪明囚徒，当轮到他来选择处死方法时，他说出一句巧妙话，结果使这个国王按照哪种方法处死他，他说出一句巧妙话，结果使这个国王按照哪种方法处死他，都违反自己决定，只好将他放了。都违反自己决定，只好将他放了。试问：这囚徒说是句什么话？试问：这囚徒说是句什么话？答案分析答案分析14/21
18、4、考试日程表安排、考试日程表安排考虑七天安排七门考试问题，要使同一考虑七天安排七门考试问题，要使同一教员举行任何两门考试不要安排在接连两教员举行任何两门考试不要安排在接连两天内进行。假如每个教员最多举行四次考天内进行。假如每个教员最多举行四次考试，证实安排这么考试日程表总是可能。试，证实安排这么考试日程表总是可能。答案分析答案分析15/21土耳其商人和帽子答案分析土耳其商人和帽子答案分析设P1表示“猜正确人戴红帽子”；P2表示“猜正确人戴黑帽子”；Q1表示“另一个人戴红帽子”；Q2表示“另一个人戴黑帽子”；R1表示“商人戴红帽子”。现在知道R1为真，又知道另一个人没有作出断定，即既不能断定Q
19、1为真，也不能断定Q2为真。依据题设条件，可得以下公式：R1P1Q2：假如商人和猜正确人戴都是红帽子，那么另一个戴就是黑帽子，因为红帽子只有两顶。R1Q1P2：假如商人和另一个戴都是红帽子，那么猜正确人戴就是黑帽子。P1P2：假如猜正确人戴不是红帽子，那么他戴就是黑帽子。Q1Q2：假如另一个人戴不是红帽子，那么他戴就是黑帽子。推演步骤以下：设P1（1）P1（依据假设）；（2）R1（依据题设）（3）R1P1（合取组成）；（4）R1P1Q2（依据题设）（5）Q2（3）（4）分离）。这就是说，“另一个人戴黑帽子”这个判定是必定能够作出，不过这与题设条件（即“另一个没有作出判定”）相矛盾，所以，P1为
20、假，即P1为真，故可得：（6）P1；（7）P1P2（依据题设）；（8）P2（6）（7）分离）。这就是说，“猜正确人戴着黑帽子”是真，所以猜正确人必定说：“我戴是黑帽子”。返返 回回16/21剪发师头谁来剃答案分析剪发师头谁来剃答案分析假如剪发师头由他人给他理，即剪发师自己假如剪发师头由他人给他理，即剪发师自己不给自己剪发，那么按要求这位剪发师头应该有不给自己剪发，那么按要求这位剪发师头应该有自己理。假如剪发师头由他自己理，按要求他只自己理。假如剪发师头由他自己理，按要求他只给那些不给自己剪发人剪发，那么剪发师头不能给那些不给自己剪发人剪发，那么剪发师头不能由他自己理，即剪发师头应该由他人来理。
21、这就由他自己理，即剪发师头应该由他人来理。这就产生了矛盾产生了矛盾:剪发师头既不能由他人理，也不能剪发师头既不能由他人理，也不能由他自己理，所以这位剪发师要求是一个悖论。由他自己理，所以这位剪发师要求是一个悖论。返返 回回17/21 聪明囚徒答案分析聪明囚徒答案分析聪明囚徒所说话，应使国王不论怎么处置他都带来聪明囚徒所说话，应使国王不论怎么处置他都带来矛盾，这句话就是矛盾，这句话就是“国王决定砍我头国王决定砍我头”。假如这和国王。假如这和国王要求一致，是说真话，因而按国王决定处死方法，讲真要求一致，是说真话，因而按国王决定处死方法，讲真话应处以绞刑，这么就造成了国王要求（砍头）同国王话应处以绞
22、刑，这么就造成了国王要求（砍头）同国王决定处死方法相矛盾。假如这和国王要求不一致，是说决定处死方法相矛盾。假如这和国王要求不一致，是说假话，因而按照国王决定处死方法，讲假话给予砍头，假话，因而按照国王决定处死方法，讲假话给予砍头，这么又造成了国王要求（绞刑）同国王决定处死方法相这么又造成了国王要求（绞刑）同国王决定处死方法相矛盾。国王处于进退维谷处境，只好免于处死，将囚徒矛盾。国王处于进退维谷处境，只好免于处死，将囚徒放掉。放掉。返返 回回18/21考试日程表答案分析考试日程表答案分析假如将七次（或七天）考试作为七个顶假如将七次（或七天）考试作为七个顶点，做一个图点，做一个图G，若两个顶点对应考试是由，若两个顶点对应考试是由不一样教员举行，则这两个顶点连一条边，不一样教员举行，则这两个顶点连一条边，实际上就是判定图实际上就是判定图G是否有哈密尔顿通路问是否有哈密尔顿通路问题。题。返返 回回19/21课课 后后 思思 考考请同学们课后经过查阅资料或上网搜索方式，列举出离散数学其它一些趣味应用问题！20/21谢谢！21/21
