離散數(shù)學英文試卷及答案

一、單項選擇題（總共10題，每題2分）1.Whichofthefollowingisavalidproposition?A)x+5=10B)2+2=4C)3<2D)AlloftheaboveAnswer:B2.Inpropositionallogic,whichofthefollowingisthenegationof"PandQ"?A)PorQB)PandnotQC)notPandnotQD)notPornotQAnswer:D3.Whatisthecomplementoftheset{1,2,3}withintheset{0,1,2,3,4}?A){0,4}B){0,1,2,3,4}C){0}D){}Answer:A4.Whichofthefollowingisatautology?A)PornotPB)PandnotPC)PimpliesQD)QimpliesPAnswer:A5.Inhowmanywayscanacommitteeof3bechosenfromagroupof5people?A)5B)10C)15D)20Answer:B6.Whatisthecardinalityofthepowersetofasetwith4elements?A)4B)8C)16D)32Answer:C7.Whichofthefollowingisavalidinductivestepinaproofbymathematicalinduction?A)AssumeP(k)istrueforallk.B)AssumeP(k)istrueforsomek.C)AssumeP(k)istrue,andshowP(k+1)istrue.D)AssumeP(k+1)istrue,andshowP(k)istrue.Answer:C8.Whatisthesumofthefirst100naturalnumbers?A)4950B)5050C)9900D)10000Answer:B9.Whichofthefollowingisagraph?A)Asetofverticeswithnoedges.B)Asetofedgeswithnovertices.C)Asetofverticesandedgeswithaspecificrelationship.D)Asetofverticesandedgeswithoutanyspecificrelationship.Answer:C10.Whatisthechromaticnumberofacompletegraphwith4vertices?A)1B)2C)3D)4Answer:D二、多項選擇題（總共10題，每題2分）1.Whichofthefollowingarepropositions?A)2+2=4B)xisgreaterthan5C)ThemoonismadeofcheeseD)33=9Answer:A,D2.Whatarethebasiclogicalconnectives?A)NegationB)ConjunctionC)DisjunctionD)ImplicationAnswer:A,B,C,D3.Whichofthefollowingaresubsetsoftheset{1,2,3,4}?A){1,2}B){3,4}C){1,3,4}D){0}Answer:A,B,C4.Whatarethepropertiesofagroup?A)ClosureB)AssociativityC)IdentityelementD)InverseelementAnswer:A,B,C,D5.Howmanyedgesdoesacompletegraphwithnverticeshave?A)nB)n(n-1)/2C)n(n+1)/2D)2nAnswer:B6.Whatarethetypesofrelations?A)ReflexiveB)SymmetricC)TransitiveD)Anti-symmetricAnswer:A,B,C,D7.Whatisthepurposeofaproofbymathematicalinduction?A)Toproveastatementistrueforallnaturalnumbers.B)Toproveastatementistrueforaspecificnumber.C)Toproveastatementisfalseforallnaturalnumbers.D)Toproveastatementisfalseforaspecificnumber.Answer:A8.Whatisthedifferencebetweenadirectedgraphandanundirectedgraph?A)Directedgraphshaveedgeswithdirections,whileundirectedgraphsdonot.B)Directedgraphshavevertices,whileundirectedgraphsdonot.C)Directedgraphsdonothaveedges,whileundirectedgraphsdo.D)Directedgraphsdonothavevertices,whileundirectedgraphsdo.Answer:A9.Whatarethepropertiesofafunction?A)Eachinputhasexactlyoneoutput.B)Eachoutputhasexactlyoneinput.C)Thedomainandcodomainarewell-defined.D)Therangeisasubsetofthecodomain.Answer:A,C,D10.Whatisatree?A)Aconnectedacyclicgraph.B)Adisconnectedacyclicgraph.C)Aconnectedgraphwithcycles.D)Adisconnectedgraphwithcycles.Answer:A三、判斷題（總共10題，每題2分）1.Thestatement"2+2=4"isaproposition.Answer:True2.ThecomplementofasetAisdenotedbyA'.Answer:True3.Theunionoftwodisjointsetsisempty.Answer:True4.Atautologyisalwaysfalse.Answer:False5.ThenumberofwaystochoosekelementsfromasetofnelementsisdenotedbyP(n,k).Answer:False6.ThepowersetofasetAhas2^|A|elements.Answer:True7.Mathematicalinductioncanbeusedtoprovestatementsaboutintegers.Answer:True8.Acompletegraphwithnverticeshasnedges.Answer:False9.Arelationisreflexiveifeveryelementisrelatedtoitself.Answer:True10.Atreeisatypeofgraphthatcannothavecycles.Answer:True四、簡答題（總共4題，每題5分）1.Explaintheconceptofapropositioninpropositionallogic.Answer:Apropositionisastatementthatcanbeeithertrueorfalse.Itisthebasicbuildingblockofpropositionallogicandcanbecombinedusinglogicalconnectivestoformmorecomplexstatements.2.Describethedifferencebetweenaunionandanintersectionoftwosets.Answer:TheunionoftwosetsAandB,denotedbyA∪B,isthesetofallelementsthatareinA,inB,orinboth.TheintersectionoftwosetsAandB,denotedbyA∩B,isthesetofallelementsthatareinbothAandB.3.Whatisadirectedgraph,andhowdoesitdifferfromanundirectedgraph?Answer:Adirectedgraphisagraphinwhicheachedgehasadirection,indicatingaone-wayrelationshipbetweenthevertices.Incontrast,anundirectedgraphisagraphinwhicheachedgehasnodirection,indicatingatwo-wayrelationshipbetweenthevertices.4.Explaintheprincipleofmathematicalinduction.Answer:Mathematicalinductionisaprooftechniqueusedtoprovestatementsaboutnaturalnumbers.Itconsistsoftwosteps:thebasecase,wherethestatementisprovenfortheinitialvalue(usuallyn=0orn=1),andtheinductivestep,whereitisshownthatifthestatementistrueforsomearbitrarynaturalnumberk,thenitisalsotruefork+1.五、討論題（總共4題，每題5分）1.Discusstheimportanceofpropositionsinpropositionallogic.Answer:Propositionsarethefundamentalbuildingblocksofpropositionallogic,allowingustoconstructandreasonaboutcomplexstatements.Theyprovideaclearandconcisewaytoexpressideasandmakelogicaldeductions,formingthebasisforvariousapplicationsincomputerscience,mathematics,andotherfields.2.Explainthesignificanceofsetoperationsindiscretemathematics.Answer:Setoperationssuchasunion,intersection,andcomplementareessentialtoolsindiscretemathematics.Theyallowustoanalyzeandmanipulatesets,solveproblemsinvolvingcollectionsofelements,andestablishrelationshipsbetweensets.Setoperationsarewidelyusedinvariousareasofcomputerscience,suchasdatabasemanagement,datastructures,andalgorithms.3.Discusstheroleofgraphsinmodelingreal-worldproblems.Answer:Graphsarepowerfultoolsformodelingreal-worldproblems,astheycanrepresentrelationshipsbetweenobjectsandentities.Theyareusedinvariousfields,includingcomputerscience,socialnetworkanalysis,transporta