离散数学第四章

1、第四章 二元关系和函数 第一节 集合的笛卡儿积和二元关系 内容：内容： 有序对，笛卡儿积，二元关系。 重点：重点： (1) 掌握有序对的概念， (2) 笛卡儿积及性质， (3) 二元关系的定义及三种表示法， (4) 一些特殊的二元关系。 了解：了解：有序nn阶笛卡儿积。 元组和一、笛卡儿积。一、笛卡儿积。 2、笛卡儿积。 ,|ABx yxAyB1、有序对、有序对，记, x y。特点： (1)xy,x yy x，时，(2) ,x yu vxu yv。有序n(3)n 12,nx xx。，记元组定义：定义：集合ABAB。的笛卡儿积，记作和解：解： 0, 0, 0, 1, 1, 1,ABabcabc,

2、0 ,1 ,0 ,1 ,0 ,1BAaabbcc0,0 , 0,1 , 1,0 , 1,1AAAB例例1、 ， 0,1 , ,ABa b c求ABBAAAAB。 ，解：解： ( ), , ,P AabA( ), , ,AP Aaaaaba A, , ,bbab bb A(2) 笛卡儿积是集合，有关集合的运算都适合。 例例2、设 , Aa b( )AP A。，求注意：注意： (1) 若则AmBnABmn元集，是元集，是元集。为(3) 一般，ABBA。(1) ()()()ABCABA C(2) ()()()BCABACA(3) ()()()ABCABA C(4) ()()()BCABACA3、笛卡

3、儿积运算对满足分配律。 或12nAAA121122,|nnnx xxxAxAxA4、n(2)n 笛卡儿积。 阶特别，当12nAAAA记为nA时，。如 , Aa b2,Aa aa bb ab b，二、二元关系。二、二元关系。 若, x yRxRy否则，记作xRy，则记作。 (1)ABAB的关系，到的任何子集都称作从特别，当AB A上关系上关系。 时，称作(2) 若集合则称RR为空集或它的元素都是有序对， 为二元关系二元关系。 1、定义设 1,0 ,0 ,2Rabb2R3RAB4,1Rb则1234,R R R RAB的关系。 到都是从例例4、 , Aa b0,1,2B ，2、A上不同关系的数目。

4、若AnAn则2AAn，元集，记为，的子集共有AA22n个，元集nA22n个。上不同的关系共有dom,Rxyx yRran,Ryxx yRflddomranRRR 关系关系RdomR值域值域ranRfldR，的定义域的定义域。和域和域3、关系、关系RA后后域域B，的的前前域域。4、特殊的关系。 空关系AEAI。，恒等关系，全域关系对任意集合A，空关系，全域关系,|AEx yxAyAAA，恒等关系,|AIx xxA。5、常用关系。 (1) 设ARA,ALx y x yAxy上小于等于关系： ，(2) 设BZB,|BDx y x yBx y上整除关系： ，(3) 幂集( )P AR,| ,( )Rx

5、 yx yP Axy：上的包含关系解：解： 2,2 , 2,3 , 2,6 , 2,8 , 3,3 ,AL3,6 , 3,8 , 6,6 , 6,8 , 8,82,2 , 2,6 , 2,8 , 3,3 , 3,6 , 6,6 , 8,8AD 例例5、2,3,6,8A ALAD。，求解：解： ， ( ), , ,P AabA, , ,Rab , , , , , ,a baaaA , , ,bbbAA A例例6、 , Aa b( )P AR。上的包含关系，求有三种集合表示法矩阵表示法图形表示法三、A上二元关系的表示法。 解：解： 0110110000100010RM关系图： 例例7、已知1,2,

6、3,4A A1,2 , 1,3 , 2,1 , 2,2 , 3,3 , 4,3R 求RRM，上关系 ，和关系图。的关系矩阵一般：设 12 ,nAx xx( )Rijn nMr，其中 10ijijijx Rxrx Rx关系图表示点( 边(每个有序对对应一条有向弧)n个顶点)四、关系的五种性质四、关系的五种性质(自反，反自反，对称，自反，反自反，对称，反对称，传递反对称，传递)。 1、定义及关系矩阵，关系图特征由下表给出( RA上关系) 为定义 关系矩阵的特点 关系图的特点 自反性 xA ，都有 , x xR主对角线元素全为1图中每个顶点都有环反自反性 xA ，都有 , x xR主对角线元素全为0

7、图中每个顶点都无环定义 关系矩阵的特点 关系图的特点 对称性 对称矩阵 若两顶点间有 边，必是一对方向相反的边 反对称性 若两顶点间有边， 必是一条有向边 若, x yR则 , y xR，若, x yRxy则 , y xR，且若1ijr ij则 0jir ，且定义 关系矩阵的特点 关系图的特点 传递性 若, x yR, y zR, x zR，则且若顶点ixjxjxkx则ixkx有边，到有边，到必有边到(1) 11,1 , 1,2 , 2,1R (2) 21,2 , 2,3 , 1,3R 例例1、1,2,3A A1234,R R R R如下所示，判断1234,R R R R各有哪些性质。上关系，

