Mathematics for Computer Science

《Mathematics for Computer Science》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、“mcs”—2017/3/6—12:54—pagei—#1MathematicsforComputerSciencerevisedMonday6thMarch,2017,12:54EricLehmanGoogleInc.FThomsonLeightonDepartmentofMathematicsandtheComputerScienceandAILaboratory,MassachussettsInstituteofTechnology;AkamaiTechnologiesAlbertRMeyerDepartmentofElectricalEnginee

2、ringandComputerScienceandtheComputerScienceandAILaboratory,MassachussettsInstituteofTechnology2016,EricLehman,FTomLeighton,AlbertRMeyer.ThisworkisavailableunderthetermsoftheCreativeCommonsAttribution-ShareAlike3.0license.“mcs”—2017/3/6—12:54—pageii—#2“mcs”—2017/3/6—12:54—pageiii—#

3、3ContentsIProofsIntroduction30.1References41WhatisaProof?51.1Propositions51.2Predicates81.3TheAxiomaticMethod81.4OurAxioms91.5ProvinganImplication111.6Provingan“IfandOnlyIf”131.7ProofbyCases151.8ProofbyContradiction161.9GoodProofsinPractice171.10References192TheWellOrderingPrincip

4、le292.1WellOrderingProofs292.2TemplateforWellOrderingProofs302.3FactoringintoPrimes322.4WellOrderedSets333LogicalFormulas453.1PropositionsfromPropositions463.2PropositionalLogicinComputerPrograms503.3EquivalenceandValidity523.4TheAlgebraofPropositions553.5TheSATProblem603.6Predica

5、teFormulas613.7References664MathematicalDataTypes914.1Sets914.2Sequences964.3Functions974.4BinaryRelations994.5FiniteCardinality103“mcs”—2017/3/6—12:54—pageiv—#4ivContents5Induction1235.1OrdinaryInduction1235.2StrongInduction1325.3StrongInductionvs.Inductionvs.WellOrdering1396Stat

6、eMachines1596.1StatesandTransitions1596.2TheInvariantPrinciple1606.3PartialCorrectness&Termination1686.4TheStableMarriageProblem1737RecursiveDataTypes2037.1RecursiveDefinitionsandStructuralInduction2037.2StringsofMatchedBrackets2077.3RecursiveFunctionsonNonnegativeIntegers2117.4Ari

7、thmeticExpressions2137.5InductioninComputerScience2188InfiniteSets2458.1InfiniteCardinality2468.2TheHaltingProblem2558.3TheLogicofSets2598.4DoesAllThisReallyWork?262IIStructuresIntroduction2879NumberTheory2899.1Divisibility2899.2TheGreatestCommonDivisor2949.3PrimeMysteries3019.4TheF

8、undamentalTheoremofArithmetic3039