第四章 二元关系-3rd-zhou

1/36第四章二元关系2/452/45回顾•关系的性质•关系的闭包运算3/453/45四、关系的闭包运算定理：设X是集合，R是集合中的二元关系，于是有()()()()()()()()()arsRsrRbrtRtrRctsRstR证明：11111()()()()()()()XXXXXXasrRsRIRIRIRIRIRRIrRRrsR4/454/45四、关系的闭包运算证明（b）：因为，，而对于所有的有，以及。根据这些关系式，可有()()XtrRtRI()()XrtRtRInNnXXIIXXIRRIR1()nniXXiRIIR于是12323()()()()()()()()iXXiXXXXXtrRtRIRIRIRIRIIRRRItRrtR5/455/45四、关系的闭包运算证明（c）：如果，则，12RR12()()sRsR12()()tRtR根据对称闭包的定义，有。首先构成上式两侧的可传递闭包，再依次构成两侧的对称闭包,可以求得以及。而ts(R)是对称的，所以，从而有。()sRR()()tsRtR()()stsRstR()()ssRtstR()()tsRstR6/456/45四、关系的闭包运算注意：（1）通常用R+表示R的可传递闭包t(R)，并读作“R加”。（2）通常用R*表示R的自反可传递闭包tr(R)，并读作“R星”。7/457/454.5特殊关系一、集合的划分和覆盖定义：给定非空集合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的覆盖。8/458/45一、集合的划分和覆盖定义：给定非空集合S，设非空集合A={A1,A2,…,An}，如果有1()(1,2,,)()()()()iijijniiaASinbAAijAAijcAS或则称集合A是集合S的一个划分。划分中的元素Ai称为划分的类。划分的类的数目叫划分的秩。划分是覆盖的特定情况，即中元素互不相交的特定情况。9/459/45一、集合的划分和覆盖例：设S={1,2,3}，考虑下列集合{{1,2},{2,3}};{{1},{1,2},{1,3}};{{1},{2,3}};{{1,2,3}};{{1},{2},{3}};{{},{,}};ABCDEFaacS的覆盖S的覆盖S的覆盖、划分，秩为2S的覆盖、划分，秩为1，最小划分S的覆盖、划分，秩为3，最大划分10/4510/45一、集合的划分和覆盖定义：设A和A'是非空集合S的两种划分，并可以表示成1miiAA1njjAA如果A'的每一类A'j，都是A的某一类Ai的子集，那么称划分A'是划分A的加细，并称A'加细了A。如果A'是A的加细并且A'≠A，则称A'是A的真加细。11/4511/45极小项、完全交集定义：划分全集E的过程，可看成是在表达全集的文氏图上划出分界线的过程。设A，B，C是全集E的三个子集。由A，B和C生成的E的划分的类，称为极小项或完全交集。n个子集生成2n个极小项，用表示。0121,,,nIII01234567IABCIABCIABCIABCIABCIABCIABCIABCABC0I1I2I3I4I5I6I7I12/4512/45一、集合的划分和覆盖定理：由全集的n个子集A1,A2,…,An所生成的全部极小项集合，能够构成全集E的一个划分。证明：证明这个定理，只需证明全集E中的每一个元素，都仅属于一个完全交集就够了。如果，则，或，或；…；或。由此可见，定有xE1xA1xA2xA2xAnxAnxA1()niixA这里或是Ai或是～Ai。试考察两个不同的完全交集T。因为两个完全交集是不同的，就是说存在这样一个i，使得和，因此可有，即；因而任何一个都不能同时属于两个不同的完全交集。iAiTAiTAiiTAATxE13/4513/45一、集合的划分和覆盖•注意：不难看出，这里所说的完全交集，与命题演算中的极小项相似。但是和极小项的集合不同，极大项的集合不能构成全集的划分。14/4514/45二、等价关系定义：设X是任意集合,R是集合中的二元关系。如果R是自反的、对称的和可传递的，则称R是等价关系。即满足以下几点：()()()()()()()()()()()()axxXxRxbxyxXyXxRyyRxcxyzxXyXzXxRyyRzxRz如果R是集合X中的等价关系，则R的域是集合X自身，所以，称R是定义于集合X中的关系。例如数的相等关系是任何数集上的等价关系。又例如一群人的集合中姓氏相同的关系也是等价关系。但朋友关系不是等价关系，因为它不可传递。15/4515/45二、等价关系例：给定集合X={1,2,…,7}，R是X中的二元关系，并且给定成{,|(()}RxyxXyXxy可被３整除）试证明R是等价关系。解：R的关系矩阵如下：1001001010010000100101001001010010000100101001001RM1746352R的关系图如下：16/4516/45二、等价关系注意：上例是模数系统中模等价关系的特定情况。设Z+是正整数集合，m是个正整数。对于来说，可将R定义成。这里，“x-y可被m整除”等价于命题“当用m去除x和y时，它们都有同样的余数”。故关系R也称为模m同余关系。,xyI{,|}mRxyxy可被所整除17/4517/45元素的等价设R是集合A上的等价关系，若元素aRb，则称a与b等价，或称b与a等价。定义：设m是个正整数，。如果对于某一个整数n，有x-y=n·m,则称x模m等价于y，并记作,xyZ(mod)xym整数m称为等价的模数。“”表示模m等价关系R。18/4518/45二、等价关系定理：任何集合中的模m相等关系，是一个等价关系。XZ证明：设R是任何集合中的模m相等价关系。如果X=Ф，则R是个空关系，显然有是自反的、对称的和可传递的。如果X≠Ф，则需考察下列三条：XI(1)对于任何来说，因为x-x=0·m，所以有。因此，模m相等关系是自反的。xX(mod)xxm(2)对于任何来说，如果，则存在某一个，能使x-y=n·m。于是可有y-x=(-n)·m，因此有，即模m相等关系是对称的。,xyX(mod)xym,xyX(mod)yxm(3)设，和。于是存在，能使和。而，从而可有，即模m相等关系是可传递的。,,xyzX(mod)xym(mod)yxm12,nnZ1()xynm2()yznm1212()xzxyyznmnmnnm(mod)xzm19/4519/45等价类定义设是集合A上的等价关系，则A中等价于元素的所有元素组成的集合称为生成的等价类，用表示，即说明：简单起见，有时候把[a]R简单写作[a]或a/R。20/4520/45等价类例：设X={a,b,c,d}，R是X中的等价关系，并把R给定成{,,,,,,,,,,,,,,,}Raaabbabbcccddcdd则：[][]{,}RRabab[][]{,}RRcdcdbadc21/4521/45等价类的性质设X是一集合，X是R中的等价关系2.对于所有的，或者，或者,xyXRRxyRRxy证明：当X=Ф，上述结论肯定为真。当X≠Ф时，分两种情况讨论(1)xRy(2)xR'y１.如果x∈X,则x∈[x]R。该性质是明显的，因为Ｒ是自反的，所以有xRx,于是x∈[x]R22/4522/45等价类的性质(1)xRy故。类似地可以证明由上得若，则xRz，由R的对称性有zRx，又由R的传递性有zRy，因此(2)xR'y假设,因此有且，故于是由xRz,zRy，得xRy，与xR'y相矛盾23/4523/45等价类的性质3.RxXxX证明：假定，对于某个，有。由于，会有，因而。设，于是因而证毕。RxXzxxXRzxRxXzXRxXxXzXRRxXzzxRxXXx24/4524/45等价类的性质例设A={a,b,c,d}，A上的关系R是A上的等价关系同一个等价类中元素均相互等价。不同等价类中的元素互不等价。由A的各元素所生成的等价类必定覆盖A，决定了集合A的一种划分。25/4525/45二、等价关系定理：设R是非空集合X中的等价关系。R的等价类的集合，是X的一个划分。{|}RxxX定义：设R是非空集合X中的等价关系。R的各元素生成的等价类集合叫按R去划分X的商集，记作X/R，也可以写成X(modR)。{|}RxxX由定义可知，按R对集合X的划分X/R是一个集合，并且X/R的基数是X的不同的R等价类的数目，因此X/R的基数又称为等价关系R的秩。26/4526/45特殊的等价关系全域关系：令等价关系R1=XX，这里X的每一个元素与X的所有元素都有R1的关系。按R1划分X的商集乃是集合{X}。等价关系R1是全域关系。全域关系会造成集合X的最小划分。恒等关系R：X的每一个元素仅关系到它自身，而不关系到其它元素。显然，R是个恒等关系。按R划分X的商集，仅由单元素集合组成。恒等关系R会造成集合X的最大划分。这些划分均称作X的平凡划分。27/4527/45等价关系与集合的划分例：令R是整数集合I中的“模3同余”关系，R可给定成3{,|()}RxyxyxyZZ被整除求Z的元素所生成的R等价类。解：等价类是[0]{,6,3,0,3,6,}[1]{,5,2,1,4,7,}[2]{,4,1,2,5,8,}RRR{0,1,2}RRRRZ可以看出，等价关系可以造成集合的一个划分。28/4528/45等价关系与集合的划分定理：设C是非空集合X的一个划分，则由这个划分所确定的下述关系R()()xRySSCxSyS必定是个等价关系，并称R为由C划分导出的X中的等价关系。证明：要证明R是个等价关系，就必须证明R是自反的、对称的和可传递的。(a)由于C是X的划分，C必定覆盖X。对任意的，必有x属于C的某一个元素S。所以对于每一个，都有xRx，即R是自反的。xXxX29/4529/45等价关系与集合的划分证明：（b）假定xRy。于是存在一个，且和，所以有yRx。因此，R是对称的。（c）假定xRy和yRz。于是存在两个元素和，且和，所以有。这样就有S1=S2，因此，。从而xRz，所以有R是可传递的。综上，R是个等价关系。证毕。SCxSyS1SC2SC1,xyS2,yzS12SS1zS可以看出，给定集合的一种划分，就可以写出一个等价关系。反过来，集合中的等价关系也能够生成该集合的划分。30/4530/45等价关系与集合的划分例：设X={a,b,c,d,e}和C={{a,b},{c},{d,e}}。试写出由划分C导出的X中的等价关系。解：用R表示这个等价关系，（每一个类做笛卡尔乘积）{,,,,,,,,,,,,,,,,,}Raaabbabbccdddeedee注意：集合中的等价关系能够生成该集合的划分，反过来集合中的任何一种划分又能确定一种等价关系。31/4531/45abc54321abcbaccabacb32/4532/45等价关系与集合的划分有时，用不同的方法定义的两种等价关系，可能会产生同一个划分。例如，设集合X={1,2,…,9}，R1和R2是X中的两种关系，并把R1和R2规