离散数学试题(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))∧R⇔T∧R(置换)⇔R2)∃x(A(x)→B(x))⇔∀xA(x)→∃xB(x)证明：∃x(A(x)→B(x))⇔∃x(⌝A(x)∨B(x))⇔∃x⌝A(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∨S2) ∀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的整数倍证明设1a，2a，…，1+m a为任取的m＋1个整数，用m去除它们所得余数只能是0，1，…，m－1，由抽屉原理可知，1a，2a，…，1+m a这m＋1个整数中至少存在两个数sa和t a，它们被m除所得余数相同，因此s a和t a的差是m的整数倍。

五、已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C) （15分）证明∵x∈ A-（B∪C）⇔ x∈ A∧x∉（B∪C）⇔ x∈ A∧（x∉B∧x∉C）⇔（x∈ A∧x∉B）∧（x∈ A∧x∉C）⇔ x∈（A-B）∧x∈（A-C）⇔ x∈（A-B）∩（A-C）∴A-（B∪C）=（A-B）∩（A-C）六、已知R、S是N上的关系，其定义如下：R={<x,y>| x,y∈N∧y=x2}，S={<x,y>| x,y∈N∧y=x+1}。

求R-1、R*S、S*R、R{1,2}、S[{1,2}]（10分）解：R-1={<y,x>| x,y∈N∧y=x2}，R*S={<x,y>| x,y∈N∧y=x2+1}，S*R={<x,y>| x,y∈N∧y=（x+1）2}，七、若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是双射。

因为<x,y>∈f-1g-1⇔存在z（<x,z>∈g-1∧<z,y>∈f-1）⇔存在z（<y,z>∈f∧<z,x>∈g）⇔<y,x>∈gf⇔<x,y>∈（gf）-1,所以（gf）-1=f-1g-1。

R{1,2}={<1,1>,<2,4>}，S[{1,2}]={1,4}。

八、（15分）设<A，*>是半群，对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，E>，且|V|＝m，|E|＝n。

试证：若n≥21-mC＋2，则G是哈密尔顿图证明若n≥21-mC＋2，则2n≥m2－3m＋6 （1）。

若存在两个不相邻结点u、v使得d(u)＋d(v)＜m，则有2n＝∑∈Vwwd)(＜m＋(m－2)(m－3)＋m＝m2－3m＋6，与（1）矛盾。

所以，对于G中任意两个不相邻结点u、v都有d(u)＋d(v)≥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)) 二、求命题公式(⌝P→Q)→(P∨⌝Q) 的主析取范式和主合取范式（10分）解：(⌝P→Q)→(P∨⌝Q)⇔⌝(⌝P→Q)∨(P∨⌝Q)⇔⌝(P∨Q)∨(P∨⌝Q)⇔(⌝P∧⌝Q)∨(P∨⌝Q) ⇔(⌝P∨P∨⌝Q)∧(⌝Q∨P∨⌝Q)⇔(P∨⌝Q)⇔M1⇔m0∨m2∨m3三、推理证明题（10分）1)(P→(Q→S))∧(⌝R∨P)∧Q⇒R→S证明：（1）R 附加前提(2)⌝R∨P P(3)PT(1)(2),I(4)P→(Q→S) P(5)Q→ST(3)(4),I(6)Q P(7)ST(5)(6),I(8)R→S CP 2) ∀x(P(x)∨Q(x))，∀x⌝P(x)⇒∃xQ(x)证明：(1)∀x⌝P(x) P(2)⌝P(c)T(1),US(3)∀x(P(x)∨Q(x)) P(4)P(c)∨Q(c) T(3),US(5)Q(c)T(2)(4),I(6)∃x Q(x) T(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∧（x∈B∨x∈C）⇔（ x∈ A∧x∈B）∨（x∈ A∧x∈C）⇔ x∈（A∩B）∨x∈ A∩C⇔ x∈（A∩B）∪（A∩C）∴A∩（B∪C）=（A∩B）∪（A∩C）六、π={A1，A2，…，A n}是集合A的一个划分，定义R={<a，b>|a、b∈A i，I=1，2，…，n}，则R是A上的等价关系（15分）。

证明：∀a∈A必有i使得a∈A i，由定义知aRa，故R自反。

∀a,b∈A，若aRb ，则a,b∈A i，即b,a∈A i，所以bRa，故R对称。

∀a,b,c∈A，若aRb 且bRc，则a,b∈A i及b,c∈A j。

因为i≠j时A i∩A j=Φ，故i=j，即a,b,c∈A i，所以aRc，故R传递。

总之R是A上的等价关系。

七、若f:A→B是双射，则f-1:B→A是双射（15分）。

证明:对任意的x∈A，因为f是从A到B的函数，故存在y∈B，使<x,y>∈f，<y,x>∈f-1。

所以,f-1是满射。

对任意的x∈A，若存在y1,y2∈B，使得<y1,x>∈f-1且<y2,x>∈f-1,则有<x,y1>∈f且<x,y2>∈f。

因为f是函数，则y1=y2。

所以，f-1是单射。

因此f-1是双射。

八、设<G，*>是群，<A，*>和<B，*>是<G，*>的子群，证明：若A∪B＝G，则A＝G或B＝G（10分）。

证明假设A≠G且B≠G，则存在a∈A，a∉B，且存在b∈B，b∉A（否则对任意的a∈A，a∈B，从而A⊆B，即A∪B＝B，得B＝G，矛盾。

）对于元素a*b∈G，若a*b∈A，因A是子群，a-1∈A，从而a-1* (a*b)＝b∈A，所以矛盾，故a*b∉A。

同理可证a*b∉B，综合有a*b∉A∪B＝G。

综上所述，假设不成立，得证A＝G或B＝G。

九、若无向图G是不连通的，证明G的补图G是连通的（10分）。

证明设无向图G是不连通的，其k个连通分支为G、2G、…、k G。

任取结点1u、v∈G，若u和v不在图G的同一个连通分支中，则[u，v]不是图G的边，因而[u，v]是图G的边；若u和v在图G的同一个连通分支中，不妨设其在连通分支G（1≤i≤k）中，在不同于i G的另一连通分支上取一结点w，则[u，w]和[w，iv]都不是图G的边，，因而[u，w]和[w，v]都是G的边。

综上可知，不管那种情况，u和v都是可达的。

由u和v的任意性可知，G是连通的。

一、选择题.(每小题2分，总计30)1.给定语句如下：（1）15是素数（质数）（2）10能被2整除，3是偶数。

（3）你下午有会吗？若无会，请到我这儿来！（4）2x+3>0.（5）只有4是偶数，3才能被2整除。

(6)明年5月1日是晴天。

以上6个语句中，是简单命题的为（A）,是复合命题的为（B）,是真命题的为（C）,是假命题的是（D）,真值待定的命题是（E）A: ①(1)(3)(4)(6) ②(1)(4)(6) ③(1)（6） B: ①(2)(4) ②(2)(4)(6) ③(2)(5)C: ①(1)(2)(5)(6) ②无真命题③（5） D: ①(1)(2) ②无假命题③(1)(2)(4)(5)E: ①(4)(6) ②（6）③无真值待定的命题2.将下列语句符号化：（1）4是偶数或是奇数。