資源描述：
《離散數(shù)學(xué)基礎(chǔ)(洪帆)第二章關(guān)系.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、第2章關(guān)系本章主要內(nèi)容：有序n元組（序偶）和笛卡兒積、關(guān)系的概念；關(guān)系的表示方法；關(guān)系的復(fù)合運(yùn)算、關(guān)系的性質(zhì)；等價(jià)關(guān)系、偏序。2.1笛卡兒積1.定義由n個(gè)具有給定次序的個(gè)體a1,a2,…,an組成的序列，稱為有序n元組，記作(a1,a2,…,an)。注：有序n元組不是由n個(gè)元素組成的集合。因?yàn)榍罢呙鞔_了元素的排列次序，而集合沒(méi)有這個(gè)要求。例如:(a,b,c)≠(b,a,c)≠(c,a,b)，但{a,b,c}={b,a,c}={c,a,b}。一、有序n元組定義假設(shè)(a1,a2,…,an)和(b1,b2,…,
2、bn)是兩個(gè)有序n元組,則(a1,a2,…,an)=(b1,b2,…,bn)成立,當(dāng)且僅當(dāng)a1=b1,a2=b2,…,an=bn。3.序偶當(dāng)n=2時(shí)，有序二元組(a,b)稱為序偶。2.兩有序n元組相等1.定義設(shè)A1,A2,…,An是任意集合,所有的有序n元組(a1,a2,…,an)的集合稱為A1,A2,…,An的笛卡兒積,用A1×A2×…×An表示，其中a1∈A1,a2∈A2,…,an∈An,即：A1×A2×…×An={(a1,a2,…,an)
3、ai∈Ai,i=1,2,…,n}二、笛卡爾積2.集合A與集合
4、B的笛卡爾積A×B={(a,b)
5、a∈A,b∈B}則A1×A2×…×An可表示為注：若所有Ai都相同，例1設(shè)A={1,3},B={1,2,4}，求：A×B，B×A解：A×B={(1,1),(1,2),(1,4),(3,1),(3,2),(3,4)}B×A={(1,1),(1,3),(2,1),(2,3),(4,1),(4,3)}顯然A×B≠B×A,即笛卡兒積不滿足交換律。例2設(shè)A={0,1},B={2,3},C={3,4}則：A×B×C={(0,2,3),(0,2,4),(0,3,3),(0,3,4)(1
6、,2,3),(1,2,4),(1,3,3),(1,3,4)}(A×B)×C={((0,2),3),((0,2),4),((0,3),3),((0,3),4),((1,2),3),((1,2),4),((1,3),3),((1,3),4)}A×(B×C)={(0,(2,3)),(0,(2,4)),(0,(3,3)),(0,(3,4)),(1,(2,3)),(1,(2,4)),(1,(3,3)),(1,(3,4))}.(A×B)×C≠A×(B×C)，因此笛卡兒積不滿足結(jié)合律。2.2關(guān)系1.定義笛卡兒積A1×A
7、2×…×An的任意一個(gè)子集稱為A1,A2,…,An上的一個(gè)n元關(guān)系。注:當(dāng)n=2時(shí),A×B的任一子集稱為由A到B的一個(gè)二元關(guān)系。一、關(guān)系的定義注：1)空集是任何集合的子集,稱為空關(guān)系。2)若集合A、B的元素分別是n、m則A到B的關(guān)系共有注：若是A到B的一個(gè)關(guān)系，如果(a,b)∈,則稱a與b有關(guān)系,記作ab,如果(a,b),則稱a與b沒(méi)有關(guān)系，記作ab。集合稱為關(guān)系的值域，記作2.關(guān)系的定義域和值域定義設(shè)是由A到B的一個(gè)關(guān)系，則使得ab(b∈B)成立的所有元素a∈A的集合稱為關(guān)系的定義域，記作則使得ab(a
8、∈A)成立的所有元素b∈B的例1設(shè)集合A={1,2,4,7,8},B={2,3,5,7},定義由A到B的關(guān)系:={(a,b)
9、(a+b)/5是整數(shù)}試問(wèn)由哪些序偶組成？并求此關(guān)系的定義域和值域。1）定義由集合A到A自身的關(guān)系稱為集合A上的關(guān)系。3.A上的關(guān)系例2設(shè)A={2,3,4,5,9,25},定義A上的關(guān)系R,對(duì)于任意的a,b∈A,當(dāng)且僅當(dāng)(a-b)2∈A時(shí),有aRb,試問(wèn)R由哪些序偶構(gòu)成？并求關(guān)系R的定義域和值域。a)普遍關(guān)系若關(guān)系R=A2,則稱R為A上的普遍關(guān)系,記作UA,即UA={(ai,ak)
10、
11、ai,ak∈A}。2）A上的普遍關(guān)系與恒等式關(guān)系b)恒等關(guān)系A(chǔ)上的恒等關(guān)系用IA表示，定義為:IA={(ai,ai)
12、ai∈A}令有向圖G=(V,E),其中頂點(diǎn)集V=A,邊集E按如下規(guī)定:有向邊二、關(guān)系的表示方法1.列舉法2.描述法3.關(guān)系圖定義設(shè)A={a1,a2,…,an},是A上的關(guān)系,的關(guān)系圖。則稱有向圖G為關(guān)系例3設(shè)集合A={1,2,3,4},R={(1,1),(1,2),(1,3),(1,4),(2,3)}S={(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)}都是A上的
13、二元關(guān)系。畫出關(guān)系R與S的關(guān)系圖。13243124圖(1)圖(2)R和S的關(guān)系圖分別如下圖(1)和圖(2)所示：且關(guān)系矩陣的第i行、第j列的元素4.關(guān)系矩陣定義設(shè)集合A={a1,a2,…,an},B={b1,b2,…,bm}是由A到B的關(guān)系,則的關(guān)系矩陣記為定義如下：定義為一個(gè)n行、m列的矩陣，例4設(shè)集合A=2{0,1},B=2{0,1,2}-2{0},={(a,b)
14、a-b=}是一個(gè)由A到B的關(guān)系,試列出關(guān)系的定義域和值域，
