离散第四章二元关系2nd

1、1/36第四章第四章 二元关系二元关系2/452/45回顾回顾 关系的定义和性质关系的定义和性质 关系的表示方法关系的表示方法关系图关系图关系矩阵关系矩阵 关系的运算关系的运算关系的合成关系的合成关系合成的规则关系合成的规则关系的幂关系的幂合成关系的矩阵表达与图解合成关系的矩阵表达与图解 关系的逆运算关系的逆运算逆运算规则逆运算规则3/453/45四、关系的闭包运算四、关系的闭包运算闭包的定义：给定集合闭包的定义：给定集合X，R是是X中的二元关系。中的二元关系。如果有另一个关系如果有另一个关系 满足满足 R（1） 是自反的是自反的(对称的、可传递的对称的、可传递的)； （2）（3）对于任何自反

2、的）对于任何自反的(对称的、可传递的对称的、可传递的)关关系系 ，如果，如果 ，则，则RRR RRR RR则称关系则称关系 为为R的的 并用并用r(R)表示的表示的R自反闭包，用自反闭包，用s(R)表示表示R的对称闭包，用的对称闭包，用t(R)表示表示R的可传递闭包。的可传递闭包。 R4/454/45四、关系的闭包运算四、关系的闭包运算定理：给定集合定理：给定集合X，R是是X中的关系。于是可中的关系。于是可有有(a) 当且仅当当且仅当 ，R才是自反的。才是自反的。(b) 当且仅当当且仅当 ，R才是对称的。才是对称的。(c) 当且仅当当且仅当 ，R才是传递的。才是传递的。 ( )r RR( )s

3、 RR( )t RRR证明：仅给出（证明：仅给出（a）的证明过程）的证明过程 如果是如果是R自反的，则自反的，则R具有定义给出的应具具有定义给出的应具备备 的全部性质。因此有的全部性质。因此有 。反之，如。反之，如果果 ，则由定义的，则由定义的(1)得得R是自反的。是自反的。( )r RR( )r RR5/455/45四、关系的闭包运算四、关系的闭包运算定理：定理： 设设X是任意集合，是任意集合，R是是X中的二元关系，中的二元关系，IX是是X中的恒等关系。于是可有中的恒等关系。于是可有 ( )Xr RRI在整数集合中，小于关系在整数集合中，小于关系“”的自反闭包是的自反闭包是“”；恒等关系；恒

4、等关系IX的自反闭包是的自反闭包是IX。不等关系。不等关系“”的自反闭包是全域关系；空关系的自反闭的自反闭包是全域关系；空关系的自反闭包是恒等关系。包是恒等关系。 6/456/45四、关系的闭包运算四、关系的闭包运算定理：给定集合定理：给定集合X，R是是X中的二元关系。于是可有中的二元关系。于是可有 1( )S RRR在整数集合中，小于关系在整数集合中，小于关系“”的对称闭包是不的对称闭包是不等关系等关系“”；小于或等于关系；小于或等于关系“”的对称闭的对称闭包是全域关系；恒等关系包是全域关系；恒等关系IX的对称闭包是的对称闭包是IX；不等关系不等关系“”的对称闭包是不等关系的对称闭包是不等关

5、系“”。 7/457/45四、关系的闭包运算四、关系的闭包运算定理：给定集合定理：给定集合X，R是是X中的二元关系。于是可有中的二元关系。于是可有 1231( )iit RRRRR 当当A A是有限集时，是有限集时，A A上只有有限个不同的关系，因此，上只有有限个不同的关系，因此，存在某个正整数存在某个正整数m m，使得，使得1( )miit RR 事实上，可以证明，若事实上，可以证明，若 ，则，则nA #1( )niit RR8/458/45四、关系的闭包运算四、关系的闭包运算例：给定集合例：给定集合X=a,b,c，R和和S是是X中的关系，给中的关系，给定定,Ra ba cc bSa bb

6、cc a 试求出试求出t(R),t(S)，并画出关系图，并画出关系图解：解：123( )t RRRRR123123( ),t SSSSSSSa bb cc aa cb ac ba ab bc c R,t(R)St(S)9/459/45四、关系的闭包运算四、关系的闭包运算定理：设定理：设X是集合，是集合，R是是X中的二元关系，于是有中的二元关系，于是有（1）如果）如果R是自反的，那么是自反的，那么s(R),t(R)也是自反的；也是自反的；（2）如果）如果R是对称的，那么是对称的，那么r(R),t(R)也是对称的；也是对称的；（3）如果）如果R是可传递的，那么是可传递的，那么r(R)也是可传递的。

