资源描述：
《Mathematics for Computer Science (MIT 310s)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、MassachusettsInstituteofTechnologyCourseNotes16.042J/18.062J,Fall’02:MathematicsforComputerScienceProfessorAlbertMeyerandDr.RadhikaNagpalProofs1WhatisaProof?Aproofisamethodofascertainingtruth.Therearemanywaystodothis:JuryTrialTruthisascertainedbytwelvepeopleselectedatra
2、ndom.WordofGodTruthisascertainedbycommunicationwithGod,perhapsviaathirdparty.WordofBossTruthisascertainedfromsomeonewithwhomitisunwisetodisagree.ExperimentalScienceThetruthisguessedandthehypothesisisconfirmedorrefutedbyexperiments.SamplingThetruthisobtainedbystatisticala
3、nalysisofmanybitsofevidence.Forexample,publicopinionisobtainedbypollingonlyarepresentativesample.InnerConviction/Mysticism“Myprogramisperfect.Iknowthistobetrue.”“Idon’tseewhynot...”Claimsomethingistrueandthenshifttheburdenofprooftoanyonewhodisagreeswithyou.“Cogitoergosu
4、m”Proofbyreasoningaboutundefinedterms.ThisLatinquotetranslatesas“Ithink,thereforeIam.”Itcomesfromthebeginningofafamousessaybythe17thcenturyMathematician/Philospher,Rene´Descartes.Itmaybeoneofthemostfamousquotesintheworld:doawebsearchonthephraseandyouwillbefloodedwithhits.
5、Deducingyourexistencefromthefactthatyou’rethinkingaboutyourexistencesoundslikeaprettycoolstartingaxiom.Butitain’tMath.Infact,DescartesgoesonshortlytoconcludethatthereisaninfinitelybeneficentGod.Mathematicsalsohasaspecificnotionof“proof”orwayofascertainingtruth.Definition.Af
6、ormalproofofapropositionisachainoflogicaldeductionsleadingtothepropositionfromabasesetofaxioms.Thethreekeyideasinthisdefinitionarehighlighted:proposition,logicaldeduction,andaxiom.Eachofthesetermsisdiscussedinasectionbelow.Copyright©2002,Prof.AlbertR.Meyer.2CourseNotes1:
7、Proofs2PropositionsDefinition.Apropositionisastatementthatiseithertrueorfalse.Thisdefinitionsoundsverygeneral,butitdoesexcludesentencessuchas,“WhereforeartthouRomeo?”and“GivemeanA!”.Proposition2.1.2+3=5.Thispropositionistrue.Proposition2.2.Letp(n)::=n2+n+41.∀n∈Np(n)isapri
8、menumber.Thesymbol∀isread“forall”.ThesymbolNstandsforthesetofnaturalnumbers,whichare0,1,2,3,...;(askyourTAfort
