1、請給出乙個集合a，並給出a上既具有對稱性，又具有反對稱性的關係。（10分）
解：a= r=
2、請給出乙個集合a，並給出a上既不具有對稱性，又不具有反對稱性的關係。（10分）
3、設a=，請給出a上的所有關係。（10分）
答：4、設a=，問a上一共有多少個不同的關係。（10分）
5、證明： 命題公式g是恆真的當且僅當在等價於它的合取正規化中，每個子句均至少包含乙個原子及其否定。（10分）
證明：設公式g的合取正規化為：g』=g1g2…gn
若公式g恆真，則g』恆真，即子句gi；i=1,2,…n恆真
為其充要條件。
gi恆真則其必然有乙個原子和它的否定同時出現在gi中，也就是說無論乙個解釋i使這個原子為1或0 ，gi都取1值。
若不然，假設gi恆真，但每個原子和其否定都不同時出現在gi中。則可以給定乙個解釋i，使帶否定號的原子為1，不帶否定號的原子為0，那麼gi在解釋i下的取值為0。這與gi恆真矛盾。
因此，公式g是恆真的當且僅當在等價於它的合取正規化中，每個子句均至少包含乙個原子及其否定。
6、若g=(p，l)是有限圖，設p(g)，l(g)的元數分別為m，n。證明：n ，其中表示m中取2的組合數。（10分）
證明：如果g=(p,l)為完全圖，即對於任意的兩點u、v（u≠v）,都有一條邊uv，則此時對於元數為m的p(g)，l(g)的元數取值最大為。因此，若g=(p,l)為一有限圖，設p(g)的元數為m，則有l(g)的元數n ，其中表示m中取2的組合數。
7、設g是有限圖，p(g)，l(g)的元數分別為m，n。，分別是g中點的最小度和最大度。證明：2n/m。（10分）
證明：因為 mm
同時由定理1知=2n
則有 m2nm
由m>0有：2n/m
八、設g=(p，l)是有限圖，p(g)，l(g)的元數分別為m，n。證明：如果n> ，則g是連通的。（10分）
證明：反證法，假設此時g不是連通的，則將g中的乙個連通分支作為乙個子圖記為g1，剩餘的部分記為g2。可設p(g1)的元數為m1，p(g2) 的元數為m2，其中1≤m1，m2n≤= m1(m1-1)/2+ m2(m2-1)/2
=1/2(m12+m22- m1- m2)
=1/2(m12+(m-m1)2- m)
=1/2(m2-m-2mm1+2m12)
=1/2(m2-m-2m1(m-m1))
=1/2(m2-m-2m1m2)
由於(m1-1) (m2-1) ≥0所以有：
m1 m2- (m1+m2)+1≥0 即 m1 m2≥ m-1
則有：n ≤1/2(m2-m-2m1m2)
≤1/2(m2-m-2(m-1))
=1/2(m2-3m+2)
=1/2(m-1)(m-2)
= 顯然這與已知n>矛盾，命題得證。
9、設g為圖（可能無限），無迴路，但若任意外加一邊於g後就形成一回路，試證g必為樹。（10分）
證明：從樹的定義出發，
1）由已知有g中無迴路
2）要證g連通，反證法，假設g不連通，則一定存在點u和v，滿足在g中沒有從u到v的路，現在連線u、v，即在g中新增一條邊uv，由已知g中加一條邊後形成一回路可知，g中u、v兩點間有一回路，即若g中刪除邊uv後，點u、v仍然連通，矛盾。所以g連通。
因此，g必為樹
10、證明：乙個有限連通圖g是一條非迴路的簡單路，當且僅當g中有兩個點的度為1，且其餘點的度均為2。（10分）
證明：必要性，設p(g)的元數為n，k=3時顯然成立。假設k=n-1時，g中有兩個點的度為1，且其餘點的度均為2。
則當k=n時，設v1是路g的起點v2是與v1相鄰的另一點，把點v1及邊v1v2從g中刪去得g。顯然g仍是非迴路的簡單路且有n-1個節點，有歸納假設知g中有兩個點的度為1，且其餘點的度均為2。把點v1及邊v1v2加入到g中得g，顯然g中有兩個點的度為1，且其餘點的度均為2，歸納法完成。
充分性，k=3時顯然成立，假設k=n-1時，g是一條非迴路的簡單路。則當k=n時，設v1是路g中度為1的一點，v2是與v1相鄰的另一點，把點v1及邊v1v2從g中刪去得g，此時v2的度必為1（若為0則與g是連通圖矛盾；若為2則在g中v2的度為3，矛盾），有假設知g是一條非迴路的簡單路。把點v1及邊v1v2加入到g中得g顯然仍成立，歸納法完成。
離散數學作業
離散數學集合論部分形成性考核書面作業 本課程形成性考核書面作業共3次，內容主要分別是集合論部分 圖論部分 數理邏輯部分的綜合練習，基本上是按照考試的題型 除單項選擇題外 安排練習題目，目的是通過綜合性書面作業，使同學自己檢驗學習成果，找出掌握的薄弱知識點，重點複習，爭取盡快掌握 本次形考書面作業是第...
離散數學作業6 集合與關係答案
離散數學作業 作業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...
離散數學形成性考核作業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.自反 ...