计算理论导论(英文版)数学基础

1,Chapter0:Introduction,mathematicalnotation,prooftechniques,2,0.2.1StandardSetTheoryreview,Asetisanunorderedcollectionofobjects.Elements(members)DonotdistinguishrepetitionsoftheelementsMultiset-Dodistinguishrepetitionsoftheelements7,7and7Singleton-mayhaveonlyoneelementTheemptysetwithnoelementatall:NonemptyNaturalnumbersN(0inclusive)IntegersZ,3,written,ListingRefertoothersetsandproperties,4,5,6,Setoperations,Union:ABIntersection:ABComplement:ADifference:A-BDisjointSets:AB=Null,7,LawsandProperties,CommutativelawAssociativelawDistributivelawAbsorptionlawDemoganslawIdempotentlaw,8,SuperSet,Acollectionofanysets,9,10,Coverage,Differencebetweencoverageandpartition,11,0.2.2sequencesandtuples,HowtoexpressrelationsbetweenobjectsThelanguageofsetsFortheobjectsbelongtotherelationNotheobjectsnotdistinguished,12,OrderedPairs,13,Cartesianproduct,14,Binaryrelation,15,Orderedtuple,Ordered2-tupleorderedpairsOrdered3-tupleorderedtriplesOrdered4-tuplequadruplesOrdered5-tuplequintuplesOrdered6-tuplesextuplesSequenceisanorderedn-tupleforsomeunspecifiedn,wherenisthelengthofthesequence.N-foldCartesianproduct,16,N-aryrelation,1-aryrelationunaryrelations2-aryrelationbinaryrelations3-aryrelationternaryrelations,17,18,5composition,QR=(a,b):forsomec,(a,c)Qand(c,b)R,Compositionoff:ABandg:BCisafunctionhfromAtoCsuchthath(a)=g(f(a).,19,6specialtypesofbinaryrelations,directedgraphNodeEdgesNotes:donotallow“parallelarrows”.Adjacentmatrix,20,Propertiesofrelations,ReflexiveSymmetricAsymmetricAnti-symmetricTransitive,21,Reflexive,ArelationRAAisreflexiveif(a,a)RforeachaA.Thedirectedgraphrepresentingareflexiverelationhasaloopfromeachnodetoitself.Whatisthecharacteristicsofitsmatrix?Alloftheelementsonthediagonallineofitsmatrixare1.,22,Symmetric,ArelationRAAissymmetricif(b,a)Rwhenever(a,b)R.Inthedirectedgraphrepresentingasymmetricrelation,wheneverthereisanarrowbetweentwonodes,therearearrowsbetweenthosenodesinbothdirections.Characteristicsofmatrix?,Example:(a,b):aandbarepersonswiththesamefather,23,undirectedgraph,Asymmetricrelationwithoutpairsoftheform(a,a)isrepresentedasanundirectedgraph,orsimpleagraph.,24,Asymmetric(非对称性）,ArelationRAAisasymmetricif：(a,bA(a,b)R(b,a)R),25,Antisymmetric(反对称性),ArelationRAAisanti-symmetric:a,bAab(a,b)R(b,a)R,Example1:LetPbethesetofallpersons,(a,b):a,bPandaisthefatherofb,26,Transitive,ArelationRAAistransitiveifwhenever(a,b)Rand(b,c)R,then(a,c)R.Intermsofthedirectedgraphrepresentation,transitivityisequivalenttotherequirementthatwheneverthereisasequenceofarrowsleadingfromanelementatoanelementz,thereisanarrowdirectlyfromatoz.,27,Equivalencerelation,ReflexiveSymmetricTransitive,28,EachelementofthepartitionisanequivalenceclassofA.,29,Exampleatable(relation)abouttoybrickssetU=x1,x2,x3,x4,x5,x6,x7,x8,30,ApathinabinaryrelationRisasequence(a1,.,an)forsomen1suchthat(ai,ai+1)Rfori=1,n-1;thispathissaidtobefroma1toan.Thelengthofapath(a1,.,an)isn.Thepath(a1,.,an)isacycleiftheaisarealldistinctandalso(an,a1)R.,31,32,Closuresofrelation,33,34,35,0.2.3function,1DefinitionAfunctionfromasetAtoasetBisabinaryrelationRonAandBwiththefollowingspecialproperty:foreachaA,thereisexactlyoneorderedpairinRwithfirstcomponenta.,R1=(x,y):xC,yS,andxisacityinstateyR2=(x,y):xS,yC,andyisacityinstatex,36,2expression,f:ABf(a)=b,Argumentvalue,f(a)imageofaunderf,Domain,37,3Certainkindsoffunctions,One-to-one一对一Onto满射Bijection双射,38,4InverseofabinaryrelationR-1,NoteTheinverseofafunctionneednotbeafunction.Iffisabijection,f-1isafunction.f-1(f(a)=a,foreachaA;f(f-1(b)=b,foreachbB;,39,FiniteandInfiniteSets,SizeWecalltwosetsAandBequinumerousifthereisabijectionf:AB.EquinumerosityisasymmetricrelationEquinumerosityisaequivalencerelation,1.4,40,finite,Ingeneral,wecallasetfiniteif,intuitively,itisequinumerouswith1,2,nforsomenaturalnumbern.Forn=0,1,2,nistheemptyset,soisfinite,beingequinumerouswithitself.IfAand1,2,nareequinumerous,thecardinalityofAisn,insymbol|A|.,41,infinite,AsetisinfiniteifitisnotfiniteThesetNofnaturalnumbersThesetofintegersThesetofrealsThesetofperfectsquaresNote:Notallinfinitesetsareequinumerous.,42,43,ThreeProofPrinciples,44,45,46,47,48,0.3typesofProof,ProofbyconstructionProofbycontradictionProofbyinduction,49,Example,ProofbyInduction(BaseCase)(InductionHypothesis)(InductiveStep):Nowcorrectlyprovethefollowingstatement:isdivisibleby6.,50,1.BasisStep:6divides13-1=0,clearly.,2.InductionStep:Suppose6|k3-k.,Wewanttoprovethat6|(k+1)3-(k+1)too.,Notethat(k+1)3-(k+1)=k3+3k2+2k=(k3k)+3k(k+1).,Now,6|k3-kbyassumption.,6|3k(k+1)too,since3|3k(k+1)(trivially)and2|k(k+1)(whichisaproductoftwoconsecutiveintegers).,Thus6|(k+1)3-(k+1)=(k3k)+3k(k+1).,51,0.2.5representinformation,Theabilitytorepresentinformationiscrucialtocommunicatingandprocessinginformation.Humansocietiescreatedspokenlanguagestocommunicateonabasiclevel,anddevelopedwritingtoreachamoresophisticatedlevel.TheEnglishlanguage,forinstance,initsspokenformreliesonsomefinitesetofbasicsoundsasasetofprimitives.Thewordsaredefinedintermoffinitesequencesofsuchsounds.Sentencesarederivedfromfinitesequencesofwords.Conversationsareachievedfromfinitesequencesofsentences,andsoforth.WrittenEnglishusessomefinitesetofsymbolsasasetofprimitives.Thewordsaredefinedbyfinitesequencesofsymbols.Sentencesarederivedfromfinitesequencesofwords.Paragraphsareobtainedfromfinitesequencesofsentences,andsoforth.,52,Similarapproacheshavebeendevelopedalsoforrepresentingelementsofothersets.Forinstance,thenaturalnumbercanberepresentedbyfinitesequencesofdecimaldigits.Computations,likenaturallanguages,areexpectedtodealwithinformationinitsmostgeneralform.Consequently,computationsfunctionasmanipulatorsofintegers,graphs,programs,andmanyotherkindsofentities.However,inrealitycomputationsonlymanipulatestringsofsymbolsthatrepresenttheobjects.Thepreviousdiscussionnecessitatesthefollowingdefinitions.,53,Alphabets,Afinite,nonemptyorderedsetwillbecalledanalphabetifitselementsaresymbols.exampleSymbols-letters,numerals,andothercommoncharacterssuchas$or#.,54,Strings,Afinitesequenceofsymbolsfromagivenalphabetwillbecalledastringoverthealphabet.Astringthatconsistsofasequencea1,a2,.,anofsymbolswillbedenotedbythejuxtapositiona1a2an.Stringsthathavezerosymbols,calledemptystrings,willbedenotedby.,55,Example,=a,.,zand=0,.,9arealphabets.abbisastringover1,and123isastringover2.ba12isnotastringover1,becauseitcontainssymbolsthatarenotin1.Similarly,314.isnotastringover2,becauseitisnotafinitesequence.Ontheotherhand,isastringoveranyalphabet.,56,Theemptysetisnotanalphabetbecauseitcontainsnoelement.Thesetofnaturalnumbersisnotanalphabet,becauseitisnotfinite.Theunionisanalphabetonlyifanorderingisplacedonitssymbols.,57,Example,0,1isabinaryalphabet,and1isaunaryalphabet.11isabinarystringoverthealphabet0,1,andaunarystringoverthealphabet1.Thelengthofastringisitslengthasasequence.Wedenotethelengthofastringwby|w|.11isastringoflength2,|=0,and|01|+|1|=3.,58,Operationsofstrings,ConcatenationSubstringExponentiationReversal,59,concatenation,60,61,62,reversal,63,Theuniverseofstringsisausefulmediumfortherepresentationofinformationaslongasthereexistsafunctionthatprovidestheinterpretationfortheinformationcarriedbythestrings.Aninterpretationisjusttheinverseofthemappingthatarepresentationprovides,thatis,aninterpretationisafunctiongfrom*toDforsomealphabetandsomesetD.Thestring111,forinstance,canbeinterpretedasthenumberonehundredandelevenrepresentedbyadecimalstring,asthenumbersevenrepresentedbyabinarystring,andasthenumberthreerepresentedbyaunarystring.,64,Thepartiescommunicatingapieceofinformationdotherepresentingandinterpreting.Therepresentationisprovidedbythesender,andtheinterpretationisprovidedbythereceiver.Theprocessisthesamenomatterwhetherthepartiesarehumanbeingsorprograms.Consequently,fromthepointofviewofthepartiesinvolved,alanguagecanbejustacollectionofstringsbecausethepartiesembedtherepresentationandinterpretationfunctionsinthemselves.,65,Example,IfRistherelation(,),(,01),thenR-1=(,),(01,),R0=(,),andR2=(,),(,01),(,0101).,66,67,language,Ingeneral,ifisanalphabetandLisasubsetof*,thenLissaidtobealanguageover,orsimplyalanguageifisunderstood.EachelementofLissaidtobeasentenceorawordorastringofthela