8、解：解：1R是对称的，不是传递的。 既不是自反又不是反自反， 解：解：2R是反自反的，反对称的，传递的。 (3) 31,1 , 3,3R (4) 41,1 , 2,2 , 3,3 , 1,2 , 1,3 , 2,1R 例例1、1,2,3A A1234,R R R R如下所示，判断1234,R R R R各有哪些性质。上关系，解：解：3R既是对称又是反对称的，传递的。 既不是自反又不是反自反的， 解：解：4R不是传递的。 是自反的，既不是对称又不是反对称的， 例例2、判断下图中的关系分别具有哪些性质。 解：解：1R是反自反，反对称，不是传递的。 例例2、判断下图中的关系分别具有哪些性质。 解：解

9、：2R既是对称又是反对称的，传递的。是空关系，是反自反，例例2、判断下图中的关系分别具有哪些性质。 解：解：3R既是对称又是反对称的，传递的。 是恒等关系，是自反的，例例2、判断下图中的关系分别具有哪些性质。 解：解：4R传递的。是全域关系，是自反的，对称的，例例2、判断下图中的关系分别具有哪些性质。 解：解：5R反对称的，传递的。 既不是自反也不是反自反的， 例例2、判断下图中的关系分别具有哪些性质。 解：解：6R又不是反对称，不是传递的。 是反自反的，既不是对称则有以下文氏图。 2、若把A上所有关系看成一个全集， 则有以下文氏图。 2、若把A上所有关系看成一个全集， 第二节第二节 关系的运

10、算关系的运算 内容：内容：关系的定义域，值域，逆关系，合成关系。重点：重点：(1) 掌握逆关系，合成关系的概念及求法， 一般：一般：关系的定义域，值域。 (2) 掌握关系n次幂的概念及性质。 一、逆关系，合成关系。一、逆关系，合成关系。 1、关系的逆。 (1) 定义：定义：关系R1,Ry xx yR的逆关系定义为解：解： 12,2 , 3,3 , 3,2 , 6,2 , 6,3 , 6,6AL,x y x yAxy12,2 , 6,2 , 3,3 , 6,3 , 6,6AD,| ,x yx yAxy 是 的倍数例例1、2,3,6A ALA为ADA1AL1AD上小于等于关系， 为，。，上整除关系

11、，分别求出即1ALA上大于等于关系。 为即1ADA上的倍数关系。 为2、关系的合成 (复合) 。(1) 定义定义，关系R和S的合成关系定义为： ,()RSx yz xSzzRy(2)1R1RMRRM，的关系矩阵与的关系矩阵满足1RRMM的转置。的关系图只需将改向即得。 1RR的关系图中的有向弧(3) 11()RR。例例2、设 1,2 , 2,2 , 3,4R 1,3 , 2,5 , 3,1 , 4,2 , 4,5S 求 R RR SSRSS()R RR，()R SR，。解：解： 1,4 , 3,2 , 4,2R S 1,5 , 2,5 , 3,2 , 3,5SR 1,2 , 2,2R R 例例

12、2、设 1,2 , 2,2 , 3,4R 1,3 , 2,5 , 3,1 , 4,2 , 4,5S 求 R RR SSRSS()R RR，()R SR，。1,1 , 3,3 , 4,5S S 解：解： ()1,2 , 2,2R RR ()3,2R SR 逻辑加法： 0000 11 1011 11 ，。(2)R SR SM,R S,RSMM满足R SSRMMM的关系矩阵 与的关系矩阵。的关系图可将R S,R S起来求得。 的关系图连接如例2中， 次幂的运算满足： nmnm nRRR，()mnmnRR( ,)m nN(3) 合成关系满足结合律：()()R STRS T。(4) 关系Rn次幂。的定义

13、：设RAnN的Rn 0,|Rx xxA 1(1)nnRRRn次幂次幂规定为： ，上关系，为解法一解法一 用集合表示。 0,Ra ab bc cd d10RRRR21,RRRR Ra aa cb bb d例例3、 , , , ,Aa b c dRa bb ab cc d求iR0,1,2,3,4,5i 。，543,RRRa ba db ab cR432,RRRa aa cb bb dR32,RRRa ba db ab c解法一解法一 用集合表示。 例例3、 , , , ,Aa b c dRa bb ab cc d求iR0,1,2,3,4,5i 。，解法二解法二 用关系图表示。 例例3、 , , ,

14、 ,Aa b c dRa bb ab cc d求iR0,1,2,3,4,5i 。，解法二解法二 用关系图表示。 解法三解法三 用矩阵表示(略)。 例例3、 , , , ,Aa b c dRa bb ab cc d求iR0,1,2,3,4,5i 。，3、关系的逆与合成间的联系。 111()R SSR证明：任取 , x y1,()x yR S, y xR S,zy zSz xR 11, x ySR11,zz ySx zR 3、关系的逆与合成间的联系。 111()R SSR证明：任取 , x y1,()x yR S故111()R SSR。例例4、分别求出以下关系的定义域和值域。 (1) 1,Rx y

15、 x yZxy解：解： 11domranRRZ20,1 , 0, 1 , 1,0 ,1,0R 解：解： (2) 222,1Rx y x yZxy22domran0,1, 1RR例例4、分别求出以下关系的定义域和值域。 (3) 3,2Rx y x yZyx解：解： 3domRZ(4) 4,3Rx y x yZxy解：解： 43,3 , 3, 3 ,3,3 ,3, 3R 44domran3, 3RR3ran |2Rt tkkZ即偶数集 第三节第三节 关系的性质关系的性质 例例3、设1,2,3A A11,2 , 1,3R 21,2 , 2,1 , 1,3 , 2,3R 判断12,R R是否传递的。

