離散數(shù)學(xué)作業(yè)6_集合與關(guān)系答案

1、離散數(shù)學(xué)作業(yè)作業(yè)6 等價(jià)關(guān)系1. 設(shè)R和S均為A上的等價(jià)關(guān)系，確定下列各式，哪些是A上的等價(jià)關(guān)系？如果是，證明之；否則，舉反例說(shuō)明。（1）RS （2）RS （3）r (R-S) （4）R- S （5）RS （6）R2解：(1),(6)正確，其余錯(cuò)誤。2. R是集合A上的二元關(guān)系，" a,b,c ,若aRb,且bRc,有cRb,則稱R是循環(huán)關(guān)系。證明R是自反和循環(huán)的，當(dāng)且僅當(dāng)R是一等價(jià)關(guān)系。分析: 需要證明兩部分:(1) 已知R是自反和循環(huán)的，證明:R是一等價(jià)關(guān)系(2) 已知R是一等價(jià)關(guān)系, 證明R是自反和循環(huán)的.證明：（1）先證必要性。只需要證明R是對(duì)陳的和傳遞的。 任取(x,y)R

2、。因?yàn)镽是自反的，所以(y,y)R。由R是循環(huán)的可得(y,x)R，即R是對(duì)陳的。 任取(x,y)，(y,z)R。因R是循環(huán)的，所以(z,x)R。由R對(duì)稱性得(x,z)R，即R是傳遞的。 （2）證充分性。只需要證明R是循環(huán)的。任取(x,y)，(y,z)R，下證(z,x)R。由于R是傳遞的，所以(x,z)R。又由R是對(duì)稱的得(z,x)R。所以R是循環(huán)的。3. 設(shè)|A|=n，在A上可以確定多少個(gè)不同的等價(jià)關(guān)系？ 解：2n!/(n+1)n!n!)4. 給定集合S= 1 , 2 , 3, 4, 5 ，找出S上的等價(jià)關(guān)系R，此關(guān)系R能夠產(chǎn)生劃分1，2，3，4，5，并畫出關(guān)系圖。 解：5. 設(shè)A=1，2，3

3、，4，5。R是集合A上的二元關(guān)系，其關(guān)系矩陣如下圖所示。求包含R的最小等價(jià)關(guān)系和該等價(jià)關(guān)系所確定的劃分。 分析: 可以證明tsr(R)是包含R的最小等價(jià)關(guān)系. 解：包含R的最小等價(jià)關(guān)系的矩陣表示如下： 上述等價(jià)關(guān)系確定的劃分為1,2,4,3,5.6. 自學(xué)華氏(WalShall)算法，寫出算法的基本概念、基本步驟和一個(gè)求解傳遞閉包的具體實(shí)例，并可清晰講解算法整體實(shí)現(xiàn)過程。7. （選做題）設(shè)R與S是A上的等價(jià)關(guān)系，證明：（1）RS是A上的等價(jià)關(guān)系，iff RS=SR；（2）RS是A上的等價(jià)關(guān)系，if RSS 且 SRR.分析: iff是if and only if的縮寫, 是當(dāng)且僅當(dāng)?shù)囊馑? 證

4、明：（1）先證必要性。任取(x,z)RS，則存在y使得xRy,ySz。因?yàn)镽與S是A上的等價(jià)關(guān)系，所以R與S是對(duì)陳的，即yRx,zSy,所以(z,x) SR。因此，RSSR。 任取(x,z)SR，則存在y使得xSy,yRz。由R與S是對(duì)陳的得ySx,zRy，即(z,x) RS。又因?yàn)镽S是對(duì)陳的，所以(x,z) RS，即SR RS。 綜上RS=SR，必要性得證，下面證充分性。 因?yàn)镮AR，IAS，所以IARS，即RS是自反的。 任取(x,z)RS，則存在y使得xRy,ySz。由R與S是對(duì)陳的得yRx,zSy，即(z,x)SR。因?yàn)镽S=SR，所以(z,x)RS，即RS是對(duì)陳的。 因?yàn)?所以RS是傳遞的。 綜上，RS是等價(jià)關(guān)系，充分性得證