![c北京郵電大學計算機學院-離散數學-數學結構-群論-hap9-1_第1頁](http://file4.renrendoc.com/view5/M01/2E/38/wKhkGGZMXYCAR4oyAAEqWP9ZnEw515.jpg)
![c北京郵電大學計算機學院-離散數學-數學結構-群論-hap9-1_第2頁](http://file4.renrendoc.com/view5/M01/2E/38/wKhkGGZMXYCAR4oyAAEqWP9ZnEw5152.jpg)
![c北京郵電大學計算機學院-離散數學-數學結構-群論-hap9-1_第3頁](http://file4.renrendoc.com/view5/M01/2E/38/wKhkGGZMXYCAR4oyAAEqWP9ZnEw5153.jpg)
![c北京郵電大學計算機學院-離散數學-數學結構-群論-hap9-1_第4頁](http://file4.renrendoc.com/view5/M01/2E/38/wKhkGGZMXYCAR4oyAAEqWP9ZnEw5154.jpg)
![c北京郵電大學計算機學院-離散數學-數學結構-群論-hap9-1_第5頁](http://file4.renrendoc.com/view5/M01/2E/38/wKhkGGZMXYCAR4oyAAEqWP9ZnEw5155.jpg)
版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 公路建筑材料質檢合同范例
- 北京出租合同范例
- 財產抵押擔保借款合同范本
- 冷庫安裝合同范例
- 公廁維修施工合同范本
- 公司工程裝修合同范例
- 個人廣告采購合同范本
- 全屋定制套餐合同范例
- 2025年度工傷事故責任認定與賠償金支付協議書
- 包子配送合同范本
- 《消防機器人相關技術研究》
- 2024年考研政治真題及答案
- 【直播薪資考核】短視頻直播電商部門崗位職責及績效考核指標管理實施辦法-市場營銷策劃-直播公司團隊管理
- 項目設計報告范文高中
- 《千年古村上甘棠》課件
- 部編版小學語文二年級下冊電子課文《小馬過河》
- 《醫(yī)療機構工作人員廉潔從業(yè)九項準則》專題解讀
- 愛車講堂 課件
- 成立商會的可行性報告5則范文
- 市場監(jiān)督管理局反電信網絡詐騙工作總結
- 2024-2030年中國免疫細胞存儲行業(yè)發(fā)展模式及投資戰(zhàn)略分析報告
評論
0/150
提交評論