16、上关系，解：解：因111RRR1R是传递的。 ，所以因2221,1 , 1,3 , 2,2 , 2,3RRR所以2R，不是传递的。 三、关系在各种运算下保持原有特性问题。三、关系在各种运算下保持原有特性问题。 证明：证明：对任意 , x y12, x yRR12,x yRx yR12,y xRy xR12, y xRR例如：设12,R RA证明12RRA上的对称关系， 为上的对称关系。 也是所以12RRA上是对称的。 在又如：设12,R RA证明A12RR上反对称关系， 为上的反对称关系。 不一定是反例： 121,2,1,2,2,1ARR都是A上的反对称关系，但121,2 , 2,1RR 的反

17、对称关系。A上不是第四节第四节 关系的闭包关系的闭包 内容：内容：关系的自反，对称，传递闭包。 重点：重点：掌握关系的自反，对称，传递闭包 的概念及求法。 一、闭包的定义。一、闭包的定义。 (2)RR1、定义：定义：设RA的自反闭包(对称闭包，传递闭包) RR也是A上的关系， 是非空集合上关系，且满足： (1)R是自反的(对称的，传递的)， (3) 对传递关系)RRRAR的自反关系(对称关系，上的任何包含。，都有2、记号。 3、性质。 ( )r RR的自反闭包， ( )s RR的对称闭包， ( )t RR的传递闭包。 是自反的R( )r RR，是对称的R( )s RR ，是传递的R( )t R

18、R。二、闭包的求法。 1、利用以下公式。 (1) 0( )r RRR，(2)1( )s RRR，(3)23( )t RRRR。二、闭包的求法。 2、利用关系图。 (1)( )r R的关系图：在没有环的结点上加上环， (2)( )s R的关系图：把单向边改为双向边， (3)以到达的终点添加一条有向边，直到添加完毕。 ( )t Rxyxy，分别找出可的关系图：对每个结点没有有向边，则到，若二、闭包的求法。 3、利用关系矩阵。 注意到以上公式，如0( )r RRR关系矩阵，即rRMMEE其余为0的矩阵)，其中的“+”表示矩阵对应元素的逻辑加。同样，可得sRRMMM( 转置)，RMRM23tRRRMM

