关系和函数PPT课件

《关系和函数PPT课件》由会员分享，可在线阅读，更多相关《关系和函数PPT课件（100页珍藏版）》请在金锄头文库上搜索。

1、S e t sS e t s集合集合集合集合 笛卡儿积与二元关系笛卡儿积与二元关系笛卡儿积与二元关系笛卡儿积与二元关系在现实社会中有许多事物是成对出现的，而且其中的两个事物是有一定次序的，例如一双鞋子有左右只，影剧院的坐号的表示（排号）平面上点的表示，等，概括起来，数学上用两个有次序的元素组成一个称之为序偶的结构就可以表示现实世界中那种成对出现而且有一定次序关系的事物9/17/20241S e t sS e t s集合集合集合集合 两个具有固定次序的客体组成的集合，记作：序偶序偶1.序偶可看作是具有两个元素组成的集合，即=x,x,y。2.序偶刻画了两个客体间的次序,它并不表示由两个元素组成的集

2、合;x,y=y,x3.序偶中的元素分别称为的第一客体与第二客体4.序偶只有当其两个客体相同且次序相同时才相等5.序偶的元素可分别来自两个集合，它们可以代表不同类型的事物，但次序确定笛卡儿积与二元关系笛卡儿积与二元关系笛卡儿积与二元关系笛卡儿积与二元关系序偶序偶序偶序偶9/17/20242S e t sS e t s集合集合集合集合 例例1A=1，2，24，B=1，2，60，对aA，bB，则为一序偶，表示几点几分。有序对不是由两个元素组成的集合x,y例例2在笛卡儿坐标系中，平面上点的坐标（x，y）就是有序对。（1，2），（2，1）代表不同的点。（1，1），（2，2）代表点（允许x=y）笛卡儿积与

3、二元关系笛卡儿积与二元关系笛卡儿积与二元关系笛卡儿积与二元关系序偶序偶序偶序偶例例3A为操作码集合，B为指令码集合，对aA，bB，则为一序偶，表示一条地址指令9/17/20243S e t sS e t s集合集合集合集合 三元组是一个序偶，其第一元素本身也是一个序偶，可形式化表示为，z.三元组三元组1.x,不是一个三元组,只是一个序偶2.四、五元组类似定义元组元组n元组是一个序偶，其第一元素为（n-1）元组可形式化表示为：笛卡儿积与二元关系笛卡儿积与二元关系笛卡儿积与二元关系笛卡儿积与二元关系序偶序偶序偶序偶9/17/20244S e t sS e t s集合集合集合集合 设A和B是任意两个

4、集合，若序偶的第一成员是A的元素，第二成员是B的元素，所有这样序偶的集合，称为集合A与B的笛卡尔积（直积），记作笛卡尔积笛卡尔积笛卡儿积与二元关系笛卡儿积与二元关系笛卡儿积与二元关系笛卡儿积与二元关系笛卡尔积笛卡尔积笛卡尔积笛卡尔积9/17/20245S e t sS e t s集合集合集合集合 例例一天内的时间可用时分表示，它们的全体可用笛卡儿乘积表示例例上面例3所有指令的集合构成一个操作码与指令码集合的笛卡儿积AB例例平面上直角坐标中的所有点可用笛卡儿乘积表示其中(R为实数集)直积不具有交换率例例 设设试求AB和BA由此得笛卡儿积与二元关系笛卡儿积与二元关系笛卡儿积与二元关系笛卡儿积与二元

5、关系笛卡尔积笛卡尔积笛卡尔积笛卡尔积9/17/20246S e t sS e t s集合集合集合集合 多重直积多重直积=| 例例A=1，2 B=a，b C=，笛卡儿积与二元关系笛卡儿积与二元关系笛卡儿积与二元关系笛卡儿积与二元关系笛卡尔积笛卡尔积笛卡尔积笛卡尔积9/17/20247S e t sS e t s集合集合集合集合 其中、例例计算机内的字是由固定的n个有序二进位所组成，它的全体可以表示成n重有序组形式笛卡儿积与二元关系笛卡儿积与二元关系笛卡儿积与二元关系笛卡儿积与二元关系笛卡尔积笛卡尔积笛卡尔积笛卡尔积9/17/20248S e t sS e t s集合集合集合集合 定理定理 设A，

