离散数学教案课件教材汇总.doc-得力文库

资源描述

《离散数学教案课件教材汇总.doc》由会员分享，可在线阅读，更多相关《离散数学教案课件教材汇总.doc（97页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

2、 2010.主要参考书目：1邵学才,叶秀明. 离散数学M.北京电子工业出版社，2009.2邵志清,虞慧群. 离散数学M.北京电子工业出版社，2003.3屈婉玲. 离散数学习题解析M.北京大学出版社，2008.本课程的先修课程是高等数学、线性代数，后续课程包含数据结构、数据库原理及应用、操作系统、数字逻辑、人工智能、算法分析与设计等。二、教学基本要求与内容安排二、教学基本要求与内容安排（一）教学目的与要求离散数学是研究离散量的结构及其相互关系的学科,它在各学科领域特别在计算机科学领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程必不可少的先行课程。本课程的教学目的旨在通过对离散数学的教

3、学，让学生不但可以掌握处理如集合、代数结构和图等离散结构的描述工具和方法，为后续课程的学习创造条件，而且为学生今后提高专业理论水平，从事计算机行业的实际工作提供必备的抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。（二）教学内容安排/学时分配教学内容教学要求教学方法重点()难点()讲课实验上机其他备注第一部分数理逻辑讲授15.51 命题逻辑的基本概念21.1 命题与联接词B11.2 命题公式及其赋值A12 命题逻辑等值演算3.52.1 等值式B12.2 析取范式与合取范式A12.3 联接词的完备集C0.52.4 可满足性与消解法B13 命题逻辑的推理理论2 3.

4、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.

5、1 函数的定义与性质A0.53.2 函数的复合与反函数A0.5/3.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 最短路问

6、题与货郎担问题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 学期授课教师姓名赵欢欢职称助教授课专业网络工程班级 2011 级课程名称离散数学教材名称离散数学出版社清华大学出版社其中周次日期周学时讲

7、课实验课习题课课堂讨论其他环节教学内容摘要（章节名称、讲述的内容提要、实验的名称、课堂讨论的题目等）第一周 9 月 3 日至 9 月 9 日44第一讲集合、映射与运算（一） 1.1 集合的基本概念理论：集合、子集、幂集、n 元组、笛卡尔积第二讲集合、映射与运算（二） 1.2 映射的有关概念理论：映射的定义、映射的性质、逆映射、复合映射第二周 9 月 10 日至 9 月 16 日22第三讲集合、映射与运算（三） 1.3 运算的定义和性质理论：运算的定义、运算的性质第三周 9 月 17 日至 9 月 23 日44第四讲集合、映射与运算（四）

8、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 关系的闭包理论：关系的性质：自反性、反自反性、对称性、反

9、对称性、传递性；自反闭包 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、、命题公式的类型第八周 10 月 22 日至 10 月 28 日22第十一讲命题逻辑（三） 3.4 逻辑等值的命题公式理论：逻辑等值的定义、基本等值式、等值演算法、对偶原理周数 16 周计划学时 48 学时讲课 48 学时课堂讨论 0 学时实验课 0 学时习题课 0 学时其他环节 0 学时/第九周 10 月 29 日至 11 月 4 日 44第十二讲命题逻辑（四） 3.5 命题公式的范式理论：命题公式的析取范式和合取范式的定义域求法命题公式的主析取范式及主合取范式的定义和求法第十三讲命题逻辑（五） 3.7 命题逻辑中的推理理论：推理形式有效性的定义；基本推理规

11、则；命题逻辑的自然推理系统第十周 11 月 5 日至 11 月 11 日22第十四讲谓词逻辑（一） 4.1 个体、谓词、量词和函词理论：谓词逻辑概念，谓词的概念与表示，量词的概念与表示，个体域，辖域，约束变元和自由变元的含义第十一周11 月 12 日至 11 月 18 日44第十五讲谓词逻辑（二） 4.2 谓词公式及命题的符号化 4.3 谓词公式的解释及类型理论：谓词公式的定义，将命题用用符号（个体，量词，谓词）来表示，消去量词的逻辑等值式，永真式，科满足式，永假式及中性式的概念第十六讲谓词逻辑（三） 4.4 逻辑等值的谓词公式 4.5 谓词公式的前束范式理论：谓词公

