离散数学期末考试试题

《离散数学期末考试试题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、离散数学试题(A卷及荇案)一、证明题(10分)1)(-,PA(iQAR))V(QAR)V(PAR)<=>Ri鵬MS»(-m-OAR)V((QW)AR)»((-J5A-«)AR))V((QW)AR)«(，(!)VQ)AK)V((QVP)AK)«(，(PVQ)V(QVP))AR»WPVQ)V(PVQ))AR«TAR(鵬2)3x(A(x)^B(x))«VxA(x)^3xB(x)月：彐x(A(x)—>B(x))<=>3x(VB(x))<=>3x-iA(x)V彐xB(x)<=^-iVxA(x)V3xB(x)<=>Vx

2、A(x)—>3xB(x)二、求命题公式卬7(0八10)->(?八0八10的主析取范式和主合取范式(10分)证明:(PV(QAR))^(PAQAR)<=>^(PV(QAR))V(PAQAR))<=>(-iPA(-.QViR))V(PAQAR)<=>(-iPAiQ)V(-,PA-,R))V(PAQAR)^(iPAiQAR)V(-.PA1QA1R)V(-.PAQA-.R))V(-.PA1QA1R))V(PAQAR)«mOVmlVm2Vm7<=>M3VM4VM5VM6三、推理证明题(10分)1)CVD，(CVD)^

3、-,E,-,E->(AA-.B),(AA证明(1)3xP(x)-nB)^(RVS)=>RVS(2)P(a)证明：(1)(CVD)^E(3)Vx(P(x)(y)AR(x))(2)^E^(AA^B)(4)P(a)-^Q(y)八R(a)(3)(CVD)^(AA-,B)(5)Q(y)AR(a)(4)(AA^B)^(RVS)(6)Q(y)(5)(CVD)^(RVS)(7)R(a)⑹CVD(8)P(a)(7)KVS(9)P(a)AR(a)2)Vx(P(x)->Q(y)AR(x)),3xP(x)=>Q(y)A(10)3x

4、(P(x)AR(x))3x(P(x)AR(x))(ll)Q(y)A3x(P(x)AR(x))四、设m是一个取定的正整数，证明：在任取/H-1个整数中，至少有两个整数，它们的差是m的整数倍证明设仏，％，•••，1„+1为任取的//7+1个整数，用仍去除它们所得余数只能是0,1,…，似一1,由抽屉原理可知，A,6Z,,,+1这〃/+1个整数中至少存在两个数人和仏，它们被/〃除所得余数相同，因此人和％的差是/〃的整数倍。五、己知A、B、C是三个集合，证明A-(BUC)=(A-B)n(A-C)(15分)证明VxeA

5、-(BUC)<=>xeAAx^(BUC)<=>xeAA(x^BAx^C)<=>(xeAAx芒B)A(xeAAx^C)»xg(A-B)Axg(A-C)»xe(A-B)n(A-C)...A-(BUC)=(A-B)n(A-C)六、己知R、S是N上的关系，其定义如下：R={

6、x,yeNAy=x2},S={〈x,y〉

7、x,yeNAy=x+l}。求R-1、R*S、S*R、rT{1,2},S[{1,2}](10分)解：R_1={

8、x,veNAy=x2},R*S={〈x,y〉

9、x,yeNAy=x2+l}

10、,S*R={

11、x,yeNAy=(x+1)2},七、若f:A—B和g:B—C是双射，贝lj(gf)(10分)。证明：因为f、g是双射，所以gf:A—C是双射，所以gf有逆函数(gf)C—A。同理可推f、1:C-^是双射。因为〈x,y〉Gf_1g_1«存在z(^fA^g)«〈x，y〉e(gf)i，所以(gf)Lfg1。RHl,2}二{〈1，1〉，〈2,4〉},S[{1，2}]={1，4}。八、(15分)设〈儿*〉

12、是半群，对J中任意元a和么如必有a*Z^Z^a，证明：(1)对J中每个元a，有a^a=ac⑵对J中任意元a和么有a*Z?*a=a。(3)对J中任意元a、Z?和c,有证明由题意W知，若讲b=l件a，则必有(1)由(<9*5)*(3)由(讲奴(?)==z7*(/^c)=(c7*Z?)*6>=(a*Z?)*(c*a*c)=(讲*(a*c),所以有a^b^c=a^co九、给定简单无向图C=〈K及，且IF):

13、/??，

14、^

15、=/7o试证：若ch+2,则《是哈密尔顿图证明若则3仍+6(1)。若存在两个不相邻结点W、V使得d(w)+d(V)<777,则有2/7=<777+(777—2)(777—3)+777=Zff—3/77+ueV6,与(1)矛盾。所以，对于(中任意两个不相邻结点《、v都有d(w)+d(v)>/〃，所以(是哈密尔顿图。离散数学试题(B卷及答案)一、证明题(10分)1)((PVQ)A-,(iPA(1QV-1