离散数学教案全案设计--教案.学案

1、 滁州学院计算机与信息工程学院课程教案课程名称： 离散数学授课教师： 赵欢欢授课对象：11级网络工程专业 3、4班授课时间：2012年9月-2012年12月滁州学院计算机科学与信息工程学院2012年8月离散数学 教学大纲（ Discrete Mathematic）课程代码： 学时： 48 学分： 3一、课程简介本大纲根据 2009 版应用型人才培养方案制订。（一）教学对象：网络工程、计算机科学与技术专业本科学生（二）开课学期：第三学期（三）课程类别：专业基础课（四）考核方式：考试（五）参考教材：离散数学第 2 版 邓辉文 清华大学出版社 2010. 主要参考书目：邵学才，叶秀明离散数学M.北京

2、电子工业出版社，2009.邵志清，虞慧群.离散数学M.北京电子工业出版社，2003.屈婉玲.离散数学习题解析M.北京大学出版社，2008.本课程的先修课程是高等数学、线性代数，后续课程包含数据结构、数据库原理 及应用、操作系统、数字逻辑、人工智能、算法分析与设计等。二、教学基本要求与内容安排（一）教学目的与要求离散数学是研究离散量的结构及其相互关系的学科 ,它在各学科领域特别在计 算机科学领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程必 不可少的先行课程。本课程的教学目的旨在通过对离散数学的教学，让学生不但可以掌握处理如 集合、代数结构和图等离散结构的描述工具和方法，为后续课程的

3、学习创造条件， 而且为学生今后提高专业理论水平，从事计算机行业的实际工作提供必备的抽象 思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基 础。（二）教学内容安排教学内容教学教学重点难点学时分配备注要求方法()()讲课实 验上 机苴丿、他第一部分数理逻辑讲授15.51命题逻辑的基本概念21.1命题与联接词B11.2命题公式及其赋值A12命题逻辑等值演算3.52.1等值式B122析取范式与合取范式A12.3联接词的完备集C0.52.4可满足性与消解法B13命题逻辑的推理理论23.1推理的形式结构A13.2自然推理系统PB14一阶逻辑基本概念24.1 一阶逻辑命题符号化A14.

4、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双射函数与集合的基 数CA13.4 个电话系统的描述 实例CA14集合

5、论在计算机中的应 用2第三部分代数结构讲授61.51代数系统31.1二元运算及其性质A11.2代数系统A11.3代数系统的同态与同 构BA12群与环32.1群的定义及其性质A12.2循环群与置换群AA2第四部分图论讲授121图的基本概念2.51.1图A0.51.2连通与回路A0.51.3图的连通性A0.51.4图的矩阵表示A0.51.5图的运算AA0.52欧拉图与哈密顿图22.1欧拉图A0.52.2哈密顿图A0.52.3最短路问题与货郎担 问题CA13树1.53.1无向树及其性质A0.53.2生成树A0.53.3根树及其应用B0.54平面图34.1平面图的基本概念B0.54.2欧拉公式B0.5