6、B，C为任意三个集合，则有a)A（BC）=（AB）（AC）；b)A（BC）=（AB）（AC）；c)（AB）C=（AC）（BC）；d)（AB）C=（AC）（BC）。笛卡儿积与二元关系笛卡儿积与二元关系笛卡儿积与二元关系笛卡儿积与二元关系笛卡尔积笛卡尔积笛卡尔积笛卡尔积9/17/20249S e t sS e t s集合集合集合集合 关系在日常生活中无处不在，我们熟知的一些常见的关系刻划着事物的结构。例例设一旅馆有n个房间，每个房间可住两个旅客，所以一共可住2n个旅客。在旅馆内，旅客与房间有一定的关系，我们讨论关系“某旅客住在某房间”，用R表示这种关系，设n=3旅客分别为a,b,c,d,e,f旅客

7、住房间用表示:a与1间存在关系R记aR1b与1间存在关系R记bR1c与2间存在关系R记cR2d与2间存在关系R记dR2e与3间存在关系R记eR3e与3间存在关系R记eR3关系及运算关系及运算关系及运算关系及运算关系关系关系关系9/17/202410S e t sS e t s集合集合集合集合 关系及运算关系及运算关系及运算关系及运算关系关系关系关系满足的关系可看成是一个有序偶：(p,q)如aR1可写成有序偶：(a,1)满足R的所有关系可看成是一个有序偶的集合，这个集叫R，即这种关系称为二元关系，它只涉及两个客体间的关系若则AB的任何子集都定义了一个二元关系。关系在现实社会中处处可见如看电影对号

8、入座关系型数据库里的关系（成绩单）等9/17/202411S e t sS e t s集合集合集合集合 若一个集合的元素都是有序对，则称这个集合是一个二元关系，简称关系,记为 R，在R中的任一序偶，可记为R或xRy。关系关系即设有任意两个集合X和Y，XY的子集R称作X到Y的（二元）关系。当X=Y时，称R为X上的二元关系关系及运算关系及运算关系及运算关系及运算关系关系关系关系9/17/202412S e t sS e t s集合集合集合集合 例例实数集R上小于等于的关系为=注意前一个为关系，后一个为不等号例例设A=a,b,是2A上的包含于关系，求解解 关系及运算关系及运算关系及运算关系及运算关系

9、关系关系关系9/17/202413S e t sS e t s集合集合集合集合 前域前域 设二元关系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，3R=，则domR=a，branR=1，2，3FLDR=a，b，1，2，3关系也可以用图表来表示.如右关系及运算关系及运算关系及运算关系及运算关系关系关系关系9/17/202414S e t sS e t s集合集合集合

10、集合 三种特殊关系全域关系全域关系XY的平凡子集XY称为X到Y的全域关系。空关系空关系XY的平凡子集，称为X到Y的空关系。例 H=f,m,s,d,写出成员关系，不相识关系，长幼关系恒等关系恒等关系设Ix是X上的二元关系，且满足条件Ix=|xX则称Ix是X上的恒等关系。例关系及运算关系及运算关系及运算关系及运算关系关系关系关系9/17/202415S e t sS e t s集合集合集合集合 设两个有限集合R为X到Y的一个二元关系，对应于关系R有一个关系矩阵关系矩阵关系矩阵其中 关系及运算关系及运算关系及运算关系及运算关系表示法关系表示法关系表示法关系表示法9/17/202416S e t sS

11、 e t s集合集合集合集合 设两个有限集合R为X到Y的一个二元关系，关系图关系图关系及运算关系及运算关系及运算关系及运算关系表示法关系表示法关系表示法关系表示法9/17/202417S e t sS e t s集合集合集合集合 解解D=|x，yA，x|y=，例设例设A=2，3，6，8，12，32 试写出试写出A上的整除关系上的整除关系D 当元素与自身够成关系时，用一个闭合的有向弧表示关系图为关系表为 AA2368123221011113011010600101080001011200001032000001矩阵形式为关系及运算关系及运算关系及运算关系及运算关系表示法关系表示法关系表示法关系表

12、示法9/17/202418S e t sS e t s集合集合集合集合 P2P5P4P3P1例设有六个程序，它们之间有一定的调用关系例设有六个程序，它们之间有一定的调用关系这个关系是集合上的关系，有关系图为矩阵形为关系及运算关系及运算关系及运算关系及运算关系表示法关系表示法关系表示法关系表示法9/17/202419S e t sS e t s集合集合集合集合 定理定理 若Z和S是从集合X到集合Y的两个关系，则Z，S的并、交、补、差仍是X到Y的关系。例例设X从Y到的关系:则有是从X到Y的一个新关系有关集合的运算公式，在关系中也同样适合关系及运算关系及运算关系及运算关系及运算关系表示法关系表示法关

13、系表示法关系表示法9/17/202420S e t sS e t s集合集合集合集合 设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的关系为则复合关系为关系是集合，可进行集合的并、交、补运算，产生新的关系。除此之外，还有其特殊的运算。关系及运算关系及运算关系及运算关系及运算运算运算运算运算9/17/202421S e t sS

