離散數(shù)學(xué)（第二版） 課件 鄒麗娜 5 二元關(guān)系2

離散數(shù)學(xué)第5章二元關(guān)系關(guān)系的運(yùn)算說明：

1有關(guān)集合運(yùn)算的一些公式在關(guān)系運(yùn)算中也同樣適合。2在關(guān)系中還有兩種新的運(yùn)算：復(fù)合關(guān)系和逆關(guān)系。關(guān)系的運(yùn)算關(guān)系的交、并、補(bǔ)、差由于關(guān)系是一些有序偶的集合，因此集合的交、并、補(bǔ)、差等運(yùn)算在關(guān)系中也同樣適用。例：設(shè)X={a，b，c}，Y={1，2}，且R，S均是從X到Y(jié)的關(guān)系。

R={<a，1>，<b，2>，<c，1>}S={<a，1>，<b，1>，<c，1>}

R∪S={<a，1>，<b，1>，<b，2>，<c，1>}

R∩S={<a，1>，<c，1>}R的補(bǔ)={<a，2>，<b，1>，<c，2>}

R-S={<b，2>}運(yùn)算結(jié)果仍是從X到Y(jié)上的關(guān)系。復(fù)合關(guān)系例：設(shè)某人a與某人b有“兄妹”關(guān)系R，又設(shè)有某人c，而b與c有“母子”關(guān)系，a與c得到一個(gè)新的關(guān)系—“舅甥”關(guān)系。abcRSTb—中間元素“o”—復(fù)合運(yùn)算R={<a，b>}S={<b，c>}RoS={<a，c>}復(fù)合關(guān)系例如,F={<3,3>,<6,2>},G={<2,3>},則復(fù)合關(guān)系不滿足交換律關(guān)系復(fù)合運(yùn)算相當(dāng)于矩陣的乘法運(yùn)算R1aaabbccaR2abacbacbccbbR1○R2

abca110b001c100

abca011b110c011×=abacbccacb

abca011b001c110練習(xí)#例如,F={<3,3>,<6,2>},G={<2,3>},則F-1

={<3,3>,<2,6>}逆關(guān)系關(guān)系逆運(yùn)算相當(dāng)于矩陣的轉(zhuǎn)置運(yùn)算Raaabbccaaabacbac

abca110b001c100

abca101b100c010R-1練習(xí)#練習(xí)關(guān)系的運(yùn)算關(guān)系R的n次冪此外,R0=IA的關(guān)系矩陣為:dabcR0R0關(guān)系圖如下:關(guān)系復(fù)合運(yùn)算與冪復(fù)合運(yùn)算的矩陣解釋2RaaabbccaaabbccR0=IaaabbccaR○

I=R○

R0

abca110b001c100

abca100b010c001

abca110b001c100×=關(guān)系冪復(fù)合運(yùn)算相當(dāng)于矩陣的冪運(yùn)算RaaabbccaRaaabacbacacbR○R=R2

abca110b001c100

abca111b100c110×=aaabbcca

abca110