资源描述:
《离散数学及其应用(英文版第7版)【迷你书】》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、P1:1/1P2:1/2QC:1/1T1:2CH01-7TRosen-2311TMHIA017-Rosen-v5.clsMay13,201115:27CHAPTERTheFoundations:1LogicandProofs1.1Propositionalherulesoflogicspecifythemeaningofmathematicalstatements.Forinstance,theserulesLogicThelpusunderstandandreasonwithstatementssu
2、chas“Thereexistsanintegerthatisnotthesumoftwosquares”and“Foreverypositiveintegern,thesumofthepositiveintegers1.2Applicationsofnotexceedingnisn(n+1)/2.”Logicisthebasisofallmathematicalreasoning,andofallPropositionalautomatedreasoning.Ithaspracticalapplic
3、ationstothedesignofcomputingmachines,totheLogicspecificationofsystems,toartificialintelligence,tocomputerprogramming,toprogramming1.3Propositionallanguages,andtootherareasofcomputerscience,aswellastomanyotherfieldsofstudy.EquivalencesTounderstandmathematic
4、s,wemustunderstandwhatmakesupacorrectmathematical1.4Predicatesandargument,thatis,aproof.Onceweproveamathematicalstatementistrue,wecallitatheorem.AQuantifierscollectionoftheoremsonatopicorganizewhatweknowaboutthistopic.Tolearnamathematicaltopic,apersonnee
5、dstoactivelyconstructmathematicalargumentsonthistopic,andnotjust1.5Nestedreadexposition.Moreover,knowingtheproofofatheoremoftenmakesitpossibletomodifyQuantifierstheresulttofitnewsituations.1.6RulesofEveryoneknowsthatproofsareimportantthroughoutmathematics
6、,butmanypeoplefindInferenceitsurprisinghowimportantproofsareincomputerscience.Infact,proofsareusedtoverifythatcomputerprogramsproducethecorrectoutputforallpossibleinputvalues,toshowthat1.7Introductiontoalgorithmsalwaysproducethecorrectresult,toestablisht
7、hesecurityofasystem,andtocreateProofsartificialintelligence.Furthermore,automatedreasoningsystemshavebeencreatedtoallow1.8ProofMethodscomputerstoconstructtheirownproofs.andStrategyInthischapter,wewillexplainwhatmakesupacorrectmathematicalargumentandintro
8、-ducetoolstoconstructthesearguments.Wewilldevelopanarsenalofdifferentproofmethodsthatwillenableustoprovemanydifferenttypesofresults.Afterintroducingmanydifferentmethodsofproof,wewillintroduceseveralstrategiesforconstructingproofs