14、e t s集合集合集合集合 例例 设则例例 设从X到Y的关系从Y到z的关系由此得从X到Z的关系123123123复合关系可以用图表示如右关系及运算关系及运算关系及运算关系及运算运算运算运算运算9/17/202422S e t sS e t s集合集合集合集合 复合运算不满足交换律。但复合运算满足结合律即设R是从X到Y的关系，S是从Y到Z的关系，P是从Z到W的关系，则有（RS）P=R（SP）证明证明:先证设有类似可知故于是R本身所组成的复合关系可写成：关系及运算关系及运算关系及运算关系及运算运算运算运算运算9/17/202423S e t sS e t s集合集合集合集合 复合关系可用矩阵运算表

15、示 其中其中为逻辑加(布尔加):为逻辑乘(布尔积):关系及运算关系及运算关系及运算关系及运算运算运算运算运算9/17/202424S e t sS e t s集合集合集合集合 关系是序偶的集合，由于序偶的有序性，交换次序后将得到一个新的关系，逆关系逆关系设R为X到Y的二元关系，如将R中每一序偶的元素顺序互换，所得到的集合称为R的逆关系，记作即例如例如父子关系的逆关系是子亲关系，“”关系的逆关系是“”关系也有些关系的逆关系是相等的例如例如朋友关系，实数的相等关系关系及运算关系及运算关系及运算关系及运算运算运算运算运算9/17/202425S e t sS e t s集合集合集合集合 Rc的关系图

16、是由R的关系图通过将其中的所有的有向弧的方向逆转得到，Rc的关系矩阵MRC可由R的关系矩阵转置得出关系及运算关系及运算关系及运算关系及运算运算运算运算运算9/17/202426S e t sS e t s集合集合集合集合 定理定理设R，R1和R2都是从X到Y的二元关系，则下列各式成立：定理定理 设T为从X到Y的关系，S为从Y到Z的关系，则定理定理设R为X上的二元关系，则R是对称的，仅当R是反对称的，仅当关系及运算关系及运算关系及运算关系及运算运算运算运算运算9/17/202427S e t sS e t s集合集合集合集合 设R为X上的二元关系，如果对于xX必有xRx，称R为X上的自反关系，自

17、反关系自反关系即（x）（xXxRx）为真。例例 在实数R上的关系“”是自反的实数集R上小于等于的关系为=对任意xR，有xx例例 平面几何上三角形的相似关系为自反的设相似三角型的集合为A相似关系为对任意xA，有关系及运算关系及运算关系及运算关系及运算性质性质性质性质9/17/202428S e t sS e t s集合集合集合集合 例例在实数域上的关系”是反自反的，实数集R上小于的关系为不是自反的未必就一定是反自反的例例 在集合上的关系此关系既不是自反的亦不是反自反的一个关系的自反性与非自反性可能都不存在，一个关系的自反性在图形表示法中相当于一个关系图中的每一一个结点均有环出现。而一个关系的非自

18、反性相当于一个关系图中的每个结点均无环出现关系及运算关系及运算关系及运算关系及运算性质性质性质性质9/17/202429S e t sS e t s集合集合集合集合 例例 全集上的互补集A和是对称关系，即补集是互为的关系及运算关系及运算关系及运算关系及运算性质性质性质性质设R为X上的二元关系，如果对于每个x，yX，每当xRy，就有yRx，则称R是X上的对称关系，对称关系对称关系例例 一个班级的全体学员构成的集合，朋友关系是对称的，即朋友是互为的9/17/202430S e t sS e t s集合集合集合集合 反对称关系反对称关系设R为X上的二元关系，对于每一个x，yX，每当xRy和yRx，必

19、有x=y，则称R是X上的反对称关系，例例 父子关系是反对称的例例 包含关系是反对称的例例 小于等于关系是反对称的即除了自身,别的元素没有交换关系对称关系也非必具其一例例在集合上的关系这些关系既不是对称的亦不是非对称的关系的对称图形表示中相当于关系图中两个结点间如有边相连则一定有方向相反的两条有向边连接。一个关系的非对称图形相当于关系图中两个结点间如有有向边相连则一定只有一条边关系及运算关系及运算关系及运算关系及运算性质性质性质性质9/17/202431S e t sS e t s集合集合集合集合 设R为X上的二元关系，如果对任意x,y,z X，每当xRy,yRz时必有xRz, 称R是X上的传递

