Discrete-Mathematics----Chapter-1-Sets-and-logic-Chapter-2-Proofs第一章第二章课件.pptVIP

????

DiscreteMathematics

8/30Ch19/1Ch1Hw1Ch1,26Ch28Ch215Ch320Ch3Hw2Ch3,422Ch4Quiz1Ch1,227Ch429Ch510/4Ch5Hw3Ch5,66Ch611Ch6Quiz2Ch3,413Ch718Ch7Hw4Ch7,820WedExam1Ch1~625Ch827Ch8

11/1Ch93Ch9Hw5Ch9,108Ch10Quiz3Ch7,810Ch1015Ch1117Ch11Hw6Ch11,1222WedExam2Ch7~1024Ch1229Ch1212/16-Quiz4Ch11,128-FinalAllchapters

DiscreteMathematics

7thedition,2009Chapter1SetsandlogicChapter2Proofs

51.1SetsSet=acollectionofdistinctunorderedobjectsMembersofasetarecalledelementsHowtodetermineasetListing:Example:A={1,3,5,7}DescriptionExample:B={x|x=2k+1,0k3}

6FiniteandinfinitesetsFinitesetsExamples:A={1,2,3,4}B={x|xisaninteger,1x4}InfinitesetsExamples:Z={integers}={…,-3,-2,-1,0,1,2,3,…}S={x|xisarealnumberand1x4}=[1,4]

7SomeimportantsetsTheemptyset?hasnoelements.Alsocallednullsetorvoidset.Universalset:thesetofallelementsaboutwhichwemakeassertions.Examples:U={allnaturalnumbers}U={allrealnumbers}U={x|xisanaturalnumberand1x10}

8CardinalityCardinalityofasetA(insymbols|A|)isthenumberofelementsinAExamples:IfA={1,2,3}then|A|=3IfB={x|xisanaturalnumberand1x9}then|B|=9InfinitecardinalityCountable(e.g.,naturalnumbers,integers)Uncountable(e.g.,realnumbers)

9Subsets,PowersetXisasubsetofYifeveryelementofXisalsocontainedinY (insymbolsX?Y)Equality:X=YifX?YandY?XXisapropersubsetofYifX?YbutY?XObservation:?isasubsetofeverysetThepowersetofXisthesetofallsubsetsofX,insymbolsP(X),i.e.P(X)={A|A?X}Example:ifX={1,2,3}, thenP(X)={?,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}Theorem2.1.4:If|X|=n,then|P(X)|=2n.

10SetoperationsGiventwosetsXandYTheunionofXandYisdefinedasthesetX?Y={x|x?Xorx?Y}