第1章 集合与关系(1)教学课件计算机数学课件.ppt

《第1章 集合与关系(1)教学课件计算机数学课件.ppt》由会员分享，可在线阅读，更多相关《第1章 集合与关系(1)教学课件计算机数学课件.ppt（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章集合与关系(1)教学课件高教版计算机数学课件第1章 集合与关系广东科学技术职业学院计算机学院Septemper 20141.1 集合 集合与函数的概念对应用数学来说是最基本的。所有的数学，以及依赖于数学的计算机科学（如程序设计、数据结构、数据库和软件工程等课程）都要使用这些基本概念。本章主要讲述集合、关系、关系数据库和函数等知识41.1 集合集合的朴素定义：集合是一组无序的对象这一定义是德国数学家康托尔於1895年首先给出的。由这一朴素定义得出的理论导致出悖论，在1902年英国数学家罗素提出的，罗素悖论可以简单描述为：我只给所有不给自己刮胡须的男人刮胡须，我也只给这些人刮脸。康托尔(18

2、45-1918)，出身於俄罗斯的圣彼得堡，1862年入苏黎世大学学工,翌年转入柏林大学攻读数学和神学，受教于库默尔（Kummer）、维尔斯特拉斯（Weierstrass）和克罗内克(Kronecker)。1867获博士学位。1869年康托尔获得哈雷大学任教资格，并在那里一直工作到去世。康托尔1874年结婚，有5个子女。他忧郁的气质和妻子的乐观性情相互平衡。尽管他从父亲那里得到大笔遗产，但作为教授的收入却很少，为此他曾试图得到柏林大学一个待遇更高的位置，对他的这一任命被Kronecker阻止了，因为Kronecker不同意康托尔集合论的观点。由于学术观点上受到的沉重打击，使康托尔曾一度患精神分裂

3、症，虽在1887年恢复了健康，继续工作，但晚年一直病魔缠身。1918年1月6日在德国哈雷（Halle）-维滕贝格大学附属精神病院去世。罗素(1872-1970)：罗素生于一个以积极参与进步运动，热烈投身自由事业而闻名的英格兰家庭。年幼时成为孤儿的罗素由祖父母抚养，并在家里接受教育。1890年他进入剑桥的Trinity学院学习数学与伦理学。他在几何学基础方面的工作为他赢得一个研究员职位。1910年Trinity学院任命他教授逻辑和数学原理的课程罗素毕生为进步事业而战斗。他有强烈的和平主义观点，他对第一次世界大战的抗议使他失去了Trinity学院的位置。由于一篇被认为具有煽动性的文章使他在1918

4、年被囚禁6个月。罗素还为英国妇女的选举权而斗争。1961年在他89岁高龄时第二次入狱，原因是加入呼吁核裁军的抗议活动。罗素最伟大的工作是他提出的可以作为所有数学学科基础的原理。他与怀特海合著的数学原理对逻辑学、数学、集合论、语言学和分析哲学有着巨大影响。1950年，罗素获得诺贝尔文学奖，以表彰其“多样且重要的作品，持续不断的追求人道主义理想和思想自由”。引言计算机中的数据类型就是建立在集合概念之上的。其中的结构体类型就是编程者自己根据实际需要使用基本的数据类型而构造的一种新的数据类型。这种类型能把多个不同类型的信息作为一个整体。structmy_structcharname20；intage;

5、floatheight;floatweight;my_friend;这里关键字struct声明了一个结构my_struct，它是一个存放着字符型、整型、浮点型的不同数据的集合引言在C语言中，下面程序用来求出6个数中的最小值。#includemain()ints6,min,i;printf(input6numbers:n);for(i=0;i6;i+)scanf(%d,&si);min=s0;for(i=0;isi)min=si;printf(min=%dn,min);其中的主函数main()就是一个由具有不同功能的句子所组成的集合。1.1 集合（温故）关于集合，下面的知识你懂的1、集合的概念、

6、组成集合元素的特点；2、集合的表示；3、特殊集合：空集、常用数集 R Z N Q C4、集合与元素关系 5、集合与集合的关系：6、集合运算：交集、并集、补集1.1 集合（知新）幂集课堂练习1、口答完成课本P18页习题1.1的4，7，82、上黑板完成课本P18页习题1.1的1，53、思考完成课本P19页习题1.1的91.1 集合-划分集合的划分是集合中元素之间的一种分类。在信息科学中，对知识库分类就是集合的一种划分。集合X的一个划分是把集合X分成互不重叠的一些子集。一般地，一个集合X的若干个非空子集组成的集合S，如果X的每个元素都属于且只属于S中的某一个元素，就称S为X的一个划分。注意，如果S是

