教案
离散数学课程教案
离散数学课程教案
离散数学课程教案
离散数学课程教案
离散数学课程教案
离散数学课程教案
离散数学课程教案
离散数学课程教案
离散数学课程教案
离散数学 课程教案
《离散数学》教案 第一章集合与关系 集合是数学中最基本的概念，又是数学各分支、自然科学及社会科学各领域的最普 遍采用的描述工具。集合论是离散数学的重要组成部分，是现代数学中占有独特地位的 一个分支。 G. Cantor( 康脱 ) 是作为数学分支的集合论的奠基人。1870 年前后，他关于无穷序列的研究导致集合论的系统发展。 1874 年他发表了关于实数集合不能与自然数集合建立 一一对应的有名的证明。 1878 年，他引进了两个集合具有相等的“势”的概念。然 而，朴素集合论中包含着悖论。第一个悖论是布拉利 - 福尔蒂的最大序数悖论。 1901 年罗素发现了有名的罗素悖论。 1932 年康脱也发表了关于最大基数的悖论。集合论的现代公理化开始于1908 年策梅罗所发表的一组公理，经过弗兰克尔的加工，这个系统称 为策梅罗 - 弗兰克尔集合论（ ZF），其中包括 1904 年策梅罗引入的选择公理。另外一种系 统是冯·诺伊曼 - 伯奈斯 - 哥德尔集合论。公理集合论中一个有名的猜想是连续统假设（CH）。哥德尔证明了连续统假设与策梅罗 - 弗兰克尔集合论的相容性，科恩证明了连续统假设与策梅罗 - 弗兰克尔集合论的独立性。现在把策梅罗 - 弗兰克尔集合论与选择公理一起称为 ZFC系统。 一、学习目的与要求 本章目的是介绍集合的基本概念，讲授集合运算的基本理论，关系的定义与运算。 通过本章的学习，使学生了解集合是数学的基本语言，掌握主要的集合运算方法和关系运 算方法，为学习后续章节打下良好基础。 二、知识点 1．集合的基本概念与表示方法； 2．集合的运算； 3．序偶与笛卡尔积； 4．关系及其表示、关系矩阵、关系图； 5．关系的性质，符合关系、逆关系； 6．关系的闭包运算； 7．集合的划分与覆盖、等价关系与等价类；相容关系； 8．序关系、偏序集、哈斯图。
学习目标: 1.深刻理解序偶、笛卡尔积、关系、集合的划分与覆盖、等价关系、等价类、商集、相容关系、(最大)相容类、偏序关系、极大元、极小元、上(下)界、上(下)确界、最大(小)元、全序关系、良序关系等概念; 2.掌握集合的交、并、差、补、对称差的运算及其运算规律; 3.掌握关系的交、并、逆、复合运算、闭包运算及其性质; 4.掌握关系的矩阵表示与关系图; 5.深刻理解关系的自反性、反自反性、对称性、反对称性与传递性,掌握其判别方法; 6.掌握集合的覆盖与划分的联系与区别; 7.掌握偏序关系的判别及其哈斯图的画法;会求偏序集中给定集合的极大元、极小元、上(下)界、上(下)确界、最大(小)元。 主要内容: 1.集合的基本概念及其运算 2.序偶与笛卡尔积 3.关系及其表示 4.关系的性质及其判定方法 5.复合关系与逆关系 6.关系的闭包运算 7.等价关系与相容关系 8.偏序关系 重点: 1.关系的性质及其判别; 2.关系的复合运算及其性质; 3.等价关系与等价类、等价关系与集合的划分的联系; 4.偏序关系判别及其哈斯图的画法、偏序集中特异位置元素的理解。 难点: 1.关系的传递性及其判别; 2.等价关系的特性; 3.偏序关系的哈斯图的画法;偏序集中特异位置元素的求法。 教学手段: 通过多个实例的精讲帮助同学理解重点与难点的内容,并通过大量的练习使同学们巩固与掌握关系的性质及其判别、关系的复合运算及其性质、等价关系的特性、偏序关系的哈斯图的画法及偏序集中特异位置元素的求法。 习题: 习题3、1:4,6;习题3、2:3(8),4(12),6(m);习题3、4:1 (2)、(4),3;习题3、5:1,4;习题3、6:2,5,6;习题3、7:2,5,6;习题3、8:1(1)-(6);习题3、9:3(2)、(4),4(3);习题3、10:1 ,4,5。
集合论练习题 一、选择题 1．设B = { {2}, 3, 4, 2}，那么下列命题中错误的是（ ）． A ．{2}∈ B B ．{2, {2}, 3, 4}B C ．{2}B D ．{2, {2}}B 2．若集合A ={a ，b ，{ 1，2 }}，B ={ 1，2}，则（ ）． A ． B A ，且BA B ．B A ，但BA C ．B A ，但BA D ．B A ，且BA 3．设集合A = {1, a }，则P (A ) = ( )． A ．{{1}, {a }} B ．{?,{1}, {a }} C ．{?,{1}, {a }, {1, a }} D ．{{1}, {a }, {1, a }} 4.已知AB ={1,2,3}, AC ={2,3,4},若2 B,则（ ） A ． 1?C B ．2? C C ．3?C D ．4?C 5. 下列选项中错误的是( ) A ． ??? B ． ?∈? C ． {}??? D ．{}?∈? 6. 下列命题中不正确的是（ ） A ． x {x }-{{x }} B ．{}{}{{}}x x x ?- C ．{}A x x =?,则xA 且x A ? D ． A B A B -=??= 7. A , B 是集合，P (A ),P (B )为其幂集，且A B ?=?，则()()P A P B ?=( ) A ． ? B ． {}? C ． {{}}? D ．{,{}}?? 8. 空集?的幂集()P ?的基数是( ) A ． 0 B ．1 C ．3 D ．4 9．设集合A = {1，2，3，4，5，6 }上的二元关系R ={a , b ∈A , 且a +b = 8}，则R 具有的性质为（ ）． A ．自反的 B ．对称的 C ．对称和传递的 D ．反自反和传递的
学习目标： 1．深刻理解序偶、笛卡尔积、关系、集合的划分与覆盖、等价关系、等价类、商集、相容关系、（最大）相容类、偏序关系、极大元、极小元、上（下）界、上（下）确界、最大（小）元、全序关系、良序关系等概念； 2．掌握集合的交、并、差、补、对称差的运算及其运算规律； 3．掌握关系的交、并、逆、复合运算、闭包运算及其性质； 4．掌握关系的矩阵表示和关系图； 5．深刻理解关系的自反性、反自反性、对称性、反对称性和传递性，掌握其判别方法； 6．掌握集合的覆盖与划分的联系与区别； 7．掌握偏序关系的判别及其哈斯图的画法；会求偏序集中给定集合的极大元、极小元、上（下）界、上（下）确界、最大（小）元。 主要内容： 1．集合的基本概念及其运算 2．序偶与笛卡尔积 3．关系及其表示 4．关系的性质及其判定方法 5．复合关系和逆关系 6．关系的闭包运算 7．等价关系与相容关系 8．偏序关系 重点： 1．关系的性质及其判别； 2．关系的复合运算及其性质； 3．等价关系与等价类、等价关系与集合的划分的联系； 4．偏序关系判别及其哈斯图的画法、偏序集中特异位置元素的理解。 难点： 1．关系的传递性及其判别； 2．等价关系的特性； 3．偏序关系的哈斯图的画法；偏序集中特异位置元素的求法。 教学手段： 通过多个实例的精讲帮助同学理解重点和难点的内容，并通过大量的练习使同学们巩固和掌握关系的性质及其判别、关系的复合运算及其性质、等价关系的特性、偏序关系的哈斯图的画法及偏序集中特异位置元素的求法。 习题：
习题 3.1：4，6；习题 3.2：3（8），4（12），6（m ）；习题 3.4：1 （2）、 (4)，3；习题 3.5：1，4；习题 3.6：2，5，6；习题 3.7：2，5，6；习题 3.8：1（1）-（6）；习题3.9：3（2）、（4），4（3）；习题3.10：1 ，4，5。 3.1 集合的基本概念 集合(set)（或称为集）是数学中的一个最基本的概念。所谓集合，就是指具有共同性质的或适合一定条件的事物的全体，组成集合的这些“事物”称为集合的元素。 集合常用大写字母表示，集合的元素常用小写字母表示。若A 是集合，a 是A 的元素，则称a 属于A ，记作a A ∈；若a 不是A 的元素，则称a 不属于A ，记作。若组成集合的元素个数是有限的，则称该集合为有限集(Finite Set)，否则称为无限集(Infinite Set)。 常见集合专用字符的约定： N —自然数集合(非负整数 集) I (或Z )—整数集合(I +，I -) Q —有理数集合(Q +，Q -) R —实数集合(R +，R -) F —分数集合(F +，F -) 脚标+和-是对正、负的区分 C —复数集合 P —素数集合 O —奇数集合 E —偶数集合 幂集 定义 3.1.1 对于每一个集合A ，由A 的所有子集组成的集合，称为集合A 的幂集(Power Set)，记为 ()P A 或2A ．即(){}P A B B A =?。 例如：{,,}A a b c =, (){,{},{},{},{,},{,},{,},{,,}}P A a b c a b b c a c a b c φ=。 定理3.1.1 如果有限集A 有n 个元素，则其幂集()P A 有2n 个元素。 证明 A 的所有由k 个元素组成的子集数为从n 个元素中取k 个的组合数。 (1)(2)(1)! k n n n n n k C k ---+= L 另外，因A φ?，故()P A 的元素个数N 可表示为 1 201n k n k n n n n n k N C C C C C ==++++++=∑L L 又因 0()n n k k n k n k x y C x y -=+= ∑ 令 1x y == 得 02n n k n k C ==∑ 故()P A 的元素个数是2n 。 人们常常给有限集A 的子集编码，用以表示A 的幂集的各个元素。具体方法是： 设12{,,,}n A a a a =L ，则A 子集B 按照含i a 记1、不含i a 记0(1,2,,)i n =L 的规定
《离散数学》教案 课目：第一章命题逻辑 教师：熊建英 学时： 12课时
Ⅰ教学提要 一、教学对象（人数） 学生：信息安全专业本科二年级学生50人 二、教学目标（任务） 各小结中知识点掌握程度(* 理解；** 基本掌握；***熟练掌握) 三、教学要求 （一）学生：着重知识点的学习，积极思考，参与提问。 （二）教官：严格纪律，严密组织、保持良好教学秩序，确保教学效果。 四、教官分工 主讲教师1名：负责教案编写，课堂的组织教学，教学总结编写。
五、本章重点 1、利用联接词构造复合命题公式 2、真值表的构建 3、等值演算 4、复合命题公式转化为主析取范式、主合取范式的方法 5、推理证明 六、本章难点 1、利用命题公式演算、真值表进行等值判断和公式类型判断 2、利用命题公式演算、真值表转化主析取范式、主合取范式 3、将现实背景下的条件约束构造为命题公式 七、教学方法 采用课堂教授，主要使用多媒体课件，部分内容及例题用黑板解释。 八、课时分配 1.1 命题及联接词2课时； 1.2 命题公式及其赋值2课时； 1.3 等值式2课时； 1.4 析取范式与合取范式2课时； 1.5 推理理论与消解法2课时； 1.6 命题逻辑应用案例2课时； 九、场地器材 多媒体教室 十、参考书目 1、杨圣洪、张英杰、陈义明：《离散数学》，科学出版社，2011年。 2、屈婉玲、耿素云、张立昂：《离散数学》，高等教育出版社，2008年。 3、屈婉玲、耿素云、张立昂：《离散数学学习指导与习题解析》，高等教育出版社，2008年。
Ⅱ教学进程 1.1 命题及联接词（2课时） 一、教学内容 1、命题的概念表示与分类 2、五种基本的联接词的逻辑关系 3、复合命题的符号化 4、复合命题的真值判断 二、课程时间安排 1、首先介绍本课程的性质，任务和教学安排，对学生明确提出教学上的要求（10分钟） 2、介绍离散数学学科的发展历史（20分钟） 3、命题与真值、命题的分类、简单命题符号化（15分钟） 4、联结词与复合命题（35分钟） 5、本次课小结（10分钟） 三、教学实施 （一）创设意境、导入课程（10分钟） 目的 体会离散数学理论在现实生活中的应用、是计算机专业多门核心课程的基础，让学生明白“离散数学”课程作用和意义。 1、从生活应用中理解逻辑推理作用，及离散数学学习意义； 如：犯罪推理、电路设计、人事安排的最优方案、网络中最优路径等； (1)逻辑推理问题范例（PPT展示一个犯罪推理案例） (2)离散数学是一门可以对逻辑推理规律建立相应的符号运算系统，解决此类问题的科学。 2、离散数学与其他专业课程的联系； (1) 涉及多门计算机专业中很多专业课程，如：编程语言、数据结构、操作系统、数据数据加密。
大连民族学院 计算机科学与工程学院实验报告实验题目：集合的运算 课程名称：离散数学 实验类型：□演示性□验证性□操作性□设计性□综合性专业：网络工程班级：网络111班 学生姓名：张山学号：2011083123 实验日期：2013年12月22日实验地点：I区实验机房 实验学时：8小时实验成绩： 指导教师签字：年月日老师评语：
1 实验题目：集合的运算 实验原理： 1、实验内容与要求： 实验内容：本实验求两个集合间的运算，给定两个集合A、B，求集合A与集合B之间的交集、并集、差集、对称差集和笛卡尔乘积。 实验要求：对于给定的集合A、B。用C++/C语言设计一个程序（本实验采用 C++），该程序能够完成两个集合间的各种运算，可根据需要选择输出某种运算结果，也可一次输出所有运算结果。 2、实验算法： 实验算法分为如下几步： （1）、设计整体框架 该程序采取操作、打印分离（求解和输出分开）的思想。即先设计函数求解各部分运算并将相应结果传入数组（所求集合）中，然后根据需要打印运算结果。 （2）、建立一个集合类（Gather） 类体包括的数组a、b、c、d、e、f、g分别存储集合A、B以及所求各种运算的集合。接口（实现操作的函数）包括构造函数，菜单显示函数，求解操作函数，打印各种运算结果等函数。 （3）、设计类体中的接口 构造函数：对对象进行初始化，建立集合A与集合B。 菜单显示函数：设计提示选项，给使用者操作提示。 操作函数：该函数是程序的主题部分，完成对集合的所有运算的求解过程，并将结果弹入（存入）对应数组（集合）中，用于打印。 具体操作如下： 2 1*求交集：根据集合中交集的定义，将数组a、b中元素挨个比较，把共同元素选出来，并存入数组c（交集集合）中，即求得集合A、B的交集。 2*求并集：根据集合中并集的定义，先将数组a中元素依次存入数组g（并集集合）中，存储集合A中某元素前，先将其与已存入g中的元素依次比较，若相同则存入下一个元素，否则直接存入g中，直到所有A中元素存储完毕。接着
21st Century University Planned Textbooks of Computer Science (第2版) Discrete Mathematics (2nd Edition) 李盘林赵铭伟徐喜荣李丽双编著 □概念严谨精炼 □叙述简明清晰 □推理详尽严格 人民邮电出版社 POSTS & TELECOM PRESS
第2版前言 离散数学是现代数学的一个重要分支，是计算机科学与技术的理论基础。因此，它是计算机科学与技术专业的核心、骨干课程。一方面，它给后继课，如数据结构、编译系统、操作系统、数据库原理和人工智能等，提供必要的数学基础；另一方面，通过学习离散数学，培养和提高了学生的抽象思维和逻辑推理能力，为其今后继续学习和工作，进行科学研究，攀登科技高峰，打下扎实的数学基础。 本书第1版于2002年2月出版以来，六年来，先后多次印刷发行，已得到了普遍认可，被全国部分普通高校选作教材，本版除了勘误了第1版中的不妥之处外，还增加了一些新的章节，并相应补充了例题和习题，以适应高等学校教学改革的需要。 本书共12章，内容包括命题逻辑、谓词逻辑、集合、关系、函数、代数结构的概念及性质、半群与群、环和域、格与布尔代数、图的概念与表示、几类重要的图以及数论。 本书是笔者结合多年教学实践与科学研究，参考国内外教材，在力求通俗易懂、简明扼要的指导思想下编写而成的。在编写过程中有如下3点考虑。 1. 力求做到“少而精”，注意突出重点，论证详细明了，便于自学，在定理证明中多次运用归纳法，希望读者熟练掌握这一方法。 2. 在加强基本理论教学的同时，注意了分析问题、解决问题的技能培养和训练。书中各知识点均配有典型例子，并加以说明。此外，各章都配有适量的习题，希望通过做习题这个环节，来培养、提高学生解决问题的能力。 3. 一方面每章各有独立性，教师根据需要可以单独选讲几章；另一方面，尽可能注意各章之间的联系，规范并统一了符号和术语。 本书在编写过程中，得到了有关领导、老师和同学的热情关心、支持和帮助，在此一并表示感谢。 限于作者水平，书中难免有不当和疏漏之处，恳请读者批评指正。 编者 于大连理工大学 2008年9月
教案课程 名称类别 任课教师 授课对象 基本教材和主要参考资料 教学目的要求 教学重点难点 离散数学 课程编号总计 学分 4.5 学时： 72 讲课 必修课（√ ）选修课（）理论课（√ ）实验课（）学时： 72 实验 学时：刘光辉职称讲师上机 学时： 专业班级：信息科学 0501、 0502、 0503共 3 个班 序号教材名称作者出版社出版时间1离散数学孙吉贵等高等教育出版社2002 年2离散数学王兵山等国防科技大学出社2001 年3离散数学（修订版） 耿素云 高等教育出版社2004 年 屈婉玲 本课程共分为四个部分，分别是数理逻辑、集合论、代数系统、图论。在 教学过程中除讲清楚各部分的基本内容外，还应使学生在以下几方面得到培养和训练。 1.有效地掌握该门课程中的所有概念。通过讲课和布置一定数量的习题 使学生能够使用所学的概念对许多问题作出正确的判断。 2.通过课程中许多定理的证明过程复习概念，了解证明的思路，学会证 明的方法，并使学生掌握定理的内容和结果。 3.通过介绍各种做题的方法，启发学生独立思维的能力。创造性的提出 自己解决问题的方法，提高学生解决问题的能力。 4．通过该门课程的学习使学生掌握逻辑思维和逻辑推理的能力，培养学生正规的逻辑思维方式。 教学重点： 1．数理逻辑：等价演算，推理理论 2．集合论：集合恒等式，关系运算，关系性质，等价关系，偏序关系 3．代数系统：代数系统，群的性质，子群，陪集与拉格朗日定理，循环群，置换群 4．图论：图的基本概念，图的矩阵，根树，平面图的概念与性 质教学难点： 一阶逻辑推理，关系的运算，偏序关系，陪集，置换群，根树的应用，平面图 的性质
)? * A. B. 目 C. D. (a) (b) (c) (d) 2. 是强连通的 是强连通的 是强连通的 是强连通的 设有向图（a）、（b）、（c）与（d）如图所示，则下列结论成立的是（ 盘）（ A.(a) 是弱连通的 B.(b) 是弱连通的 C.(c) 是弱连通的 D.(d) 是弱连通的 3. 设无向图G的邻接矩阵 为（）?1 1 1 [I I 1 1 1 则G的边数 A. 1 n B. 6 C. 7 D. 14 110 1Q011 10000 C1001 [0101oj 为 4. 设无向图G的邻接矩阵 （）- 则G的边数为r A. 6 B. 5 C. 4
A. e 是割点 巫B. { a, e}是点割集 C. { b, e}是点割集 D. {d}是点割集 A. {(a, e)} 是割边 b. {(a, ◎}是边割集 c. {(a, e ,(b, c)}是边割集 豈D . {(d, e)}是边割集 8. 图G 如图所示，以下说法正确的是 ( )? 厂A. 5点， 8边 「B. 6点， 7边 c C. 6点， 8边 斶D. 5点， 7边 6. 如图所 斤示，以下说法正确的是 已知无向图G 的邻接矩阵 5. ()- 1 0 1 r 1 0 0 [1 1 Q Q 0 1 1 1 0 1 0 i _1 1 1 1 oj 为 c f )? b 7. 如图所示，以下说法正确的是
目A. a是割点广B.｛b, c｝是点割集 C. ｛b, d｝是点割集已 D. ｛c｝是点割集 9. 图G如图所示，以下说法正确的是（） A. Cl B. * C. 口D. 10. {(a, d)}是割边 {(a, d)}是边割集 {(a, d) ,(b, d)}是边割集 ｛（b, d）｝是 边割集 设图G-
离散数学集合运算（第一次作业） C语言写法： #include printf(“\n”); } if(i >=n) { if(G[0]) cout < 理工大学 教案首页 第 1 次课授课时间2017 年9 月14 日教案完成时间：2017 年9 月10 日 （ §4.1谓词和量词 1.全称量词， 全称量词(Universal Quantifier)：在自然语言中“所有的”、“一切”、“任意的”、“每一个”等表示数量的词，称为全称量词。它用于描述讨论范围中的全部个体，用符号“?”表示。 2.存在量词， 存在量词(Existential Quantifier)：用符号“?”表示，对应自然语言中“存在一些”、“至少有一个”等表示数量的词。?xF(x)表示个体域中存在个体具有性质F。 3.存在唯一量词 4.将具体命题符号化 例2.1-6将下列命题符号化。 ⑴好人自有好报。 ⑵有会说话的机器人； ⑶没有免费的午餐； ⑷在北京工作的人未必都是北京人。 解在本题中没有指定个体域，故取个体域为全总个体域。 ⑴设F(x)：x是好人；G(x)：x会有好报，则命题符号化为：?x(F(x)→G(x))。 ⑵设F(x)：x是机器人；G(x)：x是会说话的，则命题符号化为：?x(F(x)∧G(x))。 ⑶设M(x)：x是午餐；F(x)：x是免费的，则命题符号化为：┐?x(M(x)∧F(x))。这句话可作如下叙述，“所有的午餐都不是免费的”，故命题可符号化为：?x(M(x)→┐F(x))。因为在含义上这句话和题目的是一样的，所以可以看出，┐?x(M(x)∧F(x))和?x(M(x)→┐F(x))是等价的，后面还将给出具体的证明。 ⑷设F(x)：x在北京工作；G(x): x是北京人，则命题符号化为：?x(F(x)→G(x))。这句话也可作如下叙述，“存在着在北京工作的非北京人”，故可符号化为：?x(F(x)∧G(x))。因为在含义上这句话和题目是一样的。所以可以看出，?x(F(x)→G(x))和?x(F(x)∧G(x))是等价的，后面也将给出具体的证明。 §4.2一阶语言 1.一阶语言 2.解释和赋值 一个公式A的一个解释(Interpretation) I应由以下四部分组成： ⑴非空个体域D； ⑵公式A中的每个个体常元指定为D中一个特定元素； ⑶公式A中的n元函数指定为D n到D的一个特定的函数； ⑷公式A中的n元谓词指定为D n到{0,1}的一个特定的谓词(命题函数)。 3.公式的分类 设A为一个谓词公式，如果A在任何解释下都是真的，则称A为逻辑有效式（Universal）或称为永真式； 如果A在任何解释下都是假的，则称A为矛盾式（Contradiction）或称为永假式； 若至少存在一个解释使A为真，则称A为可满足式(Satisfable)。 4.将具体的公式解释和赋值 离散数学课程设计方案 中央电大教务处教学管理科 2008年02月29日 为了落实教育部批准的《关于广播电视大学开展人才培养模式改革和开放教育试点的报告》精神，积极投入中央电大计算机科学与技术专业本科开放教育工程的建设和实施，搞好离散数学课程教学与管理工作，保证本课程的教学质量，实现本专业的培养目标，给出以下设计方案。 一、课程的性质与任务 计算机科学与技术专业是中央广播电视大学于1999年开设的开放教育试点专业，开设之初的合作高校为清华大学。在当时的专业教学计划中，把计算机数学基础（1）——离散数学确定为统设必修课程，课程的主要内容包括：数理逻辑、集合论、图论、代数系统等。由于2007年初，中央广播电视大学工学院将该专业的合作建设高校改为北京交通大学，并在新教学计划中把离散数学课程确定为该专业的学位课程，该课程的主要内容包括：集合论、图论、数理逻辑等。 离散数学是计算机科学与技术专业的基础核心课程。通过本课程的学习，使学生具有现代数学的观点和方法，并初步掌握处理离散结构所必须的描述工具和方法。同时，也要培养学生抽象思维和慎密概括的能力，使学生具有良好的开拓专业理论的素质和使用所学知识，分析和解决实际问题的能力，为学生以后学习计算机基础理论与专业课程打下良好的基础。 本课程是一门理论性较强的课程，要求在完成基础知识教学任务的同时，通过适当的实际应用的介绍，提高学生的实际应用能力的培养。 二、课程的目的与要求 本课程是计算机科学与技术专业及有关学科的一门重要的基础核心课程，内容主要是介绍离散量的结构及其相互关系，其包含的理论与方法在各学科领域都有着广泛的应用。同时，离散数学也是计算机科学与技术专业的许多专业课程，包括程序设计、数据结构、操作系统、编译技术、数据库、人工智能等的先修课程。教学内容以基本概念、结论、算法、推理与证明方法，以及一般应用方法的介绍为主，课程内容突出简明扼要、体系结构清楚为原则。通过本课程的学习，学生可以初步掌握处理离散结构所必须的描述工具和方法，同时培养和提高自身的抽象思维和逻辑推理，以及分析和解决实际问题的能力，并为以后学习计算机基础理论与专业课程打下良好的基础。 本课程具体要求为： （1）了解离散数学的主要组成部分，各个部分所涉及的基本内容，及其在计算机科学与技术领域中的应用； （2）理解离散数学的的基本概念、结论、算法、应用方法及适用范围； （3）掌握离散数学的的基本推理与证明过程、基本算法及应用方法。 三、学时和学分 本课程课内学时72，共4学分，开设一学期。下表给出该课程的主要教学内容，视频课程和辅导课程的学时分配。 Author ：ssjs Mail ： 看了离散数学中的关系整理了一点关于n 元集合中各种关系的计算，现写下这个方便大家学习交流理解。对文章所致一切后果不负任何责任，请谨慎使用。 如有错误之处请指正。 定义： 1，对称：对于a,b R a b ∈∈∈),b (),a (,A 有如果只要 2，反对称：如果R a b R b a b b ∈∈=∈),(),(a ,A ,a 和时仅当 3，自反：如果对每个元素R ),(A a ∈∈a a 有 4，反自反：如果对于每个R ),(A a ?∈a a 有 5，传递：如果对R ),(,R ),(R ),(,A ,,∈∈∈∈c a c b b a c b a 则且 6，非对称：如果R ),(R ),(?∈a b b a 推出【注】其中是含（a,a)这样的有序对的。 【重要】集合A 的关系是从A 到A 的关系 （也就是说集合A 的关系是A A ?的子集）。 如下结论： N 元集合上的自反关系数为：)1(2 -n n N 元集合上的对称关系数为：2/)1(2+n n N 元集合上的反对称关系数为：2/)1(n 3 2-n n N 元集合上的非对称关系数为：2/)1(3-n n N 元集合上的反自反关系数为：)1(n 2-n N 元集合上的自反和对称关系数为：2/)1(n 2-n N 元集合上的不自反也不反自反关系数为：)1(n n 222 2-?-n 下面是上面结论的计算 1，自反 2A A ,A n n =?=因为也就是说集合A 有n 平方个有序对，由自反定义可知，对R ),(A a ∈∈?a a 有所以n 个有序对()).....3,2,1i X ,X (n i i =其中一定在所求关系中，否则的话此关系就不是自反的了，那么还有n n -2个有序对，所以由集合子集对应二进制串可得自反关系数为)1(n 222--=n n n 下图有助于理解。 （1,1) (2,2).......(n,n) | (1,2) (1,3).........(n-1,n) N n n -2个有序对 2，对称 2A A ,A n n =?=因为也就是说集合A 有n 平方个有序对，由对称定义可知，对于R a b b ∈∈∈),b (),a (,A ,a 有只要。另外知道在n 平方个有序对中有n 个有序对()).....3,2,1i X ,X (n i i =其中，相应的就有n n -2个有序对（X,Y)且X Y ≠，定义可知后面 的n n -2个有序对只能成对出现，所以有2/)(n 2n -对。前面的那n 对可以出现任意多对。 离散数学作业 作业6 ——等价关系 1. 设R和S均为A上的等价关系，确定下列各式，哪些是A上的等价关系？如果是，证明之；否则，举反例说明。 （1）R∩S （2）R∪S （3）r (R-S) （4）R- S （5）R?S （6）R2 解：(1),(6)正确，其余错误。 2. R是集合A上的二元关系， a,b,c ,若aRb,且bRc,有cRb,则称R是循环关系。证明R是自反和循环的，当且仅当R是一等价关系。 分析: 需要证明两部分: (1)已知R是自反和循环的，证明:R是一等价关系 (2)已知R是一等价关系, 证明R是自反和循环的. 证明：（1）先证必要性。只需要证明R是对陈的和传递的。 任取(x,y)∈R。因为R是自反的，所以(y,y)∈R。由R是循环的可得(y,x)∈R，即R是对陈的。 任取(x,y)，(y,z)∈R。因R是循环的，所以(z,x)∈R。由R对称性得(x,z)∈R，即R是传递的。 （2）证充分性。只需要证明R是循环的。任取(x,y)，(y,z)∈R，下证(z,x)∈R。由于R是传递的，所以(x,z)∈R。又由R是对称的得(z,x)∈R。所以R是循环的。 3. 设|A|=n ，在A 上可以确定多少个不同的等价关系？ 解：2n!/((n+1)n!n!) 4. 给定集合S={ 1 , 2 , 3, 4, 5 }，找出S 上的等价关系R ，此关系R 能够产生划分{{1，2}，{3}，{4，5}}，并画出关系图。 解：{(1,2),(2,1),(4,5),(5,4)}S R I =? 5. 设A={1，2，3，4，5}。R 是集合A 上的二元关系，其关系矩阵如下图所示。求包含R 的最小等价关系和该等价关系所确定的划分。 ????????????????=0010001000 000000101000001R M 分析: 可以证明tsr(R)是包含R 的最小等价关系. 解：包含R 的最小等价关系的矩阵表示如下： 100000 1010001010 101000101?? ? ? ? ? ? ??? 上述等价关系确定的划分为{{1},{2,4},{3,5}}. 6. 自学华氏(WalShall)算法，写出算法的基本概念、基本步骤和一个 求解传递闭包的具体实例，并可清晰讲解算法整体实现过程。 7. （选做题）设R 与S 是A 上的等价关系，证明： （1）R o S 是A 上的等价关系，iff R o S=S o R ； （2）R ∪S 是A 上的等价关系，if R o S ?S 且 S o R ?R. 分析: iff 是if and only if 的缩写, 是当且仅当的意思. 证明：（1）先证必要性。任取(x,z)∈R o S ，则存在y 使得xRy,ySz 。 离散数学集合论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第11周末前完成并上交任课教师（不收电子稿）。并在03任务界面下方点击“保存”和“交卷”按钮，完成并上交任课教师。 一、填空题 1．设集合{1,2,3},{1,2} ==，则P(A)-P(B )= {{3}，{1,3}，{2,3}， A B {1,2,3}} ，A?B= {<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3.2>} ．2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为1024 ．3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， ∈ R? x ∈ > y 且 =且 ∈ < {B , , x A y A y B x } 则R的有序对集合为{<2, 2>，<2, 3>，<3, 2>}，<3,3> ． 4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} y y x∈ = < > ∈ x , , x , 2 {B y A 那么R－1＝{<6,3>,<8,4>} 5．设集合A=｛a, b, c, d｝，A上的二元关系R={离散数学-学校教案
离散数学课程设计方案
离散数学N元集合关系个数计算
离散数学作业6_集合与关系答案教学文案
2016离散数学作业3答案
相关主题
文本预览