離散數(shù)學(xué) 二元關(guān)系

離散數(shù)學(xué)二元關(guān)系第一頁，共十二頁，2022年，8月28日2

有序?qū)Φ男再|(zhì)：1）有序性<x,y><y,x>（當(dāng)xy時(shí)）2）<x,y>與<u,v>相等的充分必要條件是<x,y>=<u,v>x=uy=v例4.1<2,x+5>=<3y4,y>，求x,y.解3y4=2,x+5=y

y=2,x=3

§4.1二元關(guān)系的概念1.有序?qū)?序偶：由兩個(gè)元素x和y按一定順序排成的組合。記作：<x，y>。其中x稱作第一個(gè)元素；y稱作第二個(gè)元素。第二頁，共十二頁，2022年，8月28日3

注：<x1,<x2,x3,…,xn>>≠<x1,x2,…,xn>實(shí)例：1.空間直角坐標(biāo)系中的坐標(biāo)

<3，5，－6>是有序三元組2.圖書館記錄<書類別，書號(hào)，書名，作者，出版社，年份>是一個(gè)有序六元組.2.有序n元組：一個(gè)有序n(n3)元組<x1,x2,…,xn>是一個(gè)有序?qū)?，其中第一個(gè)元素是一個(gè)有序n-1元組，即

<<x1,x2,…,xn-1>,xn>=

<x1,x2,…,xn>。我們將來的研究重點(diǎn)為有序二元組，即有序?qū)?序偶第三頁，共十二頁，2022年，8月28日4例4.2A={1,2,3},B={a,b,c},C=

AB={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>}

BA={<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>,<a,3>,<b,3>,<c,3>}AA={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}AC=CA=3.笛卡兒積：設(shè)A,B為集合，用A中元素為第一個(gè)元素，B中元素為第二個(gè)元素，構(gòu)成有序?qū)?所有這樣的有序?qū)M成的集合叫做

A與B的笛卡兒積記作AB,即AB={<x,y>|xAyB}。第四頁，共十二頁，2022年，8月28日5笛卡兒積的性質(zhì)：1.不適合交換律ABBA(AB,A,B)2.若A或B中有一個(gè)為空集，則AB就是空集.

AB=BA=

3.若|A|=m,|B|=n,則|AB|=mn

4.不適合結(jié)合律(AB)CA(BC)(A,B)例：A={1},B={2},C={3}AB={<1,2>},(AB)C={<<1,2>,3>}={<1,2,3>}BC={<2,3>},A(BC)={<1,<2,3>>}{<1,2,3>}第五頁，共十二頁，2022年，8月28日6二元關(guān)系：集合中兩個(gè)元素之間的某種關(guān)系例4.3甲、乙、丙3個(gè)人進(jìn)行乒乓球比賽，任何兩個(gè)人之間都要比賽一場。假設(shè)比賽結(jié)果是乙勝甲，甲勝丙，乙勝丙。比賽結(jié)果可表示為：{<乙,甲>，<甲,丙>，<乙,丙>}，其中<x,y>表示x勝y.它表示了集合{甲,乙,丙}中元素之間的一種勝負(fù)關(guān)系.例4.4有A、B、C3個(gè)人和四項(xiàng)工作G1、G2、G3、G4，已知A可以從事工作G1和G4，B可以從事工作G3，C可以從事工作G1和G2.

那么，人和工作之間的對(duì)應(yīng)關(guān)系可以記作

R＝

{<A,G1>,<A,G4>,<B,G3>,<C,G1>,<C,G2>}它表示了集合{A,B,C}到工作{G1,G2,G3,G4}之間的關(guān)系第六頁，共十二頁，2022年，8月28日如<x,y>∈R,可記作xRy；如果<x,y>R,則記作xRy實(shí)例：R1={<1,2>,<a,b>},R2=

,R3={<1,2>,3,4}，R4={<x,y>|x∈N∧y∈Z}R1,R2,R4是二元關(guān)系；R3不是二元關(guān)系。4.

二元關(guān)系：如果一個(gè)集合滿足以下條件之一：（1）集合非空,且它的元素都是有序?qū)Γ?）集合是空集則稱該集合為一個(gè)二元關(guān)系,簡稱為關(guān)系，記作R.第七頁，共十二頁，2022年，8月28日85.從A到B的關(guān)系與A上的關(guān)系設(shè)A,B為集合,A×B的任何子集所定義的二元關(guān)系叫做從A到B的二元關(guān)系,當(dāng)A=B時(shí)則叫做

A上的二元關(guān)系.例4.5A={0,1},B={1,2,3},R1={<0,2>},R2=A×B,R3=,R4={<0,1>}.那么R1,R2,R3,R4是從A到B的二元關(guān)系,R3和R4同時(shí)也是A上的二元關(guān)系.

計(jì)數(shù)：|A|=n,|B|=m,|A×B|=n×m,A×B的子集有個(gè).所以A到B上有個(gè)不同的二元關(guān)系.|A|=n,|A×A|=

,A×A的子集有個(gè).所以A上有個(gè)不同的二元關(guān)系.例如|A|=3,則A上有512個(gè)不同的二元關(guān)系.

第八頁，共十二頁，2022年，8月28日9設(shè)A為任意集合，是A上的關(guān)系，稱為空關(guān)系EA,IA分別稱為全域關(guān)系與恒等關(guān)系，定義如下：EA={<x,y>|x∈A∧y∈A}=A×A

IA={<x,x>|x∈A}

例如,A={1,2},則

EA={<1,1>,<1,2>,<2,1>,<2,2>}

IA={<1,1>,<2,2>}

注：{<1,1>}≠IA;{<2,2>}≠IA6.A上的特殊關(guān)系第九頁，共十二頁，2022年，8月28日10小于等于關(guān)系LA,整除關(guān)系DA,包含關(guān)系R定義：

LA={<x,y>|x,y∈A∧x≤y},AR，R為實(shí)數(shù)集合

DB={<x,y>|x,y∈A∧x整除y},BZ*,Z*為非0整數(shù)集

R={<x,y>|x,y∈P(A)∧xy},P(A)是集合A的冪集.類似的還可以定義大于等于關(guān)系,小于關(guān)系,大于關(guān)系,真包含關(guān)系等等.6.A上的特殊關(guān)系第十頁，共十二頁，2022年，8月28日11例4.6A={1,2,3},B={a,b},則

LA={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}

DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}

P(B)={,{a},,{a,b}},則B上的包含關(guān)系是R={<,>,<,{a}>,<,>,<,{a,b}>,<{a},{a}>,<{a},{a,b