7、X的一个划分，则S必定是两两不相交的，且S=X。简而言之：1、互斥原则2、穷尽原则课堂练习1、完成习题1.1的3一组元素的次序有时往往是重要的。一个由两个元素组成的有序偶有序偶（或序偶），写为（a,b）。这与另一个序偶（b,a）是不同的，除非a=b。用另一种形式可表示为（a,b）=（c,d）当且仅当a=c，b=d。比如，平面直角坐标系中任意一点可用二元有序数组（x,y）来表示；空间直角坐标系中任意一点用三元有序数组（x,y,z）来表示。笛卡尔集：如果X和Y是集合，令XY表示序偶（x,y）的集合，我们把XY称为X和Y的笛卡儿积。即 1.1 集合-笛卡尔集例1.1.13 P17 请自行阅读P17例

8、1.1.14n元序组课堂练习1、完成习题1.1的21.1 集合集合-集合运算律集合运算律 P16你是否观察到，除了对合律，其它集合运算律都是成对 出现的，这种特性称为对偶性，只要将 和 ，和U对换，一个公式就变成了它的对偶式。公式对偶性在命题逻辑的运算律中还会出现。有了集合的运算律，我们可以很方便地利用运算律对复杂的集合运算进行化简和推导例：试证明证明：1.2 关系每天我们都要涉及各种关系。例如，雇员与其工资之间的关系，一个商行与它的电话号码之间的关系。关系这个概念对今后学习数据结构和数据库都很重要。目前最常用的数据库Oracle、SQLServer、DB2都是关系型数据库系统，数据库中常见的

9、分类、排序，实质上是关系的应用。在信息科学中二元关系以及以此为基础的关系代数是关系数据库的基础。关系的表示列表一般地，关系可以想象成一个列表，表1.2.1说明了一些学生与一些课程的关系。关系的表示集合集合表1.2.1，学生若选了某课程，用关系术语就说，学生与这门课程有关系，在数学上用序偶表示，如（比尔，计算机）、（玛丽，数学），因此，我们把关系定义为序偶的集合。定义1.2.1 设X和Y是集合，一个从X到Y的二元关系R是笛卡儿积XY的一个子集。用记号xRy表示（x,y）R。而当（x,y）R时，我们也说x与y有关系R。也就是说，一个从X到Y的二元关系是有序对的集合R，其中每个有序对的第一个元素取自