20、关系，传递关系传递关系即为真例例 实数域上的关系是传递的，因为若xy，yz则xz例例 集合上的包含关系是传递的，因为若因为若例例设A=a，b，c，R=为A上的一个传递关系如果你感到大惑不解的话，你可以自问一下，“关系R是否真的不符合定义”问题出现了，归根结底还是一种对蕴含形式给出的命题PQ的不正确的理解。PQ为真，要求的是对假设前提为真时，结论Q一定为真。除此之外，它并不理会别的什么，反过来说，你要证实PQ不是真的，只能通过举一个反例的方法才成，即找出一种情况，这时P成立（为真），而Q不成立（为假），那么，在此例中，R=，你能找到这样的三个元素xA，yA，zA，使得xRy，yRz都成立吗？不能

21、，这就是说既然你举不出一种假设前提为真的情况，你又如何去论证PQ为假呢？于是又回到过去讲过的“善意推断”关系及运算关系及运算关系及运算关系及运算性质性质性质性质9/17/202432S e t sS e t s集合集合集合集合 关系的闭包运算关系的闭包运算关系的闭包运算关系的闭包运算 前面介绍的关系的运算，都是构成新关系的一种途径，闭包运算是通过对其进行扩充序偶来构成一种新的关系闭包闭包9/17/202433S e t sS e t s集合集合集合集合 例例设A=a，b，c，R=，r(R)=，若在添加得R=，,虽然也是自反的，但却不是最小的了s(R)=，t(R)=，例例集合上的”=”关系.它的

22、自反闭包对称闭包传递闭包都是自身自反闭包，对称闭包，传递闭包分别是包含原关系的最小自反关系，对称关系，传递关系。如何寻找闭包呢？下面给出了寻找它们的法则关系的闭包运算关系的闭包运算关系的闭包运算关系的闭包运算9/17/202434S e t sS e t s集合集合集合集合 定理定理设R是X上的二元关系，那么R是自反的，当且仅当r(R)=RR是对称的，当且仅当s(R)=RR是传递的，当且仅当t(R)=R。例例R=，则r(R)=RR=，,则S(R)=RR=,则t(R)=R此定理用于判断关系的闭包运算关系的闭包运算关系的闭包运算关系的闭包运算9/17/202435S e t sS e t s集合集

23、合集合集合 定理定理 设R是集合X上的二元关系，则r（R）=RIx例例设A=a，b，c，d,则Ix=,RIx=r(R)自反闭包的构造关系的闭包运算关系的闭包运算关系的闭包运算关系的闭包运算9/17/202436S e t sS e t s集合集合集合集合 定理定理设R是集合X上的二元关系，则S（R）=RRc例例设R=，则Rc=，s(R)=RRc对称闭包的构造关系的闭包运算关系的闭包运算关系的闭包运算关系的闭包运算9/17/202437S e t sS e t s集合集合集合集合 定理定理设R是集合X上的二元关系，则定理定理设X是含有n个元素的集合，R是X上的二元关系，则存在一个正整数kn，使得

24、关系的闭包运算关系的闭包运算关系的闭包运算关系的闭包运算9/17/202438S e t sS e t s集合集合集合集合 例例设A=a，b，c，d， R=， 求t（R）解解 R2=, R3=, R4=,故 t（R）=用矩阵形式表示， ，=关系的闭包运算关系的闭包运算关系的闭包运算关系的闭包运算9/17/202439S e t sS e t s集合集合集合集合 当有限集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

25、（5）如果in，则转到步骤（3），否则停止。例例P124/3关系的闭包运算关系的闭包运算关系的闭包运算关系的闭包运算9/17/202440S e t sS e t s集合集合集合集合 关系的闭包运算关系的闭包运算关系的闭包运算关系的闭包运算9/17/202441S e t sS e t s集合集合集合集合 等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系覆盖与划分覆盖与划分覆盖与划分覆盖与划分 若把一个集合A分成若干个叫做分块的非空子集，使得A中每个元素至少属于一个分块，这些分块的全体叫做A的一个覆盖。即设A为非空集合，覆盖覆盖则集合S称作集合A的覆盖。例例 学校运动员

26、全体人员组成的集合为A，每个运动队为一Si,则所有的运动队组成了A的一个覆盖9/17/202442S e t sS e t s集合集合集合集合 划分划分设S为A的一个覆盖，若A中的每个元素属于且仅属于S的一个分块，那末S称作是A的一个划分。即若S是集合A的覆盖，且满足SiSj=，这里（ij）则称S是A的划分。 例例如人群中的同姓关系，性别关系，年龄段关系等，都是人群的划分覆盖是可以重叠的，而划分是不能重叠的等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系覆盖与划分覆盖与划分覆盖与划分覆盖与划分9/17/202443S e t sS e t s集合集合集合集合 等价关系和

