复旦大学-赵一鸣-离散数学-二省名师优质课赛课获奖课件市赛课一等奖课件

每七天一交作业，作业成绩占总成绩10%；平时不定时进行小测验，占总成绩

20%；期中考试成绩占总成绩20%；期终考试成绩占总成绩50%1/28A∪B=A∪C⇏

B=Ccancellationlaw

。Example:A={1,2,3},B={3,4,5},C={4,5},

B

C,ButA∪B=A∪C={1,2,3,4,5}Example:A={1,2,3},B={3,4,5},C={3},B

C,ButA∩B=A∩C={3}A-B=A-C⇏B=Ccancellationlaw:symmetricdifference

2/28ThesymmetricdifferenceofAandB,writeA

B,isthesetofallelementsthatareinAorB,butarenotinbothAandB,i.e.A

B=(A∪B)-(A∩B)。(A∪B)-(A∩B)=(A-B)∪(B-A)

3/284/28Theorem1.4:ifA

B=A

C,thenB=C

Distributivelaws

andDeMorgan’slaws:

B∩(A1∪A2∪…∪An)=(B∩A1)∪(B∩A2)∪…∪(B∩An)B∪(A1∩A2∩…∩An)=(B∪A1)∩(B∪A2)∩…∩(B∪An)5/28Chapter2Relations

Definition2.1:Anorderpair(a,b)isalistingoftheobjectsaandbinaprescribedorder,withaappearingfirstandbappearingsecond.Twoorderpairs(a,b)and(c,d)areequalifonlyifa=candb=d.{a,b}={b,a}，orderpairs:(a,b)

(b,a)unlessa=b.(a,a)

6/28Definition2.2:Theorderedn-tuple(a1,a2,…,an)istheorderedcollectionthathasa1asitsfirstelement,a2asitssecondelement,…,andanasitsnthelement.Twoorderedn-tuplesareequalisonlyifeachcorrespondingpairoftheirelementsiaequal,i.e.(a1,a2,…,an)=(b1,b2,…,bn)ifonlyifai=bi,fori=1,2,…,n.7/28Definition2.3:LetAandBbetwosets.TheCartesianproductofAandB,denotedbyA×B,isthesetofallorderedpairs(a,b)wherea

Aandb

B.HenceA×B={(a,b)|a

Aandb

B}

Example:LetA={1,2},B={x,y},C={a,b,c}.A×B={(1,x),(1,y),(2,x),(2,y)};B×A={(x,1),(x,2),(y,1),(y,2)};B×A

A×Bcommutativelaws×

8/28A×C={(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)};A×A={(1,1),(1,2),(2,1),(2,2)}。A×

=

×A=

Definition2.4:LetA1,A2,…Anbesets.TheCartesianproductofA1,A2,…An,denotedbyA1×A2×…×An,isthesetofallorderedn-tuples(a1,a2,…,an)whereai

Aifori=1,2,…n.HenceA1×A2×…×An={(a1,a2,…,an)|ai

Ai,i=1,2,…,n}.

9/28Example:A×B×C={(1,x,a),(1,x,b),(1,x,c),(1,y,a),(1,y,b),(1,y,c),(2,x,a),(2,x,b),(2,x,c),(2,y,a),(2,y,b),(2,y,c)}。IfAi=Afori=1,2,…,n,thenA1×A2×…×AnbyAn.Example：LetArepresentthesetofallstudentsatanuniversity,andletBrepresentthesetofallcourseattheuniversity.WhatistheCartesianproductofA×B?TheCartesianproductofA×Bconsistsofalltheorderedpairsoftheform(a,b),whereaisastudentattheuniversityandbisacourseofferedattheuniversity.ThesetA×Bcanbeusedtorepresentallpossibleenrollmentsofstudentsincoursesattheuniversity10/28studentsa,b,c,

courses:x,y,z,w(a,y),(a,w),(b,x),(b,y),(b,w)，(c,w)R={(a,y),(a,w),(b,x),(b,y),(b,w)}R

A×B,i.e.

RisasubsetofA×Brelation

11/282.2BinaryrelationsDefinition2.5:LetAandBbesets.AbinaryrelationfromAtoBisasubsetofA×B.ArelationonAisarelationfromAtoA.If(a,b)

R,wesaythataisrelatedtobbyR,wealsowriteaRb.If(a,b)