19、MM，转换成表示主对角线为1，(的为。解法一解法一 0( )r RRR,a bb ab cc d,a ab bc cd d,a bb ab cc d,a ab bc cd d例例1、设 , , , ,Aa b c d,Ra bb ab cc d求( ), ( ), ( )r R s R t R。1( )s RRR,a bb ab cc d,b aa bc bd c,a bb ab cc bc dd c例例1、设 , , , ,Aa b c d,Ra bb ab cc d求( ), ( ), ( )r R s R t R。23( )t RRRR(参考第二节例3) ,a bb ab cc d,a

20、aa cb bb d,a bb aa db c例例1、设 , , , ,Aa b c d,Ra bb ab cc d求( ), ( ), ( )r R s R t R。23( )t RRRR(参考第二节例3) ,a aa ba ca db a,b bb cb dc d例例1、设 , , , ,Aa b c d,Ra bb ab cc d求( ), ( ), ( )r R s R t R。例例1、设 , , , ,Aa b c d,Ra bb ab cc d求( ), ( ), ( )r R s R t R。解法二解法二 先画出( ), ( ), ( )r R s R t RR的关系图。 的关系

21、图，再画出 解法二解法二例例1、设 , , , ,Aa b c d,Ra bb ab cc d求( ), ( ), ( )r R s R t R。解法二解法二例例1、设 , , , ,Aa b c d,Ra bb ab cc d求( ), ( ), ( )r R s R t R。解法二解法二例例1、设 , , , ,Aa b c d,Ra bb ab cc d求( ), ( ), ( )r R s R t R。解法三解法三 利用关系矩阵(略)。 例例1、设 , , , ,Aa b c d,Ra bb ab cc d求( ), ( ), ( )r R s R t R。第五节第五节 等价关系和偏序

22、关系等价关系和偏序关系 内容：内容：等价关系，偏序关系。 重点：重点：(1) 掌握等价关系和等价类的概念， (3) 掌握偏序关系的概念， (4) 偏序集哈斯图的画法。 (2)之间的联系， AA的划分上的等价关系与集合一、等价关系。一、等价关系。 1、等价关系的定义。 若则称RRAA满足自反，对称，传递，上关系上的等价关系等价关系。为若, x yRxy 。，记(2) 三角形的全等关系，三角形的相似 关系是等价关系。 (3) 在一个班级里“年龄相等”的关系 是等价关系。 例例1、(1) 集合A是等价关系。 上的恒等关系，全域关系 例例2、 1,2,3,4,5,7A ,(mod3)Rx y x yA

23、xy(其中(mod3)xy3|()xy验证RA称模3的同余关系)， 上的等价关系。为，也就是证明：证明：显然，是等价关系。RR满足自反，对称，传递，所以例例2、R的关系图如下：其中1 4 72 5。，推广 ：整数集Zm,(mod)Rx y x yZxym的同余关系是等价关系： 上模事实上：(1)故xZ |()mxx, x xRR是自反的。，(2) 若, x yR|()mxy则|()myx, y xR是对称的。 R，故，即推广 ：整数集Zm,(mod)Rx y x yZxym的同余关系是等价关系：上模事实上：(3) 若, x yR, y zR即|()mxy|()myz()()xzxyyz因所以|

24、()mxz, x zR是传递的。 R，故， ，由(1)，(2)，(3)，R是等价关系。例例2、 1,2,3,4,5,7A ,(mod3)Rx y x yAxy(其中(mod3)xy3|()xy验证RA称模3的同余关系)， 上的等价关系。 为，也就是证明：证明：显然，是等价关系。RR满足自反，对称，传递，所以例例2、R的关系图如下： 其中1 4 72 5。，推广 ：整数集Zm,(mod)Rx y x yZxym的同余关系是等价关系： 上模事实上：(1)故xZ |()mxx, x xRR是自反的。，(2) 若, x yR|()mxy则|()myx, y xR是对称的。 R，故，即推广 ：整数集Zm

25、,(mod)Rx y x yZxym的同余关系是等价关系： 上模事实上：(3) 若, x yR, y zR即|()mxy|()myz()()xzxyyz因所以|()mxz, x zR是传递的。 R，故，由(1)，(2)，(3)，R是等价关系。例例3、设RA, a bR, a cR , b cRR，上的自反关系，且当是是等价关系。 ，证明时，有证明：证明：已知RR只要证R是等价关系，是自反的，要证是对称的和传递的即可。 若, a bR, a bR, a aRR有, b aRR是对称的。，所以是自反的)， (及，由例例3、设RA, a bR, a cR , b cRR，上的自反关系，且当是是等价关

26、系。 ，证明时，有证明：证明：已知RR只要证R是等价关系，是自反的，要证是对称的和传递的即可。 有若, a bR, b cRR, b aR, b cR, a cR所以R的对称性，由， ，所以，又是传递的。 由于RR是等价关系。 是自反，对称，传递的，故2、等价类。 (1) 定义：定义：设对RAxA |Rxy yAxRy则称 RxxR简称x x的等价类的等价类，记 的等价类的等价类，关于关于为，记上的等价关系，是非空集合在例2中，有 1471,4,7 252,5 33(2) 性质。(证明略) 定理：定理：, x yRRA，上的等价关系，是非空集合() x xA，且() 若xRy xy，则() 若

27、xRy xy，则() x AxA。 在例2中， 1231,2,3,4,5,7。， 1 2 3A的非空子集，都是，, a bA， ab ab(由abab 或 决定)，或3、商集。 定义：定义：设以叫做即 RA RxxARARARA R。，下的商集商集，记作在的不交的等价类为元素的集合 上的等价关系， 为非空集合例如：在例2中， 1,4,7 , 2,5 , 3A R 。例例4、(1) 非空集合AAI，xA xx AA Ix xA，所以商集是等价关系， 上的恒等关系(2) 非空集合AAExA ， xA AA EA是等价关系，上的全域关系，所以商集 其等价类是： 0km kZ1(1)mkmmkZ 11

28、kmkZ 22kmkZ 商集 0 , 1 , 2 ,1Z Rm例例5、整数集Zm,(mod)Rx y x yZxym的等价关系上模二、集合的划分。二、集合的划分。 1、划分的定义。 满足：(1) ()ijAAij(2) 12mAAAA是非空集合，A12,mA AA是它的非空子集，则称12,mA AAA而12,mA AA称为这个划分的块划分的块。 的一个划分划分， 为例例6、设判断下列子集族是否, , ,Aa b c dA，的划分。(5) , , ,a b c d是A的划分，(4) ,ab cd是A的划分，(3) ,a bc d不是A的划分，(1) ,a bcc d不是A的划分，(2) ,a b

29、d不是A的划分，2、集合AA的一个等价关系。 的一个划分确定上的一个划分AA若定义同一块中的元素有关系R可以证明RA称为划分则这个划分的块就是等价关系的等价类， 划分就是商集。 分成若干划分块， 把，上的一个等价关系， 是诱导的等价关系，,Ra ab bb cc bc cd d商集： ,A Rab cd如例6中的(4)的划分确定等价关系AR2、集合AA的一个等价关系。 的一个划分确定如下： 上的一个3、AA的一个划分。上的一个等价关系可确定若RA即商集A RA诱导的划分。R的一个划分，称为由，就是上的等价关系，则所有等价类的集合， 为即如例2中由R 1,4,7 , 2,5 , 3诱导的划分，。

30、由以上可知，集合集合AA上的等价关系与的划分是一一对应的。例例7、设1,2,3A 求出A，上的所有的等价关系。解：解：只需列出A并找出由它们确定的等价关系。 上所有的划分，11,2 , 1,3 , 2,1 , 2,3 , 3,1 , 3,2R AAIE22,3 , 3,2ARI例例7、设1,2,3A 求出A解：解：A(1,2,5)ii的等价关系为iR上的所有的等价关系。，的不同划分只有以上五种，设对应于划分，则有 31,3 , 3,1ARI41,2 , 2,1ARI5ARI例例7、设1,2,3A 求出A解：解：A(1,2,5)ii的等价关系为iR上的所有的等价关系。，的不同划分只有以上五种，设

31、对应于划分，则有 ,a bc dSS,a bc dadbc则由此等价关系诱导的划分中 (1) 共有几个划分块？(2) 求其中最大的块。 (3) 求其中最小的块。例例8、设1,2,3S SS：上定义等价关系，在解：解：依题意得： ,a bc dadbcabcd差为0的:1,1 2,2 3,3差为1的： 2,1 3,2差为2的： 3,1即第一元素与第二元素之差相等的有序对互相等价，将SS中的元素按差划分。差为11,2 2,3的：差为21,3的：解：解：(1) 共有5个划分块。 (2) 最大的划分块为： 1,1 , 2,2 , 3,3(3) 最小的划分块为：1,3和3,1三、偏序关系。三、偏序关系。

32、 1、偏序关系的定义。 若则称记作ARRA, x yRxy满足自反，反对称，传递， 上关系上的偏序关系偏序关系，简称偏序偏序， 为。，记，若集合记作AAR,A R。一起叫做偏序集偏序集，上的偏序关系与例例1、偏序关系的常见例子。有理数集上的小于等于关系正整数集上的整除关系,Q R,ZR整除,AA I集合A上的恒等关系( ),P A R幂集( )P A上的包含关系2、偏序集中的两元素可比，盖住的定义。 设,A , x yA，为偏序集，若xyyx则称, x y成立，或是可比可比的，若xyxyxy且不存在zAxzy则称yx)，且 ( ， 使得。盖住盖住1与任何数都可比，2与3不可比，2盖住1，4盖住

33、2，例例2、1,2,3,4,5A 为偏序集。 ,A 为整除关系， ，但4不盖住1( 124 )3、全序集。 是全序集，,A R,A R整除不是全序集。 设,A , x yA都可比，则称xyA ,A 为全序集全序集。上的全序关系全序关系，且称 为和，为偏序集，若例如：1,2,3,4,5A ，步骤如下： 四、偏序关系的哈斯图四、偏序关系的哈斯图()Hasse 。 1、哈斯图()Hasse。(1)A若xyxy中的每个元素用结点表示， 结点的下方。排在，结点(2) 若yx, x y之间连一条线。 ，则在盖住(1) 1,2,3,12A 解：解：哈斯图： 812435610121179例例3、画出,A R

34、整除A分别为的哈斯图，其中1,2,3,4,6,9,12,18,36A (2) 解：解：哈斯图： 364916121823例例3、画出,A R整除A分别为的哈斯图，其中解：解： ( ),P Aaba b哈斯图： , a b a b(1) ,Aa b例例4、画出A( ),P A R分别为 的哈斯图，其中(2) , ,Aa b c ( ),P Aabca b解：解： , ,a cb ca b c例例4、画出A( ),P A R分别为 的哈斯图，其中(2) 解：解：哈斯图： , ,Aa b c, ,a b c, a b, a c, b c a b c例例4、画出A( ),P A R分别为 的哈斯图，其

35、中其哈斯图为一直线 (右图)： 51234例例5、画出偏序集1,2,3,4,5A ,A R，的哈斯图。解：解：因,A R(任两元素均可比)为全序集abfcdegh解：解：, , , , , ,Aa b c d e f g h,a ca da eb cb d,Ab ec ed ef gI例例6、已知偏序集,R 哈斯图(右图)，求集合的偏序关系A的。五、偏序集中极小元，极大元，最小元，五、偏序集中极小元，极大元，最小元，最大元，上界，下界，上确界，下确界。最大元，上界，下界，上确界，下确界。 1、极大、小元，最大、小元。 定义：设,A BA，为偏序集，(1) 若yB (x xByx）则称By的最小

36、元最小元。 是成立， ，使得(2) 若yB (x xBxy）则称By的最大元最大元。是成立， ，使得五、偏序集中极小元，极大元，最小元，五、偏序集中极小元，极大元，最小元，最大元，上界，下界，上确界，下确界。最大元，上界，下界，上确界，下确界。 1、极大、小元，最大、小元。 定义：设,A BA，为偏序集，(3) 若yB x xBxy（）则称By成立，使得的极小元极小元。是(4) 若yB ()x xByx则称By的极大元极大元。是成立，使得五、偏序集中极小元，极大元，最小元，五、偏序集中极小元，极大元，最小元，最大元，上界，下界，上确界，下确界。最大元，上界，下界，上确界，下确界。 1、极大、小

37、元，最大、小元。 由定义知： 最小元最大元BBBB不一定存在,若存在必唯一中其它元，小于中其它元，大于五、偏序集中极小元，极大元，最小元，五、偏序集中极小元，极大元，最小元，最大元，上界，下界，上确界，下确界。最大元，上界，下界，上确界，下确界。 1、极大、小元，最大、小元。 由定义知： 中没有比它小的元极小元极大元BBBB一定存在，可能多个中没有比它大的元，五、偏序集中极小元，极大元，最小元，五、偏序集中极小元，极大元，最小元，最大元，上界，下界，上确界，下确界。最大元，上界，下界，上确界，下确界。 2、上、下界，上、下确界。 定义：设,A BA，为偏序集，(1) 若存在则称ByyA()x

38、xBxy成立， ，使得的上界上界。为(2) 若存在则称ByyA()x xByx成立， ，使得的下界下界。 为五、偏序集中极小元，极大元，最小元，五、偏序集中极小元，极大元，最小元，最大元，上界，下界，上确界，下确界。最大元，上界，下界，上确界，下确界。 2、上、下界，上、下确界。 (3) 令为Cy yB为 的上界CB定义：设,A BA，为偏序集，的上确界上确界(最小上界最小上界)。中最小元 ，称(4) 令为BDy yB为 的下界D的下确界下确界(最大下界最大下界)。 中最大元 ，称五、偏序集中极小元，极大元，最小元，五、偏序集中极小元，极大元，最小元，最大元，上界，下界，上确界，下确界。最大元

39、，上界，下界，上确界，下确界。 2、上、下界，上、下确界。 由定义知： 上界中其它元下界中其它元不一定存在，若存在不一定只有一个AABB，小于，大于五、偏序集中极小元，极大元，最小元，五、偏序集中极小元，极大元，最小元，最大元，上界，下界，上确界，下确界。最大元，上界，下界，上确界，下确界。 2、上、下界，上、下确界。 由定义知： 上确界最小的上界下确界最大的下界不一定存在，若存在必唯一, ,a b c, a b, a c, b c a b c(1) ,Bacb c例例7、, ,Aa b c( ),P A R求上、下界，上、下确界。B，偏序集的最大、小元，极大、小元，解：解：B的最大元：无，最

40、小元：无， 极大元： ,ab c ,ac ，极小元：上界：, ,a b c，下界：上确界：, ,a b c。，下确界：, ,a b c, a b, a c, b c a b c(2) ,Baba b例例7、, ,Aa b c( ),P A R求上、下界，上、下确界。B，偏序集的最大、小元，极大、小元，解：解：B, a b，最小元：无， 的最大元：，极大元：, a b ,ab，极小元：上界： , ,a ba b c， ，下界：上确界：, a b。，下确界：(2) 其中有多少种等价关系？ 例例8、设1,2A ，问： (1)A上可以定义多少种不同的二元关系？ 解：解：因2A 2 24AA的不同子集共

41、4216AA个。，也就是说A上可以定义16种不同的二元关系。 解：解：因1,2A 即1,2 1 , 2，所以只有2种等价关系。 和，不同的划分只有两种，(3) 其中有多少种偏序关系？ 12(i)12(ii)12(iii)所以，有3种偏序关系。 例例8、设1,2A ，问：解：解：因只有以下三种：A只有2个元素，不同的哈斯图不满足自反性，所以既不是等价关系， 又不是偏序关系。 例例8、设1,2A ，问：(4)是偏序关系吗？ AI是等价关系吗？ 和空关系解：解：所以AIAI满足自反，对称和反对称，传递，既是等价关系，又是偏序关系。 第六节第六节 函数的定义和性质函数的定义和性质 内容：内容：函数的定

42、义，性质。 重点：重点：掌握函数的定义，单射、满射、 双射的概念及判定。 一、函数的定义。一、函数的定义。 而211122132,Fx yx yxyxy不是函数。1、定义：定义：FdomxF都存在唯一的ranyFxFy称F，为二元关系，若对任意的成立，则 ，使得为函数函数。 例如：1122231,Fx yxyxy是函数， 3、有关集合和关系的运算对函数都适合。 fgfggfdomdom ,xfg ( )( )f xg x2、记号：如, , ,F G Hf g h，若xFy( )F xy。，记4、函数的定义域，值域。设,A Bf(1)dom fAran fB则称fAB:fAB满足：是集合，若函数

43、，(2)。的函数，记作到是从符号:ABf fABAB的全体构成的集合。 的函数到表示从例如：函数( )2f xxxR到RRRfR，是从实数集，的函数，即函数( )lng xxxR 到RRRgR，是从正实数集 ，。的函数，即10, 1, 2,faaa20, 1, 2,faab30, 1, 2,faba40, 1, 2,fabb例例1、0,1,2A ,Ba bAB。，求，解：解：题目要求从定义，有AB的所有函数，依函数到50, 1, 2,fbaa60, 1, 2,fbab70, 1, 2,fbba80, 1, 2,fbbb例例1、0,1,2A ,Ba bAB。，求，解：解：题目要求从定义，有AB的

44、所有函数，依函数到解：解：故128,ABfff例例1、0,1,2A ,Ba bAB。，求，一般，若AmBn,m n则AmBn。不全为0)，(，二、函数的性质。二、函数的性质。 1、满射：满射：若ran fBf(或到上的) 。 是满射满射的，则称2、单射：单射：若12,x xA12xx12()()f xf x，则f(或一一的)。 ，则 ，称是单射单射的 3、双射：双射：若f是双射双射的 (或一一到上的)。 f既是满射，又是单射，则称 1,8 , 3,9 , 4,10 , 2,6 , 5,9f 也不是满射。例例2、判断以下, ,f g hAB若是函数，再判断是否单射，满射，双射的； 若不是，请说明

45、理由。 的函数， 到的是否从(1)1,2,3,4,5A 6,7,8,9,10B ，解：解：fAB的函数，到是从但f不是单射，1,8 , 3,10 , 2,6 , 4,9g 例例2、判断以下, ,f g hAB若是函数，再判断是否单射，满射，双射的； 若不是，请说明理由。 的函数， 到的是否从解：解：ABg的函数， 到不不是从(1)1,2,3,4,5A 6,7,8,9,10B ，1,7 , 2,6 , 3,8 , 4,5 , 1,9 , 5,10h 例例2、判断以下, ,f g hAB若是函数，再判断是否单射，满射，双射的； 若不是，请说明理由。 的函数， 到的是否从(1)1,2,3,4,5A

46、6,7,8,9,10B ，解：解：ABh的函数，到不不是从2( )f xxx但它不是单射， 也不是满射。3( )g xx( )h xx(2)ABR(实数集) 解：解：fAB的函数，到是从解：解：gAB的双射函数。到是从解：解：hAB的函数。到不不是从( )1g xx( )1f xx且是单射的， 但不是满射的 。(3)ABZ(正整数集)解：解：fAB的函数，到是从解：解：gAB的函数。到不不是从1(1)( )1(1)xh xxx是满射的。 不是单射的，(3)ABZ(正整数集)解：解：hAB的函数，到是从三、常用的一些函数。三、常用的一些函数。 1、常函数常函数，:fABxA ( )f xc( c

47、Bc都有 ，为常数)，2、恒等函数恒等函数，:AIAAxA 都有 ( )AIxx，3、特征函数特征函数，:0,1AAxA 1( )0AxAxxAA，其中AA，。三、常用的一些函数。三、常用的一些函数。 4、自然映射自然映射，设RA是从gAA R:g AA R，aA ( )g aa。，的函数到商集上的一个等价关系，是第七节第七节 函数的复合和反函数函数的复合和反函数 内容：内容：复合函数，反函数。 一般：一般：基本掌握复合函数，反函数的定义及求法。一、复合函数。一、复合函数。 1、定义：定义：设函数:fBC:g AB则:fg ACxA( )( )fg xfg x，称为, f g的复合函数复合函数

48、。 ，对任意，例例1、设, ,Rf g hR( )3f xx( )21g xx( )2xh x ，求fggfffgghffh g，其中。，解：解：因为, ,f g hRR的复合函数也是从RR的函数 。 到的函数，所以所求 到均为从解：解：( )( )(21)fg xfg xfx(21)324xx( )( )(3)gf xg f xg x2(3)127xx 例例1、设, ,Rf g hR( )3f xx( )21g xx( )2xh x ，求fggfffgghffh g，其中。，解：解：( )( )(3)ff xff xf x(3)36xx( )( )(21)gg xg g xgx2(21)14

49、3xx 例例1、设, ,Rf g hR( )3f xx( )21g xx( )2xh x ，求fggfffgghffh g，其中。，解：解：1( )( )(3)(3)2hf xh f xh xx例例1、设, ,Rf g hR( )3f xx( )21g xx( )2xh x ，求fggfffgghffh g，其中。，( )( )(21)fh g xf h g xf hx17322xx11(21)22fxfx解：解：例例1、设, ,Rf g hR( )3f xx( )21g xx( )2xh x ，求fggfffgghffh g，其中。，2、性质。 因此， ( )( )( )fg xf g xf

50、 yz设:fBC:g AB，(1) 若, f g:fg AC也是满射的。 是满射的，则证：zC fyB ( )f yz，使满射，故，由于对这个ygxA ( )g xy，使满射，故，又由于所以fg是满射。 2、性质。设:fBC:g AB，(2) 若, f g:fg AC也是单射的。是单射的，则证：12,x xA12xxg故12()()g xg x12(), ()domg xg xBf，且单射，由于，若又由f12()()f g xf g x即12()()fg xfg x，的单射，有，所以fg是单射的。2、性质。 二、反函数。二、反函数。 设:fBC:g AB ，(3) 若, f g:fg AC也是

51、双射的。是双射的，则证：综合(1)、(2)，即得fg是双射的。1、定义：定义：设函数:fAB1:fBA也是双射的，称1f反函数反函数。f的是是双射的，则 例例2、判断以下函数是否存在反函数，若存在， 请写出反函数，否则，请说明理由。(1) :fRR2( )1f xx，解：解：f不存在反函数，因为f( 1)(1)0ff。不是单射，(2) :g RR( )31g xx，解：解：g是双射的，存在反函数1:gRR11( )(1)3gxx。，例例2、判断以下函数是否存在反函数，若存在， 请写出反函数，否则，请说明理由。(3) :h RR( )xh xe，解：解：h是双射的，存在反函数1:hRR1( )l

52、nhxx。，第四章第四章 小结和例题小结和例题 一、集合的笛卡儿积与二元关系。一、集合的笛卡儿积与二元关系。 1、基本概念。 2、应用。(1) 求给定集合的笛卡儿乘积。 (2) 求给定集合上的小于等于关系，整除关系，及幂集上的包含关系。 有序对，笛卡儿积；关系，集合AB集合A关系矩阵，关系图。 的关系，到上的关系；空关系，全域关系，恒等关系；一、集合的笛卡儿积与二元关系。一、集合的笛卡儿积与二元关系。 1、基本概念。 2、应用。(3) 关系三种表示法间的互相转换。有序对，笛卡儿积；关系，集合AB集合A关系矩阵，关系图。 的关系，到上的关系；空关系，全域关系，恒等关系；二、关系的运算。二、关系的

53、运算。1、基本概念。 关系的定义域，值域；逆关系，合成关系； 关系的幂运算。 2、运用。(1) 求给定关系的逆关系，合成关系。(3) 求给定关系的定义域，值域。 (2) 求给定关系的n次幂。三、关系的性质。三、关系的性质。1、基本概念。 关系的自反性，反自反性，对称性，反对称性，传递性。2、运用。(1) 关系的五种性质及关系图，关系矩阵特征。(2) 五种性质的判断和验证。 四、关系的闭包。四、关系的闭包。1、基本概念。 自反闭包，对称闭包，传递闭包。 2、运用。求给定关系的自反，对称，传递闭包。五、等价关系和偏序关系。五、等价关系和偏序关系。1、基本概念。 2、运用。(1) 等价关系，偏序关系

54、的判断。等价关系，等价类，商集，划分；偏序关系，偏序集，哈斯图；极大元，极小元，最大元，最小元，上界，下界，上确界，下确界。 (2) 求给定等价关系决定的划分；求给定划分决定的等价关系。五、等价关系和偏序关系。五、等价关系和偏序关系。1、基本概念。 2、运用。(3) 画出给定偏序关系的哈斯图。等价关系，等价类，商集，划分；偏序关系，偏序集，哈斯图；极大元，极小元，最大元，最小元，上界，下界，上确界，下确界。 (4) 求极大、小元，最大、小元，上、下界，上、下确界。六、函数的定义和性质。六、函数的定义和性质。1、基本概念。 函数；单射，满射，双射。2、运用。(1) 判断一个关系是否为函数。 (2

55、) 判断一个函数是否单射，满射，双射。 七、函数的复合和反函数。七、函数的复合和反函数。1、基本概念。 复合函数，反函数。2、运用。(1) 求复合函数和反函数。 (2) 验证函数的单射，满射，双射性，经过复合运算后仍保持。 解：解：2,1 , 3,2 , 4,3 , 5,4 ,R 6,5 , 3,1 , 4,2 , 5,3 , 6,4例例1、设1,2,3,4,5,6A A2,()Rx yxyAxyS , x yyxT ,xx yy上的二元关系，的倍数是是素数 (1) 写出, ,R S T的元素。1,1 , 2,2 , 3,3 , 4,4 , 5,5 , 6,6 ,S 1,2 , 1,3 , 1

56、,4 , 1,5 , 1,6 , 2,4 ,2,6 , 3,6解：解：例例1、设1,2,3,4,5,6A A2,()Rx yxyAxyS , x yyxT ,xx yy上的二元关系，的倍数是是素数 (1) 写出, ,R S T的元素。解：解：2,1 , 3,1 , 5,1 , 4,2 , 6,2 , 6,3T 例例1、设1,2,3,4,5,6A A2,()Rx yxyAxyS , x yyxT ,xx yy上的二元关系，的倍数是是素数 (1) 写出, ,R S T的元素。是自反，反对称，传递的。 S是反自反，反对称的。T例例1、设1,2,3,4,5,6A A2,()Rx yxyAxyS , x

57、 yyxT ,xx yy上的二元关系，的倍数是是素数 (2), ,R S T具有哪些性质。解：解：R是反自反，反对称的。解：解：3,1 , 4,2 , 5,3 , 5,2 ,R R 6,4 , 6,3 , 4,1 , 6,24,1 , 6,1 , 6,2R T 例例1、设1,2,3,4,5,6A A2,()Rx yxyAxyS , x yyxT ,xx yy上的二元关系，的倍数是是素数 (3) 求R RR T，解：解：1,1 , 2,2 , 3,3R 解：解：1,2 , 2,1 , 1,3R 解：解：1,2 , 2,3 , 1,3R 例例2、举出使它有如下的性质：1,2,3A R的例子，上的关

58、系(1)R既是对称的，又是反对称的。(2)R既不是对称的，也不是反对称的。 (3)R是传递的。(1) 1(0)_R1,2,3,4(2) 2(0)_R1,0(3) 3(3)_R(4) 1(1)_R2,3,4例例3、xXRX定义集合( )R xy xRy若4, 3, 2, 1,0,1,2,3,4X 且令1,Rx y x yXxy2,12Rx y x yXyxy 23,Rx y x yXxy求以下集合： ，上的二元关系，对是(5) 2( 1)_R 2, 1例例3、xXRX定义集合( )R xy xRy若4, 3, 2, 1,0,1,2,3,4X 且令1,Rx y x yXxy2,12Rx y x yXyxy 23,Rx y x yXxy求以下集合： ，上的二元关系，对是解：解：关系图：0100001001010010RM关系矩阵：例例4、设, , ,Aa b c dA,Ra bb cc bc dd c上关系，(1) 画出RR的关系矩阵。的关系图，并写出解：解：2,Ra cb bc cb dd bd d3,Ra ba db cc bc dd c4,Ra cb bb dc cd bd d1,Rb ac bb cd cc d例例4、设, , ,Aa b c dA,Ra bb cc bc