離散數學試題(a捲及答案）
一、證明題（10分）
1)(p∧(q∧r))∨(q∧r)∨(p∧r)r
證明: 左端(p∧q∧r)∨((q∨p)∧r)((p∧q)∧r))∨((q∨p)∧r)
((p∨q)∧r)∨((q∨p)∧r)((p∨q)∨(q∨p))∧r
((p∨q)∨(p∨q))∧rt∧r(置換)r
2)x(a(x)b(x)) xa(x)xb(x)
證明 ：x(a(x)b(x))x(a(x)∨b(x))xa(x)∨xb(x)xa(x)∨xb(x)xa(x)xb(x)
二、求命題公式(p∨(q∧r))(p∧q∧r)的主析取正規化和主合取正規化（10分）
證明：(p∨(q∧r))(p∧q∧r)(p∨(q∧r))∨(p∧q∧r))
（p∧(q∨r)）∨(p∧q∧r)
(p∧q)∨(p∧r))∨(p∧q∧r)
(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r))∨(p∧q∧r))∨(p∧q∧r)
m0∨m1∨m2∨m7
m3∨m4∨m5∨m6
三、推理證明題（10分）
1） c∨d, (c∨d) e, e(a∧b), (a∧b)(r∨s)r∨s
證明：(1) (c∨d)e
(2) e(a∧b
(3) (c∨d)(a∧b)
(4) (a∧b)(r∨s
(5) (c∨d)(r∨s
(6) c∨d
(7) r∨s
2) x(p(x)q(y)∧r(x))，xp(x)q(y)∧x(p(x)∧r(x))
證明（1）xp(x)
(2)p(a)
(3)x(p(x)q(y)∧r(x))
(4)p(a)q(y)∧r(a)
(5)q(y)∧r(a)
(6)q(y)
(7)r(a)
(8)p(a)
(9)p(a)∧r(a)
(10)x(p(x)∧r(x))
(11)q(y)∧x(p(x)∧r(x))
四、設m是乙個取定的正整數，證明：在任取m＋1個整數中，至少有兩個整數，它們的差是m的整數倍
證明設，，…，為任取的m＋1個整數，用m去除它們所得餘數只能是0，1，…，m－1，由抽屜原理可知，，，…，這m＋1個整數中至少存在兩個數和，它們被m除所得餘數相同，因此和的差是m的整數倍。
五、已知a、b、c是三個集合，證明a-(b∪c)=(a-b)∩(a-c) （15分）
證明 ∵x a-（b∪c） x a∧x（b∪c） x a∧（xb∧xc） （x a∧xb）∧（x a∧xc） x（a-b）∧x（a-c） x（a-b）∩（a-c）∴a-（b∪c）=（a-b）∩（a-c）
六、已知r、s是n上的關係，其定義如下：r=，s=。求r-1、r*s、s*r、r、s（10分）
解：r-1=，r*s=，s*r=，
七、若f:a→b和g:b→c是雙射，則（gf）-1=f-1g-1（10分）。
證明：因為f、g是雙射，所以gf：a→c是雙射，所以gf有逆函式（gf）-1：c→a。同理可推f-1g-1：c→a是雙射。
因為∈f-1g-1存在z（∈g-1∈f-1）存在z（∈f∈g）∈gf∈（gf）-1,所以（gf）-1=f-1g-1。
r=，s=。
八、（15分）設是半群，對a中任意元a和b，如a≠b必有a*b≠b*a，證明：
(1)對a中每個元a，有a*a＝a。
(2)對a中任意元a和b，有a*b*a＝a。
(3)對a中任意元a、b和c，有a*b*c＝a*c。
證明由題意可知，若a*b＝b*a，則必有a＝b。
(1)由(a*a)*a＝a*(a*a)，所以a*a＝a。
(2)由a*(a*b*a)＝(a*a)*(b*a)＝a*b*(a*a)＝(a*b*a)*a，所以有a*b*a＝a。
(3)由(a*c)*(a*b*c)＝(a*c*a)*(b*c)＝a*(b*c)＝(a*b)*c＝(a*b)*(c*a*c)＝(a*b*c)*(a*c)，所以有a*b*c＝a*c。
九、給定簡單無向圖g＝，且|v|＝m，|e|＝n。試證：若n≥＋2，則g是哈密爾頓圖
證明若n≥＋2，則2n≥m2－3m＋6 （1）。
若存在兩個不相鄰結點、使得d()＋d()＜m，則有2n＝＜m＋(m－2)(m－3)＋m＝m2－3m＋6，與（1）矛盾。所以，對於g中任意兩個不相鄰結點、都有d()＋d()≥m，所以g是哈密爾頓圖。
離散數學試題(b捲及答案）
一、證明題（10分）
1)((p∨q)∧(p∧(q∨r)))∨(p∧q)∨(p∧r)t
證明左端((p∨q)∧(p∨(q∧r)))∨((p∨q)∧(p∨r))(摩根律) ((p∨q)∧(p∨q)∧(p∨r))∨((p∨q)∧(p∨r))(分配律) ((p∨q)∧(p∨r))∨((p∨q)∧(p∨r)) (等冪律) t (代入)
2)x(p(x)q(x))∧xp(x)x(p(x)∧q(x))
證明 x(p(x)q(x))∧xp(x)x((p(x)q(x)∧p(x))x((p(x)∨q(x)∧p(x))x(p(x)∧q(x))xp(x)∧xq(x)x(p(x)∧q(x))
二、求命題公式(pq)(p∨q) 的主析取正規化和主合取正規化（10分）
解：(pq)(p∨q)(pq)∨(p∨q)(p∨q)∨(p∨q)(p∧q)∨(p∨q) (p∨p∨q)∧(q∨p∨q)(p∨q)m1m0∨m2∨m3
三、推理證明題（10分）
1)(p(qs))∧(r∨p)∧qrs
證明：（1）r 附加前提
(2)r∨pp
(3)pt(1)(2),i
(4)p(qs) p
(5)qst(3)(4),i
(6)qp
(7)st(5)(6),i
(8)rscp
2) x(p(x)∨q(x))，xp(x)x q(x)
證明：(1)xp(x) p
(2)p(ct(1),us
(3)x(p(x)∨q(xp
(4)p(c)∨q(ct(3),us
(5)q(ct(2)(4),i
(6)x q(xt(5),eg
四、例5在邊長為1的正方形內任意放置九個點，證明其中必存在三個點，使得由它們組成的三角形（可能是退化的）面積不超過1/8（10分）。
證明：把邊長為1的正方形分成四個全等的小正方形，則至少有乙個小正方形內有三個點，它們組成的三角形（可能是退化的）面積不超過小正方形的一半，即1/8。
五、已知a、b、c是三個集合，證明a∩(b∪c)=(a∩b)∪(a∩c) （10分）
證明：∵x a∩（b∪c） x a∧x（b∪c） x a∧（xb∨xc）（ x a∧xb）∨（x a∧xc） x（a∩b）∨x a∩c x（a∩b）∪（a∩c）∴a∩（b∪c）=（a∩b）∪（a∩c）
六、=是集合a的乙個劃分，定義r=，則r是a上的等價關係（15分）。
證明：a∈a必有i使得a∈ai，由定義知ara，故r自反。
a,b∈a，若arb ，則a,b∈ai，即b,a∈ai，所以bra，故r對稱。
a,b,c∈a，若arb 且brc，則a,b∈ai及b,c∈aj。因為i≠j時ai∩aj=，故i=j，即a,b,c∈ai，所以arc，故r傳遞。
總之r是a上的等價關係。
七、若f:a→b是雙射，則f-1:b→a是雙射（15分）。
證明: 對任意的x∈a，因為f是從a到b的函式，故存在y∈b，使∈f，∈f-1。所以,f-1是滿射。
對任意的x∈a，若存在y1,y2∈b，使得∈f-1且∈f-1,則有∈f且∈f。因為f是函式，則y1=y2。所以，f-1是單射。 因此f-1是雙射。
八、設是群，和是的子群，證明：若a∪b＝g，則a＝g或b＝g（10分）。
證明假設a≠g且b≠g，則存在aa，ab，且存在bb，ba（否則對任意的aa，ab，從而ab，即a∪b＝b，得b＝g，矛盾。）
對於元素a*bg，若a*ba，因a是子群，a-1a，從而a-1 * (a*b)＝b a，所以矛盾，故a*ba。同理可證a*bb，綜合有a*ba∪b＝g。
綜上所述，假設不成立，得證a＝g或b＝g。
九、若無向圖g是不連通的，證明g的補圖是連通的（10分）。
證明設無向圖g是不連通的，其k個連通分支為、、…、。任取結點、∈g，若和不在圖g的同乙個連通分支中，則[，]不是圖g的邊，因而[，]是圖的邊；若和在圖g的同乙個連通分支中，不妨設其在連通分支（1≤≤）中，在不同於的另一連通分支上取一結點，則[，]和[，]都不是圖g的邊，，因而[，]和[，]都是的邊。綜上可知，不管那種情況，和都是可達的。
由和的任意性可知，是連通的。
一、 選擇題.(每小題2分，總計30
1. 給定語句如下：
（1）15是素數（質數）
離散數學試卷 答案
一 判斷下列命題對錯 每小題前標記 或 總20分 1.集合的交運算關於對稱差運算滿足分配律。2.對於集合a，aa a。3.集合的差運算滿足結合律。4.集合a上的關係都是自反的。5.若r,s都是a上的自反關係，則復合關係rs也是自反關係。6.若,都是a上的等價關係，則復合關係也是等價關係。7.合取正規...
08 09 2 離散數學A卷 答案
一 填空題 共30分，每小題3分 1.設p與q的真值為f,r與s的真值為t,則命題的真值是 t 2.公式 pq q的型別為矛盾式 3.設集合a 則a上的等價關係共有 5 個。4.若連通平面圖有12個結點，7個面，則它有 17 條邊。5.設s 其中的三個運算f1，f2，f3如圖1所示。則滿 換律的運算...
離散數學10A答案
暨南大學考試試卷 一 填空題 共 10 小題，每空 2 分，共 20 分 1.設是環,a,b 為環中任意元素,化簡 a b 2 2.避圈法是指 3.尤拉迴路是指 4.半哈密頓迴路是指 5.破圈法是指 6.極大平面圖的充分必要條件是 7.4 階布林代數有幾個原子 8.19.什麼是無零因子環 二 選擇題...