離散數學作業
作業6 ——等價關係
1. 設r和s均為a上的等價關係，確定下列各式，哪些是a上的等價關係？如果是，證明之；否則，舉反例說明。
（1）r∩s （2）r∪s （3）r (r-s)
（4）r- s （5）rs6）r2
解：(1),(6)正確，其餘錯誤。
2. r是集合a上的二元關係， a,b,c ,若arb,且brc,有crb,則稱r是迴圈關係。證明r是自反和迴圈的，當且僅當r是一等價關係。
分析: 需要證明兩部分:
(1) 已知r是自反和迴圈的，證明:r是一等價關係
(2) 已知r是一等價關係, 證明r是自反和迴圈的.
證明：（1）先證必要性。只需要證明r是對陳的和傳遞的。
任取(x,y)∈r。因為r是自反的，所以(y,y)∈r。由r是迴圈的可得(y,x)∈r，即r是對陳的。
任取(x,y)，(y,z)∈r。因r是迴圈的，所以(z,x)∈r。由r對稱性得(x,z)∈r，即r是傳遞的。
（2）證充分性。只需要證明r是迴圈的。任取(x,y)，(y,z)∈r，下證(z,x)∈r。
由於r是傳遞的，所以(x,z)∈r。又由r是對稱的得(z,x)∈r。所以r是迴圈的。
3. 設|a|=n，在a上可以確定多少個不同的等價關係？
解：2n!/((n+1)n!n!)
4. 給定集合s=，找出s上的等價關係r，此關係r能夠產生劃分，，}，並畫出關係圖。
解：5. 設a=。r是集合a上的二元關係，其關係矩陣如下圖所示。求包含r的最小等價關係和該等價關係所確定的劃分。
分析: 可以證明tsr(r)是包含r的最小等價關係.
解：包含r的最小等價關係的矩陣表示如下：
上述等價關係確定的劃分為,,}.
6. 自學華氏(walshall)演算法，寫出演算法的基本概念、基本步驟和乙個求解傳遞閉包的具體例項，並可清晰講解演算法整體實現過程。
7. （選做題）設r與s是a上的等價關係，證明：
（1）rs是a上的等價關係，iff rs=sr；
（2）r∪s是a上的等價關係，if rss 且 srr.
分析: iff是if and only if的縮寫, 是當且僅當的意思.
證明：（1）先證必要性。任取(x,z)∈rs，則存在y使得xry,ysz。
因為r與s是a上的等價關係，所以r與s是對陳的，即yrx,zsy,所以(z,x) ∈sr。因此，rssr。
任取(x,z)∈sr，則存在y使得xsy,yrz。由r與s是對陳的得ysx,zry，即(z,x) ∈rs。又因為rs是對陳的，所以(x,z) ∈rs，即sr rs。
綜上rs=sr，必要性得證，下面證充分性。
因為iar，ias，所以iars，即rs是自反的。
任取(x,z)∈rs，則存在y使得xry,ysz。由r與s是對陳的得yrx,zsy，即(z,x)∈sr。因為rs=sr，所以(z,x)∈rs，即rs是對陳的。
因為所以rs是傳遞的。
綜上，rs是等價關係，充分性得證。
（2） 因為iar，ias，所以iar∪s，即r∪s是自反的。
由得，r∪s是對陳的。
由得r∪s是傳遞的。
綜上，r∪s是等價關係。
離散數學 大作業 與答案
1 請給出乙個集合a，並給出a上既具有對稱性，又具有反對稱性的關係。10分 解 a r 2 請給出乙個集合a，並給出a上既不具有對稱性，又不具有反對稱性的關係。10分 3 設a 請給出a上的所有關係。10分 答 4 設a 問a上一共有多少個不同的關係。10分 5 證明 命題公式g是恆真的當且僅當在等...
離散數學形成性考核作業2答案
1.若集合a 則下列表述正確的是 a.a b.a c.a d.a 2.設a b是兩個任意集合，側a b a.a b b.ab c.ab d.b 3.集合a 上的關係r r是a上的二元關係，其關係矩陣為 則r的關係表示式是 a.b.c.d.5.設集合a 上的二元關係r s 則s是r的 閉包 a.自反 ...
離散數學形成性考核作業5答案
一 填空題 1 已知圖g中有1個1度結點，2個2度結點，3個3度結點，4個4度結點，則g的邊數是 15 2 設給定圖g 如右由圖所示 則圖g的點割集是 和，e 試 1 給出g的圖形表示2 寫出其鄰接矩陣 3 求出每個結點的度數4 畫出其補圖的圖形 解 1 如右圖 2 3 v1的度數為1，v2的度數為...