離散數(shù)學第二章關系(Relation).ppt

1、第二章關系(Relation )，第一節(jié)集合的外積第二節(jié)關系第三節(jié)關系的運算第四節(jié)二元關系的基本性質第五節(jié)等價關系第六節(jié)半序關系，第一節(jié)集合的外積，定義1a、b為兩個個體，由a、b構成的一個順序被稱為二元組，記為()的二元組在集合中因為二元組內的個體很在意順序。 位于第I個位置的個體被稱為二進制組的第I個坐標，位于不同位置的個體可以來自同一集合，也可以來自不同的集合。 位于不同位置的個體可以相同，也可以不同。 定義2為=(a，b )、=(c，d )。 如果a=c并且b=d，則等于，并且(a，b)=(c，d )。 二進制組與二進制組相等的概念也可在m組的情況下推廣。 定義3a、b稱為2個非空集合

2、AB=(a，b)aAbB，AB稱為a與b的外積(笛卡兒積)集合。 兩個集合的外積是一個新的集合，其元素是幾個組，各兩個組中，第一個位置的元素稱為前者，第二個位置的元素稱為后者。 在AB中，a稱為前集，b稱為后集。 前置和后置可以相同也可以不同。 如果前置和后置相同，則記作AA=A2。 假設A=B。 如果不存在偶對的第一或第二分量，則不存在偶對，并將它們的外積集定義為空集。 由于偶對中的元素是規(guī)則的，所以一般來說，A B B A、例1 A=a、b、c、b=0、1 A=a、0 )、(a、1 )、(b、0 )、B=白狗、黃狗AB=(張三、白狗)、(張三、黃狗)、(李四、白狗)、(李四、黃狗) BA=

3、(白狗、黃狗) 如果成為(1) a (BC )=(AB ) (AC )2) a (BC )=(ab ) (AC )3) (ab )的r是ab的子集，則r被稱為a和b的元素之間的二元關系。 aA和bB以及(a，b)R時，a和b有關系r。 在A=B時，r被稱為a上的二元關系。 例1設a為西安交通大學的全體同學的集合，R=(a，b) aA bA a和b為同鄉(xiāng)AA例2設a為大家庭R1=(a，b)aaba為b的父親或母親R2=(a，b)aaba為b的哥哥的例4x=風、馬、牛、R=(風、馬)、(馬、牛) 定義2a、b為兩個非空集合，如果rab1)r=，則將r稱為空關系。 如果R=AB，則將r稱為全部關系；

4、3 )如果R=AB且R=(a，a)aA，則將r稱為這樣的關系。 定義3a、b為兩個非空集合，將rab1)=a(bb)(a，b)R )、(r )稱為r的前域。 2 )將(r )=b (aa ) (a，b)R )，將(r )稱為r的背景區(qū)域。 示例a=1、2、3b=2、4、6、8、10 r=(1，2 )、(2，4 )、(3，6 )、(r )=1r 2是AB上的二元關系，則表示1 )、(r1r2)=(r1)、(r2)2)、(r1r2)=(r1)、(r2)3)、(r1r2)、(r1) a的圓在表示b的圓中，b的元素用小點表示，小點旁邊有元素的名稱。 關系r的對偶用有向圓弧表示。 如果a的元素x與b的元

5、素y相關，則在x和y之間繪制一個有向弧。 有向弧的始端與x連接，有向弧的終端與y連接。將r中的所有偶對連接后，將所有有向弧和有向弧相連的要素全部舍入，得到關系r的圖形表示。 有向弧的始點全部構成(r )，有向弧的終點全部構成(r )。 如果A=B，則可以在一個集合中描繪元素間的關系。 例如，關系r的圖表表示，2 )關系的矩陣表示法是將a、b設為兩個非空的有限集合，將R AB A=a1、a2、a3、am B=b1、b2、b3、bn設為mr=(xij，例如A=a1、a2、a3、a4、R AA R=(a1，a1)， 3 )設(RS )1=r1s 14 ) (RS )1=r1s 1，3.2復合關系定義

6、2a，b，c為3個非空集合，R AB，S BC R o S=(a，c)|的例子1a為老年男性的集合，b為中年男性的集合，c為青少年男性的集合。 r是從a到b的父子關系，R AB S是從b到c的父子關系，S BC是符號關系R o S是從a到c的祖先關系。 例子A=a1、a2、a3、B=b1、b2、C=c1、c2、c3、c4 R=(a1，b1)、(a2，b2)的定理2a、b、c、d為四個非空集合，r、R1、R2 AB、s、S1、S2 BC， 第四關節(jié)二維函數(shù)，其中ro=OS=2、ROS=5、ro=s1s 2、ROS 1、s1s 2、ot=s2ot、s2o t 7、ROS1=s1o r 1、第四關節(jié)

7、二維函數(shù)如果對于x的每個元素x都有(x，x) R，則r稱為x上的自反關系。 假設例子X=a、b、c、d、R=(a，b )、(a )、(b，b )、(c，d )、(c，c )。 如果R=(a，a )、(b，b )、(c，c )、(d，d )，則r是x上的某種關系。 由此可知，關系必定是自我反向關系，但自我反向關系不一定有關系。 定義2r為非空集合x上的二元關系。 如果對于x的每個元素x都有(x，x) R，則r被稱為x上的反自反關系。 根據例子X=a，b，c，d，R=(a，b )，(a，c )，(a，d )，(c，d )反自反轉關系的定義，r為x上的反自反轉關系，定義3r為非空集合x上的二項關系。