12、式等值的定义，基本等值式，前束范式第十二周 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 日

13、至 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 月

14、24 日至 12 月 30 日22第二十四讲总复习系主任签名：院长签名：年月日年月日说明：1本教学进度表由主讲教师负责填写，于每学期开学第一周内送交教师所在系，经领导审定、签字后备查。/2此表一式三份，其中，任课教师一份，教师所在系一份，教务处一份。第一讲：集合、映射和运算（一）一、教学目标1. 掌握集合的概念与表示 2. 理解子集、幂集、 n 元组与笛卡儿积的概念 3.掌握子集，幂集，笛卡尔积的求法二、重点与难点分析1.重点：集合的概念，子集，幂集，笛卡尔积的概念及求法2.难点：幂集三、教学内容与教学过程1.1.进行自我介绍（进行自我介绍（5 5 分钟）分钟）姓名，联系方

15、式，专业方向。建议学生用电子邮件方式联系。2.2.进行课程简介（进行课程简介（1010 分钟）分钟）离散数学是研究离散量的结构及相互之间关系的学科是一门专业基础课，是数据结构、操作系统、计算机组成原理、数据库原理等课程的数学基础。特点：知识点集中，概念，定理多；方法性强；学数学就要做数学成绩评定：平时成绩(到课情况，书面作业，平时测验)占 30%,期末考试占70%3.3.进入主题，开始第一讲进入主题，开始第一讲(1) 集合的有关概念(20 分钟)集合定义：集合是具有某种特定性质的对象汇集成的一个整体，通常用大写字母 A,B,C,D 表示。例如：滁州学院全体学生计算机与信息工程学院所有女生常见

16、的数的集合：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 或xA|A|表示集合 A 中的元素个数注意：集合中的元素可以是集合，如 A=a,a,b,b,c,|A|=4,a,bA注：集合中的元素无顺序；集合中无重复元素例：指出下列哪些是集合，哪些不是集合？中国人的集合；百货商店里好看的花布的集合；1000 以内的素数

17、的集合；26 个英文字母组成的集合；这个班里高个子学生的集合；直线 y2x-5 上的点的集合。(2)集合之间的关系子集（15 分钟）定义：若 A 中的任意元素都属于 B，则 A 是 B 的子集，称 A 包含于 B 或 B包含 A，包括的两层含义：包含与真包含（AB），A 是 B 的真子ABAB集注意：属于（元素与集合的关系）与包含于（集合与集合的关系）的区别例：A=1,2,3,4，B=2,4或BAAB定理 1-1：A定理 1-2：（自反性）(1);AA则 A=B(2),AB BA则（传递性） (3),AB BCAC用定义进行证明定理 1-3：A=B 的充要条件是,AB BA注：该定理是证明两

18、个集合相等的基本方法该定理与定理 1-2 中的(2)的区别例 1-2/注：A 中有一个元素不属于 C，则，反证法是一种很好的方法AC幂集（15 分钟）定义：由 X 的所有子集组成的集合，()|P XA AX例：x=1,2，() ,1,2,1,2P X Y=a,b,c() , , , , , , , , , , , , P Xabca ba cb ca b c 例 1-3注：若|X|=n,P(x)的元素有：；由一个元素构成的子集；由两个元素构成的子集；由 n 个元素构成的子集计数的基本原理：加法原理：图示乘法原理：图示定理 1-4：若|X|=n,|P(X)|=2n证明：加法原理：二项式定理：0

19、()n nrrn r n rxyC x y1211.(1 1)2nnnn nnnnCCCC乘法原理：注：每个元素的参与与否构成不同的子集n 元组（5 分钟）定义：论域 U 中选取的 n 个元素按照一定的顺序排列，得到 n 元有序组，称n 元组，记为：(x1,x2,x3,xn)或例：平面直角坐标系中点的坐标是 2 元组；空间直角坐标系中点的坐标是 3元组；n 元组在数据结构中是一个表有序对，序偶：2 元组注：(x,y)(y,x)笛卡尔积（10 分钟）定义：设是集合，称为1,2,.,A AAn,( 1, 2,.,)|1,2,., iix xxnxA inA1,A2,An 的笛卡尔积（直积，叉积）

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

