资源描述：
《discrete mathematics - chen》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、DISCRETEMATHEMATICSWWLCHENcWWLChen,1982.Thisworkisavailablefree,inthehopethatitwillbeuseful.Anypartofthisworkmaybereproducedortransmittedinanyformorbyanymeans,electronicormechanical,includingphotocopying,recording,oranyinformationstorageandretrievalsy
2、stem,withorwithoutpermissionfromtheauthor.Chapter1LOGICANDSETS1.1.SentencesInthissection,welookatsentences,theirtruthorfalsity,andwaysofcombiningorconnectingsentencestoproducenewsentences.Asentence(orproposition)isanexpressionwhichiseithertrueorfalse.T
3、hesentence“2+2=4”istrue,whilethesentence“πisrational”isfalse.Itis,however,notthetaskoflogictodecidewhetheranyparticularsentenceistrueorfalse.Infact,therearemanysentenceswhosetruthorfalsitynobodyhasyetmanagedtoestablish;forexample,thefamousGoldbachconje
4、cturethat“everyevennumbergreaterthan2isasumoftwoprimes”.Thereisadefectinourdefinition.Itissometimesverydifficult,underourdefinition,todeterminewhetherornotagivenexpressionisasentence.Consider,forexample,theexpression“Iamtellingalie”;amI?Sincethereareexpres
5、sionswhicharesentencesunderourdefinition,weproceedtodiscusswaysofconnectingsentencestoformnewsentences.Letpandqdenotesentences.Definition.(CONJUNCTION)Wesaythatthesentencep∧q(pandq)istrueifthetwosentencesp,qarebothtrue,andisfalseotherwise.Example1.1.1.T
6、hesentence“2+2=4and2+3=5”istrue.Example1.1.2.Thesentence“2+2=4andπisrational”isfalse.Definition.(DISJUNCTION)Wesaythatthesentencep∨q(porq)istrueifatleastoneoftwosentencesp,qistrue,andisfalseotherwise.Example1.1.3.Thesentence“2+2=2or1+3=5”isfalse.†Thisc
7、hapterwasfirstusedinlecturesgivenbytheauthoratImperialCollege,UniversityofLondon,in1982.1–2WWLChen:DiscreteMathematicsExample1.1.4.Thesentence“2+2=4orπisrational”istrue.Remark.Toprovethatasentencep∨qistrue,wemayassumethatthesentencepisfalseandusethistod
8、educethatthesentenceqistrueinthiscase.Forifthesentencepistrue,ourargumentisalreadycomplete,nevermindthetruthorfalsityofthesentenceq.Definition.(NEGATION)Wesaythatthesentencep(notp)istrueifthesentencepisfalse,andisfalseifthesentencepistr
