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

1Chapter0:Introduction,mathematicalnotation,prooftechniques20.2.1StandardSetTheoryreviewAsetisanunorderedcollectionofobjects.Elements(members)DonotdistinguishrepetitionsoftheelementsMultiset-Dodistinguishrepetitionsoftheelements{7,7}and{7}Singleton-mayhaveonlyoneelementTheemptyset–withnoelementatall:ΦNonemptyNaturalnumbersN(0inclusive)IntegersZ3writtenListingRefertoothersetsandproperties456SetoperationsUnion:ABIntersection:ABComplement:ADifference:A-BDisjointSets:AB=Null7LawsandPropertiesCommutativelawAssociativelawDistributivelawAbsorptionlawDemogan’slawIdempotentlaw8SuperSetAcollectionofanysetsSS910CoverageDifferencebetweencoverageandpartition110.2.2sequencesandtuplesHowtoexpressrelationsbetweenobjectsThelanguageofsetsFortheobjectsbelongtotherelationNotheobjectsnotdistinguished12OrderedPairs13Cartesianproduct14Binaryrelation15OrderedtupleOrdered2-tupleorderedpairsOrdered3-tupleorderedtriplesOrdered4-tuplequadruplesOrdered5-tuplequintuplesOrdered6-tuplesextuplesSequenceisanorderedn-tupleforsomeunspecifiedn,wherenisthelengthofthesequence.N-foldCartesianproduct16N-aryrelation1-aryrelationunaryrelations2-aryrelationbinaryrelations3-aryrelationternaryrelations17185compositionQR={(a,b):forsomec,(a,c)Qand(c,b)R}Compositionoff:ABandg:BCisafunctionhfromAtoCsuchthath(a)=g(f(a)).196specialtypesofbinaryrelationsdirectedgraphNodeEdgesNotes:donotallow“parallelarrows”.AdjacentmatrixotherwisefbaifbaM0),(1{],[20PropertiesofrelationsReflexiveSymmetricAsymmetricAnti-symmetricTransitive21ReflexiveArelationRA×Aisreflexiveif(a,a)RforeachaA.Thedirectedgraphrepresentingareflexiverelationhasaloopfromeachnodetoitself.Whatisthecharacteristicsofitsmatrix?Alloftheelementsonthediagonallineofitsmatrixare1.22SymmetricArelationRA×Aissymmetricif(b,a)Rwhenever(a,b)R.Inthedirectedgraphrepresentingasymmetricrelation,wheneverthereisanarrowbetweentwonodes,therearearrowsbetweenthosenodesinbothdirections.Characteristicsofmatrix?Example:{(a,b):aandbarepersonswiththesamefather}23undirectedgraphAsymmetricrelationwithoutpairsoftheform(a,a)isrepresentedasanundirectedgraph,orsimpleagraph.24Asymmetric(非对称性）ArelationRA×Aisasymmetricif：∃(a,b∈A∧(a,b)R→(b,a)R)25Antisymmetric(反对称性)ArelationRA×Aisanti-symmetric:a,b∈A∧a≠b∧(a,b)R→(b,a)RExample1:LetPbethesetofallpersons,{(a,b):a,bPandaisthefatherofb}26TransitiveArelationRA×Aistransitiveifwhenever(a,b)Rand(b,c)R,then(a,c)R.Intermsofthedirectedgraphrepresentation,transitivityisequivalenttotherequirementthatwheneverthereisasequenceofarrowsleadingfromanelementatoanelementz,thereisanarrowdirectlyfromatoz.27EquivalencerelationReflexiveSymmetricTransitive28EachelementofthepartitionisanequivalenceclassofA.29Exampleatable(relation)abouttoybrickssetU={x1,x2,x3,x4,x5,x6,x7,x8}elementsColor(R1)Shape(R2)Size(R3)x1redroundSmallx2bluesquareLargex3redtriangularSmallx4bluetriangularSmallx5yellowroundSmallx6yellowSquareSmallx7redtriangularLargex8yellowtriangularLarge30ApathinabinaryrelationRisasequence(a1,..,an)forsomen1suchthat(ai,ai+1)Rfori=1,…,n-1;thispathissaidtobefroma1toan.Thelengthofapath(a1,..,an)isn.Thepath(a1,..,an)isacycleiftheai’sarealldistinctandalso(an,a1)R.3132Closuresofrelation3334350.2.3function1DefinitionAfunctionfromasetAtoasetBisabinaryrelationRonAandBwiththefollowingspecialproperty:foreachaA,thereisexactlyoneorderedpairinRwithfirstcomponenta.R1={(x,y):xC,yS,andxisacityinstatey}R2={(x,y):xS,yC,andyisacityinstatex}362expressionf:ABf(a)=bArgumentvaluef(a)imageofaunderfDomain373CertainkindsoffunctionsOne-to-one一对一Onto满射Bijection双射384InverseofabinaryrelationR-1NoteTheinverseofafunctionneednotbeafunction.Iffisabijection,f-1isafunction.f-1(f(a))=a,foreachaA;f(f-1(b))=b,foreachbB;39FiniteandInfiniteSetsSizeWecalltwosetsAandBequinumerousifthereisabijectionf:AB.EquinumerosityisasymmetricrelationEquinumerosityisaequivalencerelation1.440finiteIngeneral,wecallasetfiniteif,intuitively,itisequinumerouswith{1,2,…,n}forsomenaturalnumbern.Forn=0,{1,2,…,n}istheemptyset,soisfinite,beingequinumerouswithitself.IfAand{1,2,…,n}areequinumerous,thecardinalityofAisn,insymbol|A|.41infiniteAsetisinfiniteifitisnotfiniteThesetNofnaturalnumbersThesetofintegersThesetofrealsThesetofperfectsquaresNote:Notallinfinitesetsareequinumerous.4243ThreeProofPrinciples44454647480.3typesofProofProofbyconstructionProofbycontradictionProofbyinduction49ExampleProofbyInduction(BaseCase)(InductionHypothesis)(InductiveStep):Nowcorrectlyprovethefollowingstatement:isdivisibleby6.nnNn3,50nnNn3,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=(k3–k)+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)=(k3–k)+3k(k+1).510.2.5representinformationTheabilitytorepresentinformationiscrucialtocommunicatingandprocessinginformation.Humansocietiescreatedspokenlan