7、也是可传递的。xX证明（证明（1）：若）：若R是自反的，则对于所有的是自反的，则对于所有的 都有都有 ,( )x xRx xRRs R 1,( )iix xRx xRt R 即即s(R),t(R)是自反的是自反的10/45四、关系的闭包运算四、关系的闭包运算证明（证明（2）：）：11/45四、关系的闭包运算证明（2）：12/45四、关系的闭包运算证明（3）：13/4513/45四、关系的闭包运算四、关系的闭包运算定理：设定理：设X是集合，是集合，R是集合中的二元关系，于是有是集合中的二元关系，于是有( )( )( )( )( )( )( )( )( )ars Rsr Rbrt Rtr Rcts

8、 Rst R证明：证明：( )( )()()()()( )XXXXXXasr Rs RIRIRIRIRIRRIr RRrs R14/4514/45四、关系的闭包运算四、关系的闭包运算证明（证明（b）：因为）：因为 ， ，而，而对于所有的对于所有的 有有 ，以及，以及 。根据这些关系式，可有根据这些关系式，可有( )()Xtr Rt RI( )( )Xrt Rt RInNnXXIIXXIRR IR1()nniXXiRIIR于是于是12323( )()()()()()( )( )iXXiXXXXXtr Rt RIRIRIRIRIIRRRIt Rrt R15/4515/45四、关系的闭包运算四、关系

9、的闭包运算证明（证明（c）：如果）：如果 ，则，则 ，12RR12()()s Rs R12()()t Rt R根据对称闭包的定义，有根据对称闭包的定义，有 。首先构成上。首先构成上式两侧的可传递闭包，再依次构成两侧的对称闭式两侧的可传递闭包，再依次构成两侧的对称闭包包,可以求得可以求得 以及以及 。而。而ts(R)是对称的，所以是对称的，所以 ，从而有，从而有 。 ( )s RR( )( )ts Rt R( )( )sts Rst R( )( )s s RtstR( )( )ts Rst R16/4516/45四、关系的闭包运算四、关系的闭包运算注意：注意：（1）通常用）通常用R+表示表示R的

10、可传递闭包的可传递闭包t(R)，并，并读作读作“R加加”。（2）通常用）通常用R*表示表示R的自反可传递闭包的自反可传递闭包tr(R)，并读作并读作“R星星”。17/4517/454.7特殊关系特殊关系一、集合的划分和覆盖一、集合的划分和覆盖定义：给定非空集合定义：给定非空集合S，设非空集合，设非空集合A=A1,A2, , An，如果有，如果有1( )(1,2, )( )iniiaASinbAS则称集合则称集合A是集合是集合S的的覆盖覆盖。注意：集合的覆盖不唯一。注意：集合的覆盖不唯一。例如：例如：S=a,b,c，A =a,b,b,c，B=a,b,c，A和和B都是集合都是集合S的覆盖。的覆盖。

11、18/4518/45一、集合的划分和覆盖一、集合的划分和覆盖定义：给定非空集合定义：给定非空集合S，设非空集合，设非空集合A=A1,A2, An，如果有，如果有1( )(1,2, )( )()()( )iijijniiaAS inbAAijAAijcAS 或则称集合则称集合A是集合是集合S的一个的一个划分划分。划分中的元素划分中的元素Ai称为划分的称为划分的。 划分的类的数目叫划分的划分的类的数目叫划分的。 划分是覆盖的特定情况，即中元素互不相交的划分是覆盖的特定情况，即中元素互不相交的特定情况。特定情况。 19/4519/45一、集合的划分和覆盖一、集合的划分和覆盖例：设例：设S=1,2,3