6、4.3平面图的判断B14.4平面图的对偶图C15图论在计算机中的应用3（教学要求：A熟练掌握；B掌握；C了解）三、实验内容本课程无实验制订人（签字）：学进审核人（签字）：教度表20122013学年第1学期授课教师姓名赵欢欢职称助教周数 16周计划学时48学时授课专业网络工程班级2011 级讲课48学时课堂讨论0学时课程名称离散数学实验课 0 学时习题课 0学时教材名称离散数学其他环节0学时出版社清华大学出版社-周学时中 其要称 名摘的验容实内趴等要学绸容教仙 的 述 讲 名 节 章 z(周次 日期讲课实验课习题课课堂讨论其他环节日周3 9一9M一44rT 只 映 耳R合 L 复 删元！I L

7、映 n映、 、 二二 合 合用 集隼集加 讲念幕5念卿 第S第哉 基、有的 厶口合集射映 集：映： 1论 2论 1理仁理日16510月日 第鋼22-集伽 讲质才 三性4 第和曲日2344关 划 、 妁 或 等合 值 OM集 炜 合第 义 叩集运 定 (B5本合 的 算力基集 系 等数-)关 郃笛补垛讲 2 集集茫htx .5差可第儿系 呻亠处w扯佞 第算车伽念系数 运的集概朕函 的合、的元、 合集盖系门赤 集：覆关表 4论与 1论的 1理分 2理系日30 周24月日 四月9 第9至22算 运 二合 (-复 系、 关算运 讲逆 六第氯 1 2理日7 周1月 五月10日 第10至44的XI 称低

8、)对S 三、包 z( 三可 系包反加 关闭自押 的反区 讲系、八 七关性低 第4反r 2自包 质恍 性的自 的系E; 假系关酬 灿关 万 3 7 国 2理日14 周8月 六月O日 第鋼22四骨“ 士糸 Z/IX分闿-一介一匸 系7 ;殊 关2类特价的 讲系等中 八关集 第W-厶库系图 系关斯 仆杯哈 等：儿 5论定 2理的日21讪150M日第1OM144一司3二命 Z/IX、. Z/IX 辑祇瀝辑低 逻单命 逻 号 题塑再题符 命遇命矽 讲33、讲#0 九值断十表、 第真判第值义 念与的真定 概义假 其的 关定真及式型 有的,式公类 的题义公题的 题命含题命式 命：的命公 1论词 3论题 3理

9、接 3理命系主任签名：院长签名：第八周10月22日 至10月28日22第一讲 命题逻辑（三）3.4逻辑等值的命题公式理论：逻辑等值的定义、基本等值式、等值演算法、对偶原 理第九周 10月29日 至11月4日44第十二讲命题逻辑（四）3.5命题公式的范式 理论：命题公式的析取范式和合取范式的定义域求法 命题公式的主析取范式及主合取范式的定义和求法 第十三讲命题逻辑（五）3.7命题逻辑中的推理理论：推理形式有效性的定义；基本推理规则；命题逻辑的自然推理系统第十周11月5日 至11月11日22第十四讲谓词逻辑（一）4.1个体、谓词、量词和函词理论：谓词逻辑概念，谓词的概念与表示，量词的概念与表示，

10、个体域，辖域，约束变元和自由变元的含义%144第十五讲谓词逻辑（二）4.2谓词公式及命题的符号化4.3谓词公式的解释及类型理论：谓词公式的定义，将命题用用符号（个体，量词，谓词） 来表示，消去量词的逻辑等值式，永真式，科满足式，永假式及中性式的概念第十六讲谓词逻辑（三）4.4逻辑等值的谓词公式4.5谓词公式的前束范式理论：谓词公式等值的定义，基本等值式，前束范式第十11 日至18 日一周 月12 11月第十二周11月19日 至11月25日22第十七讲图论（一）6.1图的基本概念 6.2节点的度数6.3子图，图的运算和图 同构理论：图的定义，邻接，关联，简单图，节点的度数，子图第十三周11月26

11、日 至12月2 日44第十八讲图论（二）6.4路与回路6.5图的连通性理论内容：路，回路，无向图的连通性，无向连通图的点连通 度与边连通度，有向图的连通性第十九讲图论（三）6.6图的矩阵表示 6.7赋权图及最短路径 理论内容：图的邻接矩阵，可达矩阵，关联矩阵，赋权图，最 短路径第十四周12月3日 至12月9日22第二十讲图论（四）7.1欧拉图理论内容：欧拉图的有关概念，欧拉定理，中国邮递员问题、Hamilt on 图第十五周 12月8日 至12月16日44第二十一讲图论（五）7.2无向树 7.3有向树理论内容：树的基本概念，最小生成树，二叉树的遍历与表 达式的计算第二十二讲代数结构（一）5.1

12、代数结构简介理论内容：代数结构的定义，半群及独异点，子代数，代数结 构的同态与同构第十六周12月17日 至12月23日22第二十三讲代数结构（二） 5.2群的定义及性质理论内容：群的有关概念，子群，群的冋态第十七周12月24日 至12月30日22第二十四讲 总复习说明： 1本教学进度表由主讲教师负责填写， 于每学期开学第一周内送交教师所在系， 经领导审定、 签字后备查2此表一式三份，其中，任课教师一份，教师所在系一份，教务处一份。第一讲：集合、映射和运算（一）一、教学目标掌握集合的概念与表示理解子集、幂集、 n 元组与笛卡儿积的概念掌握子集，幂集，笛卡尔积的求法二、重点与难点分析重点：集合的概

13、念，子集，幂集，笛卡尔积的概念及求法难点：幂集三、教学内容与教学过程进行自我介绍（ 5 分钟） 姓名，联系方式，专业方向。建议学生用电子邮件方式联系。进行课程简介（ 10 分钟） 离散数学是研究离散量的结构及相互之间关系的学科 是一门专业基础课，是数据结构、操作系统、计算机组成原理、数据库原理 等课程的数学基础。特点：知识点集中，概念，定理多；方法性强；学数学就要做数学 成绩评定：平时成绩 （ 到课情况，书面作业，平时测验 ）占 30%,期末考试占 70%进入主题，开始第一讲（1）集合的有关概念 （20 分钟 ）集合 定义：集合是具有某种特定性质的对象汇集成的一个整体，通常用大写字 母 A,B

14、,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,空集._ 元素与集合x A 或 X A|A|表示集合A中的元素个数注意：集合中的元素可以是集合，如A=a,a,b,b,c,|A|=4,a,b A注：集合中的元素无顺序；集合中无重复元素例：指出下列哪些是集合，哪

15、些不是集合？中国人的集合；百货商店里好看的花布的集合；1000以内的素数的集合；26个英文字母组成的集合；这个班里高个子学生的集合；直线y= 2x-5上的点的集合。（2）集合之间的关系子集（15分钟）定义：若A中的任意元素都属于B,则A是B的子集，称A包含于B或B包 含A, AGB ,包括的两层含义：包含与真包含（ 心B）, Au B , A是B的真子集注意：属于（元素与集合的关系）与包含于（集合与集合的关系）的区别例：A=1,2,3,4 , B=2,4B工A或A = B定理1-1 ：、 A定理1-2 : （1）A5 A;（自反性）（2）A - B, B - A,则 A=B（3）A B,B C

16、,则 A C （传递性）用定义进行证明定理1-3 : A=B的充要条件是A B,B A注：该定理是证明两个集合相等的基本方法 该定理与定理1-2中的（2）的区别例1-2注：A中有一个元素不属于C,则A二C ,反证法是一种很好的方法 幕集(15分钟)定义：由X的所有子集组成的集合，P(X)二A|A X例：x=1,2P(X) =._ ,1,2, 1,2，Y=a,b,cP(X)珂、,a, b, c, a, b, a,c, b,c, a,b,c例1-3注：若|X|=n,P(x)的元素有：-；由一个元素构成的子集；由两个元素构 成的子集；由n个元素构成的子集计数的基本原理： 加法原理：图示乘法原理：图示

17、定理 1-4：若 |X|=n,|P(X)|=2n证明：n加法原理：二项式定理：(x y)n = 7 C；xryn 1 C1 C2 . C： C性(1 1)n =2n乘法原理：a2 2 . 2 = 2n.注：每个元素的参与与否构成不同的子集n元组(5分钟)定义：论域U中选取的n个元素按照一定的顺序排列，得到 n元有序组，称 n 元组，记为：(x1,x2,x3,xn)或例：平面直角坐标系中点的坐标是2元组；空间直角坐标系中点的坐标是3元组；n元组在数据结构中是一个表有序对，序偶：2元组注：(x,y)工(y,x)笛卡尔积(10分钟)定义：设A1，A2，.A.是集合，称(x1,x2，xn)|xAii

18、=1,2,n为A1,A2,An的笛卡尔积(直积，叉积)，记为：A1 A2，An例：A=a,b,B=1,2，例1-4注：A 一 - 一 A =：一一般来说，A B = B A定理 1-5：若 |A|=m,|B|=n,则 |A B|=mX n教学小结(5分钟)本讲首先介绍了集合的概念与表示方法，接着介绍了集合之间的关系一一子集与幂集， n 元组，笛卡尔积的概念及相关定理四、作业与实验（ 5 分钟）书面作业：习题 1.1 1 、 2、 3、 7、 10上机作业：无第二讲：集合、映射和运算（二）一、教学目标掌握映射的概念与表示理解映射的三种性质：单射、满射、双射，会判断某个具体映射是否具有 这些性质掌

19、握逆映射的含义，复合映射的定义及性质二、重点与难点分析重点：理解和判断映射的三种性质，逆映射，复合映射难点：映射三种性质的判断，复合映射的性质三、教学内容与教学过程习题讲解（10分钟）2上讲内容回顾（3分钟）集合的概念：集合、元素、集合的表示方法集合间的关系：子集、幕集、n元组、笛卡尔积（1）映射的定义（15分钟）定义：对于A,B,若存在对应法则f,对于A，唯一的r B与它对应, 称f是A到B的一个映射或一个函数。记为：f:A f B （图示）例: Ceiling functionf ： g = g Q fFloor functionx取整函数xl定义域：自变量x的取值范围domf值域：函数值

20、y的取值范围ranf像：f （X）二f （x）X X为x在映射f下的像1 _原像：f （X）二x| f（x）丫为丫在映射f下的原像注：全函数即domf =A y= f（x）为x在映射f下的像AB =f I f :A B : A到B的所有映射组成的集合定理 1-6 : |A|=m,|B|=n,贝U BA = nm （证明）映射的性质单射（一对一映射）（10分钟）定义：-x1,x2 A，f（x1） = f（x2）可推出 x仁 x2或一x1,x2 A，若 x1 工x2，可得出 f（x1）=f（x2）例1-6 :设f :N N, f （x2x,则f是N到N的单射，试证明之。 证：对于_x1，x N，由

21、f（x1）=f（x2）得出2昭=厶2，进而x仁x2（使用定义证明）满射（10分钟）定义：对于y B，A，使得y=f（x）充要条件：ranf =B例1-7 :设f :Zt N, f (x) =|x，则f是Z到N的满射，试证明之。 证：对于- y三N,取x = y三Z，显然有y = f (x)(使用定义证明)双射(一一对应)(5分钟)定义:既单射又满射例1-8例1-9 :建立一个(0,1 )到R的对应解：f : (0,1) R, f(x)二 tan(x 一 1/2)二置换：A到A的双射逆映射(逆函数，反函数)(10分钟)定义：f:A -B,将f的方向逆转后，得到的集合 B到集合A的映射f J 定理

22、1-7 : f的逆映射存在的充要条件是f是双射(加以说明解释)注：若f是双射，则f也是双射，且(f二f例1-11 :判断所给出的映射是否有逆射，若有，求出其逆映射f : R R, f (x x2g : R R, f(x) =x3解： f(2)=f(-2)=4,根据单射定义知f不是单射，进而其不是双射，根据定理1-7知其不存在逆映射显然g是双射，其逆映射为g:R R,g(y) = 3y复合映射(20分钟)定义:设 f :A B,g： B C,对于一 x A，令 h(x)二 g(f(x)，则 h 是 A 到C的映射，h为f和g的复合映射或复合函数，记为f g (图示) 注：(f ：g)(x)二 g

23、(f (x)条件：f(A)dom(g)例 1-12例 1-13注：一般来说即使f g和g f都有意义，也不能保证f g = g f成立恒等映射(I a) : f ： A A, f (xx定理1-9 :若f ： A * B是双射，则f0fl：f7f B若 f ： at A是双射，则 f 0 f = f f = Ia定理 1-10 : f : A B,g： B C若f和g是单射，则f?g是单射（证明） 若f和g是满射，则f?g是满射（证明）若f和g是双射，则 仁9是双射且（f g）二gOf定理 1-11 :设 f : A B,g： B C若f ?g是单射，则f是单射，但g不一定（证明）若fJg是满

24、射，则g是满射，而f不一定（证明）ABc定理 1-12 设 f：AT B,g:BTC,h:CT D，贝(f(3g)0h=fC(g0h)教学小结（5分钟）本讲首先介绍了映射（函数）的定义及定义域、值域、像、原像等相关概念; 接着介绍了映射的三种性质：单射，满射，双射；最后介绍了逆映射的定义及复 合映射的定义及其具有的相关性质。四、作业与实验（2分钟）书面作业：习题1.2 1、2、6、11、14.上机作业：无第三讲：集合、映射和运算（三）一、教学目标理解运算的定义掌握运算的表示及常用运算理解运算的性质并能判断具体运算是否具有某些性质二、重点与难点分析重点：运算的定义，运算的性质难点：运算性质的判定

25、三、教学内容与教学过程1习题讲解（5分钟）2上讲内容回顾（5分钟）映射的定义映射的性质：单射，满射，双射逆映射复合映射3进入主题，开始第二讲。本讲知识点概括运算的定义（25分钟）定义：设A1，A2，.，An和B是集合，若f:A1 A2 . AnB，称f为 A1，A2,., An 到 b 的 n 元运算。nA至U B的n元运算，或 A上的n元运算:a汇A.At bA上的n元封闭运算（代数运算）：nf：AA 汉 At A，V x1,x2,.x n A,有 f（x1,x2,.,x n） = y A例：判定取绝对值运算|、加法运算+、取大运算max是否是自然数集合N（Z） 上的代数运算。解：-x N

26、- 斗=x N- x, y N = x y NVx1, x 2 , .x n 4 m ax （ x1, 2x,n. N例：判定减法运算-,取小运算min是否是自然数集合N上的代数运算。解：例：判断数的加法运算是否是集合 A=2n |n N上的代数运算？解：21 - 22 =6Jn例：将十进制数273转换成八进制解：273=34 8 1,34 =4 8 2 ,=2 73= 3 4 8 1 （4 8）2） 81= 48+2 工8 +1273 =(421)8模运算定义. f : Z t N, f (x) = x(mod m) x(mod m)是使 x = qm+r,0 兰 r cm 成立 的整数r,

27、即x除以m的余数。例：16(mod 3)、-8(mod 5)、9(mod 2)模m加法，模m乘法x my 彳 x y( m o dm )x *m y =( x * y( m o dm )例：m=5, 3 5(-5) =3,3 5(-5) =0最大公约数，最小公倍数_m, 乙若d|m且d|n,贝U d是m,n的公约数，用gcd(m,n)表示m,n的最 大公约数_m, 乙若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|) 素因数分解：

28、(对于大于1的正整数n都可以分解成一些素数乘积) r1 r2rk一 出s, s2s _ -Hm = p/p；P/ Z ,n 二 p；P22piZ(Pk为素数，rk, sk为非负整数) gcd(m,n) = p,min( )p；in( r2，s2)pJn(rk，Sk) lcm(m,n)二卩罟心卩异心2).Euclid算法m 二q,nr,0:r,： n, n二 q?*咕0：r?：r,：n，r“ 二 qkiR一1 二qkrk = gcd(m, n) = mx ny例 1-19若 gcd(m,n)=1,称 m 和n互素。欧拉函数：(n)：表示小于等于n且与n互素的正整数的个数运算表给定集合A，则集合A

29、上的1元或2元运算可以用运算表来表示 例：A=a,b,c,*abcabcababccbca思考：A上的封闭的1元，2元，3元运算的个数是多少?33 39327运算的性质对合性（5分钟）定义：设*是A上的一元代数运算，“（“x）=x,A.例：-x R: _（-x） = x（A）二二 A,（AT）T = AI x| = x ？幕等性（5分钟）幕等元：x* x = x,x A定义：A中的每个元素对于*都是幕等元例：*123112322323313例：R, *?交换性（5分钟）定义：对于A上的二元运算*, -x, y A,均有x” y = y ” X, 例：R上的+具有交换性R上的-，映射的复合运算f

30、jg?结合性（5分钟）定义：-x, y, z A: （x y） z = x （y z）.例:映射的复合运算（f g）Qh二f （g h）具有结合性R上的+具有结合性R上的-?单位元素（幺元素）（5分钟）定义：对于A上的二元运算*， e，使得对于-xx e 二 x.e x 二 x.例：R关于加法运算+的单位元素是0R关于乘法运算的勺单位元素是1R关于减法运算-的单位元素是？定理1-3：若A关于*有单位元素，则单位元素是唯一的 证明：设e1,e2是A关于*的单位元素，则e仁e1*e2=e2零元素（5分钟）定义：对于A上的二元运算*，二，使得对于x日*x=T x*日=0例:R关于乘法运算的零兀素是0

31、R关于减法运算-的零兀素是？R关于加法运算的零兀素是？定理1-4:若A关于*有零元素，则零元素是唯一的证明：设e1,e2是A关于*的零元素，贝U e仁e1*e2=e2逆元素(5分钟)前提：A关于二元运算*有单位元素e定义：x A, y A，使得：x y = e. y x = e.例：R上的加法运算+: x+(-x)=O=(-x)+x TOC o 1-5 h z 一 11R上的乘法运算: x = 0, x1xxx注：逆元不一定存在，存在不一定唯一，参见表 1-5 定理1-5：若A关于*运算有单位元素为e且*运算满足结合律，若对于 A 中的x有左逆元 y与右逆元 z,贝U y=z,此逆元唯一证明：

32、y*x=e,x*z=ey=y*e=y*(x*z)=(y*x)*z=e*z=z消去性(分钟)定义：若A关于*有零元，则记为v，对于-x, y, A，若x -x y = x z= y = z. y x 二 z x 二 y = z.例1-31 Z上的加法运算+和乘法运算均满足消去律.分配性(5分钟)定义：*,】是A上的两个二元运算，对于 x, y, z Ax (y z) = (x y) (x z). (y z) x = (y x) (z x). 则称*关于是可分配的吸收性(2分钟)定义：*,是A上的两个二元运算，对于-x,y, Ax (x y)二 x. (y x) x = x.则称*关于是可吸收的德

33、摩根律(3分钟)定义：是A上的一元运算，是A上的两个二元运算，对于x,y,z A(x y) =(% (y).*(x y)=(叹)(y).教学小结(3分钟)本讲首先介绍了运算的定义并介绍了几种常用的运算，接着介绍了运算的性 质：对合性、幕等性、交换性、结合性、单位元素、零元素、逆元素、消去性、 分配性、吸收性、德摩根律，并结合之前所学知识讲解运算的性质。四、作业与实验（ 2 分钟）书面作业：习题 1.3： 1、3、5、6、8上机作业：无第四讲：集合、映射和运算（四）一、教学目标掌握集合的各种运算理解各种集合运算所满足的性质掌握集合的划分与覆盖的概念了解集合的对等，集合的基数，可数集合等概念二、重

34、点与难点分析重点：集合的运算一一并、交、补、差、对称差集合运算性质难点：集合运算等值式的证明，集合的对等、基数三、教学内容与教学过程1上讲内容回顾（5分钟）运算的定义运算的性质：对合性、幕等性、交换性、结合性、单位元素、零元 素、逆元素、消去性、分配性、吸收性、德摩根律2进入主题、开始第四讲本讲知识点概括（1）集合的运算并运算（15分钟）定义：A-B=x|x A或 x B.定理1-16 : A _ B是包含A和B的最小集合WC A,C：Bn C：AuB定理1-17 :并运算满足的性质：A _ B 二 B _ A （交换律）（A - B） - C = A - （B - C）（结合律）A. A二A

35、 （幕等律）A - 一 一 - A = A （.一是u运算的单位元素）A-U=U-A=U （ U是U运算的零元素）例 1-38:设 f : A B, X, Y A,则证明：f（X Y）二 f（X） 一. f（Y）:X X _ Y= f(X) f (X _ Y)证明：Y X 一 丫二 f (Y) f (X 一 Y) .f(X)_.f(Y) f(X 一 丫)-b f(X 一 Y)= a (X 一 Y): b = f (a) a X 二 b 二 f(a) f (X)a Y二 b = f (a) f (Y).b f(X) 一 f(Y)f(X Y) f(Xh，f(Y)交运算(15分钟)定义：A B 二x

36、|x A且x BcuM c 厅=4 * E = AB定理1-18 : A、B是包含在A和B的最大集合.一 C 三 A,C - B = C - A 一 B定理1-19 :交运算满足的性质：AA二A （幕等律）A r B二B r A （交换律）（A B） C=A （B C）（结合律）A* （、是运算的零元素）A - U二U二A （ U是运算的单位元素）例：定理1-20 :并运算与交运算之间满足的性质：A _ （A - B） =A（一.对 可吸收）A、（A_. B） 对一可吸收）A 一（B 一 C） =（A_. B厂（A_. C）（_.对-可分配）A 一（B 一 C）二（A 一 B） 一 （A 一

37、C）（-对一.可分配）例 1-41 : A - B ：= AB 二 A ：= A B 二 B 证：A 二 B ：= A B = BB A 一 Bx A - B,x A,由于 A-B= x B补运算（10分钟）定义：A 二 Cu（A）U例1-42 : （A的补集依赖于全集U的选取）A=a,b,cU=a,b,c,d二 A 二dU =a,b,c,d,a,b,b,c, c二 A=d,a,b, b,c, c定理1-21 :定理1-22 :德摩根律:P25: 一厂，运算的重要性质差运算（10分钟）定义：A-B=x|x A且x- E例 1-43 :a,b,c -b,c,d,e f二a b,c,d,e, f

38、-a,b,c =d,e, f定理 1-23 : A -B 二 A B证明：x A-B= x A,x - B二 x A,x B = x AB 例 1-45 :证明：（A -B） -C =A-（B C）例 1-46 :A B 二 A - B 二一例 1-47 :（A -B） _ （A -C） =（AB） _ （AC）=A（B 一 C） =ABC =A -（BC）A ；= B C（A _B） -C =（AB） -C =（AB厂 C证：=A 一 （BC） =A-（B - C）对称差运算（10分钟）定义：A _ B =（A_B） 一（B A）A B =例a,b,c - b,c,d,e, f =a,d,e

39、, fA_ BB i A（交换律）定理1-24 :=0径A=A（0是的单位元素）（A轻B）C=A （ B过C）（结合律）A : A= .容斥原理形式：| Au B | =| A| + |B | -1 AC B |. 或：AcB =|U A B +|AcB例：求1到1000之间（包含1和1000在内）既不能被5和6整 除数有多少个？解：|S| = 1000|A|=I11000/5 =200, |B|= H.1000/6 =166|A B| = Il1000/lcm（5,6）= I11000/33 = 33Ac B =1000 -200 -166 +33 =667集合的划分与覆盖(12分钟)划分定

40、义：兀=A | A匸A,i乏1A，一 i I其中：AAj一，一jA = Ai日例1-53 :设A = a, b, c, 则A的所有不同的划分分别为：1 二a,b,c,二 a,b, c,3 二a,c, b, ：；4 b, c, a,二5 - a,b,c.覆盖设A是集合，由A的若干非空子集构成的集合称为A的覆盖,如果这些非空子集的并等于A.（3）集合的对等（10分钟）定义：AB =存在双射f : AB.例：（0, 1）R集合的基数|A :无限集合A若集合A和B对等,则称这两个集合的基数相同.例：|（0,1）可数集合：能与自然数集合 N对等的集合教学小结（2分钟）本讲首先介绍了集合的各种运算（并，交

41、，补，差，对称差）及其满足的性 质，接着介绍了集合的划分与覆盖的概念；最后介绍了集合对等、集合的基数及 可数集合。四、作业与实验（1分钟）书面作业： 习题1.4 5、8、10、13.习题 1.5: 1、7上机作业：无第五讲：关系（一）一、教学目标掌握关系的概念尤其是二元关系的概念掌握关系的定义域和值域掌握关系的三种表示方法理解函数的关系定义二、重点与难点分析重点：二元关系概念、关系的三种表示方式、函数的关系定义难点：关系的概念三、教学内容与教学过程1习题讲解（15分钟）2上章内容回顾（5分钟）集合的有关概念映射的有关概念运算的定义与性质集合的运算、集合的划分与覆盖、集合的对等进入主题，开始第五

42、讲本讲知识点介绍（1）关系的定义关系的概念（15分钟）引例：A = 张三,李四,王五；B = 英语,C语言,离散数学,数据结构,汇编语言；C = 优,良,合格,不合格.A与B之间的关系R = （张三,离散数学）,（张三,数据结构）,（张 三，英语）,（李四，数据结构）,（王五，C语言）,（王五，汇编语言）A B.A, B与C之间的关系S = （张三,离散数学,优）,（张三,数据结 构，良），（张三，英语，优）,（李四，数据结构，优）,（王五，C语 言,合格）,（王五,汇编语言,良） ABC.定义：A,A2,.An是集合，jR A汇人2乞肿代，贝U R为A,A2,.An间的n元关系特别的R A

43、A . A为A上的n元关系注（两层含义）：集合、关系例：A=王，李，张，黄 , B=100米，400米，铅球，跳远 , C=第 一名，第二名，第三名，优秀奖R=(王，100米，第二名)，(李，铅球，优秀奖)，(张，100米，第 一名)，(黄，跳远，第二名)二元关系的定义：两个集合 A和B (可以相同)之间的关系称为二元关系A 到B的关系：R A BA 上的关系：R A A例：A=甲，乙，丙R=(乙，甲)，(乙，丙)，(甲，丙)注：(x,y)表示x胜y例：A=张三，李四，王五，B=教师，辅导员，导师R=(张三，辅导员)，(张三，教师)，(李四，教师)，(王五，导师)，(王五，教师)例 2-1 :

44、A 二a,b, B 二1,2,3R =( a,3),( a,2),( b,1),(b,3) A B =( a,1),(a,2),( a,3),( b,1),(b,2),( b,3)例：A=a,b,R 是 P(A)上的包含关系，R=(x,y)|x,y P(A)且 xyP(A)=f - ,a, b, AR 二(、，、),(_, a),(、， b),( - , A),( a, a),( a, A),( b, b),( b, A),(代 A) 注意：关系的次序定理2-1 :若=m, B=n，则A到B的关系有2mn若|A|=m，则A上的关系有2mm注：A到B的关系是AX B的子集三种特殊的关系(5分钟)

45、空关系：A到B的空关系、A 上的空关系-全关系：A到B的全关系A BA 上的全关系A A恒等关系：Ia 二(x,x)|x a例：A=0,1,2A a=(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)I a=(0,0),(1,1),(2,2)关系符号(10分钟)定义：若(x,y)R,则可记为xRy例：实数集合R上的大于“ ”关系：x(x, y)|x, R,x y.例：整数集Z上的整除关系“ I”m |n 二 n = mq ,卜( x, y) | x, y 己 Z , x| y(2,6),( -2,6),(2, -6),( -2, -6)

46、|(1)若 x|y且 y|x,则x =y 或 x = y整除性质：(2)若x | y且y |乙则x|z(3)若x | y且x | 乙则x |my nz例：模m同余关系三mx=m y = m (x-y)3(x-y)u x除以3的余数=y除以3的余数 性质：(1)x 三 x(mod m).I ix 三 y(mod m)= y 三 x(mod m)x 三 y(modm), y三 z(modm)二x 三 z(mod m)a 三 b(modm), c三 d(modm)=ax cy 三 bxdy(mod m)a= b(modm), c三 d(modm)二ac 三 bd (modm)a 三 b(modm)=

47、an 三 bn(mod m)a 三 b(mod m)二 f (a)三 f (b)(mod m)关系的定义域和值域(5分钟)定义域：设R - A B,domR=x|存在y B,使(x, y) R .即 R中所有有序对中 第一位置元素组成的集合，它显然是A的子集值域：设 RA B, ran R = y| y B,存在 x A,使得(x, y)F,即 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 =

48、1,2, 3, 4.关系的表示(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， R =( a,b),( a, c),( c, a),(d,c),(d,d)注：有向边关系矩阵表示法= 1,2,，m, j1A =Xi, X2,., Xm, B = yi, y2,., Ym, R A B 定义：=M R = (mj )m n例

49、2-13:A = a,b, c,d, B = 1,2, 3,R = ( a, 2), ( a, 3), ( c, 2),(d, 2).一0111 1000M R =111011010mijR,i_ 1,(xi,yj)0,(xi, yj) R= 1,2,., n例：A=a,b,c, I A =(a, a),(b,b),(c,c)01(3)函数的关系定义(5分钟)函数到关系的转换例：A = a, b, c, B = 1,2, 3, f: AB, f(a) = 2, f(b) = 3, f(c) =3.-f =(a,2),(b,3),(c,3)关系能够转换成函数的条件domf 二 A(x, yj f

50、 ,(x, y2) f 二 力二 y2例：A =x, y, z, B 巩1,2,3,4, R =( x,1),( y,2),( z,4),( y,3)，不能转换成函数。例 2-16教学小结(3分钟)本讲首先讲解关系的概念与表示，特别介绍了二元关系，同时描述了三 种特殊的关系：空关系、全关系、恒等关系，然后讲解了关系的三种表示方式：集合表示法、关系图表示法、关系矩阵表示法，接着讲解了关系与函数的区别与联系及它们间的转换。13、14.四、作业与实验( 2 分钟)书面作业：习题 2.1： 2 、4(2)(4)(5)上机作业：无第六讲：关系（二）一、教学目标掌握关系的集合运算掌握关系的逆运算，逆关系的

51、关系矩阵、关系图及逆关系的定理掌握复合关系、复合关系相关定理了解函数的复合运算二、重点与难点分析重点：复合关系、逆关系的概念及相关性质难点：复合关系、逆关系的性质三、教学内容与教学过程1习题讲解（10分钟）2上讲内容回顾（5分钟）N元关系的定义2元关系关系的定义域与值域关系的表示函数的关系定义3进入主题，开始第六讲。（1）关系的集合运算（15分钟）关系的几种常见集合运算：R,S A B:R_. S,RS,R, R-S,R二S.、宀 RQ A汽Bn R = A汉 B R 注：_R AA=R = AA R例：设 A 二123,4,若R二(x,y)|(x,y)/2 是整数，x,y A,S二(x,y)

52、|(x-y)/3 是正整数，x,y A, 求 R_ S,R - S,S-R,L R,R 二 SR=(1,1),(1,3),(2,2),(2,4),(3,1),(3,3),(4,2),(4,4)S=(4,1)R _ S=(1,1),(1,3),(2,2),(2,4),(3,1),(3,3),(4,2),(4,4),(4,1)解:R S=-S-R=S=(4,1)L R=A A-R=(1,2),(1,4),(2,1),(2,3),(3,2),(3,4),(4,1),(4,3)R- S=(R 一 S)-(R - S)二R 一 S=(1,1),(1,3),(2,2),(2,4),(3,1),(3,3),

53、(4,2),(4,4),(4,1)例 2-17（2）关系的逆运算（20分钟）为何考虑关系的逆运算？若x是y的老师，则y是x的学生,定义：R A B= R二(y,x) |(x,y) R B A注：R1就是将所有R中的有序对中的两个元素交换次序，例 2-18 : A = a, b, c, d, B = 1,2, 3, R = ( a, 3), ( c, 2), ( a, 2), ( b, 2).则 R=(3,a),(2,c),(2, a),(2, b)逆关系的关系图Gri有向线条反向(图示例2-18)逆关系的关系矩阵MR1原关系的关系矩阵的转置(示例 2-18)逆运算的性质：定理2-2 : (R)

54、二R (对合律)定理2-3 :逆运算与关系的集合运算并，交，补的关系(R S)二 RJS(R - S)=R八 SJ(R)证明：(R - S) 二 RJ Sd):-(u,v) (RS) 二(v,u) R S：=(v, u) R,(v,u) S：= (u,v) R，,(u,v) S二(u,v) RJ SJ.关系的复合运算(35分钟)为何考虑关系的复合运算？若x是y的母亲，y是z的妻子，则x是z的 岳母，关系R到关系S的复合运算(10分钟)R 三 A B,S - B C=二(x,z)| y B,(x,y) R,( y, z) S.例：F 二(3,3),(6,2), G 二(2,3)，贝U：F OG

55、二(6,3), G!)F 二(2,3)例 2-19 : A=a,b,c,d, B =1,2,3,4, C 二：，、,S 二(1,： ),(2, J(2,、),(3), R 二(a,1),(a,2),(b,2),(d,3),(c,4),=R S 二(a,： ),(a, J(a,、),(b, J(b,、),(d, J.借助关系图理解复合运算：关系矩阵:_1 100 101001 00010104*4-110001000001Mr=Mr,Mj00001010100sj00001010100.0000j10101010000.01004*4复合关系的性质(10分钟)R ? S - S ? R.或 y

56、= x/2 =( 0,1), (1,2), (2,3), (0,0),(2,1)例：R =(x,y)|x,y A, y = x+1S =(x, y)| x,y A, x = y +2=( 2,0), (3,1)R S =(1,0),(2,1)工 S R=(2,1),(2,0),(3,2) 定理 2-4 : (R S) T = R (S T)二 R S T.证明思路：(R 厂工R S T)(R S) T 二 R (S T)定理 2-5 : R (S T) =(R S) 一(R T).R (S T) (R Sr (R T).定理 2-6 : (R S宀 S R4.证明：- (u,v) (R S)

57、= (v,u) R Sy B:(v,y) R,(y,u) Sy B:(y,v) R,(u,y) S (u,v) S4 R.注：本性质与矩阵的有关运算性质类似，请注意顺序(AB )4 B 4 A，,(AB )T B T A T.定理 2-7 :设R5A B,则：Ia0R二 R,R0ib 二 R幕运算(10分钟)R= A A: R0 =Ia, R1 =R,R2 =R：R.幕的表示方式：Rn = R：IRI：;:R, n_2.Rn41 =Rn0 R试计算Rn例 2-23 :设 A=a,b,c,集合 A上的关系 R=(a,b),(b,c),(c,a),R1 =R=(a,b),(b,c),(c,a),R

58、2 二(a,c),(b,a),(c,b),3R =(a,a),(b,b),(c,c) = lA=R =R3$R 二 R,RR3CR2 二 R2=R3k =lA,R3k 1 = R,R3k 2 = R2设R二A A,对于非负整数m, n,有幕运算的性质:RmQRn =Rm;(Rm)n =Rmn;(Rm)NR-1)”；函数的复合运算(5分钟)设f: A B, g: B C,函数f与函数g的复合记为f:若f (x)=y 且 g(y)=乙 则(f 匂)(x) = g(f(x)=乙由于f A B, g B C,关系f与关系g的复合记为f 若(x, y) f 且(y, z) g,则(x, z) f ?g.

59、注：函数f与函数g的复合与将其看作关系时关系f与关系g的复合是 一致的教学小结(3分钟)本讲分别介绍了关系的集合运算、逆运算，复合运算，并且对复合关系、逆 关系的定义、表示方式、相应的关系矩阵进行了讲解，还介绍了它们之间满足的 相关性质，最后介绍了函数的复合运算。四、作业与实验(2分钟)书面作业：习题 2.2 1、3、6、8、12(选).上机作业：无第七讲：关系(三)一、教学目标理解关系的各种性质掌握满足各种性质的关系的关系矩阵和关系图理解闭包的含义掌握闭包的几个关键掌握闭包的构造二、重点与难点分析 重点：自反性、反自反性、对称性、反对称性、传递性概念的理解，闭包 的理解与构造难点：同上三、教

60、学内容与教学过程1上讲内容回顾(5分钟)关系的集合运算关系的逆运算 关系的复合运算2进入主题，开始第七讲本讲知识点概括关系的性质自反性(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自反=IA R注：空关系是空集一上的自反关系关系矩阵：对角线元素都为1关系图：结点含有环反自反性