10、X，第二个元素取自Y。例1.2.2 令X=比尔，玛丽，贝思，戴夫 Y=计算机，数学，艺术，历史表1.2.1所表示的关系R可以写为 R=（比尔,计算机),（玛丽,数学),（比尔,艺术）,(贝思，历史）,(贝思，计算机),(戴夫，数学）（贝思，历史）R，我们可写为：贝思R历史，它表示贝思选修历史课。R的定义域是X（表中的第一列），值域是Y（表中的第二列）。一个关系可以由简单地列出那些属于它的序偶而给出。下一个例子表明，关系也可以由给出规则的方法来定义。例1.2.3 令X=2，3，4 和 Y=3，4，5，6，7我们定义一个从X到Y 的关系R如下：如果x整除y，则（x,y）R根据R的定义，我们可以写出

11、R中的有序,得到 R=（2,4），（2,6），（3,3），（3,6），(4,4)把关系R写成列表的形式，可以得到表1.2.2R的定义域是2,3,4，值域是3,4,6。此例中的关系有时也写成R=（x，y）|x整除y，x X，y Y。阅读 P21 例1.2.4关系的表示关系图关系图某个集合上的关系可以表示成一个有向图（也称关系图）。先画出顶点（或结点），表示X的元素，然后，如果元素（x,y）在关系R中，我们就画一条从x到y的有向边（带箭头的线）。一个关系中的形如（x,x）的元素，对应着一个从x到x的有向边。这样的有向边也称为一个环。右图表示关系R=1,1),(1,2),(1,3),(1,4),(2

12、,2),(2,3),(2,4),(3,3),(3,4),(4,4）例1.2.5在集合X=a，b，c，d上定义一个关系R：R=（a,a）,（b,c）,（c,b）,（d,d）此关系可以用如下的关系图表示出来，如下图所示。课堂练习P28习题1.2的1,2,3,4关系的特殊性质偏序关系定义1.2.19 集合X上的关系R，如果它是自反的，反对称的和传递的，则R称为一个偏序关系。提问：判断下列关系是不是偏序关系？（1）正整数集Z Z+上的整除关系：（2）实数集R上的大于或小于关系；（3）集合X的幂集上的包含关系 如果R是集合X上的一个偏序关系，我们就用符号xy来表示（x，y）R或xRy。它只是意味着，集合

13、X中的元素的一种次序。对于x，yX，如果有xy，或者yx成立，就说x和y是可比的。如果既没有xy，也没有yx，就说x和y是不可比的。全序关系定义1.2.23 假设R是集合X上的一个偏序关系，如果X中的任何一对元素x、y都是可比的，也就是说，有xRy或者yRx，二者必有其一，此时称R是全序关系，集合X称为全序集。提问：判断下列说法是否正确（1）正整数集Z+上的“小于等于”关系是偏序关系也是全序关系。（2）正整数集Z+上的“整除”关系是偏序关不是全序关系；课题练习：习题1.2P29的7，8关系运算关系是以有序对为元素的集合，所以它可以进行集合的一般运算，也可以进行“新”运算。P27 例1.2.26

14、设A=1，2，3，B=1，2，3，4，从A到B的关系R1=（1，1），（2，2），（3，3）和关系R2=（1，1），（1，2），（1，3），（1，4），那么R1R2=（1，1），（2，2），（3，3），（1，2），（1，3），（1，4）R1R2=（1，1）R1R2=（2，2），（3，3）它们定义了从A到B的另一些关系。关系的运算逆关系定义1.2.24 令R是从X到Y的关系。R的逆关系表示为R-1，是由下式定义的从Y到X的关系R-1=（y，x）|（x，y）RP26 例1.2.25 关系R=（2，4），（2，6），（3，3），（3，6），（4，4）的逆关系是R-1=（4,2），（6,2），（3,3

15、），（6,3），（4,4）关系的运算复合关系定义1.2.27 令R1是一个从X到Y的关系，R2是从Y到Z的关系，关系R1和R2复合表示为R2R1，是一个由下式定义的从X到Z的关系：R2R1=（x，z）|存在y,使得（x,y）R1且（y,z）R2此处要注意这两个关系的先后次序，R2R1表示先R后R2。R2R1的有序对(x,z)是由(x,y),(y,z)通过中间元素y“结合”而成的。阅读P27例1.2.28，例1.2.29（关系的幂运算）课堂练习：P29习题1.2的6,9,111.3 等价关系生活中常常对事物进行分类，如垃圾分类、图书分类。通过分类便于认识和管理事物。集合划分是集合元素之间的一种分

16、类，什么情况下集合元素可以分类？如何分类呢？定义1.3.1 集合X上的一个关系R，如果它是自反的、对称的和传递的，称R为集合X上的一个等价关系。提问：判断下列关系是否等价关系（1）一个班级上的“同乡”关系（2）正整数集上的“整除”关系。（3）正整数集上的“同奇偶性”关系例1.3.3 考虑在集合X=1，2，3，4，5上的关系R=（1，1），（1，3），（1，5），（2，2），（2，4），（3，1），（3，3），（3，5）（4，2），（4，4），（5，1），（5，3），（5，5），画出R的关系图，根据关系图判断R是不是等价关系。图？从关系图看到，R满足自反性、对称性、传递性，所以R是等价关系。并且

17、集合X的元素按照关系R分成了2,4,1,3,5两类，称为等价类。等价类定义1.3.8 令R是集合X上的一个等价关系。X，由X中与元素a具有等价关系R的全体元素组成的X的子集a，称为由关系R确定的a的等价类。阅读P33例1.3.10，例1.3.11（恒等关系），例1.3.12（同余关系）反过来，由等价类可以确定等价关系定理1.3.15 令S=T1，T2，Tn是集合X的一个划分，在集合X上定义关系：xRy表示x、y同时属于某一个Ti，则关系R是等价关系。定理1.3.15告诉我们，划分和等价关系是同一个硬币的两面。一方面，集合X的每一个划分以一种自然方式确定了X上的一个等价关系；另一方面，每个非空集

18、合X上的等价关系以同样一种自然方式确定了一个X的划分。例1.3.16 考虑集合X=1，2，3，4，5，6上的一个划分S=1,3,5,2,6，4由定理1.3.15可知，X上的划分S确定一个等价关系R。根据等价关系的定义，等价类2,6包含着序偶（2,2），（2,6），（6,2），（6,6），同理可写出等价类1,3,5和4包含的序偶。从而，等价关系R=（1,1,），（1,3），（1,5），（3,1,），（3,3），（3,5），（5,1），（5,3），（5,5），（2,2），（2,6），（6,2），（6,6），（4,4）课堂练习：P37习题1.3的1,6（判断等价关系），3（求等价类）,8，2（求等价

19、关系）课堂练习P37习题1.3判断等价关系：1,6求等价类：3求等价关系：8划分、等价关系、等价类概念之间关系如果R是集合X的一个等价关系，则等价类是集合X的一个划分。1.4 关系矩阵关系的表示常用列表、有序对、关系图，再介绍一种表示从X到Y的关系的便利方法关系矩阵。它是01矩阵（后面第3章介绍矩阵的相关知识）。计算机可以用这种方法来对一个关系进行分析。我们用X中元素来标记行（以任意的次序），用Y中元素来标记列（也是任意的次序）。如果有xRy,我们就令x行y列的元素之值为1，否则，其值为0。这个矩阵就称为关系R的矩阵（与X和Y的次序对应），简称关系矩阵。阅读P38例1.4.1，例1.4.2，例

20、1.4.3关系矩阵特征满足自反性、对称性、反对称性的关系R，其关系矩阵特征阅读P39(1)(2)(3)课堂练习：P40习题1.4的1,2,3关系矩阵的关系运算关系复合关系矩阵相乘例1.4.6 令R1是从X=1,2,3到Y=a,b的关系，定义为：R1=(1,a),(2,b),(3,a),(3,b)令R2是从Y到Z=x,y,z的关系，定义为：R2=（a，x），（a,y）,(b,y),(b,z)则R1与R2的复合是R2R1=(1,x),(1,y),(2,y),(2,z),(3,x),(3,y),(3,z)而R1对应于次序1,2,3和a，b的关系矩阵是：A1R2的对应于次序a，b和x,y,z的关系矩阵

21、是：A2两个矩阵相乘得：再将矩阵之积A1A2中，非0元素用1代替定理1.4.7 令R1是从X到Y的关系，R2是从Y到Z的关系。选择好X,Y和Z的次序，所有的关系矩阵都是与这个次序相对应的。令R1的关系矩阵是A1，R2的关系矩阵是A2。则R2R1的关系矩阵是：在矩阵之积A1A2中，把非0项用1代替而得的矩阵。课堂练习：P41习题1.4的4,5,6,8,71.5 关系数据库比较流行的数据模型有三种：层次模型、网状模型、关系模型。应用最广泛的为关系模型。关系数据模型的基本结构是表（Table)，由行和列组成，表又称为关系(Relation，)。关系数据库中的几个名词，在不同领域有不同称谓：列、行、二

22、维表属于日常用语；属性、元组、关系属于数学用语；字段、记录、数据库是数据库领域用语。如果一个表有n列，其对应的关系就称为n元关系。表1.5.1表示一个4元关系字段、记录、数据库字段：表格的每一列称为一个字段（属性），字段名相当标题栏中的标题。表1.5.1包含了4个字段（属性）：ID号、姓名、位置、年龄。表的每一列数据都属于同一类型。记录：表格中的每一行称为一条记录（元组），记录是由若干相关的属性组成。如表1.5.1的第一条记录是(22012,Johnson,捕手,22)，表中每条记录是4元组。数据库：由相互关联的数据表组成，它可以是一个文件，也可以由若干文件，按照一定法则组织而成。数据库管理系

23、统则是一些程序，它能帮助用户访问数据库中的信息。由E.F.科德（Codd）在1970年提出的关系数据库模型，就是基于n元关系的概念。表1.5.1所表示的关系可以表示为4元组的集合。（22012，Johnson，捕手，22），（93831，Glover，外场，24），（58199，Battery，投手，18），（84341，Cage，捕手，30），（01180，Homer，一垒，37)，（26710，Score，投手，22），（61049，Johnson,外场，30），（39826，Singleton，二垒，31）关系模型特点关系模型的特点是：1、每一列是基本数据，不能再分解；2、表中每一列必须

