离散数学期末试卷及部分答案

《离散数学期末试卷及部分答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散试卷及答案离散数学试题(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)®$

2、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分）第12页共12页离散试卷及答案1）C∨D,(C∨D)®ØE,ØE®(A∧ØB),(A∧ØB)®(R

3、∨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)

4、∧R(x))第12页共12页离散试卷及答案四、设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∧（xÏB∧xÏC）Û（xÎA∧xÏB）∧（xÎA∧xÏC）ÛxÎ（A-B）∧

5、xÎ（A-C）ÛxÎ（A-B）∩（A-C）∴A-（B∪C）=（A-B）∩（A-C）六、已知R、S是N上的关系，其定义如下：R={

6、x,yÎN∧y=x2}，S={

7、x,yÎN∧y=x+1}。求R-1、R*S、S*R、R{1,2}、S[{1,2}]（10分）解：R-1={

8、x,yÎN∧y=x2}，R*S={

9、x,yÎN∧y=x2+1}，S*R={

10、x,yÎN∧y=（x+1）2}，第12页共12页离散试卷及答案七、若f:A→B和g:B→C是双射，则（gf）-1=f-1g-1（10分）。证明

11、：因为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{1,2}={<1,1>,<2,4>}，S[{1,2}]={1,4}。八、（15分）设是半群，对A中任意元a和b，如a≠b必有a*b≠b*a，证明：(1)对A中每个元a，有a*a＝a。(2)对A中任意元a和b，

12、有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＝，且

13、V

14、＝m，

15、E

16、＝n。试证：若n≥

17、＋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