《关系和函数》PPT课件.ppt

SetsSets 集合集合 4.1笛卡儿积与二元关系 在现实社会中有许多事物是成对出现 的，而且其中的两个事物是有一定次序 的，例如 一双鞋子有左右只， 影剧院的坐号的表示（排号） 平面上点的表示，等， 概括起来，数学上用两个有次序的元素 组成一个称之为序偶的结构就可以表示 现实世界中那种成对出现而且有一定次 序关系的事物 Date1liu qun, northeastern Univ. SetsSets 集合集合 两个具有固定次序的客体组成的集合，记作： 序偶 1.序偶可看作是具有两个元素组成的集合，即=x,x,y。 2.序偶刻画了两个客体间的次序,它并不表示由两个元素组成的集合 ; x,y=y,x 3.序偶中的元素分别称为的第一客体与第二客体 4.序偶只有当其两个客体相同且次序相同时才相等 5.序偶的元素可分别来自两个集合，它们可以代表不同类型的事物， 但次序确定 4.1笛卡儿积与二元关系序偶 Date2liu qun, northeastern Univ. SetsSets 集合集合 例1 A=1，2，24 ，B=1，2，60 ， 对aA，bB，则为一序偶，表示几点几分。 有序对 不是由两个元素组成的集合 x,y 例2 在笛卡儿坐标系中，平面上点的坐标（x，y） 就是有序对。 （1，2） ， （2，1）代表不同的点。 （1，1） ， （2，2）代表点（ 允许 x=y） 4.1笛卡儿积与二元关系序偶 例3 A为操作码集合，B为指令码集合，对aA，bB， 则为一序偶，表示一条地址指令 Date3liu qun, northeastern Univ. SetsSets 集合集合 三元组是一个序偶，其第一元素本身也是一个序偶， 可形式化表示为，z. 三元组 1.不是一个三元组,只是一个序偶 2.四、五元组类似定义 3.n元组 n元组是一个序偶，其第一元素为（n-1） 元组可形式化表示为： 4.1笛卡儿积与二元关系序偶 Date4liu qun, northeastern Univ. SetsSets 集合集合 设A和B是任意两个集合，若序偶的第一成员是A的元素， 第二成员是B的元素，所有这样序偶的集合，称为集合A与 B的笛卡尔积（直积）， 记作 笛卡尔积 4.1笛卡儿积与二元关系笛卡尔积 Date5liu qun, northeastern Univ. SetsSets 集合集合 例 一天内的时间可用时分表示， 它们的全体可用笛卡儿乘积表示 例 上面例3所有指令的集合构成一个操作码与指令 码集合的笛卡儿积AB 例 平面上直角坐标中的所有点可用笛卡儿乘积表示 其中 (R为实数集) 直积不具有交换率 例 设试求AB和BA 由此得 4.1笛卡儿积与二元关系笛卡尔积 Date6liu qun, northeastern Univ. SetsSets 集合集合 多重直积 = =| 例 A=1，2 B=a，b C=， 4.1笛卡儿积与二元关系笛卡尔积 Date7liu qun, northeastern Univ. SetsSets 集合集合 其中、 例 计算机内的字是由固定的n个有序二进位所组成， 它的全体可以表示成n重有序组形式 4.1笛卡儿积与二元关系笛卡尔积 Date8liu qun, northeastern Univ. SetsSets 集合集合 定理 设A，B，C为任意三个集合，则有 a) A（BC）=（AB）（AC）； b) A（BC）=（AB）（AC）； c)（AB）C=（AC）（BC）； d)（AB）C=（AC）（BC）。 4.1笛卡儿积与二元关系笛卡尔积 Date9liu qun, northeastern Univ. SetsSets 集合集合 关系在日常生活中无处不在， 我们熟知的一些常见的关系刻划着事物的结构。 例设一旅馆有n个房间，每个房间可住两个旅客，所以 一共可住2n个旅客。在旅馆内，旅客与房间有一定的关 系，我们讨论关系“某旅客住在某房间”，用R表示这种关 系，设n=3旅客分别为a,b,c,d,e,f 旅客住房间用表示: a与1间存在关系R记aR1 b与1间存在关系R记bR1 c与2间存在关系R记cR2 d与2间存在关系R记dR2 e与3间存在关系R记eR3 e与3间存在关系R记eR3 4.2关系及运算关系 Date10liu qun, northeastern Univ. SetsSets 集合集合 4.2关系及运算关系 满足的关系可看成是一个有序偶：(p,q) 如aR1可写成有序偶： (a,1) 满足R的所有关系可看成是一个有序偶的集合，这个集叫R，即 这种关系称为二元关系，它只涉及两个客体间的关系 若 则AB 的任何子集都定义了一个二元关系。 关系在现实社会中处处可见 如 看电影对号入座 关系型数据库里的关系（成绩单）等 Date11liu qun, northeastern Univ. SetsSets 集合集合 若一个集合的元素都是有序对，则称这个集合是一个 二元关系，简称关系,记为 R， 在R中的任一序偶，可记为R或xRy。 关系 即设有任意两个集合X和Y，XY的子集R称作X到Y的 （二元）关系。 当X=Y时，称R为X上的二元关系 4.2关系及运算关系 Date12liu qun, northeastern Univ. SetsSets 集合集合 例 实数集R上小于等于的关系为 = 注意 前一个 为关系，后一个 为不等号 例 设 A=a,b,是 2A上的包含于关系，求 解 4.2关系及运算关系 Date13liu qun, northeastern Univ. SetsSets 集合集合 前域 设二元关系R，由 R中的所有x组成的集合 ，称为R的前域，记作domR。 即 domR=x|y（R） 值域 设二元关系R，由 R中的所有y组成的集合 ，称为R的值域，记作ranR。 即 ranR=x|x（R） 域 R的前域和值域一起称作R的域，记为 FLDR=domRranR 例令A=a，b，c, B=1，2，3 R=， 则 domR=a，b ranR=1，2，3 FLDR=a，b，1，2，3 关系也可以用图表来表示.如右 4.2关系及运算关系 Date14liu qun, northeastern Univ. SetsSets 集合集合 三种特殊关系 全域关系 XY的平凡子集XY称为X到Y的全域关系。 空关系 XY的平凡子集，称为X到Y的空关系。 例 H=f,m,s,d, 写出成员关系，不相识关系，长幼关系 恒等关系 设Ix是X上的二元关系，且满足条件 Ix=|xX 则称Ix是X上的恒等关系。 例 4.2关系及运算关系 Date15liu qun, northeastern Univ. SetsSets 集合集合 设两个有限集合 R为X到Y的一个二元关系， 对应于关系R有一个关系矩阵 关系矩阵 其中 4.2关系及运算关系表示法 Date16liu qun, northeastern Univ. SetsSets 集合集合 设两个有限集合 R为X到Y的一个二元关系， 关系图 4.2关系及运算关系表示法 Date17liu qun, northeastern Univ. SetsSets 集合集合 解D=|x，yA，x|y =， ， ， ， ， 例设A=2，3，6，8，12，32 试写出A上的整除关系D 当元素与自身够成关系时， 用一个闭合的有向弧表示 关系图为关系表为 A A 23681232 2101111 3011010 6001010 8000101 12000010 32000001 矩阵形式为 4.2关系及运算关系表示法 Date18liu qun, northeastern Univ. SetsSets 集合集合 P2 P5 P4 P3 P1 例设有六个程序，它们之间有一定的调用关系 这个关系是集合 上的关系， 有 关系图为 矩阵形为 4.2关系及运算关系表示法 Date19liu qun, northeastern Univ. SetsSets 集合集合 定理 若Z和S是从集合X到集合Y的两个关系， 则Z，S的并、交、补、差仍是X到Y的关系。 例 设 X从Y到的关系: 则有 是从X到Y的一个新关系 有关集合的运算公式，在关系中也同样适合 4.2关系及运算关系表示法 Date20liu qun, northeastern Univ. SetsSets 集合集合 设R为X到Y的关系，S为从Y到Z的关系， 则RS称为R和S的复合关系， 即RS=| xXzZ(y)(yYRS) 复合关系 例 设某a与某b有“表兄妹”关系R，b与c有“父子”关系S， 则a与c有新关系“舅甥”关系P，是由R与S复合而成的， 称关系P是关系R与关系S的复合关系。 复合关系是一个从到的关系 即X到Y的关系为 Y到Z的关系为 则复合关系为 关系是集合，可进行集合的并、交、补运算，产生新的关系。 除此之外，还有其特殊的运算。 4.2关系及运算运算 Date21liu qun, northeastern Univ. SetsSets 集合集合 例 设 则 例 设 从X到Y的关系 从Y到z的关系 由此得从X到Z的关系 1 2 3 1 2 3 1 2 3 复合关系可以用图表示如右 4.2关系及运算运算 Date22liu qun, northeastern Univ. SetsSets 集合集合 复合运算不满足交换律。但复合运算满足结合律 即设 R是从X到Y的关系，S是从Y到Z的关系，P是从Z到W的关系， 则有 （RS）P=R（SP） 证明 :先证 设 有 类似可知 故 于是R本身所组成的复合关系可写成： 4.2关系及运算运算 Date23liu qun, northeastern Univ. SetsSets 集合集合 复合关系可用矩阵运算表示 其中 为逻辑加(布尔加): 为逻辑乘(布尔积): 4.2关系及运算运算 Date24liu qun, northeastern Univ. SetsSets 集合集合 关系是序偶的集合， 由于序偶的有序性，交换次序后将得到一个新的关系， 逆关系 设R为X到Y的二元关系，如将R中每一序偶的元素顺序互换， 所得到的集合称为R的逆关系，记作 即 例如 父子关系的逆关系是子亲关系， “”关系的逆关系是“”关系 也有些关系的逆关系是相等的 例如 朋友关系，实数的相等关系 4.2关系及运算运算 Date25liu qun, northeastern Univ. SetsSets 集合集合 Rc的关系图是由R的关系图通过将其中的所有的有向 弧的方向逆转得到， Rc的关系矩阵MRC可由R的关系矩阵转置得出 4.2关系及运算运算 Date26liu qun, northeastern Univ. SetsSets 集合集合 定理 设R，R1和R2都是从X到Y的二元关系， 则下列各式成立： 定理 设T为从X到Y的关系，S为从Y到Z的关系，则 定理 设R为X上的二元关系，则 R是对称的，仅当 R是反对称的，仅当 4.2关系及运算运算 Date27liu qun, northeastern Univ. SetsSets 集合集合 设R为X上的二元关系，如果对于xX必有xRx， 称R为X上的自反关系， 自反关系 即（ x）（x XxRx）为真。 例 在实数R上的关系“为A上的一个传递关系 如果你感到大惑不解的话，你可以自问一下，“关系R是否真的不符合定义”问题 出现了，归根结底还是一种对蕴含形式给出的命题PQ的不正确的理解。PQ 为真，要求的是对假设前提为真时，结论Q一定为真。除此之外，它并不理会别 的什么，反过来说，你要证实PQ不是真的，只能通过举一个反例的方法才成 ，即找出一种情况，这时P成立（为真），而Q不成立（为假），那么，在此例 中，R=，你能找到这样的三个元素xA，yA，zA，使得xRy， yRz都成立吗？不能，这就是说既然你举不出一种假设前提为真的情况，你又如 何去论证PQ为假呢？于是又回到过去讲过的“善意推断” 4.3关系及运算性质 Date32liu qun, northeastern Univ. SetsSets 集合集合 4.4关系的闭包运算 前面介绍的关系的运算，都是构成新关系的一种途径， 闭包运算是通过对其进行扩充序偶来构成一种新的关系 闭包 Date33liu qun, northeastern Univ. SetsSets 集合集合 例设A=a，b，c， R=， r(R)= ， 若在添加得 R=，, 虽然也是自反的，但却不是最小的了 s(R)=， t(R)=， 例 集合上的”=”关系. 它的自反闭包对称闭包传递闭包都是自身 自反闭包，对称闭包，传递闭包 分别是包含原关系的最小自反关系，对称关系，传递关系。 如何寻找闭包呢？下面给出了寻找它们的法则 4.4关系的闭包运算 Date34liu qun, northeastern Univ. SetsSets 集合集合 定理 设R是X上的二元关系，那么 R是自反的，当且仅当r(R)=R R是对称的，当且仅当s(R)=R R是传递的，当且仅当t(R)=R。 例R=， 则r(R)=R R=，, 则S(R)=R R=, 则t(R)=R 此定理用于判断 4.4关系的闭包运算 Date35liu qun, northeastern Univ. SetsSets 集合集合 定理 设R是集合X上的二元关系，则 r（R）=RIx 例 设A=a，b，c，d, 则Ix=, RIx=r(R) 自反闭包的构造 4.4关系的闭包运算 Date36liu qun, northeastern Univ. SetsSets 集合集合 定理 设R是集合X上的二元关系，则 S（R）=RRc 例 设R=， 则Rc =， s(R)= RRc 对称闭包的构造 4.4关系的闭包运算 Date37liu qun, northeastern Univ. SetsSets 集合集合 定理 设R是集合X上的二元关系，则 定理 设X是含有n个元素的集合，R是X上的二元关系， 则存在一个正整数kn，使得 4.4关系的闭包运算 Date38liu qun, northeastern Univ. SetsSets 集合集合 例设A=a，b，c，d， R=， 求t（R） 解 R2=, R3=, R4=, 故 t（R）= 用矩阵形式表示 ， ， ， = 4.4关系的闭包运算 Date39liu qun, northeastern Univ. SetsSets 集合集合 当有限集X元素太多时，运算较麻烦，这是有如下算法 传递闭包R+的Warshall算法 （1）置新矩阵A：=M； （2）置i：=1； （3）对所有j，如果Aj,i=1，则对k=1，2，n， 有 Aj,k：=Aj,k+Ai,k; （4）i加1 （5）如果in，则转到步骤（3），否则停止。 例P124/3 4.4关系的闭包运算 Date40liu qun, northeastern Univ. SetsSets 集合集合 4.4关系的闭包运算 Date41liu qun, northeastern Univ. SetsSets 集合集合 4.5等价关系和偏序关系覆盖与划分 若把一个集合A分成若干个叫做分块的非空子集， 使得A中每个元素至少属于一个分块， 这些分块的全体叫做A的一个覆盖。 即设A为非空集合， 覆盖 则集合S称作集合A的覆盖。 例 学校运动员全体人员组成的集合为A，每个运动队为 一Si,则所有的运动队组成了A的一个覆盖 Date42liu qun, northeastern Univ. SetsSets 集合集合 划分 设S为A的一个覆盖，若A中的每个元素属于且仅属于S的 一个分块，那末S称作是A的一个划分。 即若S是集合A的覆盖，且满足SiSj=， 这里（ij）则称S是A的划分。 例如 人群中的同姓关系，性别关系，年龄段关系等， 都是人群的划分 覆盖是可以重叠的，而划分是不能重叠的 4.5等价关系和偏序关系覆盖与划分 Date43liu qun, northeastern Univ. SetsSets 集合集合 4.5等价关系和偏序关系覆盖与划分 Date44liu qun, northeastern Univ. SetsSets 集合集合 例如 两个色子投掷点数的集合，如何划分，如何加细 4.5等价关系和偏序关系覆盖与划分 Date45liu qun, northeastern Univ. SetsSets 集合集合 4.5等价关系和偏序关系覆盖与划分 Date46liu qun, northeastern Univ. SetsSets 集合集合 等价关系 设R为定义在集合A上的一个关系， 若R是自反的、对称的和传递的， 则R称为A上的等价关系。 例 人群所组成的的集合上的“同姓”关系是等价关系 例 所有三角形所组成的集合上的“相似”关系是等价 例 在坐的所有人，“同学”关系是等价的 4.5等价关系和偏序关系等价关系 Date47liu qun, northeastern Univ. SetsSets 集合集合 例 X是整数集，X上的关系R 此关系是等价关系，m为任意正整数既： 满足这个关系R的x和y，用m除所有相同的余数这个 关系也叫同余关系或称以m为模的同余关系，一般将 xRy写成 叫做x与y对模m是同余的的，这种式子称为同余式用 上例方法可证：同余关系是一个等价关系。 4.5等价关系和偏序关系等价关系 Date48liu qun, northeastern Univ. SetsSets 集合集合 等价类 设R为集合A上的等价关系，对任何aA， 集合aR=x|xA，aRx,称为元素a形成的R等价类。 例 两个人同姓，这个关系为等价关系 所有同姓的人构成一个等价类 4.5等价关系和偏序关系等价关系 Date49liu qun, northeastern Univ. SetsSets 集合集合 等价类的性质 4.5等价关系和偏序关系等价关系 Date50liu qun, northeastern Univ. SetsSets 集合集合 集合X上的等价关系R所够成的类，它们两两互不相交且 覆盖整个集合X，故它们构成X的一个划分，而每个类是 这个划分的快。 由此得： 商集 即商集是由等价类为元素构成的集合 4.5等价关系和偏序关系等价关系 Date51liu qun, northeastern Univ. SetsSets 集合集合 4.5等价关系和偏序关系等价关系 Date52liu qun, northeastern Univ. SetsSets 集合集合 4.5等价关系和偏序关系等价关系 Date53liu qun, northeastern Univ. SetsSets 集合集合 定理 设给定集合A上等价关系R， 对于a,bA，有aRb，iffaR=bR。 定理 集合A上有一个等价关系R， 决定了A的一个划分，该划分就是商集A/R。 定理 集合A的一个划分确定A 的元素间的一个等价关系。 利用关系式很容易判断等价关系和等价类 4.5等价关系和偏序关系等价关系 Date54liu qun, northeastern Univ. SetsSets 集合集合 012 3 5 68 其关系图为 从图中知，此关系满足自反性，对称性，传递性， 即为等价关系R的等价类有3类 4.5等价关系和偏序关系等价关系 Date55liu qun, northeastern Univ. SetsSets 集合集合 例 设集合 上的关系R为 关系图为 由图知R为等价关系，等价类 bc ad 4.5等价关系和偏序关系等价关系 Date56liu qun, northeastern Univ. SetsSets 集合集合 偏序集 设A是一个集合，如果A上的一个关系R， 满足自反性，反对称性和传递性， 则称R是A上的一个偏序关系，并记为“ ” 序偶 称为偏序集 例 由集合A所组成的幂集2A上的关系 是自反的，非对称的，传递的，故他是编序的 例 奇数集I上的“,。 显然 ，等等。 2)设X=Y=R（实数集）， 显然 f对应一条在x轴上方顶点在原点的折线 3)设（PQ）R表示命题演算的一个合式公式。对每一个 命题变元都能且只能以V=F，T中的两元素之一代入。其 结果对应一张真值表。于是合式公式表示一个从 的函 数。实际上，我们早在第二章里就用过命题函数这个名词。 定义一个函数，只是规定一种将集合X中每一元素变换成另一集合Y（ 允许Y=X）中确定的一个元素的规则 4.6函数的概念 Date73liu qun, northeastern Univ. SetsSets 集合集合 函数相等 即定义域和对应关系相同的函数相等 4.6函数的概念 Date74liu qun, northeastern Univ. SetsSets 集合集合 函数集合 4.6函数的概念 Date75liu qun, northeastern Univ. SetsSets 集合集合 4.6函数的概念 Date76liu qun, northeastern Univ. SetsSets 集合集合 4.6函数的概念 Date77liu qun, northeastern Univ. SetsSets 集合集合 三类特殊的映射 单射：不同的x函数值不同 满射：B为A的值域 双射：一一对应 （或入射） 4.6函数的概念 注意f(A)与f(x)的区别 f(A)为A在f下的像集 f(x)为x在f下的像 Date78liu qun, northeastern Univ. SetsSets 集合集合 例 则f为单射，非满射 例 则f为满射，非单射 例 则f为双射 4.6函数的概念 Date79liu qun, northeastern Univ. SetsSets 集合集合 4.7逆函数和复合函数 逆函数 一、逆函数 Date80liu qun, northeastern Univ. SetsSets 集合集合 X Y x1 x2 x3 X Y 不存在逆函数的举例图 y1 y2 y3 y4 x1 x2 x3 x4 y1 y2 y3 以上分析说明了双射是函数有逆函数的必要条件。还 容易证明双射也是函数可逆的充分条件。这是说，一 个建立在X到Y上的双射。则f作为二元关系，它的逆关 系也一定是一个函数。且也是双射。 定理 一个函数可逆的充分必要条件为函数是双射。 并且逆函数也是双射。 由逆函数的定义可知，若函数f可逆，则必有 4.7逆函数和复合函数 逆函数 Date81liu qun, northeastern Univ. SetsSets 集合集合 二、复合函数 4.7逆函数和复合函数 复合函数 Date82liu qun, northeastern Univ. SetsSets 集合集合 4.7逆函数和复合函数 复合函数 Date83liu qun, northeastern Univ. SetsSets 集合集合 X Y Z x1 x2 x3 x4 Z1 Z2 z3 X Z 复合函数举例图 y1 y2 y3 y4 y5 x1 x2 x3 x4 Z1 Z2 z3 例 求上图中给出的g在f左复合所得复合函数。 解 关系的任何普遍成立的性质，函数亦同样具有。所以现 在用矩阵的布尔乘法来计算该复合函数。 故 4.7逆函数和复合函数 复合函数 Date84liu qun, northeastern Univ. SetsSets 集合集合 函数复合的结合性 4.7逆函数和复合函数 复合函数 Date85liu qun, northeastern Univ. SetsSets 集合集合 4.7逆函数和复合函数 复合函数 Date86liu qun, northeastern Univ. SetsSets 集合集合 4.7逆函数和复合函数 复合函数 Date87liu qun, northeastern Univ. SetsSets 集合集合 4.7逆函数和复合函数 复合函数 Date88liu qun, northeastern Univ. SetsSets 集合集合 4.7逆函数和复合函数 复合函数 Date89liu qun, northeastern Univ. SetsSets 集合集合 4.7逆函数和复合函数 Date90liu qun, northeastern Univ. SetsSets 集合集合 接P96 函数：1、要素 2、 表达（映射关系） 3、函数集合 4、特殊映射（单、满、双） 5、逆函数与复合函数 Date91liu qun, northeastern Univ. SetsSets 集合集合 2.3.11相容关系 给定集合A上关系r，若r是自反的，对称的， 则称r是相容关系。 相容关系 例 设有字母串集合 在X上的关系R是：字母串间有相同的字母。即 则可验证R是自反的，对称的 故R是相容的 Date92liu qun, northeastern Univ. SetsSets 集合集合 2.3.11相容关系 例 设 关系R为元素间有相同的数字。即 R= R= 则R满足自反性，对称性，故R是相容关系。 相容关系用“”表示，如2166243，243375但2166375 一般来说，想容关系不满足传递性 Date93liu qun, northeastern Univ. SetsSets 集合集合 2.3.11相容关系 例2中的元素用 表示，则