27、偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系覆盖与划分覆盖与划分覆盖与划分覆盖与划分9/17/202444S e t sS e t s集合集合集合集合 例例如两个色子投掷点数的集合，如何划分，如何加细等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系覆盖与划分覆盖与划分覆盖与划分覆盖与划分9/17/202445S e t sS e t s集合集合集合集合 等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系覆盖与划分覆盖与划分覆盖与划分覆盖与划分9/17/202446S e t sS e t s集合集合集合集合 等价关系等价关系设R为

28、定义在集合A上的一个关系，若R是自反的、对称的和传递的，则R称为A上的等价关系。例例 人群所组成的的集合上的“同姓”关系是等价关系例例 所有三角形所组成的集合上的“相似”关系是等价例例 在坐的所有人，“同学”关系是等价的等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系等价关系等价关系等价关系 9/17/202447S e t sS e t s集合集合集合集合 例例X是整数集，X上的关系R此关系是等价关系，m为任意正整数既：满足这个关系R的x和y，用m除所有相同的余数这个关系也叫同余关系或称以m为模的同余关系，一般将xRy写成叫做x与y对模m是同余的的，这种式子称

29、为同余式用上例方法可证：同余关系是一个等价关系。等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系等价关系等价关系等价关系9/17/202448S e t sS e t s集合集合集合集合 等价类等价类设R为集合A上的等价关系，对任何aA，集合aR=x|xA，aRx,称为元素a形成的R等价类。例例两个人同姓，这个关系为等价关系所有同姓的人构成一个等价类等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系等价关系等价关系等价关系9/17/202449S e t sS e t s集合集合集合集合 等价类的性质等价类的性质等价关系和偏序关系等

30、价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系等价关系等价关系等价关系9/17/202450S e t sS e t s集合集合集合集合 集合X上的等价关系R所够成的类，它们两两互不相交且覆盖整个集合X，故它们构成X的一个划分，而每个类是这个划分的快。由此得：商集商集即商集是由等价类为元素构成的集合等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系等价关系等价关系等价关系9/17/202451S e t sS e t s集合集合集合集合 等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系等价关系等价关系等价关系9/17/

31、202452S e t sS e t s集合集合集合集合 等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系等价关系等价关系等价关系9/17/202453S e t sS e t s集合集合集合集合 定理定理设给定集合A上等价关系R，对于a,bA，有aRb，iffaR=bR。定理定理集合A上有一个等价关系R，决定了A的一个划分，该划分就是商集A/R。定理定理集合A的一个划分确定A的元素间的一个等价关系。利用关系式很容易判断等价关系和等价类等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系等价关系等价关系等价关系9/17/202454S

32、 e t sS e t s集合集合集合集合 0123568其关系图为从图中知，此关系满足自反性，对称性，传递性，即为等价关系R的等价类有3类等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系等价关系等价关系等价关系9/17/202455S e t sS e t s集合集合集合集合 例例 设集合上的关系R为关系图为由图知R为等价关系，等价类 bcad等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系等价关系等价关系等价关系9/17/202456S e t sS e t s集合集合集合集合 偏序集偏序集设A是一个集合，如果A上的一个关系R

33、，满足自反性，反对称性和传递性，则称R是A上的一个偏序关系，并记为“”序偶称为偏序集例例 由集合A所组成的幂集2A上的关系是自反的，非对称的，传递的，故他是编序的例例奇数集I上的“”是偏序关系例例一个单位里，部门的隶属关系是偏序等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系偏序关系偏序关系偏序关系偏序关系 9/17/202457S e t sS e t s集合集合集合集合 例例 证明集合A=2,3,6,8,12,16,24,32上的“整除”关系R=（x,y）|y/x=整数是偏序的236812162432证明1）因为每一个非零整数都可以整除它自己所以R是自反的2）任取两

34、个整数x,yA，并设则有x=py=pqx,即pq=1p=1,q=1故x=y，即R非对称3)任取两个整数x,y,zA，并设则有z=py=pqx,pq为整数，故即R可传递,故R为一偏序等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系偏序关系偏序关系偏序关系偏序关系9/17/202458S e t sS e t s集合集合集合集合 偏序关系因为反对称，所以关系图中是单向箭头盖住关系盖住关系从关系图中看，就是把间隔的关系去掉，如上例2368121624328为2的盖住，16为8的盖住，32为16的盖住等等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系偏序