24、是相同数据类型（如字符型、数值型）；3、每一列的名字必须唯一；4、表中不能有内容完全相同的行；5、行的顺序、列的顺序不影响表所表示对的信息的含义关键字主键(Key)关键字是指表中的某一列，该列的值能唯一的标识一行。如表1.5.1的4个属性：ID号、姓名、位置，年龄，只有ID号字段为关键字，因为每个人的ID号是唯一的，即对于表中的每一条记录，ID号的值是唯一的。在绝大多数情况下，姓名字段都是不能设定为关键字的，因为不同的人可以有相同的姓名。同理，我们也不能把位置或年龄作为关键字。关键字可以由多个字段构成。在表1.5.1中，姓名和位置的联合可以作为关键字，因为一个运动员可以唯一地由姓名和位置来确定

25、。数据库的基本操作运算计算机系统可以把大量的信息存放在数据库中。人们可以对数据进行各种操作，比如，一个数据库管理系统要执行查询、插入、删除，以及从一些重叠的数据库中组合记录的操作。在例1.5.1中，“找出所有的外场手”就是一个有意义的关系查询。下面我们讨论对关系的基本操作运算。选择：选择操作符Sc是从n元关系中选择符合给定条件c的某些n元组构成新的n元关系。投影：投影操作符P（i1，i2，im)将n元组（a1，a2，an）映射为m元组（ai1，ai2，aim）。也就是在n元组的关系中选择符合给定条件的那些列i1，i2，im构成一个m元新关系。连接：选择和投影操作通常用来处理单个的关系。而连接运

