复旦大学 赵一鸣 离散数学 一

DiscretemathematicsDiscretei.e.nocontinuousSettheory,Combinatorics,Graphs,ModernAlgebra(Abstractalgebra,Algebraicstructures),Logic,classicprobability,numbertheory,AutomataandFormalLanguages,Computabilityanddecidabilityetc.,Beforethe18thcentury,Discrete，quantityandspaceastronomy,physicsExample:planetaryorbital,NewtonsLawsinThreeDimensionscontinuousmathematics:calculus,EquationsofMathematicalPhysics,FunctionsofRealVariable,FunctionsofcomplexVariableDiscrete?stagnancy,inthethirtiesofthetwentiethcentury,TuringMachinesFiniteDiscreteDataStructuresandAlgorithmDesignDatabaseCompilersDesignandAnalysisofAlgorithmsComputerNetworksSoftwareinformationsecurityandcryptographythetheoryofcomputationNewgenerationcomputers,Settheory,IntroductoryCombinatorics,Graphs,Algebtaicstructures,Logic.Thisterm:Settheory,IntroductoryCombinatorics,Graphs,Algebtaicstructures(Group,Ring，Field).Nextterm:Algebtaicstructures(LatticesandBooleanAlgebras),Logic,每周一交作业，作业成绩占总成绩的10%；平时不定期的进行小测验，占总成绩的20%；期中考试成绩占总成绩的20%；期终考试成绩占总成绩的50%,1.离散数学及其应用（英文版第5版）作者：KennethH.Rosen著出版社：机械工业出版社2.组合数学（英文版第4版）经典原版书库作者：（美）布鲁迪（Brualdi,R.A.）著出版社：机械工业出版社3,离散数学暨组合数学（英文影印版）DiscreteMathematicswithCombinatoricsJamesA.Anderson,UniversityofSouthCarolina,Spartanburg大学计算机教育国外著名教材系列（影印版）清华大学出版社,IntroductiontoSetTheory,TheobjectsofstudyofSetTheoryaresets.Assetsarefundamentalobjectsthatcanbeusedtodefineallotherconceptsinmathematics.GeorgCantor(1845-1918)isaGermanmathematician.Cantors1874paper,OnaCharacteristicPropertyofAllRealAlgebraicNumbers,marksthebirthofsettheory.paradox,twentiethcenturyaxiomaticsettheorynaivesettheoryConceptRelation,function,cardinalnumberparadox,Chapter1BasicConceptsofSets,1.1SetsandSubsetsWhatareSets?AcollectionofdifferentobjectsiscalledasetS,ATheindividualobjectsinthiscollectionarecalledtheelementsofthesetWewrite“tA”tosaythattisanelementofA,andWewrite“tA”tosaythattisnotanelementofA,Example:Thesetofallintegers,Z.Then3Z,-8Z,6.5ZThesesets,eachdenotedusingaboldfaceletter,playanimportantroleindiscretemathematics:N=0,1,2,thesetofnaturalnumberI=Z=,-2,-1,0,1,2,thesetofintegersI+=Z+=1,2,thesetofpositiveintegersI-=Z-=-1,-2,thesetofnegativeintegersQ=p/q|pZ,qZ,q0,thesetofrationalnumbersQ+,thesetofpositiverationalnumbersQ-,thesetofnegativerationalnumbers,1.Representationofset(1)Listingelements,Onewayistolistalltheelementsofasetwhenthisispossible.Example：ThesetAofoddpositiveintegerslessthan10canbeexpressedbyA=1,3,5,7,9。B=x1,x2,x3,(2)Setbuildernotion:Wecharacterizethepropertyorpropertiesthattheelementsofthesethaveincommon.Example:ThesetAofoddpositiveintegerslessthan10canbeexpressedbyA=x|xisanoddpositiveintegerlessthan10Example:C=x|x=y3,yZ+Cdescribesthesetofallcubesofpositiveintegers.D=x|-1x2,(3)RecursivedefinitionRecursivedefinitionsofsetshavethreesteps:1)Basicstep:Specifysomeofthebasicelementsintheset.2)recursivestep:Givesomerulesforhowtoconstructmoreelementsinthesetfromtheelementsthatweknowarealreadythere.3)closedstep:Therearenootherelementsinthesetexceptthoseconstructedusingsteps1and2.,Example:ThesetofevennonnegativeintegersE=x|x0,andx=2y,whereyZ(1)Basicstep:0E+。(2)Recursivestep:IfnE+,thenn+2E+.(3)Closedstep:TherearenootherelementsinthesetEexceptthoseconstructedusingsteps(1)and(2).Example：(1)Basicstep:3S。(2)Recursivestep:IfxandyS,thenx+yS。(3)Closedstep:TherearenootherelementsinthesetSexceptthoseconstructedusingsteps(1)and(2).S=?S=y|y=3x,xZ+,Letai,sequencesoftheforma1a2anareoftenincomputerscience.Thesefinitesequencesarealsocalledstrings.ThelengthofthestringSisthenumberoftermsinthisstring.Theemptystring,denotedby,isthestringthathasnoterms.Theemptystringhaslengthzero.Ifx=a1a2an,andy=b1b2bmarestrings,whereai,bj(1in,1jm),wedefinethecatenationofxandyasthestringa1a2anb1b2bm.Thecatenationofxandyiswrittenasxy,andisanotherstringfrom,i.e.xy=a1a2anb1b2bm.Notex=xandx=x.,Letbeanalphabet,wecanconstructtheset+consistingofallfinitenonemptystringofelementsof:(1)Basicstep:Ifa,thena+.(2)Recursivestep:Ifaandx+,thenax+.(3)Closedstep:Therearenootherelementsintheset+exceptthoseconstructedusingsteps(1)and(2).+elementorstring:infiniteLengthofstring:finite,1,2,3,Letbeanalphabet,wecanconstructtheset*consistingofallfinitestringofelementsof:(1)Basicstep:*.(2)Recursivestep:Ifx*andathenxa*.(3)Closedstep:Therearenootherelementsintheset*exceptthoseconstructedusingsteps(1)and(2).,Arithmeticexpressions(B)Anumeralisanarithmeticexpression.(R)Ife1ande2arearithmeticexpressions,thenallofthefollowingarearithmeticexpressions:e1+e2,e1e2,e1*e2,e1/e2,(e1)(C)Therearenootherarithmeticexpressionsexceptthoseconstructedusingsteps(1)and(2).,A=1,3,5,7,9,B=x1,x2,x3,finiteelements,53C=x|x=y3,yZ+,infiniteelementsAsetSiscalledfinitesetifithasndistinctelements,wherenN.Inthiscase,niscalledthecardinalityofSandisdenotedby|S|.Asetthatisnotfiniteiscalledinfiniteset.*,+,C,D,Sareinfinitesets,A,Barefinitesets.P=x|xisanprimenumberlessthan6,2,3,5,|P|=3,Example:A=x|x2+1=0,andxisanrealnumber,Noelementemptyset,|A|=0.Thesetthathasnoelementsinitisdenotedbyorthesymbolandiscalledtheemptyset.Note:isnotanemptyset.Itisasetwithoneelementwhichtheelementistheemptyset.,but.universalsetTheuniversalsetisthesetofallelementsunderconsiderationinagivendiscussion.WedenotetheuniversalsetbyU.,(1)Theorderinwhichtheelementsofasetarelistedisnotimportant.a,b,c,a,c,b,b,a,c,b,c,a,c,a,b,andc,b,aareallrepresentationsofthesameset.(2)Inthelistingoftheelementsofaset,repeatedelementsarentallowed.(3)AsetcanbeanelementofanothersetExample:S=a,b,a,b,c,d,eNote:a,b,cisalsoasetconsistingofelementsa,b,c。a,b,andcarentelementsofS.,Example：LetS=,。ElementsofSareand,2.SubsetsDefinition1.1:LetAandBaretwosets.IfeveryelementofAisalsoanelementofB,thatis,ifwheneverxAthenxB,wesaythatAisasubsetofBorthatAiscontainedinB,andwewriteAB。IfthereisanelementofAthatisnotinB,thenAisnotasubsetofB,andwewriteAB.,VennDiagramsInVenndiagramstheuniversalsetUisrepresentedbyarectangle,whilesetswithinUarerepresentedbycircles.,AB,AB,BA,Example:A=x|-1x2.0.5A,but0.5isnotaninteger,soA=x|-1x2Z,ZQ,(1)ForanysetA,A.(2)IfAB,andBC,thenAC,Definition1.2:LetAandBbesets.WesaythatAequalsB,writtenA=B,wheneverforanyx,xAifonlyifxB.IfAandBarenotequal,wewriteAB.ItiseasytoseethatA=BifonlyifABandBADefinition1.3:IfABandAB,wewriteABandsaythatAisapropersubsetofB.,Example:aa,b。Example:S1=a,S2=a,S3=a,aaS3,S1S3aS3,S2S3,S1S3,S1S2,Theorem1.1:ForanysetA,(1)A,(2)AAA=1,2,3,1,2,3,1,2,1,3,2,3and1,2,3aresubsetsofApowersetofADefinition1.4:GivenasetA,thepowersetofAisthesetofallsubsetsofthesetA.ThepowersetofAisdenotedbyP(A).|A|=k，|P(A)|=?Theorem1.2:IfAisafiniteset,then|P(A)|=2|A|.,1.2OperationsonSets,1.DefinitionofoperationsonsetsDefinition1.5：LetAandBbetwosubsetsofuniversalsetU,(1)TheunionofAandB,writeAB,isthesetofallelementsthatareinAorB.i.e.AB=x|xAorxB,(2)TheintersectionofAandB,writeAB,isthesetofallelementsthatareinbothAandB.i.e.AB=x|xAandxB。,(3)ThedifferenceofAandB,writeA-B,isthesetofallelementsthatareinAbutarenotinB.i.e.A-B=x|xAandxB。,Example:A=1,2,3,4,5,B=1,2,4,6,C=7,8,U=1