浙江大学2018-2019学年秋冬学期
《离散数学》课程期末考试试卷
课程号：21120401
开课学院：计算机学院
入场
考试试卷：????A卷??B卷
考试形式：????闭卷??开卷，允许带
考试日期:2019年1月24日，考试时间:120分钟
诚信考试,沉着应考,杜绝违纪
考生姓名
题序得分评卷人
ZhejiangUniversity
DiscreteMathematics,Fall-Winter2018
FinalExam
1.(20pts)Determinewhetherthefollowingstatementsaretrueorfalse.If
√
itistrue?llaotherwisea×inthebracketbeforethestatement.
(a)(
)TherearetwosetsAandB,suchthatbothA?BandA∈B.
(b)()LetA,Bbetwosets.If2A?2B,thenA?B,where2Xisthepowerset
ofX.(c)()Letφbeapropositionwiththreevariablesp,q,andr,ifexactlyoneof
theassignments000,011,100,and111makeφtrue,thenφcanbeconvertedinfulldisjunctivenormalformΣ(1,2,5,6).(d)()LetP={f|fisapropositionalformulawithvariablesp,q,r}andRbe
theequivalentrelationonPbyφRψi?φ?ψ,forφ,ψ∈P,thenthenumberofequivalenceclassesofPonRis256.(e)()LetP(x),Q(x)betwopredicates,then?xP(x)→?yQ(y)??x?y(P(x)→
Q(y)).(f)()ThereisabinaryrelationRonsetAsuchthatRisbothanequivalence
relationandpartialorderonA.(g)((h)((i)((j)(
)Suppose(A,?)isa?nitenonemptyposet.ThenAhasaminimalelement.)ThereisnoknownalgorithmtodecideifagraphhasaHamiltoncircuit.)Everyconnectedbipartitegraphcontainsacircuitofevenlength.)Abinarytreewithheighthhasatmost2hleaves.
1
2
学号3
4
5
所属院系6
7
8
总分
DiscreteMathematicsFinalExam(Page2of4)Jan.24,2019
2.(12pts)Constructalogicalargumentusingrulesofinferencetoshowthatthefollowingsentencesimplytheconclusion:Itrained.
Ifitdoesnotrainorifitisnotfoggy,thenthesailingracewillbeheldandthelife-savingdemonstrationwillgoon.Ifthesailingraceisheld,thenthetrophywillbeawarded.Thetrophywasnotawarded.Justifyeachstepbyindicatingtheruleyouapplied.
3.(12%)Provethatthetwosetsofrealnumbers(0,1)and[a,b)={x∈R|a≤x 4.(10pts)LetS?{1,2,3,4,5,6,···,98,99,100}where|S|=62.Provethatthereexistx,y∈Ssuchthatx?y=23. DiscreteMathematicsFinalExam(Page3of4)Jan.24,2019 5.(12pts)De?neabinaryrelationRonR×Rby(x,y)R(a,b)ifandonlyify?b=5(x?a). (a)ShowthatRisanequivalencerelationonR×R.(b)Findtheequivalenceclassesof(0,0)and(1,?2). (c)Describethegeometricmeaningtheequivalenceclass[(a,b)]. 6.(12pts)LetG=(V,E)beasimplegraphwithnvertices,wheren≥3,andd(u)+d(v)≥n,foreveryu,v∈V.Prove (a)Gisconnected.(b)GisaHamiltongraph.
浙江大学2018-2019学年秋冬学期《离散数学》课程期末考试试卷
