离散数学教案设计.doc

滁州学院计算机与信息工程学院课程教案课程名称： 离散数学 授课教师： 赵欢欢 授课对象： 11级网络工程专业3、4班 授课时间： 2012年9月-2012年12月 滁州学院计算机科学与信息工程学院2012年8月离散数学教学大纲（Discrete Mathematic）课程代码： 学时：48 学分：3一、课程简介本大纲根据2009版应用型人才培养方案制订。 （一）教学对象：网络工程、计算机科学与技术专业本科学生（二）开课学期：第三学期（三）课程类别：专业基础课（四）考核方式：考试（五）参考教材：离散数学第2版 邓辉文 清华大学出版社 2010.主要参考书目：1邵学才,叶秀明. 离散数学M.北京电子工业出版社，2009.2邵志清,虞慧群. 离散数学M.北京电子工业出版社，2003.3屈婉玲. 离散数学习题解析M.北京大学出版社，2008.本课程的先修课程是高等数学、线性代数，后续课程包含数据结构、数据库原理及应用、操作系统、数字逻辑、人工智能、算法分析与设计等。二、教学基本要求与内容安排（一）教学目的与要求离散数学是研究离散量的结构及其相互关系的学科,它在各学科领域特别在计算机科学领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程必不可少的先行课程。本课程的教学目的旨在通过对离散数学的教学，让学生不但可以掌握处理如集合、代数结构和图等离散结构的描述工具和方法，为后续课程的学习创造条件，而且为学生今后提高专业理论水平，从事计算机行业的实际工作提供必备的抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。（二）教学内容安排教学内容教学要求教学方法重点()难点()学时分配备注讲课实验上机其他第一部分 数理逻辑讲授15.51命题逻辑的基本概念21.1命题与联接词B11.2命题公式及其赋值A12命题逻辑等值演算3.52.1等值式B12.2析取范式与合取范式A12.3联接词的完备集C0.52.4可满足性与消解法B13命题逻辑的推理理论2 3.1 推理的形式结构A13.2 自然推理系统PB14一阶逻辑基本概念24.1一阶逻辑命题符号化A14.2 一阶逻辑公式及解释A15一阶逻辑等值演算与推理35.1 一阶逻辑等值式与置换规则A15.2 一阶逻辑前束范式A15.3 一阶逻辑的推理理论A16数理逻辑在计算机中的应用3第二部分 集合论讲授131集合代数21.1 集合的基本概念B0.51.2 集合的运算A0.51.3 有穷集的计数C0.51.4 集合恒等式A0.52二元关系62.1 有序对与笛卡尔积A12.2 二元关系A12.3 关系的运算A12.4 关系的性质A12.5 关系的闭包A12.6 等价关系与划分A13函数33.1 函数的定义与性质A0.53.2函数的复合与反函数A0.53.3双射函数与集合的基数C13.4 一个电话系统的描述实例C14集合论在计算机中的应用2第三部分 代数结构讲授61.51代数系统31.1 二元运算及其性质A11.2 代数系统A11.3 代数系统的同态 与同构B12群与环32.1 群的定义及其性质A12.2 循环群与置换群A2第四部分 图论讲授121图的基本概念2.51.1 图A0.51.2 连通与回路A0.51.3 图的连通性A0.51.4 图的矩阵表示A0.51.5 图的运算A0.52欧拉图与哈密顿图22.1 欧拉图A0.52.2 哈密顿图A0.52.3 最短路问题与货郎担问题C13树1.53.1 无向树及其性质A0.53.2 生成树A0.53.3 根树及其应用B0.54平面图34.1 平面图的基本概念B0.54.2 欧拉公式B0.54.3 平面图的判断B14.4 平面图的对偶图C15 图论在计算机中的应用3（教学要求：A熟练掌握；B掌握；C了解）三、实验内容本课程无实验制订人（签字）： 审核人（签字）： 教 学 进 度 表 20122013学年第1学期周 数 16 周 计划学时 48学时讲 课 48 学时 课堂讨论 0 学时实验课 0 学时 习题课 0 学时 其他环节 0 学时授课教师姓名 赵欢欢 职称 助教 授课专业 网络工程 班级 2011级 课程名称 离散数学 教材名称 离散数学 出版社 清华大学出版社 周次日期周学时其中教学内容摘要（章节名称、讲述的内容提要、实验的名称、课堂讨论的题目等）讲课实验课习题课课堂讨论其他环节第一周9月3日至9月9日44第一讲 集合、映射与运算（一）1.1 集合的基本概念 理论：集合、子集、幂集、n元组、笛卡尔积第二讲 集合、映射与运算（二）1.2 映射的有关概念 理论：映射的定义、映射的性质、逆映射、复合映射第二周9月10日至9月16日22第三讲 集合、映射与运算（三）1.3运算的定义和性质 理论：运算的定义、运算的性质第三周9月17日至9月23日44第四讲 集合、映射与运算（四）1.4 集合的运算 1.5 集合的划分 1.6 集合的对等理论：集合的并、交、差、补、对称差等基本运算，集合的划分与覆盖、集合对等、可数集合、不可数集合第五讲 关系（一）2.1 关系的概念理论：n元关系的定义、2元关系、关系的定义域和值域、关系的表示、函数的关系定义第四周9月24日至9月30日22第六讲 关系（二）2.1 关系的运算 理论：关系的集合运算、逆运算、复合运算、关系的其他运算第五周10月1日至10月7日 4 4国庆放假第七讲 关系（三）2.3 关系的性质 2.4 关系的闭包理论：关系的性质：自反性、反自反性、对称性、反对称性、传递性；自反闭包r(R)、对称闭包s(R)、传递闭包t(R)第六周10月8日至10月14日22第八讲 关系（四）2.5 等价关系 2.6相容关系 2.7偏序关系理论：等价关系的定义、等价类；相容关系的定义；偏序关系的定义、哈斯图的、偏序集中的特殊元素第七周10月15日至10月21日44第九讲 命题逻辑（一）3.1 命题的有关概念 3.2 逻辑联接词理论：命题的定义与真值、原子命题和复合命题、各种逻辑连接词的含义，真假的判断第十讲 命题逻辑（二）3.3 命题公式及其真值表理论：命题公式的定义、命题的符号化、命题公式的真值表、命题公式的类型第八周10月22日至10月28日22第十一讲 命题逻辑（三）3.4 逻辑等值的命题公式理论：逻辑等值的定义、基本等值式、等值演算法、对偶原理第九周10月29日至11月4日 44第十二讲 命题逻辑（四）3.5 命题公式的范式理论：命题公式的析取范式和合取范式的定义域求法命题公式的主析取范式及主合取范式的定义和求法第十三讲 命题逻辑（五）3.7 命题逻辑中的推理理论：推理形式有效性的定义；基本推理规则；命题逻辑的自然推理系统第十周11月5日至11月11日22第十四讲 谓词逻辑（一）4.1 个体、谓词、量词和函词理论：谓词逻辑概念，谓词的概念与表示，量词的概念与表示，个体域，辖域，约束变元和自由变元的含义第十一周 11月12日至11月18日44第十五讲 谓词逻辑（二）4.2谓词公式及命题的符号化 4.3 谓词公式的解释及类型理论：谓词公式的定义，将命题用用符号（个体，量词，谓词）来表示，消去量词的逻辑等值式，永真式，科满足式，永假式及中性式的概念第十六讲 谓词逻辑（三）4.4逻辑等值的谓词公式 4.5谓词公式的前束范式 理论：谓词公式等值的定义，基本等值式，前束范式第十二周11月19日至11月25日22第十七讲 图论（一）6.1 图的基本概念 6.2 节点的度数6.3 子图，图的运算和图同构理论：图的定义，邻接，关联，简单图，节点的度数，子图第十三周11月26日至12月2日44第十八讲 图论（二）6.4 路与回路 6.5图的连通性理论内容：路，回路，无向图的连通性，无向连通图的点连通度与边连通度，有向图的连通性第十九讲 图论（三）6.6 图的矩阵表示 6.7 赋权图及最短路径理论内容：图的邻接矩阵，可达矩阵，关联矩阵，赋权图，最短路径第十四周12月3日至12月9日22第二十讲 图论（四）7.1 欧拉图理论内容：欧拉图的有关概念，欧拉定理，中国邮递员问题、Hamilton 图第十五周12月8日至12月16日44第二十一讲 图论（五）7.2 无向树 7.3 有向树理论内容：树的基本概念，最小生成树，二叉树的遍历与表达式的计算第二十二讲 代数结构（一）5.1 代数结构简介理论内容：代数结构的定义，半群及独异点，子代数，代数结构的同态与同构第十六周12月17日至12月23日22第二十三讲 代数结构（二）5.2 群的定义及性质理论内容：群的有关概念，子群，群的同态第十七周12月24日至12月30日22第二十四讲 总复习系主任签名： 院长签名： 年 月 日 年 月 日说明：1本教学进度表由主讲教师负责填写，于每学期开学第一周内送交教师所在系，经领导审定、签字后备查。2此表一式三份，其中，任课教师一份，教师所在系一份，教务处一份。第一讲：集合、映射和运算（一）一、教学目标1. 掌握集合的概念与表示2. 理解子集、幂集、 n元组与笛卡儿积的概念3.掌握子集，幂集，笛卡尔积的求法 二、重点与难点分析1.重点：集合的概念，子集，幂集，笛卡尔积的概念及求法2.难点：幂集三、 教学内容与教学过程1.进行自我介绍（5分钟）姓名，联系方式，专业方向。建议学生用电子邮件方式联系。2.进行课程简介（10分钟） 离散数学是研究离散量的结构及相互之间关系的学科 是一门专业基础课，是数据结构、操作系统、计算机组成原理、数据库原理等课程的数学基础。 特点：知识点集中，概念，定理多；方法性强；学数学就要做数学 成绩评定：平时成绩(到课情况，书面作业，平时测验)占30%,期末考试占70%3.进入主题，开始第一讲(1) 集合的有关概念(20分钟)集合 定义：集合是具有某种特定性质的对象汇集成的一个整体，通常用大写字母A,B,C,D表示。例如：滁州学院全体学生 计算机与信息工程学院所有女生 常见的数的集合：N,N+,Z,Q,R,C元素集合中的每一个对象称为该集合的元素，通常用小写字母a,b,c,d,x,等表示例如：滁州学院的每个学生 计算机与信息工程学院的每个女生 N：0、1、2、3集合的表示方法 列举法：Z=,-2,-1,0,1,2, 描述法：x|x是自然数且x小于10 递归法文氏图： 特殊集合：全集U,空集元素与集合 xA或 |A|表示集合A中的元素个数 注意：集合中的元素可以是集合，如A=a,a,b,b,c,|A|=4,a,bA注：集合中的元素无顺序；集合中无重复元素例：指出下列哪些是集合，哪些不是集合？ 中国人的集合； 百货商店里好看的花布的集合； 1000以内的素数的集合； 26个英文字母组成的集合； 这个班里高个子学生的集合； 直线y2x-5上的点的集合。(2)集合之间的关系子集（15分钟）定义：若A中的任意元素都属于B，则A是B的子集，称A包含于B或B包含A，包括的两层含义：包含与真包含（AB），A是B的真子集注意：属于（元素与集合的关系）与包含于（集合与集合的关系）的区别例：A=1,2,3,4，B=2,4 或定理1-1：A定理1-2：（自反性）则A=B则（传递性） 用定义进行证明定理1-3：A=B的充要条件是注：该定理是证明两个集合相等的基本方法 该定理与定理1-2中的(2)的区别 例1-2注：A中有一个元素不属于C，则，反证法是一种很好的方法幂集（15分钟）定义：由X的所有子集组成的集合， 例：x=1,2 ，Y=a,b,c 例1-3 注：若|X|=n,P(x)的元素有：；由一个元素构成的子集；由两个元素构成的子集；由n个元素构成的子集计数的基本原理：加法原理：图示乘法原理：图示定理1-4：若|X|=n,|P(X)|=2n证明：加法原理：二项式定理： 乘法原理：注：每个元素的参与与否构成不同的子集n元组（5分钟） 定义：论域U中选取的n个元素按照一定的顺序排列，得到n元有序组，称n元组，记为：(x1,x2,x3,xn)或 例：平面直角坐标系中点的坐标是2元组；空间直角坐标系中点的坐标是3元组；n元组在数据结构中是一个表 有序对，序偶：2元组 注：(x,y)(y,x)笛卡尔积（10分钟） 定义：设是集合，称为A1,A2,An的笛卡尔积（直积，叉积），记为：例：A=a,b,B=1,2，例1-4注： 一般来说，定理1-5：若|A|=m,|B|=n,则|=mn4. 教学小结（5分钟）本讲首先介绍了集合的概念与表示方法，接着介绍了集合之间的关系子集与幂集，n元组，笛卡尔积的概念及相关定理。 四、 作业与实验（5分钟）1. 书面作业：习题1.1 1、2、3、7、102. 上机作业：无第二讲：集合、映射和运算（二）一、教学目标1. 掌握映射的概念与表示2. 理解映射的三种性质：单射、满射、双射，会判断某个具体映射是否具有这些性质3.掌握逆映射的含义，复合映射的定义及性质二、重点与难点分析1.重点：理解和判断映射的三种性质，逆映射，复合映射2.难点：映射三种性质的判断，复合映射的性质三、教学内容与教学过程1.习题讲解（10分钟）2.上讲内容回顾（3分钟） 集合的概念：集合、元素、集合的表示方法集合间的关系：子集、幂集、n元组、笛卡尔积(1)映射的定义（15分钟） 定义：对于A,B,若存在对应法则f，对于，唯一的与它对应，称f是A到B的一个映射或一个函数。记为：f:AB （图示） 例：Ceiling function Floor function 取整函数 定义域：自变量x的取值范围 值域：函数值y的取值范围 像：为X在映射f下的像原像：为Y在映射f下的原像注：全函数即=A；为x在映射f下的像：A到B的所有映射组成的集合定理1-6：|A|=m,|B|=n,则（证明）(2)映射的性质单射(一对一映射)（10分钟） 定义：，可推出x1=x2 或 ，若x1x2，可得出 例1-6：设则f是N到N的单射，试证明之。 证：对于，由得出，进而x1=x2 (使用定义证明)满射（10分钟）定义：对于，使得y=f(x) 充要条件：=B 例1-7：设，则f是Z到N的满射，试证明之。 证：对于取,显然有 （使用定义证明）双射（一一对应）（5分钟）定义:既单射又满射例1-8例1-9：建立一个（0,1）到R的一一对应解： 置换：A到A的双射(3)逆映射（逆函数，反函数）（10分钟）定义：f:AB，将f的方向逆转后，得到的集合B到集合A的映射定理1-7：f的逆映射存在的充要条件是f是双射（加以说明解释） 注：若f是双射，则也是双射，且 例1-11：判断所给出的映射是否有逆射，若有，求出其逆映射 解：f(2)=f(-2)=4, 根据单射定义知f不是单射，进而其不是双射，根据定理1-7知其不存在逆映射 显然g是双射，其逆映射为(4)复合映射（20分钟） 定义:设对于，令，则h是A到C的映射，h为f和g的复合映射或复合函数，记为（图示） 注： 条件: 例1-12 例1-13 注：一般来说即使和都有意义，也不能保证成立 恒等映射(IA)： 定理1-9：若是双射，则 若是双射，则定理1-10： 若f和g是单射，则是单射（证明） 若f和g是满射，则是满射（证明） 若f和g是双射，则是双射且 定理1-11：设 若是单射，则f是单射，但g不一定（证明） 若是满射，则g是满射，而f不一定（证明） 定理1-12 设，则4. 教学小结（5分钟）本讲首先介绍了映射（函数）的定义及定义域、值域、像、原像等相关概念；接着介绍了映射的三种性质：单射，满射，双射；最后介绍了逆映射的定义及复合映射的定义及其具有的相关性质。四、 作业与实验（2分钟）1. 书面作业：习题1.2 1、2、6、11、14.2. 上机作业：无第三讲：集合、映射和运算（三）一、教学目标 1. 理解运算的定义2. 掌握运算的表示及常用运算3. 理解运算的性质并能判断具体运算是否具有某些性质二、重点与难点分析1.重点：运算的定义，运算的性质2.难点：运算性质的判定 三、教学内容与教学过程 1.习题讲解（5分钟）2.上讲内容回顾（5分钟） 映射的定义 映射的性质：单射，满射，双射 逆映射 复合映射3.进入主题，开始第二讲。本讲知识点概括(1)运算的定义（25分钟） 定义:设和B是集合，若，称f为到B的n元运算。 A到B的n元运算，或A上的n元运算： A上的n元封闭运算（代数运算）： ，有例：判定取绝对值运算|、加法运算+、取大运算max是否是自然数集合N(Z)上的代数运算。解： 例：判定减法运算-,取小运算min是否是自然数集合N上的代数运算。解： 例：判断数的加法运算是否是集合A=2n |nN上的代数运算？解： 例：将十进制数273转换成八进制解： 273=, , 模运算定义：，是使成立的整数r,即x除以m的余数。例：16(mod 3)、-8(mod 5)、9(mod 2)模m加法，模m乘法 例：m=5, 最大公约数，最小公倍数若d|m且d|n,则d是m,n的公约数，用gcd(m,n)表示m,n的最大公约数若m|d且n|d，则d是m,n的公倍数，用lcm(m,n)表示m,n的最小公倍数。注：Gcd与lcm分别记为,和（，）gcd(m , n)= gcd(|m| ,| n|)且lcm(m, n)=lcm(|m|, |n|)素因数分解：（对于大于1的正整数n都可以分解成一些素数乘积） Euclid算法 例1-19若gcd(m,n)=1,称m和n互素。欧拉函数：表示小于等于n且与n互素的正整数的个数运算表给定集合A，则集合A上的1元或2元运算可以用运算表来表示例：A=a,b,c,*abcabcababccbca思考：A上的封闭的1元，2元，3元运算的个数是多少？33 39 327 (2)运算的性质 对合性（5分钟） 定义：设*是A上的一元代数运算， 例： ？幂等性（5分钟） 幂等元：定义：A中的每个元素对于*都是幂等元例：*123112322323313例：交换性（5分钟） 定义：对于A上的二元运算*,均有 例：R上的+具有交换性 R上的-，映射的复合运算?结合性（5分钟） 定义： 例:映射的复合运算具有结合性 R上的+具有结合性 R上的- ？单位元素（幺元素）（5分钟） 定义：对于A上的二元运算*，使得对于 例：R关于加法运算+的单位元素是0 R关于乘法运算的单位元素是1 R关于减法运算-的单位元素是？定理1-3：若A关于* 有单位元素，则单位元素是唯一的证明：设e1,e2是A关于*的单位元素，则e1=e1*e2=e2零元素（5分钟） 定义：对于A上的二元运算*，使得对于 例:R关于乘法运算的零元素是0 R关于减法运算-的零元素是？ R关于加法运算的零元素是？定理1-4：若A关于* 有零元素，则零元素是唯一的证明：设e1,e2是A关于*的零元素，则e1=e1*e2=e2逆元素（5分钟）前提：A关于二元运算*有单位元素e定义：，使得：例：R上的加法运算+：x+(-x)=0=(-x)+x R上的乘法运算： 注：逆元不一定存在，存在不一定唯一，参见表1-5定理1-5：若A关于*运算有单位元素为e且*运算满足结合律，若对于A中的x有左逆元y与右逆元z，则y=z,此逆元唯一证明：y*x=e,x*z=e y=y*e=y*(x*z)=(y*x)*z=e*z=z消去性（分钟） 定义：若A关于*有零元，则记为，对于，若 例1-31 Z上的加法运算+和乘法运算均满足消去律.分配性（5分钟） 定义：是A上的两个二元运算，对于 则称*关于是可分配的吸收性（2分钟） 定义：是A上的两个二元运算，对于则称*关于是可吸收的德摩根律（3分钟） 定义：是A上的一元运算，是A上的两个二元运算，对于4. 教学小结（3分钟）本讲首先介绍了运算的定义并介绍了几种常用的运算，接着介绍了运算的性质：对合性、幂等性、交换性、结合性、单位元素、零元素、逆元素、消去性、分配性、吸收性、德摩根律，并结合之前所学知识讲解运算的性质。 四、 作业与实验（2分钟）1. 书面作业：习题1.3：1、3、5、6、8 2. 上机作业：无第四讲：集合、映射和运算（四）一、教学目标1.掌握集合的各种运算2.理解各种集合运算所满足的性质3.掌握集合的划分与覆盖的概念4.了解集合的对等，集合的基数，可数集合等概念 二、重点与难点分析1.重点：集合的运算并、交、补、差、对称差 集合运算性质 2.难点：集合运算等值式的证明，集合的对等、基数三、 教学内容与教学过程1.上讲内容回顾（5分钟）运算的定义运算的性质：对合性、幂等性、交换性、结合性、单位元素、零元素、逆元素、消去性、分配性、吸收性、德摩根律2.进入主题、开始第四讲本讲知识点概括(1)集合的运算并运算（15分钟） 定义： 定理1-16：是包含A和B的最小集合 定理1-17：并运算满足的性质： （交换律） （结合律） （幂等律）（是运算的单位元素）（是运算的零元素）例1-38:设f : A B, X, Y A, 则证明：证明： 交运算（15分钟） 定义： 定理1-18：是包含在A和B的最大集合定理1-19：交运算满足的性质： （幂等律） （交换律） （结合律） （是运算的零元素）（U是运算的单位元素） 例：定理1-20：并运算与交运算之间满足的性质： 例1-41：证：补运算（10分钟） 定义：例1-42：（A的补集依赖于全集U的选取）A=a,b,cU=a,b,c,d 定理1-21：定理1-22：德摩根律：P25： 差运算（10分钟）定义：例1-43：定理1-23：证明：例1-45：证明： 证：例1-46：例1-47： 对称差运算（10分钟）定义：例定理1-24：容斥原理形式： 或： 例：求1到1000之间（包含1和1000在内）既不能被5和6整除数有多少个？ 解： |S| = 1000 |A|=1000/5=200, |B|=1000/6=166 |AB| = 1000/lcm(5,6) = 1000/33 = 33 （2）集合的划分与覆盖（12分钟） 划分定义：其中：例1-53： 设A = a, b, c, 则A的所有不同的划分分别为: 覆盖设A是集合, 由A的若干非空子集构成的集合称为A的覆盖, 如果这些非空子集的并等于A.（3）集合的对等（10分钟）定义：A B 存在双射f : A B.例：(0, 1) R 集合的基数：无限集合A 若集合A和B对等, 则称这两个集合的基数相同.例：可数集合：能与自然数集合N对等的集合3. 教学小结（2分钟）本讲首先介绍了集合的各种运算（并，交，补，差，对称差）及其满足的性质，接着介绍了集合的划分与覆盖的概念；最后介绍了集合对等、集合的基数及可数集合。四、 作业与实验（1分钟）1. 书面作业： 习题1.4 5、8、10、13. 习题1.5：1、7 2. 上机作业：无第五讲：关系（一）一、教学目标1. 掌握关系的概念尤其是二元关系的概念2. 掌握关系的定义域和值域3. 掌握关系的三种表示方法4. 理解函数的关系定义二、重点与难点分析1.重点：二元关系概念、关系的三种表示方式、函数的关系定义2.难点：关系的概念三、 教学内容与教学过程1.习题讲解（15分钟） 2.上章内容回顾（5分钟）集合的有关概念映射的有关概念运算的定义与性质集合的运算、集合的划分与覆盖、集合的对等3.进入主题，开始第五讲本讲知识点介绍(1)关系的定义关系的概念（15分钟）引例：A = 张三, 李四, 王五;B = 英语, C语言, 离散数学, 数据结构, 汇编语言;C = 优, 良, 合格, 不合格.A与B之间的关系R = (张三, 离散数学), (张三, 数据结构), (张三, 英语), (李四, 数据结构), (王五, C语言), (王五, 汇编语言) A B.A, B与C之间的关系S = (张三, 离散数学, 优), (张三, 数据结构, 良), (张三, 英语, 优), (李四, 数据结构, 优), (王五, C语言, 合格), (王五, 汇编语言, 良) A B C.定义：是集合， ，则R为间的n元关系特别的 为A上的n元关系注（两层含义）：集合、关系例：A=王，李，张，黄，B=100米，400米，铅球，跳远，C=第一名，第二名，第三名，优秀奖R=(王，100米，第二名)，（李，铅球，优秀奖），（张，100米，第一名），（黄，跳远，第二名）二元关系的定义：两个集合A和B（可以相同）之间的关系称为二元关系 A到B的关系： A上的关系：例：A=甲，乙，丙 R=(乙，甲)，（乙，丙），（甲，丙） 注：(x,y)表示x胜y例：A=张三，李四，王五，B=教师，辅导员，导师 R=（张三，辅导员），（张三，教师），（李四，教师），（王五，导师），（王五，教师）例2-1： 例：A=a,b,R是P(A)上的包含关系，R=(x,y)|x,yP(A)且P(A)= 注意：关系的次序定理2-1：若，则A到B的关系有 若，则A上的关系有注：A到B的关系是AB的子集三种特殊的关系（5分钟）空关系：A到B的空关系 A上的空关系全关系：A到B的全关系 A上的全关系恒等关系： 例：A=0,1,2 =(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2) IA=(0,0),(1,1),(2,2)关系符号（10分钟）定义：若(x,y) ,则可记为 例：实数集合R上的大于“”关系： 例：整数集Z上的整除关系“|” 整除性质：例：模m同余关系 性质：关系的定义域和值域（5分钟）定义域:设,即R中所有有序对中第一位置元素组成的集合, 它显然是A的子集.值域：设R AB, ran R = y|yB, 存在xA, 使得(x, y) R, 即R中所有有序对中第二位置元素组成的集合, 它是B的子集.例2-10 ： R= (1, 1), (1, 3), (2, 2), (2, 4), (3,1), (3, 3), (4, 2), (4, 4), 则dom R = 1, 2, 3, 4，ran R = 1, 2, 3, 4. (2) 关系的表示（20分钟）集合表示法列举法：把关系内部的元素全部列举出来描述法：把关系内部成员的性质描述出来（同集合）关系图表示法情形1 R是A到B的关系A = a, b, c, d, B = 1, 2, 3, R = (a, 2), (a, 3), (c, 2), (d, 2).情形2 R是A上的关系A = a, b, c, d， 注：有向边关系矩阵表示法定义：例2-13: A = a, b, c, d, B = 1, 2, 3, R = (a, 2), (a, 3), (c, 2), (d, 2).例：A=a,b,c,(3)函数的关系定义（5分钟）函数到关系的转换例：A = a, b, c, B = 1, 2, 3, f: A B, f(a) = 2, f(b) = 3, f(c) = 3.关系能够转换成函数的条件 例：，不能转换成函数。 例2-164. 教学小结（3分钟）本讲首先讲解关系的概念与表示，特别介绍了二元关系，同时描述了三种特殊的关系：空关系、全关系、恒等关系，然后讲解了关系的三种表示方式：集合表示法、关系图表示法、关系矩阵表示法，接着讲解了关系与函数的区别与联系及它们间的转换。四、 作业与实验（2分钟）1. 书面作业：习题2.1： 2、4(2)(4)(5)、13、14.2. 上机作业：无第六讲：关系（二）一、教学目标 1. 掌握关系的集合运算2. 掌握关系的逆运算，逆关系的关系矩阵、关系图及逆关系的定理3. 掌握复合关系、复合关系相关定理 4. 了解函数的复合运算二、重点与难点分析1.重点：复合关系、逆关系的概念及相关性质2.难点：复合关系、逆关系的性质三、 教学内容与教学过程1.习题讲解（10分钟）2.上讲内容回顾（5分钟）N元关系的定义2元关系关系的定义域与值域关系的表示函数的关系定义3.进入主题，开始第六讲。 (1)关系的集合运算（15分钟） 关系的几种常见集合运算: 注： 解：例2-17(2)关系的逆运算（20分钟） 为何考虑关系的逆运算? 若x是y的老师,则y是x的学生, 定义：注：就是将所有R中的有序对中的两个元素交换次序，例2-18：A = a, b, c, d, B = 1, 2, 3, R = (a, 3), (c, 2), (a, 2), (b, 2). 则逆关系的关系图 有向线条反向（图示例2-18）逆关系的关系矩阵 原关系的关系矩阵的转置（示例2-18） 逆运算的性质：定理2-2：（对合律）定理2-3：逆运算与关系的集合运算并, 交, 补的关系 证明：（）：(3)关系的复合运算（35分钟）为何考虑关系的复合运算? 若x是y的母亲, y是z的妻子, 则x是z的岳母, 关系R到关系S的复合运算（10分钟）例：，则：例2-19：借助关系图理解复合运算： 关系矩阵：复合关系的性质（10分钟）R S S R.例：R =(x,y)|x,yA, y = x+1或y = x/2S =(x, y)| x,yA, x = y +2定理2-4： 证明思路： 定理2-5： 定理2-6： 证明： 注：本性质与矩阵的有关运算性质类似, 请注意顺序定理2-7：幂运算（10分钟） 幂的表示方式：例2-23： 设A=a,b,c,集合A上的关系R=(a,b),(b,c),(c,a),试计算幂运算的性质：函数的复合运算（5分钟）设f: A B, g: B C,函数f与函数g的复合记为fg: 若f (x) = y且g(y) = z, 则(fg)(x) = g(f(x) = z. 由于f A B, g B C, 关系f与关系g的复合记为fg: 若(x, y) f且(y, z) g, 则(x, z) fg.注：函数f与函数g的复合fg与将其看作关系时关系f与关系g的复合是一致的4. 教学小结（3分钟）本讲分别介绍了关系的集合运算、逆运算，复合运算，并且对复合关系、逆关系的定义、表示方式、相应的关系矩阵进行了讲解，还介绍了它们之间满足的相关性质，最后介绍了函数的复合运算。四、 作业与实验（2分钟）1. 书面作业：习题2.2 1、3、6、8、12(选).2. 上机作业：无第七讲：关系（三）一、教学目标1. 理解关系的各种性质2. 掌握满足各种性质的关系的关系矩阵和关系图3. 理解闭包的含义4. 掌握闭包的几个关键5. 掌握闭包的构造二、重点与难点分析1.重点： 自反性、反自反性、对称性、反对称性、传递性概念的理解，闭包的理解与构造2.难点：同上三、教学内容与教学过程1.上讲内容回顾（5分钟）关系的集合运算关系的逆运算关系的复合运算2.进入主题，开始第七讲本讲知识点概括 (1)关系的性质 自反性（10分钟）定义：对于集合A上的元素a属于A，有(a,a)属于R,那么R就是一个自反关系例2-25： A = a, b, c, d, R = (a, a), (a, b), (b, b), (c, c), (c, a), (d, d)?注：Z上的整除关系|是自反的; P(X)上的包含关系是自反的; R上的小于等于关系是自反的; R上的小于关系不是自反的. 定理：R自反 注：空关系是空集上的自反关系. 关系矩阵：对角线元素都为1关系图：结点含有环 反自反性（10分钟）定义：设R A A, 若对于任意x A, 均有(x, x) R, 则称R是A上的反自反关系, 或称R具有反自反性.例2-26： A = a, b, c, d, R = (b, a), (a, b), (b, c), (c, d), (c, a)?注：Z上的整除关系|不是反自反的; P(X)上的包含关系不是反自反的; R上的小于等于关系不是反自反的;R上的小于关系是反自反的.定理：R反自反 注：空关系是空集上的反自反关系.关系