離散數(shù)學(xué)第二章關(guān)系(Relation).ppt

《離散數(shù)學(xué)第二章關(guān)系(Relation).ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第二章關(guān)系(Relation)第一節(jié)集合的叉積第二節(jié)關(guān)系第三節(jié)關(guān)系的運(yùn)算第四節(jié)二元關(guān)系的基本性質(zhì)第五節(jié)等價(jià)關(guān)系第六節(jié)半序關(guān)系第一節(jié)集合的叉積定義1設(shè)a,b是兩個(gè)個(gè)體，由a,b組成的一個(gè)計(jì)較順序的序列稱為二元組，記為(a,b)。二元組不是集合，因?yàn)槎M中的個(gè)體計(jì)較順序。第i個(gè)位置上的個(gè)體稱為二元組的第i個(gè)坐標(biāo)。不同位置上的個(gè)體可以來自同一個(gè)集合，也可以來自不同的集合。不同位置上的個(gè)體可以相同，也可以不相同。定義2設(shè)?=(a,b),?=(c,d)。若a=c且b=d，則稱?與?相等，記為(a,b)=(c,d)。關(guān)于二元組和二元組相等的概念可以

2、推廣到m元組的情況。定義3設(shè)A,B是兩個(gè)非空集合A?B={(a,b)｜a?A∧b?B}稱A?B是A與B的叉積（笛卡兒積）集合。兩個(gè)集合的叉積是一個(gè)新的集合，它的元素是一些二元組，在每個(gè)二元組中，第一個(gè)位置上的元素稱為前者，第二個(gè)位置上的元素稱為后者。在A?B中，A稱為前集，B稱為后集。前集與后集可以相同，也可以不相同。若前集與后集相同，則記為A?A=A2。規(guī)定A??=?=??B。由于若偶對的第一分量或第二分量不存在就沒有偶對存在，故規(guī)定它們的叉積集合為空集。由于偶對中的元素是有序的，因此一般地說A?B≠B?A例1A={a,b,c},B={

3、0,1}A?B={(a,0),(a,1),(b,0),(b,1),(c,0),(c,1)}B?A={(0,a),(0,b),(0,c),(1,a),(1,b),(1,c)}例2A={張三,李四}，B={白狗,黃狗}A?B={(張三,白狗),(張三,黃狗),(李四,白狗),(李四,黃狗)}B?A={(白狗,張三),(白狗,李四),(黃狗,張三),(黃狗,李四)}定理1設(shè)A,B,C,D是四個(gè)集合，那么A?B=C?D當(dāng)且僅當(dāng)A=C且B=D。定理2設(shè)A,B,C是三個(gè)集合，則1）A?(B∪C)=(A?B)∪(A?C)2）A?(B∩C)=(A?B)∩

4、(A?C)3）(A∪B)?C=(A×C)∪(B?C)4）(A∩B)?C=(A×C)∩(B?C)第二節(jié)關(guān)系2.1關(guān)系的基本概念2.2關(guān)系表示法2.1關(guān)系的基本概念定義1設(shè)A,B是兩個(gè)非空集合，A×B是A與B的叉積集合。若R是A×B的子集，則稱R是A與B元素之間的一個(gè)二元關(guān)系。當(dāng)a?A且b?B且(a,b)?R時(shí)，稱a與b有關(guān)系R。當(dāng)A=B時(shí)，稱R是A上的一個(gè)二元關(guān)系。例1設(shè)A是西安交通大學(xué)全體同學(xué)組成的集合，R={(a,b)∣a?A∧b?A∧a與b是同鄉(xiāng)}?A×A例2設(shè)A是一個(gè)大家庭R1={(a,b)∣a?A∧b?A∧a是b的父親或母親}R2

5、={(a,b)∣a?A∧b?A∧a是b的哥哥或姐姐}R3={(a,b)∣a?A∧b?A∧a是b的丈夫或妻子}例3設(shè)N是自然數(shù)集合，R={(a,b)∣a?N∧b?N∧a｜b}?N×N稱R是自然數(shù)集合上的整除關(guān)系。例4設(shè)X={風(fēng)，馬，牛}，R={(風(fēng),馬)，(馬,牛)}?X×X稱R是X上的二元關(guān)系。定義2設(shè)A,B是兩個(gè)非空集合，R?A×B1）若R=?，則稱R為空關(guān)系；2）若R=A×B，則稱R為全關(guān)系；3）若A=B且R={(a,a)∣a?A}，則稱R是幺關(guān)系。定義3設(shè)A,B是兩個(gè)非空集合，R?A×B1）設(shè)?(R)={a∣(?b?B)((a,b)

6、?R)}，稱?(R)為R的前域。2）設(shè)?(R)={b∣(?a?A)((a,b)?R)}，稱?(R)為R的后域。例A={1,2,3}B={2,4,6,8,10}R={(1,2),(2,4),(3,6)}?(R)={1,2,3}?A?(R)={2,4,6}?B定理1設(shè)R1,R2是A×B上的兩個(gè)二元關(guān)系，若R1?R2，則1）?(R1)??(R2)2）?(R1)??(R2)定理2設(shè)R1,R2是A×B上的兩個(gè)二元關(guān)系，則1）?(R1∪R2)=?(R1)∪?(R2)2）?(R1∪R2)=?(R1)∪?(R2)3）?(R1∩R2)??(R1)∩?(R2

7、)4）?(R1∩R2)??(R1)∩?(R2)2.2關(guān)系表示法1)關(guān)系的圖形表示法設(shè)A,B是兩個(gè)非空的有限集合，R?A?B分別用兩個(gè)圓圈表示A,B兩個(gè)集合。在表示A的圓圈中將A的元素用小圓點(diǎn)表示，小圓點(diǎn)旁邊是元素的名稱。在表示B的圓圈中將B的元素用小圓點(diǎn)表示，小圓點(diǎn)旁邊是元素的名稱。關(guān)系R中的偶對用有向弧表示。若A中的某個(gè)元素x與B中的某個(gè)元素y有關(guān)系R，則在x和y之間畫一條有向弧。有向弧的起始端與x相連，有向弧的終止端與y相連。將R中所有的偶對連完之后，將所有的有向弧及和有向弧相連的元素全部圈出來就得到關(guān)系R的圖形表示。所有有向弧的始端

8、點(diǎn)構(gòu)成?(R)，所有有向弧的終端點(diǎn)構(gòu)成?(R)。若A=B，則只需在一個(gè)集合中畫出元素間的關(guān)系即可。ABbacdefghijR例：關(guān)系R的圖形表示2)關(guān)系的矩陣表示法設(shè)A,B是兩個(gè)非空的有限集合