12、，考虑下列集合，考虑下列集合1,2,2,3;1,1,2,1,3;1,2,3;1,2,3;1,2,3; , , ;ABCDEFaa cS的覆盖的覆盖S的覆盖的覆盖S的覆盖、划分，秩为的覆盖、划分，秩为2S的覆盖、划分，秩为的覆盖、划分，秩为1，最小划分，最小划分S的覆盖、划分，秩为的覆盖、划分，秩为3，最大划分最大划分20/4520/45一、集合的划分和覆盖一、集合的划分和覆盖定义：设定义：设A和和A是非空集合是非空集合S的两种划分，并可以的两种划分，并可以表示成表示成1miiAA1njjAA如果如果A的每一类的每一类Aj，都是，都是A的某一类的某一类Ai的子集，那的子集，那么称划分么称划分A是

13、划分是划分A的加细，并称的加细，并称A加细了加细了A。如。如果果A是是A的加细并且的加细并且AA，则称，则称A是是A的真加细。的真加细。21/4521/45极小项、完全交集极小项、完全交集定义：划分全集定义：划分全集E的过程，可看成是在表达全集的的过程，可看成是在表达全集的文氏图上划出分界线的过程。设文氏图上划出分界线的过程。设A，B，C是全集是全集E的三个子集。由的三个子集。由A，B和和C生成的生成的E的划分的类，称的划分的类，称为为。 n个子集生成个子集生成2n个极小项，个极小项，用用 表示。表示。0121,nIII01234567IABCIABCIABCIABCIABCIABCIABCI

14、ABC22/4522/45一、集合的划分和覆盖一、集合的划分和覆盖定理：定理： 由全集的由全集的n个子集个子集A1,A2, An所生成的全部所生成的全部极小项集合，能够构成全集极小项集合，能够构成全集E的一个划分。的一个划分。 证明：证明这个定理，只需证明全集证明：证明这个定理，只需证明全集E中的每一个元素，中的每一个元素，都仅属于一个完全交集就够了。都仅属于一个完全交集就够了。 如果如果 ，则，则 ，或或 ， 或或 ； 或或 。由此。由此可见，定有可见，定有xE1xA1xA2xA2xAnxAnxA1()niixA这里这里 或是或是Ai或是或是 Ai 。试考察两个不同的完全。试考察两个不同的完

15、全交集交集T。因为两个完全交集是不同的，就是说存在。因为两个完全交集是不同的，就是说存在这样一个这样一个i，使得，使得 和和 ，因此可有，因此可有 ，即即 ；因而任何一个；因而任何一个 都不能同时属于两都不能同时属于两个不同的完全交集。个不同的完全交集。 iAiTAiTAiiTAAT xE23/4523/45一、集合的划分和覆盖一、集合的划分和覆盖 注意：注意：不难看出，这里所说的完全交集，与命题演算不难看出，这里所说的完全交集，与命题演算中的极小项相似。但是和极小项的集合不同，中的极小项相似。但是和极小项的集合不同，极大项的集合不能构成全集的划分。极大项的集合不能构成全集的划分。 24/45

16、24/45二、等价关系二、等价关系定义：设定义：设X是任意集合是任意集合, R是集合中的二元关系。如是集合中的二元关系。如果果R是是自反的、对称的和可传递自反的、对称的和可传递的，的， 则称则称R是等价是等价关系。即满足以下几点：关系。即满足以下几点：( )()()( )()()()( )()()()()ax xXxRxbxy xXyXxRyyRxcxyz xXyXzXxRyyRzxRz 如果如果R是集合是集合X中的等价关系，则中的等价关系，则R的域是集合的域是集合X自身，自身，所以，称所以，称R是定义于集合是定义于集合X中的关系。中的关系。 例如例如 数的相等关系是任何数集上的等价关系。数的

17、相等关系是任何数集上的等价关系。 又例如又例如一群人的集合中姓氏相同的关系也是等价关一群人的集合中姓氏相同的关系也是等价关系。系。但朋友关系不是等价关系，因为它不可传递。但朋友关系不是等价关系，因为它不可传递。 25/4525/45二、等价关系二、等价关系例：给定集合例：给定集合X=1,2,7,7，R是是X中的二元关系，并且中的二元关系，并且给定成给定成 ,|()Rx y xXyXxy 可被整除）试证明试证明R是等价关系。是等价关系。解：解：R的关系矩阵如下：的关系矩阵如下： 1001001010010000100101001001010010000100101001001RMR的关系图如下：