35、关系偏序关系偏序关系偏序关系9/17/202459S e t sS e t s集合集合集合集合 对于给定的偏序集，它的盖住是唯一的，再将盖住图简略，即将自圈和关系箭头去掉，由上往下盖住即得“哈斯图哈斯图”哈斯图哈斯图236812162432链链设是一个偏序集合，在A的一个子集中，如果每两个元素都是有关系的，则称这个子集为链。例例如上例中B1=3，6，12，24，B2=2，6，24，B3=2，8，32，B4=2，16都是链虽然从哈斯图上看，很多链都是由一条折线上的所有点组成，但这不是必须的，如上例的链B2，B3，B4就是如此等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系

36、偏序关系偏序关系偏序关系偏序关系9/17/202460S e t sS e t s集合集合集合集合 反链反链设是一个偏序集合，在A的一个子集中，如果每两个元素都是无关系的，则称这个子集为反链。若A的子集只有单个元素，则这个子集既是链又是反链。例例C1=3，C2=6，8，C3=8，12都是反链从哈斯图上看到，每个链中总可以从最高节点出发，沿着盖住方向遍历该链中所有节点，每个反链中任何两个节点间均无连线等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系偏序关系偏序关系偏序关系偏序关系9/17/202461S e t sS e t s集合集合集合集合 全序集全序集设为一个偏序集

37、，若A是一个链，则称是全序集或线序集。在这种情况下，二元关系称为全序关系或线序关系。例如例如上例中B1=3，6，12，24构成的集合集合A本身由链构成，形如线型，例例自然数N构成的集合等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系偏序关系偏序关系偏序关系偏序关系9/17/202462S e t sS e t s集合集合集合集合 极大元极大元设是一个偏序集合，且B是A的子集，对于B中一个元素b，如果B中没有任何元素x，满足bx，且bx，则称b为B的极大元。极小元极小元设是一个偏序集合，且B是A的子集，对于B中一个元素b，如果B中没有任何元素x，满足bx，且xb，则称b为

38、B的极小元。例极大元和极小元不是唯一的极大元之间没有关系，极小元既是极大元在哈斯图的顶部，极小元相反等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系偏序关系偏序关系偏序关系偏序关系9/17/202463S e t sS e t s集合集合集合集合 最大元最大元设是一个偏序集合，且B是A的子集，对于B中某个元素b，如果对B中每个元素x，都有xb，则称b为的最大元。最小元最小元设是一个偏序集合，且B是A的子集，对于B中某个元素b，如果对B中每个元素x，都有bx，则称b为的最小元。极大元和最大元是有区别的，最大元是唯一的，极大元却不，极大元含有不可比元素例例等价关系和偏序关系

39、等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系偏序关系偏序关系偏序关系偏序关系9/17/202464S e t sS e t s集合集合集合集合 上界上界最小上界（上确界）最小上界（上确界）下界下界最大下界（下确界）最大下界（下确界）等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系偏序关系偏序关系偏序关系偏序关系9/17/202465S e t sS e t s集合集合集合集合 上界与最大元是有区别的，B的最大元必须属于B，而上界不一定属于B，但要属于A最大元如果存在，则唯一，上下界则不是唯一的236812162432例例在本节的范例中 子集B=2，3，6 B没

40、有最小元，也没有下界 B有最大元6， 6也是上界且为上确界 另外还有上界12，24， 这两上界属于A-B即使有多个上界存在，上确界也不一定存在，等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系偏序关系偏序关系偏序关系偏序关系9/17/202466S e t sS e t s集合集合集合集合 cdba上下确界若存在则是唯一的等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系偏序关系偏序关系偏序关系偏序关系9/17/202467S e t sS e t s集合集合集合集合 任一偏序集合，假如它的每一个非空子集存在最小元素，这种偏序集称为良序集。定理定理

41、每一个良序集合，一定是全序集合。定理定理每一个有限的全序集合，一定是良序集。良序集良序集等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系等价关系和偏序关系偏序关系偏序关系偏序关系偏序关系9/17/202468S e t sS e t s集合集合集合集合 序偶序偶笛卡尔积笛卡尔积关系（前域、值域、域）关系（前域、值域、域）1、三种表示法、三种表示法2、复合与逆关系（三种表示法）、复合与逆关系（三种表示法）3、自反、对称、传递及其闭包与生成、自反、对称、传递及其闭包与生成4、等价关系与等价类、划分与商集、等价关系与等价类、划分与商集5、偏序集、偏序集盖住盖住哈斯图哈斯图链与反链链与反链全序全

42、序集集极小（大）最小（大）极小（大）最小（大）上下界与上下确界上下界与上下确界接接P1189/17/202469S e t sS e t s集合集合集合集合 函数的概念函数的概念函数的概念函数的概念 9/17/202470S e t sS e t s集合集合集合集合 函数的概念函数的概念函数的概念函数的概念9/17/202471S e t sS e t s集合集合集合集合 从集合X到Y的关系成为函数要满足两个条件。X的每个元素都要有象（存在性条件）X的每个元素都只有一个象（唯一性条件）f:XYX1X2X3x4y1y2y3y4y1y2y3y4g:XYX1X2X3x4不是函数关系举例图XXf:XY

