c北京邮电大学计算机学院-离散数学-数学结构-群论-hap9-1

MathematicalStructures〔数学结构〕22024/5/21CollegeofComputerScience&Technology,BUPTMathematicalstructureAcollectionofobjectswithoperationsdefinedonthemandtheaccompanyingpropertiesformamathematicalstructureorsystem.Inthisbookwedealonlywithdiscretemathematicalstructures.32024/5/21CollegeofComputerScience&Technology,BUPTExample1Thecollectionofsetswiththeoperationsofunion,intersection,andcomplementandtheiraccompanyingpropertiesisa(discrete)mathematicalstructure.Wedenotethisstructureby[sets,

,

,].42024/5/21CollegeofComputerScience&Technology,BUPTExample2Thecollectionof33matriceswiththeoperationsofaddition,multiplication,andtranspose〔转置〕isamathematicalstructuredenotedby[33matrices,+,,T].52024/5/21CollegeofComputerScience&Technology,BUPTClosure〔封闭性〕Astructureisclosedwithrespecttoanoperationifthatoperationalwaysproducesanothermemberofthecollectionofobjects.62024/5/21CollegeofComputerScience&Technology,BUPTExamplesThestructure[5

5matrices,+,*,T]isclosedwithrespecttoadditionbecausethesumoftwo5

5matricesisanother5

5matrix.Thestructure[oddintegers,+,*]isnotclosedwithrespecttoaddition.Thesumoftwooddintegersisaneveninteger.Thisstructuredoeshavetheclosurepropertyformultiplication,sincetheproductoftwooddnumbersisanoddnumber.72024/5/21CollegeofComputerScience&Technology,BUPTBinaryoperation〔二元运算〕Anoperationthatcombinestwoobjectsisabinaryoperation.Anoperationthatrequiresonlyoneobjectisaunaryoperation〔一元运算〕.Binaryoperationsoftenhavesimilarproperties,aswehaveseenearlier.Example(a)Setintersectionisabinaryoperationsinceitcombinestwosetstoproduceanewset.Producingthetransposeofmatrixisaunaryoperation.82024/5/21CollegeofComputerScience&Technology,BUPTCommutative〔交换性〕Commonpropertieshavebeengivennames.Forexample,iftheorderoftheobjectsdoesnotaffecttheoutcomeofabinaryoperation,wesaythattheoperationiscommutative.Thatis,ifx

y=y

x,whereissomebinaryoperation,iscommutative.Example(a)JoinandmeetforBooleanmatricesarecommutativeoperations.A

B=B

AandA

B=B

A.(b)OrdinarymatrixmultiplicationisnotacommutativeoperationAB

BA.92024/5/21CollegeofComputerScience&Technology,BUPTNoteanoperationhasapropertymeansthestatementofthepropertyistruewhentheoperationisusedwithanyobjectsinthestructure.Ifthereisevenonecasewhenthestatementisnottrue,theoperationdoesnothavethatproperty.102024/5/21CollegeofComputerScience&Technology,BUPTAssociative〔结合性〕Ifnisabinaryoperation,thennisassociativeorhastheassociativepropertyif(x

y)

z=x

(y

z).ExampleSetunionisanassociativeoperation,since(A

B)

C=A

(B

C)isalwaystrue.112024/5/21CollegeofComputerScience&Technology,BUPTDistributive〔分配〕propertyIfamathematicalstructurehastwobinaryoperations,say

and

,adistributivepropertyhasthefollowingpattern:

x

(y

z)=(x

y)

(x

z).Example(a)Wearefamiliarwiththedistributivepropertyforrealnumbers;ifa,b,andcarerealnumbers,thena

(b+c)=a

b+a

c.(b)Thestructure[sets,

,

,]hastwodistributiveproperties:A

(B

C)=(A

B)

(A

C)andA

(B

C)=(A

B)

(A

C).122024/5/21CollegeofComputerScience&Technology,BUPTDeMorgan‘slaws〔德.摩根律〕Severalofthestructureswehaveseenhaveaunaryoperationandtwobinaryoperations.Iftheunaryoperationis*andthebinaryoperationsare

and

.thenDeMorgan'slawsare(x