26、算J用于处理两个关系，它从两个关系中产生一个新关系。阅读P43例1.5.2（选择）阅读P43例1.5.3（投影）阅读P44例1.5.4（连接）从例中看到，选择运算的结果是一个表的水平方向的子集，此处的选择操作符：运动员位置=捕手。投影运算的结果是一个表的垂直方向的子集，例中投影操作符：运动员姓名，位置。连接运算首先将关系R,S形成笛卡尔积RS，然后根据连接条件，从RS中选出某些元组，最后对选择的元组进行投影操作，消除重复列和多余字段列。例中连接操作符：运动员ID号=PID分配。数据库查询的综合操作：阅读P45例1.5.5，例1.5.6课堂练习：P46习题1.5的1,21.6 函数函数广泛存在于

27、数学和计算机科学之中，虽它们对函数定义的表述不同，但本质上都是由输入、输出、对应关系（算法）三部分组成，是一系列有序对，即满足特定条件的一种关系。C语言中，将输入与输出之间的关系看成是一种函数关系。定义1.6.1设R是集合A到集合B的一个关系，对于任意的xA，存在唯一的yB，使得(x,y)R，则称关系R为集合A到集合B的函数。此处的定义与我们中学数学里的函数定义是一致的：对每一个x，通过规则f，都有唯一确定的y与之对应，我们就说y是x的函数，记为y=f(x)。有时候，我们把f(x)称为x的像，x称为f(x)的原像。单射、满射、双射在数学里，函数符号通常用一个英文字母f、g、h或希腊字母表示。但

28、在计算机科学里，函数的符号可根据具体情况选用不同的字符，如max、min、average、delete_string等。函数和关系两个概念的区别：阅读P49例1.6.3，例1.6.4，例1.6.5变量之间的对应可分为：一对一，多对一，一对多，其中哪种对应方式构成函数？在函数f:XY上,其对应可分为：单射、满射、双射。阅读P49定义1.6.6P50例定义1.6.11函数运算反函数、复合函数由于函数是特殊类型的关系，类似于关系的逆、关系的复合，我们可以定义反函数、函数的复合。函数二元运算、一元运算课堂练习：P53习题1.6的1,3函数运算取整函数递归定义我们常说的“知道他的过去，就知道他的现在；知

29、道他的过去和现在，就可知道他的将来”，正是体现了递归的思想。一般地，如果一个问题可以归结到其前面的一个问题或几个问题，这就是递归问题。有些数学教材上把递归又称为递推。递归地定义非负整数集上的函数，要使用两个步骤：基础步骤：规定这个函数在0处的值。（已解决的基础问题）递归步骤：给出从较小整数的值来求当前值的规则。(自身调用语句）如在求阶乘n!运算中,已解决的基础问题是0!=1，自身调用语句（递归算法）为：n!=(n-1)!n下函数取整(floor)、上取整函数(ceiling)定义1.6.21 X的下取整函数（floorfunction），表为，是小于或等于的最大整数。的上取整函数(ceilingfunction)，表为，是大于或等于的最小整数。阅读P52例1.6.22，例1,6,23，例1.6.24，例1.6.25课堂练习：P53习题1.6的9Thank You！