离散数学期末考试试题(有几套带答案)

离散试卷及答案第1页共21页离散数学试题(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离散试卷及答案第2页共21页(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ma为任取的m＋1个整数，用m去除它们所得余数只能是0，1，…，m－1，由抽屉原理可知，1a，2a，…，1ma这m＋1个整数中至少存在两个数sa和ta，它们被m除所得余数相同，因此sa和ta的差是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有逆函数离散试卷及答案第3页共21页（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离散试卷及答案第4页共21页证明左端((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∨PP(3)PT(1)(2),I(4)P(QS)P(5)QST(3)(4),I(6)QP(7)ST(5)(6),I(8)RSCP2)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)xQ(x)T(5),EG离散试卷及答案第5页共21页四、例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，…，An}是集合A的一个划分，定义R={a，b|a、b∈Ai，I=1，2，…，n}，则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，使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分）。离散试卷及答案第6页共21页证明假设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个连通分支为1G、2G、…、kG。任取结点u、v∈G，若u和v不在图G的同一个连通分支中，则[u，v]不是图G的边，因而[u，v]是图G的边；若u和v在图G的同一个连通分支中，不妨设其在连通分支iG（1≤i≤k）中，在不同于iG的另一连通分支上取一结点w，则[u，w]和[w，v]都不是图G的边，，因而[u，w]和[w，v]都是G的边。综上可知，不管那种情况，u和v都是可达的。由u和v的任意性可知，G是连通的。一、选择题.(每小题2分，总计30)1.给定语句如下：（1）15是素数（质数）（2）10能被2整除，3是偶数。（3）你下午有会吗？若无会，请到我这儿来！（4）2x+30.（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)离散试卷及答案第7页共21页C:①(1)(2)(5)(6)②无真命题③（5）D:①(1)(2)②无假命题③(1)(2)(4)(5)E:①(4)(6)②（6）③无真值待定的命题2.将下列语句符号化：（1）4是偶数或是奇数。（A）设p：4是偶数，q：4是奇数（2）只有王荣努力学习，她才能取得好成绩。（B）设p：王荣努力学习，q：王荣取得好成绩（3）每列火车都比某些汽车快。（C）设F(x):x是火车，G(y):y是汽车，H(x,y):x比y快。A:①p∨q②p∧q③p→qB:①p→q②q→p③p∧qC:①xy((F(x)∧G(y))→(H(x,y))②x(F(x)→y(G(y)∧H(x,y)))③x(F(x)∧y(G(y)∧H(x,y)))3.设S={1,2,3},下图给出了S上的5个关系,则它们只具有以下性质:R1是（A）,R2是(B),R3是(C)。ABC:①自反的，对称的，传递的②反自反的，对称的③自反的④
反对称的⑤对称的⑥自反的，对称的，反对称的，传递的4.设S={Ф，{1}，{1，2}}，则有（1）（A）S（2）(B)S（3）P(S)有（C）个元数。（4）（D）既是S的元素，又是S的子集离散试卷及答案第8页共21页A:①{1,2}②1B:③{{1,2}}④{1}C:⑤3⑥6⑦7⑧8D:⑨{1}⑩Ф二、证明（本大题共2小题，第1小题10分，第2小题10分，总计20分）1、用等值演算算法证明等值式(p∧q)∨(p∧q)p2、构造下面命题推理的证明如果今天是星期三，那么我有一次英语或数学测验；如果数学老师有事，那么没有数学测验；今天是星期三且数学老师有事，所以我有一次英语测验。三、计算（本大题共4小题，第1小题5分，第2小题10分，第3小题15分，总计30分）1、设212,，，个体域为为，整除为xxQyxy