21、含义，复合映射的定义及性质二、重点与难点分析1.重点：理解和判断映射的三种性质，逆映射，复合映射2.难点：映射三种性质的判断，复合映射的性质三、教学内容与教学过程1.习题讲解（习题讲解（1010 分钟）分钟）2.上讲内容回顾（上讲内容回顾（3 3 分钟）分钟）集合的概念：集合、元素、集合的表示方法集合间的关系：子集、幂集、n 元组、笛卡尔积(1)映射的定义（15 分钟）定义：对于 A,B,若存在对应法则 f，对于，唯一的与它对xA yB应，称 f 是 A 到 B 的一个映射或一个函数。记为：f:AB （图示）例：Ceiling function fggfFloor functionx 取整函数

23、N 的单射，试证明之。:,( )2 ,fNN f xx证：对于，由得出，进而 x1=x21, 2x xN( 1)( 2)f xf x2 12 2xx(使用定义证明)满射（10 分钟）定义：对于，使得 y=f(x),yBxA 充要条件：=Branf/例 1-7：设，则 f 是 Z 到 N 的满射，试证明之。:,( )fZN f xx证：对于取,显然有,yN xyZ( )yf x（使用定义证明）双射（一一对应）（5 分钟）定义:既单射又满射例 1-8例 1-9：建立一个（0,1）到 R 的一一对应解：:(0,1),( )tan(1/ 2)fR f xx置换：A 到 A 的双射(3)逆映射（逆函

24、数，反函数）（10 分钟）定义：f:AB，将 f 的方向逆转后，得到的集合 B 到集合 A 的映射1f定理 1-7：f 的逆映射存在的充要条件是 f 是双射（加以说明解释）注：若 f 是双射，则也是双射，且1f11()ff例 1-11：判断所给出的映射是否有逆射，若有，求出其逆映射 2:,( )fRR f xx 3:,( )g RR f xx解：f(2)=f(-2)=4,根据单射定义知 f 不是单射，进而其不是双射，根据定理 1-7 知其不存在逆映射显然 g 是双射，其逆映射为113:,( )gRR gyy(4)复合映射（20 分钟）定义:设对于，令，则 h 是 A:,:,fAB g BCx

25、A ( )( ( )h xg f x到 C 的映射，h 为 f 和 g 的复合映射或复合函数，记为（图示）fg注： ()( )( ( )fgxg f x条件: ( )( )f Adom g例 1-12例 1-13注：一般来说即使和都有意义，也不能保证成立fggffggf恒等映射(IA)： :,( )fAA f xx定理 1-9：若是双射，则:fAB11,ABffIffI若是双射，则:fAA11AffffI/定理 1-10：:,:fAB g BC若 f 和 g 是单射，则是单射（证明）fg若 f 和 g 是满射，则是满射（证明）fg若 f 和 g 是双射，则是双射且fg111()fggf定理 1

26、-11：设:,:fAB g BC若是单射，则 f 是单射，但 g 不一定（证明）fg若是满射，则 g 是满射，而 f 不一定（证明）fg定理 1-12 设，则:,:, :fAB g BC h CD)()fghfg h（4. 教学小结（教学小结（5 分钟）分钟）本讲首先介绍了映射（函数）的定义及定义域、值域、像、原像等相关概念；接着介绍了映射的三种性质：单射，满射，双射；最后介绍了逆映射的定义及复合映射的定义及其具有的相关性质。四、作业与实验（2 分钟）1. 书面作业：习题 1.2 1、2、6、11、14.2. 上机作业：无/第三讲：集合、映射和运算（三）一、教学目标 1. 理解运算的定义2.

27、掌握运算的表示及常用运算3. 理解运算的性质并能判断具体运算是否具有某些性质二、重点与难点分析1.重点：运算的定义，运算的性质2.难点：运算性质的判定三、教学内容与教学过程1.习题讲解（习题讲解（5 5 分钟）分钟）2.上讲内容回顾（上讲内容回顾（5 5 分钟）分钟）映射的定义映射的性质：单射，满射，双射逆映射复合映射3.进入主题，开始第二讲进入主题，开始第二讲。本讲知识点概括(1)运算的定义（25 分钟）定义:设和 B 是集合，若，称 f 为1,2,.,A AAn: 12 .fAAAnB到 B 的 n 元运算。1,2,.,A AAnA 到 B 的 n 元运算，或 A 上的 n 元运算：

28、A 上的 n 元封闭运算（代数运算）：，有1, 2,.,x xxnA( 1, 2,.,)f x xxnyA例：判定取绝对值运算|、加法运算+、取大运算 max 是否是自然数集合 N(Z)上的代数运算。解： xN xxN, x yNxyN1, 2,.max( 1, 2,.)x xxnNx xxnN例：判定减法运算-,取小运算 min 是否是自然数集合 N 上的代数运算。解：例：判断数的加法运算是否是集合 A=2n |nN上的代数运算？解： 122262n例：将十进制数 273 转换成八进制解： 273=, ,34 8 1 344 82 227334 8 1(4 8)2) 8 14 82 8 1