R,wesaythataisnotrelatedtobbyR,wealsowritea

℟

b.wesaythatemptysetisanemptyrelation.

12/28Definition2.6:LetRbearelationfromAtoB.ThedomainofR,denotedbyDom(R),isthesetofelementsinAthatarerelatedtosomeelementinB.TherangeofR,denotedbyRan(R),isthesetofelementsinBthatarerelatedtosomeelementinA.DomR

A,RanR

B。13/28Example:A={1,3,5,7},B={0,2,4,6},R={(a,b)|a<b,wherea

Aandb

B}HenceR={(1,2),(1,4),(1,6),(3,4),(3,6),(5,6)}DomR={1,3,5},RanR={2,4,6}(3,4)

R,Because4≮3,so(4,3)

RTableR={(1,2),(1,4),(1,6),(3,4),(3,6),(5,6)}

14/2815/28A={1,2,3,4},R={(a,b)|3|(a-b),whereaandb

A}R={(1,1),(2,2),(3,3),(4,4),(1,4),(4,1)}DomR=RanR=A。congruencemod3congruencemodr{(a,b)|r|(a-b)whereaandb

Z,andr

Z+}

16/28Definition2.7：LetA1,A2,…Anbesets.Ann-aryrelationonthesesetsisasubsetofA1×A2×…×An.

17/282.3PropertiesofrelationsDefinition2.8:ArelationRonasetAisreflexiveif(a,a)

Rforalla

A.ArelationRonasetAisirreflexiveif(a,a)

Rforeverya

A.

A={1,2,3,4}R1={(1,1),(2,2),(3,3)}?R2={(1,1),(1,2),(2,2),(3,3),(4,4)}?LetAbeanonemptyset.Theemptyrelation

A×Aisnotreflexivesince(a,a)

foralla

A.However

isirreflexive

18/28Definition2.9:ArelationRonasetAissymmetricifwheneveraRb,thenbRa.ArelationRonasetAisasymmetricifwheneveraRb,thenb℟a.ArelationRonasetAisantisymmetricifwheneveraRb,thenb℟aunlessa=b.IfRisantisymmetric,thena℟borb℟awhena

b.

A={1,2,3,4}S1={(1,2),(2,1),(1,3),(3,1)}?S2={(1,2),(2,1),(1,3)}?S3={(1,2),(2,1),(3,3)}?19/28Arelationisnotsymmetric,andisalsonotantisymmetricS4={(1,2),(1,3),(2,3)}antisymmetric,

asymmetricS5={(1,1),(1,2),(1,3),(2,3)}antisymmetric,isnotasymmetricS6={(1,1),(2,2)}antisymmetric,symmetric,isnotasymmetricArelationissymmetric,andisalsoantisymmetric

20/28Definition2.10:ArelationRonsetAistransitiveifwheneveraRbandbRc,thenaRc.ArelationRonsetAisnottransitiveifthereexista,b,andcinAsothataRbandbRc,buta℟c.Ifsucha,b,andcdonotexist,thenRistransitiveT1={(1,2),(1,3)}transitiveT2={(1,1)}transitiveT3={(1,2),(2,3),(1,3)}transitiveT4={(1,2),(2,3),(1,3),(2,1),(1,1)}?

21/28Example：LetRbeanonemptyrelationonasetA.SupposethatRissymmetricandirreflexive.ShowthatRisnottransitive.Proof:SupposeRistransitive.Matrixorpictorialrepresented22/28Definition2.11:LetRbearelationfromA={a1,a2,…,am}toB={b1,b2,…,bn}.TherelationcanberepresentedbythematrixMR=(mi,j)m×n,wheremi,j=1?aiisrelatedbjmi,j=0?aiisnotrelatedbj23/28Example:A={1,2,3,4},R={(1,1),(2,2),(3,3),(4,4),(1,4),(4,1)},Matrix:

Example：A={2,3,4},B={1,3,5,7},<R={(2,3),(2,5),(2,7),(3,5),(3,7),(4,5),(4,7)},Matrix:LetRbearelationonsetA.RisreflexiveifalltheelementsonthemaindiagonalofMRareequalto1

RisirreflexiveifalltheelementsonthemaindiagonalofMRareequalto0

RissymmetricifMRisasymmetricmatrix.

Risantisymmetricifmij=1w