18、的关系图如下：26/4526/45二、等价关系二、等价关系注意：注意：上例是模数系统中模等价关系的特定情况。上例是模数系统中模等价关系的特定情况。 设设R+是正整数集合，是正整数集合，m是个正整数。对于是个正整数。对于 来来说，可将说，可将R定义成定义成 。 这这里，里，“x-y可被可被m整除整除”等价于命题等价于命题“当用当用m去除去除x和和y时，它们都有同样的余数时，它们都有同样的余数”。故关系。故关系R也称为也称为。 , x yI,|mRx yxy 可被 所整除27/4527/45元素的等价元素的等价 设设R R是集合是集合A A上的等价关系，若元素上的等价关系，若元素aRbaRb，则称

19、，则称a a与与b b等价，或称等价，或称b b与与a a等价。等价。定义：设定义：设m是个正整数，是个正整数， 。如果对于某一个整。如果对于某一个整数数n，有，有x-y=nm,则称则称x模模等价等价于于y，并记作，并记作 , x yI(mod)xym整数整数m称为称为。“ ”表示模表示模m等价关系等价关系R。28/4528/45二、等价关系二、等价关系定理：任何集合定理：任何集合 中的模中的模m相等关系，是一个等相等关系，是一个等价关系。价关系。 XI证明：设证明：设R是任何集合是任何集合 中的模中的模m相等价关系。如果相等价关系。如果X=，则，则R是个空关系，显然有是自反的、对称的和可是个

20、空关系，显然有是自反的、对称的和可传递的。如果传递的。如果X ，则需考察下列三条：，则需考察下列三条： XI(1)对于任何对于任何 来说，因为来说，因为x-x=0m，所以有，所以有 。因此，模因此，模m相等关系是自反的。相等关系是自反的。 xX(mod)xxm(2)对于任何对于任何 来说，如果来说，如果 ，则存在某一，则存在某一个个 ，能使，能使x-y=nm。于是可有。于是可有y-x=(-n)m，因此，因此有有 ，即模，即模m相等关系是对称的。相等关系是对称的。 , x yX(mod)xym, x yX(mod)yxm(3)设设 ， 和和 。于是存。于是存在在 ，能使，能使 和和 。而而 ，从

21、而，从而可有可有 ，即模，即模m相等关系是可传递的。相等关系是可传递的。 ,x y zX(mod)xym(mod)yxm12,n nI1()xyn m2()yznm1212()xzxyyzn mnmnnm(mod)xzm29/4529/45等价类等价类 定义定义 设设 是集合是集合A A上的等价关系，则上的等价关系，则A A 中等中等价于元素价于元素 的所有元素组成的集合称为的所有元素组成的集合称为 生成的等生成的等价类，用价类，用 表示，即表示，即 Ra |Rab bAaRb 且aaR说明：简单起见，有时候把说明：简单起见，有时候把aR简单写作简单写作a或或a/R。30/4530/45等价类

22、等价类例：设例：设X=a,b,c,d，R是是X中的等价关系，并把中的等价关系，并把R给定成给定成 ,Ra aa bb ab bc cc dd cd d 则：则： , RRaba b , RRcdc d31/4531/45等价类的性质等价类的性质设设X是一集合，是一集合，X是是R中的等价关系中的等价关系2. 对于所有的对于所有的 ，或者，或者 ，或者，或者, x yX RRxy RRxy证明：当证明：当X=，上述结论肯定为真。，上述结论肯定为真。当当X时，分两种情况讨论时，分两种情况讨论 (1)xRy (2)xRy. 如果如果xX,则则x xR。该性质是明显的，因为是自反。该性质是明显的，因为是

23、自反的，所以有的，所以有xRx,于是于是x xR32/4532/45等价类的性质等价类的性质(1) xRy故故 。 RRxy类似地可以证明类似地可以证明由上得由上得 RRyx RRxy若若 ，则，则xRxRz z ， Rzx由由R R 的对称性有的对称性有zRxzRx， 又由又由R R的传递性有的传递性有zRyzRy ，因此，因此 Rzy(2) xRy假设假设 , , RRxy因此有因此有 且且 ， Rzx Rzy故故 RRxy于是由于是由xRzxRz, ,zRyzRy，得，得xRyxRy，与，与xRy相矛盾相矛盾33/4533/45等价类的性质等价类的性质3. Rx XxX证明：假定证明：假