29、 BAAAfn .:AAAAfn .:/8273(421)模运算定义：，是使成立:,( )(mod)fZN f xxm(mod)xm,0xqmrrm的整数 r,即 x 除以 m 的余数。例：16(mod 3)、-8(mod 5)、9(mod 2)模 m 加法，模 m 乘法()(mod)()(mod)mmxyxymxyxym例：m=5, 553( 5)3,3( 5)0 最大公约数，最小公倍数若 d|m 且 d|n,则 d 是 m,n 的公约数，用 gcd(m,n)表示 m,n 的最,m nZ大公约数若 m|d 且 n|d，则 d 是 m,n 的公倍数，用 lcm(m,n)表示 m,n 的,m n

30、Z最小公倍数。注：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 互素的正整数的个数( )n运算表给定集合 A，则集合 A 上的 1 元或 2 元运算可以用运算表来表示例：A=a,b,c,*abcabcababccbca思考：A 上的封闭的 1 元，2 元，3 元运算的个数是多少？12121, 12, 21, 12, 2

31、11 1212min()min()min(,) 12max()max()max(,) 12, (,)gcd(, )(, )kkkkkkrsrrss kkkkkr sr srs kr sr srs kmp ppZnp ppZ pr sm nppplcm m nppp为素数，为非负整数21112 122111,0,0,.,1gcd( , )kkkkkk kkmq nrrn nq rrrrnrqrr rq rrm nmxny /33 39 327(2)运算的性质对合性（5 分钟）定义：设*是 A 上的一元代数运算，例： : ()xRxx 11(),()TTAA AA？xx幂等性（5 分钟）幂等元：

32、*,x xx xA定义：A 中的每个元素对于*都是幂等元例：*123112322323313例：, ?R 交换性（5 分钟）定义：对于 A 上的二元运算*,均有, x yA例：R 上的+具有交换性R 上的-，映射的复合运算?fg结合性（5 分钟）定义：例:映射的复合运算具有结合性()()fghfg hR 上的+具有结合性R 上的- ？单位元素（幺元素）（5 分钟）定义：对于 A 上的二元运算*，使得对于ex例：R 关于加法运算+的单位元素是 0R 关于乘法运算的单位元素是 1R 关于减法运算-的单位元素是？定理 1-3：若 A 关于* 有单位元素，则单位元素是唯一的证明：设 e1,e2 是

