1、8/16/2023 12:17 PMliu qun,northeastern Univ.14.14.1笛卡儿积与二元关系笛卡儿积与二元关系 在现实社会中有许多事物是成对出现的，而且其中的两个事物是有一定次序的，例如一双鞋子有左右只，影剧院的坐号的表示（排号）平面上点的表示，等，概括起来，数学上用两个有次序的元素组成一个称之为序偶的结构就可以表示现实世界中那种成对出现而且有一定次序关系的事物 8/16/2023 12:17 PMliu qun,northeastern Univ.2两个具有固定次序的客体组成的集合，记作：序偶序偶1.序偶可看作是具有两个元素组成的集合，即=x,x,y。2.序偶刻画
2、了两个客体间的次序,它并不表示由两个元素组成的集合 ;x,y=y,x3.序偶中的元素分别称为的第一客体与第二客体4.序偶只有当其两个客体相同且次序相同时才相等5.序偶的元素可分别来自两个集合，它们可以代表不同类型的事物，但次序确定 4.14.1笛卡儿积与二元关系笛卡儿积与二元关系序偶序偶8/16/2023 12:17 PMliu qun,northeastern Univ.3例例1 A=1，2，24，B=1，2，60，对aA，bB，则为一序偶，表示几点几分。有序对 不是由两个元素组成的集合 x,y 例例2 在笛卡儿坐标系中，平面上点的坐标（x，y）就是有序对。（1，2），（2，1）代表不同的点
3、。（1，1），（2，2）代表点（允许 x=y）4.14.1笛卡儿积与二元关系笛卡儿积与二元关系序偶序偶例例3 A为操作码集合，B为指令码集合，对aA，bB，则为一序偶，表示一条地址指令 8/16/2023 12:17 PMliu qun,northeastern Univ.4三元组是一个序偶，其第一元素本身也是一个序偶，可形式化表示为，z.三元组三元组1.x,不是一个三元组,只是一个序偶2.四、五元组类似定义3.n元组元组 n元组是一个序偶，其第一元素为（n-1）元组可形式化表示为：121,nnx xxx4.14.1笛卡儿积与二元关系笛卡儿积与二元关系序偶序偶8/16/2023 12:17 P
4、Mliu qun,northeastern Univ.5设A和B是任意两个集合，若序偶的第一成员是A的元素，第二成员是B的元素，所有这样序偶的集合，称为集合A与B的笛卡尔积（直积），记作 笛卡尔积笛卡尔积,|,A Ba baA bB4.14.1笛卡儿积与二元关系笛卡儿积与二元关系笛卡尔积笛卡尔积8/16/2023 12:17 PMliu qun,northeastern Univ.6例例 一天内的时间可用时分表示，它们的全体可用笛卡儿乘积表示例例 上面例3所有指令的集合构成一个操作码与指令码集合的笛卡儿积AB例例 平面上直角坐标中的所有点可用笛卡儿乘积表示RyRxyxRR,|,RbRabaBA
5、,|,其中59,.1,0,23.2,1,0BA(R为实数集)直积不具有交换率 例例 设设试求AB和BA 由此得 4.14.1笛卡儿积与二元关系笛卡儿积与二元关系笛卡尔积笛卡尔积8/16/2023 12:17 PMliu qun,northeastern Univ.7多重直积多重直积 12nAAA=121()nnAAAA=12,nx xx|1122nnxAxAxA 例例 A=1，2 B=a，b C=，babaBA,2,2,1,1,2,2,2,2,1,1,1,1bbaabbaaCBA 2,2,1,2,2,1,1,1 AAnAAAA记4.14.1笛卡儿积与二元关系笛卡儿积与二元关系笛卡尔积笛卡尔积8
6、/16/2023 12:17 PMliu qun,northeastern Univ.8niAaaaaAAAAAinn.3,2,1,/,.,.21其中、1,0A例例 计算机内的字是由固定的n个有序二进位所组成，它的全体可以表示成n重有序组形式4.14.1笛卡儿积与二元关系笛卡儿积与二元关系笛卡尔积笛卡尔积8/16/2023 12:17 PMliu qun,northeastern Univ.9定理定理 设A，B，C为任意三个集合，则有 a)A（BC）=（AB）（AC）；b)A（BC）=（AB）（AC）；c)（AB）C=（AC）（BC）；d)（AB）C=（AC）（BC）。4.14.1笛卡儿积与二
7、元关系笛卡儿积与二元关系笛卡尔积笛卡尔积8/16/2023 12:17 PMliu qun,northeastern Univ.10关系在日常生活中无处不在，我们熟知的一些常见的关系刻划着事物的结构。例例设一旅馆有n个房间，每个房间可住两个旅客，所以一共可住2n个旅客。在旅馆内，旅客与房间有一定的关系，我们讨论关系“某旅客住在某房间”，用R表示这种关系，设n=3旅客分别为a,b,c,d,e,f 旅客住房间用表示:123abcdefa与1间存在关系R记aR1 b与1间存在关系R记bR1c与2间存在关系R记cR2 d与2间存在关系R记dR2e与3间存在关系R记eR3e与3间存在关系R记eR34.2
8、4.2关系及运算关系及运算关系关系8/16/2023 12:17 PMliu qun,northeastern Univ.114.24.2关系及运算关系及运算关系关系满足的关系可看成是一个有序偶：(p,q)如aR1可写成有序偶：(a,1)满足R的所有关系可看成是一个有序偶的集合，这个集叫R，即这种关系称为二元关系，它只涉及两个客体间的关系若 则AB 的任何子集都定义了一个二元关系。,1,1,2,2,3,3Rabcdef,1.2.3Aa b c d e f gB关系在现实社会中处处可见如 看电影对号入座 关系型数据库里的关系（成绩单）等 8/16/2023 12:17 PMliu qun,nor
9、theastern Univ.12若一个集合的元素都是有序对，则称这个集合是一个二元关系，简称关系,记为 R，在R中的任一序偶，可记为R或xRy。关系关系即设有任意两个集合X和Y，XY的子集R称作X到Y的（二元）关系。当X=Y时，称R为X上的二元关系4.24.2关系及运算关系及运算关系关系8/16/2023 12:17 PMliu qun,northeastern Univ.13例例 实数集R上小于等于的关系为 =yxRyRxyx,|,注意 前一个 为关系，后一个 为不等号 例例 设 A=a,b,是 2A上的包含于关系，求解解 4.24.2关系及运算关系及运算关系关系8/16/2023 12:
10、17 PMliu qun,northeastern Univ.14前域前域 设二元关系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.24.2关系及运算关系及运算关系关系8/16/2023 12:17 PMliu qun,northeast
11、ern Univ.15三种特殊关系 全域关系全域关系 XY的平凡子集XY称为X到Y的全域关系。空关系空关系 XY的平凡子集，称为X到Y的空关系。例 H=f,m,s,d,写出成员关系，不相识关系，长幼关系恒等关系恒等关系 设Ix是X上的二元关系，且满足条件 Ix=|xX 则称Ix是X上的恒等关系。例4.24.2关系及运算关系及运算关系关系8/16/2023 12:17 PMliu qun,northeastern Univ.16设两个有限集合12,mXx xx12,nYy yyR为X到Y的一个二元关系，对应于关系R有一个关系矩阵关系矩阵关系矩阵Rijm nMr其中10ijrijij当R当R (1
12、,2,;1,2,)im jn4.24.2关系及运算关系及运算关系表示法关系表示法8/16/2023 12:17 PMliu qun,northeastern Univ.17设两个有限集合12,mXx xx12,nYy yyR为X到Y的一个二元关系，关系图关系图 4.24.2关系及运算关系及运算关系表示法关系表示法8/16/2023 12:17 PMliu qun,northeastern Univ.18解解D=|x，yA，x|y=，例设例设A=2，3，6，8，12，32 试写出试写出A上的整除关系上的整除关系D 当元素与自身够成关系时，用一个闭合的有向弧表示 关系图为关系表为 AA236812
13、3221011113011010600101080001011200001032000001矩阵形式为 100000010000101000010100010110111101D4.24.2关系及运算关系及运算关系表示法关系表示法8/16/2023 12:17 PMliu qun,northeastern Univ.19P2P5P4P3P1例例设有六个程序，它们之间有一定的调用关系设有六个程序，它们之间有一定的调用关系 123445522631:,RPRPPRPP RPPRPP RPPRP621.PPPp 这个关系是集合 上的关系，6P有 123445522631,RP PP PP PP PP
14、 PP P关系图为 矩阵形为 654321000000000010010000001001100000000010ppppppp4.24.2关系及运算关系及运算关系表示法关系表示法8/16/2023 12:17 PMliu qun,northeastern Univ.20定理定理 若Z和S是从集合X到集合Y的两个关系，则Z，S的并、交、补、差仍是X到Y的关系。例例 设 ,2,1,YcbaXX从Y到的关系:1,1,1,1,2,1,cbaScbaR则有 1,2,1,1,cbbaSR是从X到Y的一个新关系 1,1,caSR 2,1,2,cbaR 2,bSR有关集合的运算公式，在关系中也同样适合 4.
15、24.2关系及运算关系及运算关系表示法关系表示法8/16/2023 12:17 PMliu qun,northeastern Univ.21设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的关系为则复合关系为,xy,yzxyz关系是集合，可进行集合的并、交、补运算，产生新的关系。除此之外，还有其特殊的运算。4.24.2关系及
16、运算关系及运算运算运算8/16/2023 12:17 PMliu qun,northeastern Univ.22例例 设 2,2,4,3,2,1R 1,3,5,2,2,4S则 1,5,3,2,2,5R S 4,2,3,2S R 4,5S S 1,2R R 例例 设 321321321,zzzZyyyYxxxX从X到Y的关系 222111,yxyxyxR 从Y到z的关系 333221,zyzyzyS 由此得从X到Z的关系 121323,R Sx zx zx z123123123RSxyz 复合关系可以用图表示如右4.24.2关系及运算关系及运算运算运算8/16/2023 12:17 PMliu
17、 qun,northeastern Univ.23复合运算不满足交换律。但复合运算满足结合律 即设 R是从X到Y的关系，S是从Y到Z的关系，P是从Z到W的关系，则有（RS）P=R（SP）证明证明:先证 R SPRS P设,x uR SPzZ 有,x zR Sz uPyY SzyRyx,y uS Px uRS PR SPRS P类似可知 RS PR SPR SPRS PR S P故于是R本身所组成的复合关系可写成：()nR nRRR 4.24.2关系及运算关系及运算运算运算8/16/2023 12:17 PMliu qun,northeastern Univ.24复合关系可用矩阵运算表示 123
18、123110010000RyyyxMxx123123010001001szzzyMyy110010011010001001000001000R SRsMMM 其中其中 为逻辑加(布尔加):为逻辑乘(布尔积):4.24.2关系及运算关系及运算运算运算8/16/2023 12:17 PMliu qun,northeastern Univ.25关系是序偶的集合，由于序偶的有序性，交换次序后将得到一个新的关系，逆关系逆关系 设R为X到Y的二元关系，如将R中每一序偶的元素顺序互换，所得到的集合称为R的逆关系，记作 cR即,|,cRy xx yR例如例如 父子关系的逆关系是子亲关系，“”关系的逆关系是“”
19、关系 也有些关系的逆关系是相等的 例如例如 朋友关系，实数的相等关系 4.24.2关系及运算关系及运算运算运算8/16/2023 12:17 PMliu qun,northeastern Univ.26Rc的关系图是由R的关系图通过将其中的所有的有向弧的方向逆转得到，Rc的关系矩阵MRC可由R的关系矩阵转置得出 010101000RM010010101100000010CTRM,2,1,3 Rabb,;1,2,3;Aa b cB例设 2,1,3,cRabb4.24.2关系及运算关系及运算运算运算8/16/2023 12:17 PMliu qun,northeastern Univ.27定理定理
20、 设R，R1和R2都是从X到Y的二元关系，则下列各式成立：定理定理 设T为从X到Y的关系，S为从Y到Z的关系，则 c(T S)ccST定理定理 设R为X上的二元关系，则 R是对称的，仅当 R是反对称的，仅当 cRRcxRRI4.24.2关系及运算关系及运算运算运算8/16/2023 12:17 PMliu qun,northeastern Univ.28设R为X上的二元关系，如果对于xX必有xRx，称R为X上的自反关系，自反关系自反关系即（x）（x XxRx）为真。例例 在实数R上的关系“”是自反的 实数集R上小于等于的关系为 =yxRyRxyx,|,对任意xR，有xx 例例 平面几何上三角形
21、的相似关系为自反的 设相似三角型的集合为A 相似关系为,|,x yxA yA xy对任意xA，有 xx 4.34.3关系及运算关系及运算性质性质8/16/2023 12:17 PMliu qun,northeastern Univ.29例例 在实数域上的关系”是反自反的，实数集R上小于的关系为,|,x yxR yR xy不是自反的未必就一定是反自反的 例例 在集合 4,3,2,1X上的关系 2,4,2,2,4,3,2,1,1,1R此关系既不是自反的亦不是反自反的 一个关系的自反性与非自反性可能都不存在，一个关系的自反性在图形表示法中相当于一个关系图中的每一一个结点均有环出现。而一个关系的非自反
22、性相当于一个关系图中的每个结点均无环出现 4.34.3关系及运算关系及运算性质性质8/16/2023 12:17 PMliu qun,northeastern Univ.30例例 全集上的互补集A和 是对称关系，即补集是互为的 4.34.3关系及运算关系及运算性质性质设R为X上的二元关系，如果对于每个x，y X，每当xRy，就有yRx，则称R是X上的对称关系，对称关系对称关系例例 一个班级的全体学员构成的集合，朋友关系是对称的，即朋友是互为的A8/16/2023 12:17 PMliu qun,northeastern Univ.31反对称关系反对称关系 设R为X上的二元关系，对于每一个x，y
23、X，每当xRy和yRx，必有x=y，则称R是X上的反对称关系，例例 父子关系是反对称的例例 包含关系是反对称的例例 小于等于关系是反对称的即除了自身,别的元素没有交换关系对称关系也非必具其一例例在集合 上的关系 这些关系既不是对称的亦不是非对称的4,3,2,1X2,44,321,2,1R关系的对称图形表示中相当于关系图中两个结点间如有边相连则一定有方向相反的两条有向边连接。一个关系的非对称图形相当于关系图中两个结点间如有有向边相连则一定只有一条边 4.34.3关系及运算关系及运算性质性质8/16/2023 12:17 PMliu qun,northeastern Univ.32设R为X上的二元
24、关系，如果对任意x,y,z X，每当xRy,yRz时必有xRz,称R是X上的传递关系，传递关系传递关系xyzxXyXzXxRyyRzxRz 即为真例例 实数域上的关系是传递的，因为若xy，yz则xz 例例 集合上的包含关系是传递的，因为若 因为若,xy yzxz则例例 设A=a，b，c，R=为A上的一个传递关系如果你感到大惑不解的话，你可以自问一下，“关系R是否真的不符合定义”问题出现了，归根结底还是一种对蕴含形式给出的命题PQ的不正确的理解。PQ为真，要求的是对假设前提为真时，结论Q一定为真。除此之外，它并不理会别的什么，反过来说，你要证实PQ不是真的，只能通过举一个反例的方法才成，即找出一
25、种情况，这时P成立（为真），而Q不成立（为假），那么，在此例中，R=，你能找到这样的三个元素xA，yA，zA，使得xRy，yRz都成立吗？不能，这就是说既然你举不出一种假设前提为真的情况，你又如何去论证PQ为假呢？于是又回到过去讲过的“善意推断”4.34.3关系及运算关系及运算性质性质8/16/2023 12:17 PMliu qun,northeastern Univ.334.44.4关系的闭包运算关系的闭包运算前面介绍的关系的运算，都是构成新关系的一种途径，闭包运算是通过对其进行扩充序偶来构成一种新的关系 闭包闭包 8/16/2023 12:17 PMliu qun,northeaster
26、n Univ.34例例设A=a，b，c，R=，r(R)=，若在添加得 R=，,虽然也是自反的，但却不是最小的了 s(R)=，t(R)=，例例 集合上的”=”关系.它的自反闭包对称闭包传递闭包都是自身|QxxxX，自反闭包，对称闭包，传递闭包分别是包含原关系的最小自反关系，对称关系，传递关系。如何寻找闭包呢？下面给出了寻找它们的法则 4.44.4关系的闭包运算关系的闭包运算8/16/2023 12:17 PMliu qun,northeastern Univ.35定理定理 设R是X上的二元关系，那么 R是自反的，当且仅当r(R)=R R是对称的，当且仅当s(R)=R R是传递的，当且仅当t(R)
27、=R。例例R=，则r(R)=R R=，,则S(R)=R R=,则t(R)=R此定理用于判断4.44.4关系的闭包运算关系的闭包运算8/16/2023 12:17 PMliu qun,northeastern Univ.36定理定理 设R是集合X上的二元关系，则 r（R）=RIx例例 设A=a，b，c，d,则Ix=,RIx=r(R)自反闭包的构造4.44.4关系的闭包运算关系的闭包运算8/16/2023 12:17 PMliu qun,northeastern Univ.37定理定理 设R是集合X上的二元关系，则 S（R）=RRc例例 设R=，则Rc=，s(R)=RRc对称闭包的构造4.44.4
28、关系的闭包运算关系的闭包运算8/16/2023 12:17 PMliu qun,northeastern Univ.38定理定理 设R是集合X上的二元关系，则 定理定理 设X是含有n个元素的集合，R是X上的二元关系，则存在一个正整数kn，使得4.44.4关系的闭包运算关系的闭包运算8/16/2023 12:17 PMliu qun,northeastern Univ.39例例设A=a，b，c，d，R=，求t（R）解解 R2=,R3=,R4=,故 t（R）=用矩阵形式表示 0110001010000000R，21010100001100000R，31110011010100000R，411101
29、01011100000R1110111011100000R=4.44.4关系的闭包运算关系的闭包运算8/16/2023 12:17 PMliu qun,northeastern Univ.40当有限集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/34.44.4关系的闭包运算关系的闭包运算8/16/2023 12:17 PMliu qun,northeas
30、tern Univ.414.44.4关系的闭包运算关系的闭包运算8/16/2023 12:17 PMliu qun,northeastern Univ.424.54.5等价关系和偏序关系等价关系和偏序关系覆盖与划分覆盖与划分若把一个集合A分成若干个叫做分块的非空子集，使得A中每个元素至少属于一个分块，这些分块的全体叫做A的一个覆盖。即设A为非空集合，覆盖覆盖则集合S称作集合A的覆盖。例例 学校运动员全体人员组成的集合为A，每个运动队为一Si,则所有的运动队组成了A的一个覆盖 8/16/2023 12:17 PMliu qun,northeastern Univ.43划分划分 设S为A的一个覆盖
31、，若A中的每个元素属于且仅属于S的一个分块，那末S称作是A的一个划分。即若S是集合A的覆盖，且满足SiSj=，这里（ij）则称S是A的划分。例例如 人群中的同姓关系，性别关系，年龄段关系等，都是人群的划分覆盖是可以重叠的，而划分是不能重叠的 4.54.5等价关系和偏序关系等价关系和偏序关系覆盖与划分覆盖与划分8/16/2023 12:17 PMliu qun,northeastern Univ.444.54.5等价关系和偏序关系等价关系和偏序关系覆盖与划分覆盖与划分8/16/2023 12:17 PMliu qun,northeastern Univ.45例例如 两个色子投掷点数的集合，如何划
32、分，如何加细 4.54.5等价关系和偏序关系等价关系和偏序关系覆盖与划分覆盖与划分8/16/2023 12:17 PMliu qun,northeastern Univ.464.54.5等价关系和偏序关系等价关系和偏序关系覆盖与划分覆盖与划分8/16/2023 12:17 PMliu qun,northeastern Univ.47等价关系等价关系 设R为定义在集合A上的一个关系，若R是自反的、对称的和传递的，则R称为A上的等价关系。例例 人群所组成的的集合上的“同姓”关系是等价关系例例 所有三角形所组成的集合上的“相似”关系是等价例例 在坐的所有人，“同学”关系是等价的 4.54.5等价关系
33、和偏序关系等价关系和偏序关系等价关系等价关系8/16/2023 12:17 PMliu qun,northeastern Univ.48例例 X是整数集，X上的关系R,|Rx yxym 能被 整除此关系是等价关系，m为任意正整数既：满足这个关系R的x和y，用m除所有相同的余数这个关系也叫同余关系或称以m为模的同余关系，一般将xRy写成叫做x与y对模m是同余的的，这种式子称为同余式用上例方法可证：同余关系是一个等价关系。)(modmyx 4.54.5等价关系和偏序关系等价关系和偏序关系等价关系等价关系8/16/2023 12:17 PMliu qun,northeastern Univ.49等价
34、类等价类 设R为集合A上的等价关系，对任何aA，集合aR=x|xA，aRx,称为元素a形成的R等价类。例例 两个人同姓，这个关系为等价关系 所有同姓的人构成一个等价类4.54.5等价关系和偏序关系等价关系和偏序关系等价关系等价关系8/16/2023 12:17 PMliu qun,northeastern Univ.50等价类的性质等价类的性质 4.54.5等价关系和偏序关系等价关系和偏序关系等价关系等价关系8/16/2023 12:17 PMliu qun,northeastern Univ.51集合X上的等价关系R所够成的类，它们两两互不相交且覆盖整个集合X，故它们构成X的一个划分，而每个
35、类是这个划分的快。由此得：商集商集 /,.RRA Rxy即商集是由等价类为元素构成的集合4.54.5等价关系和偏序关系等价关系和偏序关系等价关系等价关系8/16/2023 12:17 PMliu qun,northeastern Univ.524.54.5等价关系和偏序关系等价关系和偏序关系等价关系等价关系8/16/2023 12:17 PMliu qun,northeastern Univ.534.54.5等价关系和偏序关系等价关系和偏序关系等价关系等价关系8/16/2023 12:17 PMliu qun,northeastern Univ.54定理定理 设给定集合A上等价关系R，对于a,
36、bA，有aRb，iffaR=bR。定理定理 集合A上有一个等价关系R，决定了A的一个划分，该划分就是商集A/R。定理定理 集合A的一个划分确定A 的元素间的一个等价关系。利用关系式很容易判断等价关系和等价类 4.54.5等价关系和偏序关系等价关系和偏序关系等价关系等价关系8/16/2023 12:17 PMliu qun,northeastern Univ.550123568其关系图为 从图中知，此关系满足自反性，对称性，传递性，即为等价关系R的等价类有3类 6,3,00R 11R 8,5,22R4.54.5等价关系和偏序关系等价关系和偏序关系等价关系等价关系8/16/2023 12:17 P
37、Mliu qun,northeastern Univ.56例例 设集合 上的关系R为dcbaX,ddcddcccbbabbaaaR,关系图为由图知R为等价关系，等价类 baaR,dccR,bcad4.54.5等价关系和偏序关系等价关系和偏序关系等价关系等价关系8/16/2023 12:17 PMliu qun,northeastern Univ.57偏序集偏序集 设A是一个集合，如果A上的一个关系R，满足自反性，反对称性和传递性，则称R是A上的一个偏序关系，并记为“”,A序偶 称为偏序集例例 由集合A所组成的幂集2A上的关系 是自反的，非对称的，传递的，故他是编序的例例 奇数集I上的“”是偏序
38、关系 例例 一个单位里，部门的隶属关系是偏序 4.54.5等价关系和偏序关系等价关系和偏序关系偏序关系偏序关系8/16/2023 12:17 PMliu qun,northeastern Univ.58例例 证明集合A=2,3,6,8,12,16,24,32上的“整除”关系 R=（x,y）|y/x=整数是偏序的 236812162432证明 1）因为每一个非零整数都可以整除它自己 所以R是自反的 2）任取两个整数x,yA，并设,xypIqIyx则有x=py=pqx,即pq=1p=1,q=1 故x=y，即R非对称 3)任取两个整数x,y,zA，并设,zypIqIyx则有z=py=pqx,pq为整
39、数，故 zpqIx即R可传递,故R为一偏序 4.54.5等价关系和偏序关系等价关系和偏序关系偏序关系偏序关系8/16/2023 12:17 PMliu qun,northeastern Univ.59偏序关系因为反对称，所以关系图中是单向箭头盖住关系盖住关系 从关系图中看，就是把间隔的关系去掉，如上例 2368121624328为2的盖住，16为8的盖住，32为16的盖住等 4.54.5等价关系和偏序关系等价关系和偏序关系偏序关系偏序关系8/16/2023 12:17 PMliu qun,northeastern Univ.60对于给定的偏序集,A，它的盖住是唯一的，再将盖住图简略，即将自圈和
40、关系箭头去掉，由上往下盖住即得“哈斯图哈斯图”哈斯图哈斯图236812162432链链 设 是一个偏序集合，在A的一个子集中，如果每两个元素都是有关系的，则称这个子集为链。,A例例 如上例中B1=3，6，12，24，B2=2，6，24，B3=2，8，32，B4=2，16都是链 虽然从哈斯图上看，很多链都是由一条折线上的所有点组成，但这不是必须的，如上例的链B2，B3，B4就是如此 4.54.5等价关系和偏序关系等价关系和偏序关系偏序关系偏序关系8/16/2023 12:17 PMliu qun,northeastern Univ.61反链反链 设 是一个偏序集合，在A的一个子集中，如果每两个元
41、素都是无关系的，则称这个子集为反链。,A若A的子集只有单个元素，则这个子集既是链又是反链。例例 C1=3，C2=6，8，C3=8，12都是反链 从哈斯图上看到，每个链中总可以从最高节点出发，沿着盖住方向遍历该链中所有节点，每个反链中任何两个节点间均无连线 4.54.5等价关系和偏序关系等价关系和偏序关系偏序关系偏序关系8/16/2023 12:17 PMliu qun,northeastern Univ.62全序集全序集,A设 为一个偏序集，若A是一个链，则称是全序集或线序集。在这种情况下，二元关系称为全序关系或线序关系。,A,A例如例如上例中B1=3，6，12，24构成的集合 集合A本身由链
42、构成，形如线型，例例 自然数N构成的集合 4.54.5等价关系和偏序关系等价关系和偏序关系偏序关系偏序关系8/16/2023 12:17 PMliu qun,northeastern Univ.63极大元极大元 设 是一个偏序集合，且B是A的子集，对于B中一个元素b，如果B中没有任何元素x，满足bx，且b x，则称b为B的极大元。,A极小元极小元 设 是一个偏序集合，且B是A的子集，对于B中一个元素b，如果B中没有任何元素x，满足bx，且x b，则称b为B的极小元。,A例P99/4.16极大元和极小元不是唯一的极大元之间没有关系，极小元既是极大元在哈斯图的顶部，极小元相反4.54.5等价关系和
43、偏序关系等价关系和偏序关系偏序关系偏序关系8/16/2023 12:17 PMliu qun,northeastern Univ.64最大元最大元 设 是一个偏序集合，且B是A的子集，对于B中某个元素b，如果对B中每个元素x，都有x b，则称b为 的最大元。,A,B最小元最小元 设 是一个偏序集合，且B是A的子集，对于B中某个元素b，如果对B中每个元素x，都有b x，则称b为 的最小元。,A,B极大元和最大元是有区别的，最大元是唯一的，极大元却不，极大元含有不可比元素 例例P99/4.164.54.5等价关系和偏序关系等价关系和偏序关系偏序关系偏序关系8/16/2023 12:17 PMliu
44、 qun,northeastern Univ.65上界上界 最小上界（上确界）最小上界（上确界）下界下界 最大下界（下确界）最大下界（下确界）4.54.5等价关系和偏序关系等价关系和偏序关系偏序关系偏序关系8/16/2023 12:17 PMliu qun,northeastern Univ.66上界与最大元是有区别的，B的最大元必须属于B，而上界不一定属于B，但要属于A最大元如果存在，则唯一，上下界则不是唯一的236812162432例例 在本节的范例中 子集B=2，3，6 B没有最小元，也没有下界 B有最大元6，6也是上界且为上确界 另外还有上界12，24，这两上界属于A-B即使有多个上界
45、存在，上确界也不一定存在，4.54.5等价关系和偏序关系等价关系和偏序关系偏序关系偏序关系8/16/2023 12:17 PMliu qun,northeastern Univ.67cdba上下确界若存在则是唯一的 4.54.5等价关系和偏序关系等价关系和偏序关系偏序关系偏序关系8/16/2023 12:17 PMliu qun,northeastern Univ.68任一偏序集合，假如它的每一个非空子集存在最小元素，这种偏序集称为良序集。定理定理 每一个良序集合，一定是全序集合。定理定理 每一个有限的全序集合，一定是良序集。良序集良序集4.54.5等价关系和偏序关系等价关系和偏序关系偏序关系
46、偏序关系8/16/2023 12:17 PMliu qun,northeastern Univ.69序偶序偶笛卡尔积笛卡尔积关系（前域、值域、域）关系（前域、值域、域）1、三种表示法、三种表示法2、复合与逆关系（三种表示法）、复合与逆关系（三种表示法）3、自反、对称、传递及其闭包与生成、自反、对称、传递及其闭包与生成4、等价关系与等价类、划分与商集、等价关系与等价类、划分与商集5、偏序集、偏序集盖住盖住哈斯图哈斯图链与反链链与反链全序全序集集极小（大）最小（大）极小（大）最小（大）上下界与上下确界上下界与上下确界接接P1188/16/2023 12:17 PMliu qun,northeast
47、ern Univ.704.64.6函数的概念函数的概念8/16/2023 12:17 PMliu qun,northeastern Univ.714.64.6函数的概念函数的概念8/16/2023 12:17 PMliu qun,northeastern Univ.720100010001000100gM从集合X到Y的关系成为函数要满足两个条件。X的每个元素都要有象（存在性条件）X的每个元素都只有一个象（唯一性条件）f:XYX1X2X3x4y1y2y3y4y1y2y3y4g:XYX1X2X3x4不是函数关系举例图XXf:XYX1X2X3x4y1y2y3y4y1y2y3y4g:XYX1X2X3x
48、4函数关系举例图当用矩阵表示X到Y的函数f时，矩阵的每一行必须有且只有一个值为1的项，例如上图函数的矩阵是 1000001010000001fM用集合表示为 11233144,fx yxyxyxy 12223242,gx yxyxyxy 4.64.6函数的概念函数的概念8/16/2023 12:17 PMliu qun,northeastern Univ.73一些术语如“变换”、“映像”、“映射”、“运算”等都是函数的同义词，符号f：XY；或X Y用来表示f是X到Y的函数f 下面是一些函数的例子下面是一些函数的例子。1)设X=a,b,1,2,Y=3,5,7,f=,。显然 ，等等。,()7,()
49、5,ffDX RY f af b2)设X=Y=R（实数集），0()0 xxf xxx当当显然 f对应一条在x轴上方顶点在原点的折线,.ffDR RR3)设（PQ）R表示命题演算的一个合式公式。对每一个命题变元都能且只能以V=F，T中的两元素之一代入。其结果对应一张真值表。于是合式公式表示一个从 的函数。实际上，我们早在第二章里就用过命题函数这个名词。2VV定义一个函数，只是规定一种将集合X中每一元素变换成另一集合Y（允许Y=X）中确定的一个元素的规则 4.64.6函数的概念函数的概念8/16/2023 12:17 PMliu qun,northeastern Univ.74函数相等函数相等 即
50、定义域和对应关系相同的函数相等4.64.6函数的概念函数的概念8/16/2023 12:17 PMliu qun,northeastern Univ.75函数集合函数集合 4.64.6函数的概念函数的概念8/16/2023 12:17 PMliu qun,northeastern Univ.764.64.6函数的概念函数的概念8/16/2023 12:17 PMliu qun,northeastern Univ.774.64.6函数的概念函数的概念8/16/2023 12:17 PMliu qun,northeastern Univ.78三类特殊的映射三类特殊的映射单射：不同的x函数值不同满射