43、X1X2X3x4y1y2y3y4y1y2y3y4g:XYX1X2X3x4函数关系举例图当用矩阵表示X到Y的函数f时，矩阵的每一行必须有且只有一个值为1的项，例如上图函数的矩阵是用集合表示为函数的概念函数的概念函数的概念函数的概念9/17/202472S e t sS e t s集合集合集合集合 一些术语如“变换”、“映像”、“映射”、“运算”等都是函数的同义词，符号f：XY；或XY用来表示f是X到Y的函数下面是一些函数的例子下面是一些函数的例子。1)设X=a,b,1,2,Y=3,5,7,f=,。显然，等等。2)设X=Y=R（实数集），显然f对应一条在x轴上方顶点在原点的折线3)设（PQ）R表示

44、命题演算的一个合式公式。对每一个命题变元都能且只能以V=F，T中的两元素之一代入。其结果对应一张真值表。于是合式公式表示一个从的函数。实际上，我们早在第二章里就用过命题函数这个名词。定义一个函数，只是规定一种将集合X中每一元素变换成另一集合Y（允许Y=X）中确定的一个元素的规则函数的概念函数的概念函数的概念函数的概念9/17/202473S e t sS e t s集合集合集合集合 函数相等函数相等即定义域和对应关系相同的函数相等函数的概念函数的概念函数的概念函数的概念9/17/202474S e t sS e t s集合集合集合集合 函数集合函数集合函数的概念函数的概念函数的概念函数的概念9

45、/17/202475S e t sS e t s集合集合集合集合 函数的概念函数的概念函数的概念函数的概念9/17/202476S e t sS e t s集合集合集合集合 函数的概念函数的概念函数的概念函数的概念9/17/202477S e t sS e t s集合集合集合集合 三类特殊的映射三类特殊的映射单射：不同的x函数值不同满射：B为A的值域双射：一一对应（或入射）函数的概念函数的概念函数的概念函数的概念注意f(A)与f(x)的区别f(A)为A在f下的像集f(x)为x在f下的像9/17/202478S e t sS e t s集合集合集合集合 例例则f为单射，非满射例例则f为满射，非单

46、射例例则f为双射函数的概念函数的概念函数的概念函数的概念9/17/202479S e t sS e t s集合集合集合集合 逆函数和复合函数逆函数和复合函数逆函数和复合函数逆函数和复合函数 逆函数逆函数逆函数逆函数一、逆函数一、逆函数9/17/202480S e t sS e t s集合集合集合集合 X Yx1x2x3X Y不存在逆函数的举例图y1y2y3y4x1x2x3x4y1y2y3以上分析说明了双射是函数有逆函数的必要条件。还容易证明双射也是函数可逆的充分条件。这是说，一个建立在X到Y上的双射。则f作为二元关系，它的逆关系也一定是一个函数。且也是双射。定理定理一个函数可逆的充分必要条件为

47、函数是双射。并且逆函数也是双射。由逆函数的定义可知，若函数f可逆，则必有逆函数和复合函数逆函数和复合函数逆函数和复合函数逆函数和复合函数 逆函数逆函数逆函数逆函数9/17/202481S e t sS e t s集合集合集合集合 二、复合函数二、复合函数逆函数和复合函数逆函数和复合函数逆函数和复合函数逆函数和复合函数 复合函数复合函数复合函数复合函数9/17/202482S e t sS e t s集合集合集合集合 逆函数和复合函数逆函数和复合函数逆函数和复合函数逆函数和复合函数 复合函数复合函数复合函数复合函数9/17/202483S e t sS e t s集合集合集合集合 X Y Zx1

48、x2x3x4Z1Z2z3X Z复合函数举例图y1y2y3y4y5x1x2x3x4Z1Z2z3例例求上图中给出的g在f左复合所得复合函数。解解关系的任何普遍成立的性质，函数亦同样具有。所以现在用矩阵的布尔乘法来计算该复合函数。故逆函数和复合函数逆函数和复合函数逆函数和复合函数逆函数和复合函数 复合函数复合函数复合函数复合函数9/17/202484S e t sS e t s集合集合集合集合 函数复合的结合性函数复合的结合性逆函数和复合函数逆函数和复合函数逆函数和复合函数逆函数和复合函数 复合函数复合函数复合函数复合函数9/17/202485S e t sS e t s集合集合集合集合 逆函数和复