33、 A 关于*的单位元素，则 e1=e1*e2=e2零元素（5 分钟）定义：对于 A 上的二元运算*，使得对于x例:R 关于乘法运算的零元素是 0.,)(Axxx, xyyx).()( :,zyxzyxAzyx. xxe. xex.x.x/R 关于减法运算-的零元素是？R 关于加法运算的零元素是？定理 1-4：若 A 关于* 有零元素，则零元素是唯一的证明：设 e1,e2 是 A 关于*的零元素，则 e1=e1*e2=e2逆元素（5 分钟）前提：A 关于二元运算*有单位元素 e定义：，使得：,xAyA 例：R 上的加法运算+：x+(-x)=0=(-x)+xR 上的乘法运算：110,1xxxx

34、x注：逆元不一定存在，存在不一定唯一，参见表 1-5 定理 1-5：若 A 关于*运算有单位元素为 e 且*运算满足结合律，若对于 A 中的 x 有左逆元 y 与右逆元 z，则 y=z,此逆元唯一证明：y*x=e,x*z=ey=y*e=y*(x*z)=(y*x)*z=e*z=z消去性（分钟）定义：若 A 关于*有零元，则记为，对于，若, ,x y zAx例 1-31 Z 上的加法运算+和乘法运算均满足消去律.分配性（5 分钟）定义：是 A 上的两个二元运算，对于*, ,x y zA则称*关于是可分配的吸收性（2 分钟）定义：是 A 上的两个二元运算，对于*, ,x y zA则称*关于是可吸收

35、的德摩根律（3 分钟）定义：是 A 上的一元运算，是 A 上的两个二元运算，对于*, ,x y zA4. . 教学小结教学小结（3 分钟）本讲首先介绍了运算的定义并介绍了几种常用的运算，接着介绍了运算的性质：对合性、幂等性、交换性、结合性、单位元素、零元素、逆元素、消去性、分配性、吸收性、德摩根律，并结合之前所学知识讲解运算的性质。 . eyx. exy. zyzxyx. zyxzxy).()()(zxyxzyx).()()(xzxyxzy.)(xyxx.)(xxxy).()()(yxyx).()()(yxyx/四、作业与实验（2 分钟）1. 书面作业：习题 1.3：1、3、5、6、82.

36、上机作业：无/第四讲：集合、映射和运算（四）一、教学目标1.掌握集合的各种运算2.理解各种集合运算所满足的性质3.掌握集合的划分与覆盖的概念4.了解集合的对等，集合的基数，可数集合等概念二、重点与难点分析1.重点：集合的运算并、交、补、差、对称差集合运算性质 2.难点：集合运算等值式的证明，集合的对等、基数三、教学内容与教学过程1.上讲内容回顾（上讲内容回顾（5 5 分钟）分钟）运算的定义运算的性质：对合性、幂等性、交换性、结合性、单位元素、零元素、逆元素、消去性、分配性、吸收性、德摩根律2.进入主题、开始第四讲进入主题、开始第四讲本讲知识点概括(1)集合的运算并运算（15 分钟）定义：定

37、理 1-16：是包含 A 和 B 的最小集合AB,CA CBCAB定理 1-17：并运算满足的性质：（交换律）ABBA（结合律）()()ABCABC（幂等律）AAA（是运算的单位元素）AAA （是运算的零元素）AUUAUU例 1-38:设 f : A B, X, Y A, 则证明：()()( )f XYf Xf Y.|BxAxxBA或/证明： ()() ( )()()( )()XXYf Xf XY YXYf Yf XYf Xf Yf XY ()():( )( )()( )( )()( )()()( )bf XYaXYbf aaXbf af XaYbf af Ybf Xf Yf XYf Xf Y

38、交运算（15 分钟）定义： |BABx xAx且定理 1-18：是包含在A和B的最大集合ABCA,CBCAB定理 1-19：交运算满足的性质：（幂等律）AAA（交换律）ABBA（结合律）()()ABCABC（是运算的零元素）AA （U 是运算的单位元素）AUUAA例：定理 1-20：并运算与交运算之间满足的性质：例 1-41：ABABAABB证：ABABB,BABxAB xAB 由于ABxABBABBAAB=BAB()()()()()()()()()()()()AABAAABAABCABACABCABAC对可吸收对可吸收对可分配对可分配/补运算（10 分钟）定义：例 1-42：（A 的补集依

39、赖于全集 U 的选取）A=a,b,cU=a,b,c,d Ad , , , , , , , , , , , , , Ua b c da bb ccAda bb cc定理 1-21：AAUAA 定理 1-22：德摩根律：ABABABABP25： , 运算的重要性质差运算（10 分钟）定义： |ABx xA且xB例 1-43： , , , , , , , , , , , , , , a b cb c d e fa b c d e fa b cd e f 定理 1-23： ABAB证明：,xABxA xBxA xBxAB 例 1-45：证明： ()()ABCABC证：()()()()()ABCABCA

40、BCABCABC例 1-46：ABAB 例 1-47：()()()()()()ABACABACABCABCABCABC对称差运算（10 分钟）)(ACAU/定义：()()ABABBA例 , , , , , , , , , a b cb c d e fa d e f定理 1-24：()A=AABC=ABC AA=ABBAA 交换律（是的单位元素）（）（）（结合律）容斥原理形式：或： ABUABAB例：求 1 到 1000 之间（包含 1 和 1000 在内）既不能被 5 和 6 整除数有多少个？解： |S| = 1000|A|=1000/5=200, |B|=1000/6=166|AB| = 1

41、000/lcm(5,6) = 1000/33 = 331000200 16633667AB（2）集合的划分与覆盖（12 分钟）划分定义：|,iiAAA iI其中：,iiji i IAiIAAijAA 例 1-53：设 A = a, b, c, 则 A 的所有不同的划分分别为:覆盖设 A 是集合, 由 A 的若干非空子集构成的集合称为 A 的覆盖, 如果这些非空. |BABABA.,54321cbaacbbcacbacba/子集的并等于 A.（3）集合的对等（10 分钟）定义：A B 存在双射f : A B.例：(0, 1) R集合的基数：无限集合 A A若集合A和B对等, 则称这两个集合的基

42、数相同.例： (0,1)R可数集合：能与自然数集合 N 对等的集合3. 教学小结（教学小结（2 2 分钟）分钟）本讲首先介绍了集合的各种运算（并，交，补，差，对称差）及其满足的性质，接着介绍了集合的划分与覆盖的概念；最后介绍了集合对等、集合的基数及可数集合。四、作业与实验（1 分钟）1. 书面作业：习题 1.4 5、8、10、13.习题 1.5：1、7 2. 上机作业：无/第五讲：关系（一）一、教学目标1. 掌握关系的概念尤其是二元关系的概念2. 掌握关系的定义域和值域3. 掌握关系的三种表示方法4. 理解函数的关系定义二、重点与难点分析1.重点：二元关系概念、关系的三种表示方式、函数的

43、关系定义2.难点：关系的概念三、教学内容与教学过程1.习题讲解（习题讲解（1515 分钟）分钟） 2.上章内容回顾（上章内容回顾（5 5 分钟）分钟）集合的有关概念映射的有关概念运算的定义与性质集合的运算、集合的划分与覆盖、集合的对等3. .进入主题，开始第五讲进入主题，开始第五讲本讲知识点介绍(1)关系的定义关系的概念（15 分钟）引例：A = 张三, 李四, 王五;B = 英语, C 语言, 离散数学, 数据结构, 汇编语言;C = 优, 良, 合格, 不合格.A与B之间的关系R = (张三, 离散数学), (张三, 数据结构), (张三, 英语), (李四, 数据结构), (王五, C

44、语言), (王五, 汇编语言) A B.A, B与C之间的关系S = (张三, 离散数学, 优), (张三, 数据结构, 良), (张三, 英语, 优), (李四, 数据结构, 优), (王五, C 语言, 合格), (王五, 汇编语言, 良) A B C.定义：是集合，，则 R 为间的 n 元关12,.nA AA12.nRAAA12,.nA AA系特别的为 A 上的 n 元关系注（两层含义）：集合、关系例：A=王，李，张，黄，B=100 米，400 米，铅球，跳远，n AAAR./C=第一名，第二名，第三名，优秀奖R=(王，100 米，第二名)，（李，铅球，优秀奖），（张，100 米，第一名），（黄，跳远，第二名）二元关系的定义：两个集合 A 和 B（可以相同）之间的关系称为二元关系A 到 B 的关系：RA BA 上的关系：RAA例：A=甲，乙，丙R=(乙，甲)，（乙，丙），（甲，丙）注：(x,y)表示 x 胜 y例：A=张

展开阅读全文