y)*=x*

y*and(x

y)*=x*

y*.Example9(a)(A

B)=A

Band(A

B)=A

B.(b)Thestructure[realnumbers,+,*,]doesnotsatisfyDeMorgan'slaws.since

132024/5/21CollegeofComputerScience&Technology,BUPTIdentity(单位元〕foranoperationAstructurewithabinaryoperation

maycontainadistinguishedobjecte,withthepropertyx

e=e

x=xforallxinthecollection.Wecalleanidentityfor

.Infact,anidentityforanoperationmustbeunique.142024/5/21CollegeofComputerScience&Technology,BUPTTheorem1Ifeisanidentityforabinaryoperation

,theneisunique.ProofAssumeanotherobjectialsohastheidentityproperty,sox

i=i

x=x.Thene

i=e,butsinceeisanidentityforn,i

e=e

i=i.Thus,i=e.Thereisatmostoneobjectwiththeidentitypropertyfor

.152024/5/21CollegeofComputerScience&Technology,BUPTExample10For[n

nmatrices,+,*,T],Inistheidentityformatrixmultiplicationandthen

nzeromatrixistheidentityformatrixaddition.162024/5/21CollegeofComputerScience&Technology,BUPTInverse〔逆元〕

Ifabinaryoperation

hasanidentitye,wesayyisa

-inverseofxifx

y=y

x=e.Theorem2If

isanassociativeoperationandxhasa

-inversey,thenyisunique.ProofAssumethereisanother

-inverseforx,sayz.Then

(z

x)

y=e

y=yandz

(x

y)=z

e=z.Since

isassociative,(z

x)

y=z

(x

y)andsoy=z.172024/5/21CollegeofComputerScience&Technology,BUPTExample11(a)Inthestructure[3

3matrices,+,*,T]eachmatrixA=[aij]hasa+-inverse,oradditiveinverse,-A=[-aij].(b)Inthestructure[integers,+,*],onlytheintegersland-lhavemultiplicativeinverses.182024/5/21CollegeofComputerScience&Technology,BUPTExample12Let

,and*bedefinedfortheset{0,l}bythefollowingtables.Thus1

0=l,0

1=0,and1*=0.Determineifeachofthefollowingistruefor[{0,l},

,

,*].(a)

iscommutative.(b)

isassociative.(c)DeMorgan'slawshold.(d)Twodistributivepropertiesholdforthestructure.192024/5/21CollegeofComputerScience&Technology,BUPTExample12

Solution(a)Thestatementx

y=y

xmustbetrueforallchoicesofxandy.Sinceboth0

landl

0arel,

iscommutative.(b)Theeightpossiblecasestobecheckedareleftasanexercise.(c)(0

0)*=0*=l0*

0*=1

1=l.(0

1)*=1*=00*

1*=1

0=0. (1

1)*=0*=l1*

1*=0

0=0. ThelastpairshowsthatDeMorgan'slawsdonotholdinthisstructure.202024/5/21CollegeofComputerScience&Technology,BUPT(d)Onepossibledistributivepropertyisx

(y

z)=(x

y)

(x

z).allpossiblecasesmustbechecked.Wecanshowitinatable.

212024/5/21CollegeofComputerScience&Technology,BUPTBinaryoperations

(二元运算)AbinaryoperationonasetAisaneverywheredefinedfunctionf:A

A

A.Abinaryoperationmustsatisfy:fassignsanelementf(a,b)ofAtoeachorderedpair(a,b)inA

A.OnlyoneelementofAisassignedtoeachorderedpair.222024/5/21CollegeofComputerScience&Technology,BUPTNoteIt’scustomarytodenotebinaryoperationsbyasymbolsuchas

,insteadoff,andtodenotetheelementassignedto(a,b)bya

b[insteadof(a,b)].Aisclosed(封闭的)

undertheoperation

,ifaandbareelementsinA,a

b

A.232024/5/21CollegeofComputerScience&Technology,BUPTExample1,2

LetA=Z.Definea

basa+b.

isabinaryoperationonZ.LetA=R.Definea

basa/b.

isnotabinaryoperation.Forexample,3

0isnotdefined.242024/5/21CollegeofComputerScience&Technology,BUPTExample3LetA=Z+.Definea

basa-b.

isnotabinaryoperation.itdoesnotassignanelementofAtoeveryorderedpairofelementsofA;forexample,2

5

A.252024/5/21CollegeofComputerScience&Technology,BUPTExample4LetA=Z.Definea

basanumberlessthanbothaandb.

isnotabinaryoperation,sinceitdoesnotassignauniqueelementofAtoeachorderedpairofelementsofA;forexample,8

6couldbe5,4,3,l,andsoon.inthiscase,

wouldbearelationfromA

AtoA,butnotafunction262024/5/21CollegeofComputerScience&Technology,BUPTExample5,6LetA=Z.Definea

basmax{a,b}.

isabinaryoperation;forexample,2

4=4,-3

(-5)=-3.LetA=P(S),forsomesetS.IfVandWaresubsetsofS,defineV

WasV

W.

isabinaryoperationonA.ifwedefineV

'WasV

W,then

'isanotherbinaryoperationonA.Note:It’spossibletodefinemanybinaryoperationsonthesameset.272024/5/21CollegeofComputerScience&Technology,BUPTExample7,8LetMbethesetofalln

nBooleanmatricesforafixedn.DefineA

BasA

B

isabinaryoperation.ThisisalsotrueofA

B.LetLbealattice.Definea

basa

b.

isabinaryoperationonL.Thisisalsotrueofa

b282024/5/21CollegeofComputerScience&Technology,BUPTTables–运算表IfA={al,a2,...,an}isafiniteset,wecandefineabinaryoperationonAbymeansofatable292024/5/21CollegeofComputerScience&Technology,BUPTExample9LetA={0,l}.Definebinaryoperations

and

bythefollowingtables:302024/5/21CollegeofComputerScience&Technology,BUPTHowmanyoperations?IfA={a,b},howmanybinaryoperationscanbedefinedonA.Everybinaryoperation

onAcanbedescribedbyatableThereare2

2

2

2=24or16waystocompletethetable.312024/5/21CollegeofComputerScience&Technology,BUPTPropertiesofBinaryOperations〔二元运算的性质〕Forallelementsa,b,andcinACommutative(可交换的)a*b=b*a

Associative(可结合的)a*(b*c)=(a*b)*cIdempotent(幂等的)a*a=a322024/5/21CollegeofComputerScience&Technology,BUPTCommutative–可交换的AbinaryoperationonasetAissaidtobecommutativeifa*b=b*aforallelementsaandbinA.Example:ThebinaryoperationofadditiononZ

ThebinaryoperationofsubtractiononZ.332024/5/21CollegeofComputerScience&Technology,BUPTCommutativeAbinaryoperationthatisdescribedbyatableiscommutativeifandon1yifTheentriesinthetablearesymmetricwithrespecttothemaindiagonal.342024/5/21CollegeofComputerScience&Technology,BUPTExample12Whichofthefol1owingbinaryoperationsonA={a,b,c,d}arecommutative?352024/5/21CollegeofComputerScience&Technology,BUPTAssociative–可结合的Abinaryoperation*onasetAissaidtobeassociativeifa*(b*c)=(a*b)*cforallelementsa,b,andcinA.Example:ThebinaryoperationofadditiononZ

ThebinaryoperationofsubtractiononZ

2-(3-5)

(2-3)-5.362024/5/21CollegeofComputerScience&Technology,BUPTExample15LetLbealattice.Thebinaryoperationdefinedbya*b=a

biscommutativeandassociative.Italsosatisfiestheidempotentpropertya

a=a.372024/5/21CollegeofComputerScience&Technology,BUPTExample16Let*beabinaryoperationonasetA,andsupposethat*satisfiesthefollowingpropertiesforanya,b,andcinA:

a=a*a

a*b=b*a

a*(b*c)=(a*b)*cDefinearelation

onAbya

bifandonlyifa=a*b.Showthat(A,

)isaposet,andforalla,binA,GLB(a,b)=a*b.382024/5/21CollegeofComputerScience&Technology,BUPTExample16:SolutionWemustshowthat

isreflexive,antisymm