24、定 ，对于某个，对于某个 ，有，有 。由于由于 ，会有，会有 ，因而，因而 。设设 ，于是，于是因而因而证毕。证毕。 Rx Xzx xX Rzx RxXzX Rx XxXzX RRx Xzzx Rx XXx 34/4534/45等价类的性质等价类的性质例例 设设A A=a,b,c,da,b,c,d ，A A上的关系上的关系 ,Ra aa bb ca cc cb bb ac bc ad d R是是A上的等价关系上的等价关系 , , RRRabca b c Rdd 同一个等价类中元素均相互等价。不同等价类同一个等价类中元素均相互等价。不同等价类中的元素互不等价。中的元素互不等价。 由由A A的各元

25、素所生成的等价类必定覆盖的各元素所生成的等价类必定覆盖A A，决定，决定了集合了集合A A的一种划分。的一种划分。 35/4535/45二、等价关系二、等价关系定理：设定理：设R是非空集合是非空集合X中的等价关系。中的等价关系。R的等价类的等价类的集合的集合 ，是，是X的一个划分。的一个划分。 |RxxX定义：设定义：设R是非空集合是非空集合X中的等价关系。中的等价关系。R的各元素的各元素生成的等价类集合生成的等价类集合 叫按叫按R去划分去划分X的的，记作记作X/R，也可以写成，也可以写成X(mod R)。 |RxxX由定义可知，按由定义可知，按R对集合对集合X的划分的划分X/R是一个集是一个

26、集合，并且合，并且X/R的基数是的基数是X的不同的的不同的R等价类的数等价类的数目，因此目，因此X/R的基数又称为等价关系的基数又称为等价关系R的的。 36/4536/45特殊的等价关系特殊的等价关系全域关系：令等价关系全域关系：令等价关系R1=X X，这里，这里X的每一个的每一个元素与元素与X的所有元素都有的所有元素都有R1的关系。按的关系。按R1划分划分X的商的商集乃是集合集乃是集合X。等价关系。等价关系R1是全域关系。全域关是全域关系。全域关系会造成集合系会造成集合X的的最小划分最小划分。 恒等关系恒等关系R：X的每一个元素仅关系到它自身，而的每一个元素仅关系到它自身，而不关系到其它元素

27、。显然，不关系到其它元素。显然，R是个恒等关系。按是个恒等关系。按R划分划分X的商集，仅由单元素集合组成。恒等关系的商集，仅由单元素集合组成。恒等关系R会造成集合会造成集合X的的最大划分最大划分。这些划分均称作。这些划分均称作X的的平平凡划分凡划分。 37/4537/45等价关系与集合的划分等价关系与集合的划分例：令例：令R是整数集合是整数集合I中的中的“模模3同余同余”关系，关系，R可给可给定成定成 3,|()Rx yxIyIxy 被 整除求求I的元素所生成的的元素所生成的R等价类。等价类。 解：等价类是解：等价类是0 , 6, 3,0,3,6,1 , 5, 2,1,4,7,2 , 4, 1

28、,2,5,8,RRR 0, 1, 2 RRRI R 可以看出，等价关系可以造成集合的一个可以看出，等价关系可以造成集合的一个划分。划分。 38/4538/45等价关系与集合的划分等价关系与集合的划分定理：设定理：设C是非空集合是非空集合X的一个划分，则由这个划分的一个划分，则由这个划分所确定的下述关系所确定的下述关系R()()xRySSCxSyS 必定是个等价关系，并称必定是个等价关系，并称R为由为由C划分导出的划分导出的X中中的等价关系。的等价关系。 证明：要证明证明：要证明R是个等价关系，就必须证明是个等价关系，就必须证明R是自反是自反的、对称的和可传递的。的、对称的和可传递的。(a)由于由于C是是X的划分，的划分，C必定覆盖必定覆盖X。对任意。对任意的的 ，必有，必有X属于属于C的某一个元素的某一个元素S。所以对于。所以对于每一个每一个 ，都有，都有xRx，即，即R是自反的。是自反的。 xXxX39/4539/45等价关系与集合的划分等价关系与集合的划分证明证明：（b） 假定假定xRy。于是存在一个。于是存在一个 ，且，