49、合函数逆函数和复合函数逆函数和复合函数逆函数和复合函数 复合函数复合函数复合函数复合函数9/17/202486S e t sS e t s集合集合集合集合 逆函数和复合函数逆函数和复合函数逆函数和复合函数逆函数和复合函数 复合函数复合函数复合函数复合函数9/17/202487S e t sS e t s集合集合集合集合 逆函数和复合函数逆函数和复合函数逆函数和复合函数逆函数和复合函数 复合函数复合函数复合函数复合函数9/17/202488S e t sS e t s集合集合集合集合 逆函数和复合函数逆函数和复合函数逆函数和复合函数逆函数和复合函数 复合函数复合函数复合函数复合函数9/17/20

50、2489S e t sS e t s集合集合集合集合 逆函数和复合函数逆函数和复合函数逆函数和复合函数逆函数和复合函数9/17/202490S e t sS e t s集合集合集合集合 接接P96函数：函数：1、要素、要素 2、 表达（映射关系）表达（映射关系）3、函数集合、函数集合4、特殊映射（单、满、双）、特殊映射（单、满、双）5、逆函数与复合函数、逆函数与复合函数9/17/202491S e t sS e t s集合集合集合集合 2 2相容关系相容关系相容关系相容关系 给定集合A上关系r，若r是自反的，对称的，则称r是相容关系。相容关系相容关系例例设有字母串集合在X上的关系R是：字母串间

51、有相同的字母。即则可验证R是自反的，对称的故R是相容的9/17/202492S e t sS e t s集合集合集合集合 2 2相容关系相容关系相容关系相容关系 例例 设关系R为元素间有相同的数字。即R=R=则R满足自反性，对称性，故R是相容关系。相容关系用“”表示，如2166243，243375但2166375一般来说，想容关系不满足传递性9/17/202493S e t sS e t s集合集合集合集合 2 2相容关系相容关系相容关系相容关系 例例2中的元素用表示，则有图1（图1）（图2）相容关系的图形特征相容关系的图形特征为自身都有回路，两点关系对称，所以相容关系的图形可简化成图2，例例

52、2中的关系矩阵为相容关系的矩阵特征相容关系的矩阵特征是对角线为1的对称矩阵，所以可简化成下三角矩阵（注意少一阶）9/17/202494S e t sS e t s集合集合集合集合 2 2相容关系相容关系相容关系相容关系 相容类相容类例例上例中有相容类有x1,x2,x1,x4x2,x4x1,x2,x4等前三个都可加上一个元素扩充为另一个相容类，而最后一个却不行，即最后一个为最大相容类相容类的图形是关系r图形的子图9/17/202495S e t sS e t s集合集合集合集合 2 2相容关系相容关系相容关系相容关系 最大相容类最大相容类设r是集合A上的相容关系，不能真包含在任何其他相容类中的相

53、容类，称作最大相容类，记作从关系图中看，最大相容类的图形是关系r图形中的完备图部分（即每个顶点之间都有关系，包括孤立点）adbce例例如关系图如右则最大相容类为a,b,cc,de例例如前例中的x1,x2,x4，x2,x3,x5，x2,x4,x59/17/202496S e t sS e t s集合集合集合集合 2 2相容关系相容关系相容关系相容关系 abcd例例 同室四人每个人都有一些爱好如下：A爱好游泳(a),跳舞(b),下棋(C)B爱好跳舞(b),游泳(a)C爱好跳舞(b)打球(d)D爱好下棋(c)游泳(a)有相同爱好者必能谈得来，试给出那些人在一起时谈得来的关系解解：上的相容关系如上图，

54、找出极大相容性分块表示A,B,C爱好跳舞，谈得来；A,B,D爱好游泳，谈得来9/17/202497S e t sS e t s集合集合集合集合 2 2相容关系相容关系相容关系相容关系 完全覆盖完全覆盖在集合A上给定相容关系r，其最大相容类的集合，称作集合A的完全覆盖，记作一个集合的覆盖不是唯一的，但完全覆盖却是唯一的9/17/202498S e t sS e t s集合集合集合集合 2 2相容关系相容关系相容关系相容关系 定理定理 设r是有限集A上的相容关系，C是一个相容类，那么必存在一个最大相容类使得即由一个相容类，一定可以扩展成一个最大相容类设C是一个相容类，（1）做Caj,其中ajC，且为与C中每个元素都相容的最小足标的元素，得相容类C1（2）再对C1做上一步骤，如此进行下去，直至没有元素aj存在为止，最后得到的即为包含C的最大相容类扩展的方式是扩展的方式是：9/17/202499S e t sS e t s集合集合集合集合 2 2相容关系相容关系相容关系相容关系 9/17/2024100