8、 對于任意的x、yX，當(x，y)R時，如果存在(y，x)R，則將r稱為x上的對稱關系。 例子X=a，b，c，R1=(a，b )，(b，a )，R2=(a，a )，(b，b )，R3=X2為對稱關系的例子2r為實數(shù)集合，S=(x，y) | xR yR x=y由實數(shù)的性質可知，在x=y的情況下，由y=x，對稱關系的定義可知推廣，一切相等的關系都是對稱關系。 定義4r為非空集合x上的二元關系。 對于任意的x和yX，當(x，y)R和(y，x)R時，如果x=y，則r是x上方的相反對稱關系。 例如，假設r是實數(shù)集合，其中S=(x，y) | xR yR xy是由實數(shù)性質得知的，并且在xy和yx的情況下，存

9、在x=y，并且根據反對稱關系的定義，s是r上的反對稱關系。 定義5r為非空集合x上的二元關系。 對于任何x、y和zX，如果(x，y)R和(y，z)R存在，則r被稱為x上的傳遞關系。 假設例子X=a、b、c、d、R=(a，b )、(b，c )、(c，d )、(a，d )。 設例子2x為平面上的直線的集合，R=(x，y) | xXyXxy由平面幾何的知識知道，并且在xy和yz的情況下，R=(x，y) | xXyXxy是xz。 從傳遞關系的定義可知r是x上的傳遞關系。 例3等價關系是傳遞關系。 全關系X2是自反的、對稱的和傳遞的。 關系I是自我反對、對稱、反對稱、傳達的。 空的關系是逆、對稱、逆對稱

10、、傳達。第5節(jié)等價關系、5.1等價關系和等價類定義1r為非空集合x上的二元關系。 如果r是自反、對稱、傳遞，則r被稱為x上的等價關系。 因為等價關系是自相反的，所以(R)=(R)=X。 例1同鄉(xiāng)關系是等價關系。 例2平面幾何中三角形間的類似關系是等價關系。 例3平面幾何學中三角形間的聯(lián)合關系是等價關系。 例4平面幾何中直線間的平行關系是等價關系。 例如，將5n稱為自然數(shù)集合，將m稱為正整數(shù)，將R=(a，b) | aN bN (a b mod m )稱為r為n以上的模式m同馀關系。 從等價關系的定義可知r是n等價關系。 例6非空集合x上的關系、全部關系都是等價關系。 等價關系的本質是對集合x中的

11、要素進行分類。 定義2r為非空集合x上的等價關系。 xX將y | (y，x)R稱為x，是關于r的等價類，記作xR。 也將x稱為等價類xR的代表要素。 定義3r為非空集合x上的等價關系。 將R=xR | xX，r稱為與集合x的等價關系r相關的商集合，標記為X/R。 X/R中的元素個數(shù)稱為r的等級。 例如，設1n是非負的自然數(shù)集合，m是正整數(shù)，r是n以上的模式m同馀關系，R=(a，b) | aN bN (a b mod m )。 從等價關系的定義可知r是n等價關系。 N/R=0R、1R、2R、3R、m-1R商集N/R共有m個等價類，r的等級為m。 例2x為非空集合1 ) r為全部關系時，成為X/R

12、=X。 (最粗的關系)2)如果r是，則X/R=x | x X。 (最細小的關系)定理1r為非空集合x上的等價關系。 對于任意a、bX，如果有1)a aR 2)(a、b) R，只有aR=bR3) ar br，則ar=br。 4)aX，aR=X定理2r1和R2是非空集合x上的2個等價關系，如果是. R1 R2，則有aX，aR1 aR2。 從定理2可知，如果2個等價關系相等，對應各要素的等價類也相同。 定理3r1和R2是非空集合x上的兩個等價關系.在aX的情況下，有aR1 aR2、R1 R2。 從定理3可知，如果兩個等價關系的等價類集合相等，則兩個等價關系相同。 從定理2和定理3可知，等價關系與等價

13、類集合一一對應。5.2區(qū)分和等價關系定義4a為非空集合，=A | A、A A的話稱為a上的展望復蓋。 定義5a為非空集合，=A | A。 1 )在1)a=a2)12的情況下，如果有A 1A 2=則稱為a以上的一個區(qū)分。 從區(qū)分的定義可以看出，a上的區(qū)分必定是a上的展望復蓋。 定理4r為非空集合x上的等價關系。 如果R=xR | xX，則r被稱為x上的劃分部分。 定理4顯示了由集合x上的等價關系r產生的等價類集合構成了集合x上的一個區(qū)分。 定理5若設為非空集合a上的一個區(qū)分，則產生a上的等價關系。 定理6r為非空集合x上的等價關系，=xR | xX為根據r的x上的等價類集合。 從這個集合產生的等價關系r是(x，y) | (zX )(xzR yzR的話R=R )。 從定理6可以看出，由r可以推出，進而由r可以推出，因為R=R，所以等價關系和區(qū)分是一一對應的。 定理7將=A | A作為非空集合a上的一個區(qū)分，將R=(a，b) | ()(aA bA )作為生成的a上的等價關系，將=aR | aA作為r的等價類集合，則=。 從定理7可知，可以推出r，從r中推出，且=，因此，區(qū)分和等價