电子科技大学英才学院2012-2013学年第1学期期末考试A卷离散数学课程考试题A卷（120分钟）考试形式：闭卷考试日期2013年月日课程成绩构成：平时分，期中分，实验分，期末100分一二三四五六七八九十合计I.MultipleChoice(15%,1.5pointseach)（A）1.(p∧q)→(p∨q)islogicallyequivalenttoa)Tb)p∨qc)Fd)p∧q（A）2.IfP(A)isthepowersetofA,andA=Æ,whatis|P(P(P(A)))|?a)4b)24c)28d)216（C）3.WhichofthesestatementsisNOTaproposition?a)TodayisMonday.`b)1+1=2.c)AmIright?d)Goandplaywithme.（C）4.Whichofthesepropositionsisnotlogicallyequivalenttotheotherthree?a)(p®q)(r®q)b)(pÚr)®qc)(pr)®qd)Thecontrapositiveof¬q®(¬p^¬r)（B）5.SupposeA3andB8.Thenumberof1-1functionsfA®Bisa)24b)P(83).c)38d)83（B）6.LetRbearelationonthepositiveintegerswherexRyifxisafactorofy.WhichofthefollowinglistsofpropertiesbestdescribestherelationR?a)symmetric,transitiveb)antisymmetric,transitive,reflexivec)antisymmetric,symmetric,reflexived)symmetric,transitive,reflexive（C）7.Whichofthefollowingarepartitionsof?a).b)c).d)（C）8.Thefunctionf(x)=x2log(x3+78)isbig-Oofwhichofthefollowingfunctions?a)x2b)x(logx)3c)x2logxd)xlogx（A）9.If,thenRis:a)reflexiveb)symmetricc)antisymmetricd)transitive.（B）10.WhichofthefollowingsisafunctionfromZtoR?a).`b).c)d)II.TrueorFalse(10%,1pointeach)（T）1.If10,then56.（F）2.(p∧q)∨r≡p∧(q∨r)（F）3.IfA,B,andCaresets,then(A-C)-(B-C)=A-B.（T）4.SupposeAabc,thenaP(A).（F）5.isdefinedasafunctionwithdomainRandcodomainR.（T）6.SupposegA®BandfB®C,wherefgis1-1andfis1-1.gmustbe1-1?（T）7.Ifpandqareprimes(2),thenpqiscomposite.（F）8.IftherelationRisdefinedonthesetZwhereaRbmeansthatab0,thenRisanequivalencerelationonZ.（T）9.(AB)(AC)=A(BC).（T）10.ThesetÆaÆaÆisthepowersetofsomesetIII.FillintheBlanks(20%,2pointseach)1.Letpandqbethepropositions“Iamacriminal”and“Irobbanks”.ExpressinsimpleEnglishtheproposition“ifpthenq”:IfIamacriminalthemIrobbanks.2.P(xy)means“x2yxy”,wherexandyareintegers.ThetruthvalueofxyP(xy)isFalse.3.Thenegationofthestatement“Notestsareeasy.”issometestsareeasy.4.Ifthenis.5.SupposeAxy.Thenis{Æ,{x},{y},{x,y}}.6.SupposegA®AandfA®AwhereA1234,g(14)(21)(31)(42)andf(13)(22)(34)(42).Thenfg=(12)(23)(33)(42).7.Thesumof2481632210is2112.8.Theexpressionofgcd(45,12)asalinearcombinationof12and45is12445(1).9.Thereare5!permutationsofthesevenlettersA,B,C,D,E,FhaveAimmediatelytotheleftofE.10.Thetwo'scomplementof13is10011.IV.AnswertheQuestions(32%,4pointseach)：1.Determinewhetherthefollowingargumentisvalid:p®rq®rqÚr________pAns:Notvalid:ptrue,qtrue,rtrue2.Supposeyouwishtoproveatheoremoftheform“ifpthenq”.(a)Ifyougiveadirectproof,whatdoyouassumeandwhatdoyouprove?(b)Ifyougiveanindirectproof,whatdoyouassumeandwhatdoyouprove?(c)Ifyougiveaproofbycontradiction,whatdoyouassumeandwhatdoyouprove?Ans:(a)Assumep,proveq.(b)Assumeq,provep.(c)Assumepq,showthatthisleadstoacontradiction.3.Provethatbygivingaproofusinglogicalequivalence.Ans:4.SupposefR®Rwheref(x)x2.(a)IfSx1x6,findf(S).(b)IfT345,findf1(T).Ans:(a)0123(b)[612).5.Usethedefinitionofbig-ohtopr...