離散數(shù)學期末復習綱要

1、（1）需要熟練掌握的知識點包括：命題的定義、邏輯聯(lián)結(jié)詞、命題變元、命題公式（合式公式）、永真式、永假式、可滿足式、等價式、蘊涵式、極小項、極大項、主析取范式、主合取范式。,第1章命題邏輯重點,（2）掌握基本的等價式和蘊涵式，并掌握常用的等價式和蘊涵式的證明方法（替換規(guī)則和推論規(guī)則）。,第1章命題邏輯重點（續(xù)）,（3）要能準確地求出命題公式的主析取范式和主合取范式。掌握主析取范式和主合取范式與真值表的對應(yīng)關(guān)系，主析取范式和主合取范式的關(guān)系

2、。,第1章命題邏輯重點（續(xù)）,（4）掌握命題符號化的原則；（5）熟練掌握四個推論規(guī)則（P、T、CP、F）進行有效性論證。,第1章命題邏輯重點（續(xù)）,證明等價式:P41#8(1),(1)P→(Q→P)??P→(P→Q)左式??P∨(?Q∨P)?T右式???P∨(?P∨Q)?P∨(?P∨Q)?T所以： P→(Q→P)??P→(P→Q),P41#8(5),(5)(P∧Q∧A→C)∧(A→ P∨Q∨C) ?(A∧(P?

3、Q))→C左式?(?P∨?Q∨?A∨C)∧(?A∨P∨Q∨C) ?((?P∨?Q∨?A)∧(?A∨P∨Q))∨C ?(?A∨((?P∨?Q)∧(P∨Q)))∨C?(?A∨?((P∧Q)∨(?P∧?Q)))∨C??(A∧((P∧Q)∨(?P∧?Q)))∨C??(A∧(P?Q))∨C ? (A∧(P?Q))→C ?右式,P41#11(2),將下列公式用只含∨和?的等價式表示:,(2)(P → (Q ∨ ? R))∧ ?P ∧

4、Q,?(? P ∨ (Q ∨ ? R))∧ ?P ∧Q,?(? P ∨Q ∨? R)∧ ?P ∧Q,? ?(?(? P ∨Q ∨? R)) ∨ P ∨? Q),求命題公式的主范式P42#17,(1)(?P∨?Q)→(P??Q)??(?P∨?Q)∨(P∧?Q)∨(?P∧??Q)? (P∧Q)∨(P∧?Q)∨(?P∧Q),01,10,11,?∑(m1,m2,m3)?∏(M0)?P∨Q,求命題公式的主范式P42#17,(6)(P→Q∧R

5、))∧(?P→?Q∧?R))?(?P∨(Q∧R))∧(??P∨(?Q∧?R))?(?P∨Q)∧(?P∨R)∧(P∨?Q)∧(P∨?R)?((?P∨Q)∨(R∧?R))∧((?P∨R) ∨(Q∧?Q))∧((P∨?Q) ∨(R∧?R))∧((P∨?R)∨(Q∧?Q))? (?P∨Q∨R)∧(?P∨Q∨?R)∧(?P∨Q∨R)∧(?P∨?Q∨R) ∧(P∨?Q∨R)∧(P∨?Q∨?R) ∧(P∨Q∨?R)∧(P∨?Q ∨?R)

6、? ∏(M1 , M2 , M3 , M4 , M5 , M6)?∑(m0,m7)?(?P∧?Q∧?R)∨(P∧Q∧R),CP規(guī)則的使用P42#22(3),(P∨Q)→R?(P∧Q)→RP∧Q P規(guī)則（附加前提）PT規(guī)則(1)Q T規(guī)則(1)P∨QT規(guī)則(2)(3)(P∨Q)→R P規(guī)則RT規(guī)則(4)(5)(P∧Q)→RCP規(guī)則(1)(6),F規(guī)則

7、的使用P43#23(2),S→?Q,R∨S, ?R, ?P? Q? P ?PP規(guī)則（假設(shè)前提）?P? QP規(guī)則QT規(guī)則（1）（2）S→?QP規(guī)則?ST規(guī)則（3）（4）R∨SP規(guī)則RT規(guī)則（5）（6）?RP規(guī)則R∧ ?RT規(guī)則（1）（8）矛盾式PF規(guī)則（1）（9）,符號化并驗證結(jié)論的有效P43#25(1),1）如果6是偶數(shù)，則2不能整除7；2）或者5不是素

8、數(shù)，或者2整除7；3）5是素數(shù)； 結(jié)論：因此6是奇數(shù)。,符號化,P:6是偶數(shù);,Q:2能整除7;,R: 5是素數(shù);,如果6是偶數(shù)，則2不能整除7:,P→?Q,或者5不是素數(shù)，或者2整除7:,?R∨Q,5是素數(shù):,R,? 6是奇數(shù):,?P,證明,RP規(guī)則?R∨QP規(guī)則QT規(guī)則(1)(2)P→?QP規(guī)則?PT規(guī)則(3)(4),P→?Q,?R∨Q,R,?,?P,P43#25(6),符號化:,P:今天是星期

9、二;,Q:我們有離散數(shù)學測驗;,R:我們有高等數(shù)學測驗;,S:高等數(shù)學老師生病;,P→Q ∨R,S→?R,P∧S,?,Q,P43#25(6)(續(xù)),P→Q ∨R,S→?R,P∧S,?,Q,(1) P∧S(P規(guī)則),(2) P(T規(guī)則(1)),(3) S(T規(guī)則(1)),(4) S→?R (P規(guī)則),(5) ?R (T規(guī)則(3)(4)),(6) P→Q ∨R (P規(guī)則),(7) Q ∨R (T規(guī)則

10、(2)(6)),(8) Q (T規(guī)則(5)(7)),第2章謂詞邏輯重點,（1）需要熟練掌握的知識點包括：謂詞、全稱量詞(?x)、存在量詞 (?x) 、個體、個體域、個體變元（約束變元和自由變元）、謂詞公式的解釋（永真、永假、可滿足）、謂詞公式的基本的等價式和蘊涵式。,第2章謂詞邏輯重點（續(xù)）,（2）在符號化時要特別注意量詞和邏輯聯(lián)結(jié)詞的搭配：全稱量詞對應(yīng)邏輯聯(lián)結(jié)詞“→”，存在量詞對應(yīng)邏輯聯(lián)結(jié)詞“∧”。（3）在謂詞邏輯推理的

11、證明中，要特別注意US，ES，UG，EG規(guī)則成立的條件（用ES規(guī)則指定的個體不能用UG規(guī)則加以推廣）。,符號化并證明結(jié)論的有效性P64#18(1),1）所有有理數(shù)是實數(shù)；2）某些有理數(shù)是整數(shù)；結(jié)論：某些實數(shù)是整數(shù)。,符號化,特性謂詞:Q(x):x是有理數(shù)；I(x):x是整數(shù)；R(x):x是實數(shù)；,(?x) ( ∧ ),所有有理數(shù)是實數(shù)：,(?x) ( → ),Q(x),R

12、(x),某些有理數(shù)是整數(shù):,(?x) ( ∧ ),Q(x),I(x),?某些實數(shù)是整數(shù):,R(x),I(x),證明,(?x)(Q(x)→R(x)), (?x)(Q(x)∧I(x)) ?(?x)(R(x)∧I(x))(1) (?x)(Q(x)∧I(x))P規(guī)則 (2) Q(a)∧I(a)ES規(guī)則(3) Q(a)T規(guī)則（2）(4) I(a) T規(guī)則（2）(5) (?

13、x)(Q(x)→R(x)) P規(guī)則 (6) Q(a)→R(a) US規(guī)則(5)(7) R(a) T規(guī)則（3）(6)(8) R(a) ∧I(a) T規(guī)則（4）(7)(9) (?x)(R(x)∧I(x)) UG規(guī)則(8),首先使用含有存在量詞的前提,符號化并證明結(jié)論的有效性P64#18(2),任何人如果他喜歡步行，他就不喜歡乘車。每個人或者喜歡乘車或者喜歡騎自行車；有的人不愛騎自行車，因而有的人不

14、愛步行。,符號化,特性謂詞: P(x):x是人；W(x):x喜歡步行;T(x):x喜歡乘車;B(x):x喜歡騎自行車任何人如果他喜歡步行，他就不喜歡乘車:,(?x)( → ),P(x),(W(x)→?T(x),(?x)( → ),(P(x)∧W(x),?T(x),每個人或者喜歡乘車或者喜歡騎自行

15、車:,(?x)( → ),P(x),(T(x)∨R(x),符號化(續(xù)),有的人不愛騎自行車:,(?x) ( ∧ ),P(x),?R(x),?有的人不愛步行:,(?x) ( ∧ ),P(x),?W(x),證明,(?x)(P(x)→(W(x)→?T(x)),(?x)(P(x)→(T(x)∨R(x)),

16、(?x) (P(x)∧?R(x))? (?x) (P(x)∧?W(x)) (?x) (P(x)∧?R(x))P規(guī)則P(a)∧?R(a)ES規(guī)則P(a)T規(guī)則(2)?R(a)T規(guī)則(2)(?x)(P(x)→(T(x)∨R(x))P規(guī)則P(a)→(T(a)∨R(a))US規(guī)則(5)T(a)∨R(a)T規(guī)則(3)(6)T(a)T規(guī)則(4)(7)(?x)(P(x)→(W(x)→?

17、T(x))P規(guī)則P(a)→(W(a)→?T(a))US規(guī)則(9)W(a)→?T(a)T規(guī)則(3)(10)?W(a)T規(guī)則(8)(11)P(a) ∧?W(a)T規(guī)則(3)(12)(?x) (P(x)∧?W(x))EG規(guī)則(13),首先使用含有存在量詞的前提,符號化并證明結(jié)論的有效性P64#18(3),任何人違反交通規(guī)則，都要被罰款，因此，如果沒有罰款，則沒有人違反交通規(guī)則。,符號化,特性謂詞: M(

18、x):x是人；P(x):x違反交通規(guī)則；Q(x):x被罰款。任何人違反交通規(guī)則，都要被罰款：,(?x)( → ),M(x),(P(x)→Q(x),(?x)( → ),(M(x)∧P(x),Q(x),?如果沒有罰款，則沒有人違反交通規(guī)則：,?(?x)Q(x)→?(?x)(M(x)∧P(x)),證明,(?x)

19、(M(x)→(P(x)→Q(x))? ?(?x)Q(x)→?(?x)(M(x)∧P(x))?(?x)Q(x)P規(guī)則（附加前提）(?x)?Q(x)T規(guī)則(1)?Q(a)US規(guī)則(2)(?x)(M(x)→(P(x)→Q(x))P規(guī)則 M(a)→(P(a)→Q(a))US規(guī)則(4)?M(a)∨?P(a)∨Q(a)T規(guī)則(5)?M(a)∨?P(a)T規(guī)則(3)(6)?(M(a)

20、∧P(a))T規(guī)則(7)(?x) ?(M(a)∧P(a))UG規(guī)則(8)?(?x)(M(x)∧P(x))T規(guī)則(9)?(?x)Q(x)→?(?x)(M(x)∧P(x))CP規(guī)則(1)(10),第三章集合,(1)掌握集合的基本概念及其表示，集合之間的關(guān)系（子集? 、真子集? ）、元素與集合的關(guān)系（屬于? ）、全集、空集、冪集、笛卡爾乘積等概念。(2)能熟練地證明集合中的相等關(guān)系、包含關(guān)系。(3)掌握集

21、合的五種基本運算：~A、A∩ B、A∪ B、A-B、A⊕ B及集合運算的基本定律。,P84#4,A={1}B={{1}}C={{{1}}}滿足：A∈ B,B∈ C,但是A? C,P84#5,(1)T(2)F :A={1},B={{1}},C={{1},2}(3)F: A={1},B={1,2},C={{1,2},3}(4)F:A={1},B={1,2},C={{1,2},3},P84#6,是?！?~A∩B=~A∩C∴

22、 B-A=C-AB=(A∩B)∪(B-A)= (A∩C)∪(C-A)=C,P84#8,(1)否：A={1,2},B={1},C={2}(2)否:A={1},B={1,2},C={1,2,3}(3)是:∵ A⊕B=A⊕C∴ A⊕(A⊕B)=A⊕(A⊕C)(A⊕A)⊕B=(A⊕A)⊕Cφ⊕B=φ⊕CB=C,P85#11,證明：對任意的x?A?x?B x?A① x?C?x?A∩C (A∩C? B∩C)?x?B∩C?

23、x?B ② x?C? x?~C? x?A∩~C(A∩~C?B∩~C)? x?B∩~C ?x?B,P85#12,(1)必要性：已知C?A，證明 (A∩B)∪C=A∩(B∪C)左式＝(A∩B)∪C= (C∪B) ∩(A∪C) (∵ C?A)=A∩(B∪C)=右式,P85#12（續(xù)）,(2)充分性：已知(A∩B)∪C=A∩(B∪C) 證明C?A對任意的x

24、?C? x? (A∩B)∪C? x? A∩(B∪C) (∵(A∩B)∪C=A∩(B∪C))? x? A ∴ C?A,P85#17(1),A-(B∪ C)=A∩ ~ (B∪ C)= A∩ ~B ∩~C=(A∩ ~B) ∩(A ∩~C)=(A-B) ∩(A-C),第四章二元關(guān)系,(1)掌握關(guān)系矩陣和關(guān)系圖的表示方法。(2)掌握合成運算、逆運算、閉包運算的概念。(3)熟練掌握關(guān)系的性質(zhì)（自反性、反自反性、對稱性、反對稱

25、性、可傳遞性）及其判別方法。,第四章二元關(guān)系（續(xù)）,(4)掌握等價關(guān)系（自反、對稱、可傳遞）和偏序關(guān)系（自反、反對稱、可傳遞）的概念及證明。(5)掌握等價關(guān)系和劃分之間的相互關(guān)系。(6)掌握偏序關(guān)系和哈斯圖，并會求極大（?。┰?、最大（?。┰?、上（下）界、上（下）確界。,P125#10,(2)對任意的?R∩S?R∧?S?R∧?S (∵R、S是對稱的)? R∩S∴ R∩S是對稱的,P125#12,(1)對任意的?R1°R3?(

26、?y) ( ?R1∧ ? R3) ?(?y) ( ?R2∧ ? R3) (∵R1 ? R2 )??R2°R3∴ R1°R3 ? R2°R3,P125#13,(1)T.對任意的x?X∵ R1和R2都是自反的，∴?R1∧?R2 ? ? R1°R2 ∴ R1°R2都是自反的,P125#13,(2)F.R1 ={,}是對稱的；R2 ={,}是對稱的；但是R1°R2 ={}不是對稱的。,P125#13,(3)F.R1 ={

27、,}是反對稱的；R2 ={,}是反對稱的；但是R1°R2 ={,}不是反對稱的。,P125#13,(4)F.R1 ={,}是可傳遞的；R2 ={,}是可傳遞的；但是R1°R2 ={,}不是可傳遞的。,,,P126#22,(1)必要性：,R是等價關(guān)系,? R是循環(huán)的,對于任意的?R∧?R,(R是可傳遞的),??R,(R是對稱的),??R,,,R是循環(huán)的,,,,,證明（續(xù)）,(2)充分性：,R是自反和循環(huán)的,? R是等價關(guān)系,對稱

28、性:,對于任意的?R,（R是自反的）,? ?R ∧?R,（R是循環(huán)的）,? ?R,,,R是對稱的,可傳遞性:,對于任意的?R∧?R,（R是循環(huán)的）,? ?R,(R是對稱的),??R,,,R是可傳遞的,P126#23,只需證明自反性：對任意的a ?A??R(由定義可知）??R∧?R（R是對稱的）??R（R是可傳遞的）,,,P126#24,（1）自反性：,R是自反的,對任意的a?X,? ?R,等冪率,? ?R∧?

29、R,(S的定義),? ?S,,,S是自反的,,,證明（續(xù)）,（2）對稱性：,對任意的?S,(S的定義),?(?c)(?R∧?R),R是對稱的,? (?c)(?R∧?R),(S的定義),??S,,,S是對稱的,,,證明（續(xù)）,(3)可傳遞性：,對任意的?S ∧?S,(S的定義),?(?d)(?R∧?R)),∧(?e) (?R∧?R)),（R是可傳遞的）,? ?R ∧?R,(S的定義),? ?S,,,R是可傳遞的,P126#25,(1)充分

30、性：已知R是自反的，?R∧?R→?R證明： R是等價關(guān)系①對任意的?R（ R是自反的）??R∧?R（定義）? ?R 所以：R是對稱的；②對任意的?R ∧?R??R ∧?R（ R是對稱的）? ?R （定義）所以：R是可傳遞的。,證明（續(xù)）,(2)必要性：已知R是等價關(guān)系，證明： ?R∧?R→?R對任意的?R∧?R（ R是對稱的）??R∧?R（ R是可傳遞的）? ?R,P126#26,(1)自反

31、性：∵ R是集合X上的等價關(guān)系，∴ R是自反的，即：對任意的x? X，均有：?R??R-1 ∴R-1是自反的,P126#26,(2)對稱性：對任意的?R-1?R(由逆關(guān)系的定義) ?R(∵ R是對稱的)?R-1(由逆關(guān)系的定義)∴R-1是對稱的,P126#26,(3)可傳遞性：對任意的?R-1∧?R-1 ?R ∧?R (由逆關(guān)系的定義)?R ∧?R ?R(∵ R是可傳遞的)? R-1

32、(由逆關(guān)系的定義)∴ R-1是可傳遞的∴ R-1是集合X上的等價關(guān)系。,P126#30,[1]R={1,6,11,16}[2]R={2,7,12,17}[3]R={3,8,13,18}[4]R={4,9,14,19}[5]R={5,10,15,20}S/R={[1]R, [2]R, [3]R, [4]R, [5]R}={{1,6,11,16}, {2,7,12,17}, {3,8,13,18}, {4,9,14,1

33、9}, {5,10,15,20}},P127#42,(2)A={1,3,5,9,15,18,27,36,45,54}R={,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,}COV(A)={,, ,, , ,, , , ,, },P127#42,(3)A={1,2,3,4,5,6,7,8,9,10,11,12}R={,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,}COV(A)={,,

34、 , , ,,, ,, ,, , },P127#43,? ={,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,},解答（續(xù)）,COV(L)={, , , , ,, , ,},P127#44,(1)x4Rx1、x3Rx3、x1Rx1、x5Rx1是真的；(2)、(3),P127#44,P127#45(1),R1={,,,,,,,}COV(X)={,, },P127#45(2),R2={, ,,,,,,}COV(X

35、)={,, ,},P127#45(3),R3={, ,,,,,,,}COV(X)={, , },P127#45(4),R4={, ,,,,,,}COV(X)={, , },第四章函數(shù),一、主要內(nèi)容二、本章要點,一、主要內(nèi)容,1、函數(shù)的基本概念2、函數(shù)的性質(zhì)3、特種函數(shù)4、復合函數(shù)5、逆函數(shù),1、函數(shù)的基本概念,設(shè)f是從集合X到Y(jié)上關(guān)系，若對任意的x?X都存在唯一的y?Y，使?f，則稱關(guān)系f為函數(shù)（或映射），記作：

36、f: X→Y。(1)對于函數(shù)f: X→Y，如果﹤x，y﹥?f，也寫成y=f(x), 并稱x為自變量，y稱為函數(shù)在x處的值，或稱y為在函數(shù)f的作用下x的像點，相應(yīng)地稱x為y的原像。(2)對于函數(shù)f: X→Y，則稱X為函數(shù)f的定義域，Y稱為f的陪域；Rf是f的值域。,2、函數(shù)的性質(zhì),設(shè)函數(shù)f: X→Y,則f滿足下面兩個性質(zhì)：(1)任意性：函數(shù)的定義域必須是集合X，即：Df = X；(2)唯一性：對任意的x?X，必存在唯一的y?Y，

37、使?f，即：對任意的x?X，y，z?Y，有：?f∧?f ? y = z。,3、特種函數(shù),設(shè)函數(shù)f: X→Y,則：(1)若f(X)=Rf=Y, 則稱f是滿射的；(2)對任意x1,x2?X，如果:x1≠x2?f(x)≠f(y),或:f(x1)=f(x2)?x1 =x2； 則稱f是單射的；(3)若f是既是滿射的，又是單射的，則稱f是雙射的。,4、復合函數(shù),給定函數(shù)f: X→Y，g: X→Z，則：gｏf=｛│x?X∧z?Z∧(?

38、y) (f∧g)｝則稱gｏf為f和g的合成函數(shù)（或復合函數(shù)）。,5、逆函數(shù),如果f是個雙射函數(shù)，則f的逆關(guān)系稱為f的逆函數(shù)（或反函數(shù)），并記作：f–1。,相關(guān)定理,定理1 設(shè)函數(shù)f: A→B，所有從A到B的函數(shù)的集合{ f | f: A→B}，記作BA，如果|A|＝m, |B|=n,則|BA|＝nm 。 定理2 設(shè)函數(shù)f: X→Y，g: Y→Z，則復合函數(shù)gｏf是從X→Z上的函數(shù)，并對任意的xX，都有：（gｏf）（x）= g (f

39、 (x) )。,相關(guān)定理（續(xù)）,定理3 函數(shù)的復合運算是可結(jié)合的，即如果f、g和h都是函數(shù)，則有： （gｏf）ｏh = gｏ(fｏh) = gｏfｏh定理4 設(shè)函數(shù)f: X→Y，f的逆關(guān)系f –1是從Y→X上函數(shù)，當且僅當f是個雙射函數(shù)。,二、本章要點,1、掌握函數(shù)的定義（任意性、唯一性）:設(shè)f是從集合X到Y(jié)的關(guān)系，即f:X→Y，若對任意的x?X都存在唯一的y?Y，使 ? f，或y=f(x)，則稱關(guān)系f為函數(shù)（或映射）

40、注意：函數(shù)和關(guān)系的聯(lián)系和區(qū)別。,本章要點（續(xù)）,2、掌握合成函數(shù)的概念：設(shè)函數(shù)f: X→Y ,g: Y→Z,則: g?f={|x∈X∧z∈Z∧(?y)(y∈Y∧y=f(x)∧z=g(y))}稱為f和g的合成函數(shù)（復合函數(shù)）。注意：合成關(guān)系和合成函數(shù)書寫格式的區(qū)別。,本章要點（續(xù)）,3、掌握反函數(shù)的概念及其存在的條件：設(shè) f: X→Y是雙射函數(shù)，則f的逆關(guān)系稱f的反函數(shù)，記作f-1注意：只有雙射函數(shù)才有反函數(shù)。,本章要點

41、（續(xù)）,4、掌握特種函數(shù)的定義（單射、滿射、雙射）及證明：①滿射函數(shù)：設(shè)函數(shù)f: X→Y，若f(X)=Rf=Y（值域＝陪域）。②單射函數(shù)：設(shè)函數(shù)f: X→Y，對任意x1，x2　∈X，如果： x1≠x2 ?f(x1)≠f(x2)或 f(x1)=f(x2) ? x1=x2；,P148#3,(1)任意性：對于ρ(E)×ρ(E)中的任意一個元素,根據(jù)f的定義有：f()=S1∩S2? E,即： S1∩S2? ρ(E)(2

42、)惟一性：假設(shè)ρ(E)×ρ(E)中的某一個元素在ρ(E)中有兩個象點S和S′ ,即：f()=S1∩S2 =S和f()=S1∩S2 =S′即： S1∩S2 =S =S′(3)滿射：對任意的S?ρ(E)，在ρ(E)×ρ(E)中至少有一個原像，使得： f()=S∩S＝S,P148#6,(1)從X到Y(jié)的不同的單射函數(shù)：P|X||Y|(2)從X到Y(jié)的不同的雙射函數(shù)：m!(3)存在單射函數(shù)的必要條件:|X|≤ |Y|

43、(4)存在滿射函數(shù)的必要條件:|X|≥ |Y|(5)存在雙射函數(shù)的必要條件:|X|=|Y|,P148#10,(1)必要性：已知g°f=IX、 f°g = IY證明：g=f-1先證明f是雙射函數(shù)：∵恒等函數(shù)IX是雙射，所以g°f：X→X是雙射，∴f是單射。∵恒等函數(shù)IY是雙射，所以f°g：Y→Y是雙射， ∴ f是滿射?！?f是雙射函數(shù)，即： f反函數(shù)存在。,P148#10,再證明：g=f-1∵ g：Y→X，f-1：Y→X對

44、于任意的y?Y，由f-1：Y→X，令f-1(y)=x?X?f(x)=yg(y)=g(f (x))=g°f(x)=IX(x)=x= f-1(y)，所以，g=f -1,P148#10,(2)充分性：已知：g=f-1，證明： g°f=IX、 f°g = IYg°f(x)=g(f(x))= f-1 (f(x))= f-1°f(x)= IX(x) ∴ g°f=IXf°g (y)=f(g(y))=f(f-1 (y))= f°f-1(

45、y) = Iy(y) ∴ f°g = IY,P148#11,f(x)=2x+1,g(x)=x2-2g?f(x)=g(f(x))=g(2x+1)=(2x+1)2-2=4x2+4x-1f?g(x)=f(g(x))=f(x2-2)=2(x2-2)+1=2x2-3((g?f)?f)(x)=(g?f)(f(x))=(g?f)(2x+1)=4(2x+1)2+4(2x+1)-1=4(4x2+4x+1)+8x+4-1=16x2+24x+7g?

46、f2(x)= g?f(f(x))= g?f(2x+1)=g(f(2x+1))=g(2(2x+1)+1))=g(4x+3)=(4x+3)2-2=16x 2 +24x+9-2= 16x2+24x+7,P148#12,f(n)=n+1,g(n)=2n,f?f(n)=f(f(n)=f(n+1)=n+1+1=n+2f?g(n)=f(g(n))=f(2n)=2n+1g?f(n)=g(f(n))=g(n+1)=2(n+1)g?h(n)=

47、g(h(n)),P148#12（續(xù)）,h?g(n)=h(g(n))=h(2n)=0f?g?h(n),P149#15,設(shè)f={,,}是單射函數(shù)，且f≠IXf ? f={,,}f ? f ? f = {,,}f-1= {,,}f ? f-1={,,}= IXg={,,}是單射函數(shù)，且f≠IX g ? g={,,} = IX,第五章代數(shù)結(jié)構(gòu),一、主要內(nèi)容二、本章要點,一、主要內(nèi)容,1. 代數(shù)運算2. 二元運算的性質(zhì)

48、3．二元運算的特異元 4. 可約的或可消去的 5. 代數(shù)系統(tǒng)的概念 6. 同態(tài)與同構(gòu)的概念 7. 代換性質(zhì)和同余關(guān)系8. 商代數(shù)與積代數(shù)9.半群和群,1. 代數(shù)運算,設(shè)X集合，f是從Xn →X上映射，則稱f為集合X中的n元運算。特別是：(1)當n=1時，f：X →X稱為集合X中的一元運算；(2)當n=2時，f：X×X →X稱為集合X中的二元運算。如果對給定的集合中的元素進行運算，從而產(chǎn)生了像點，而該像點

49、又是該集合中的元素，則稱給定的運算對該集合封閉。在上述的代數(shù)運算的定義中蘊含著對集合的封閉性。,2. 二元運算的性質(zhì),設(shè)°和*為集合X上的二元運算，與這些運算相關(guān)的性質(zhì)有：(1)交換律：x，y?Ｘ，有 x°y=y°x；(2)結(jié)合律：x,y,z?Ｘ，有:(x°y)°z=x°(y°z)；(3)等冪律：x?Ｘ有x°x=x； (4)分配律：x,y,z?Ｘ有:x°(y*z)=(x°y)* (x°z),3．二元運算的特異元,(1)幺元

50、(2)零元(3)逆元,(1)幺元,設(shè)*為Ｘ上的二元運算，則:(1)如果(?el)(el?X∧(?x)(x?X→el*x=x))，則稱el為集合X關(guān)于運算*的左幺元；(2)如果(?er)(er?X∧(?x)(x?X→x*er=x))，則稱er為集合X關(guān)于運算*的右幺元；(3)如果運算的左幺元和右幺元同時存在，則必有el=er=e，使得對任意的x?X，有:x*e=e*x=x并稱e為運算*的幺元且幺元e是惟一的。,(2)零元,(1

51、)如果(?0l)(0l ?X∧(?x)(x?X→0l*x=0l))，則稱0l為集合X關(guān)于運算*的左零元；(2)如果(?0r)(0r ?X∧(?x)(x?X→x*0r=0r))，則稱0r為集合X關(guān)于運算*的右零元； (3)如果運算的左零元和右零元同時存在，則必有0l=0r=0，使得對任意的x?X，有:x*0=0*x=0并稱0為運算*的零元。,(3)逆元,設(shè)*為Ｘ上的二元運算，且X中對于運算存在幺元e。令x?X。(1)

52、如果(?xl)(xl?X∧xl*x=e)，則稱xl是x的左逆元，并稱x是左可逆的；(2)如果(?xr)(xr?X∧x*xr=e)，則稱xr是x的右逆元，并稱x是右可逆的；(3)如果元素x既是左可逆的，又是右可逆的，則稱x是可逆的。,4. 可約的或可消去的,設(shè)為代數(shù)系統(tǒng)，且a?X，如果對任意的x，y?X有： （a*x=a*y）∨（x*a=y*a）?x = y則稱a是可約的或可消去的。,5. 代數(shù)系統(tǒng),設(shè)X是一個非空集合，?為

53、X上的代數(shù)運算構(gòu)成的非空集合，則稱序偶為一個代數(shù)系統(tǒng)（或代數(shù)結(jié)構(gòu)），其中：(1)集合X為代數(shù)系統(tǒng)的定義域。如果X是個有限集合，則稱為有限代數(shù)系統(tǒng)，│X│=n為代數(shù)系統(tǒng)的階；否則稱為無限代數(shù)系統(tǒng)。(2)?=?1，?2，…?n｝為X中的n元運算（n=1，2，3，…）構(gòu)成的集合，如果?為有限集合，則可將表示為：。,6. 同態(tài)與同構(gòu)的概念,設(shè)U＝，V＝是兩個代數(shù)系統(tǒng)，ｏ和*是二元運算，函數(shù)f：X→Y，如果對任意的x，yX有: f(xｏy)

54、=f(x)*f(y) (運算的像=像的運算)則稱f是代數(shù)系統(tǒng)U到V同態(tài)映射(簡稱同態(tài))，并稱代數(shù)系統(tǒng)U與V同態(tài)。(1) 如果f是滿射的，則稱f 是從U到V的滿同態(tài)；(2) 如果f是單射的，則稱f 是從U到V的單一同態(tài)；(3) 如果f是雙射的，則稱f 是從U到V的同構(gòu)。(4) 如果U=V，則稱f是從U到U的自同構(gòu)。,7. 代換性質(zhì)和同余關(guān)系,代換性質(zhì)：給定代數(shù)系統(tǒng)，其中是個二元運算。設(shè)R是X中的等價關(guān)系，如果對任意的x1，x

55、2?X和y1，y2?X有： (x1Rx2)∧(y1Ry2)?(x1*y1)R(x2*y2)則稱等價關(guān)系E對于運算具有代換性質(zhì)。同余關(guān)系：給定代數(shù)系統(tǒng)U=，且R是集合X中的等價關(guān)系。如果等價關(guān)系R對運算具有代換性質(zhì)，則稱R是代數(shù)系統(tǒng)U中的同余關(guān)系。,8. 商代數(shù)與積代數(shù),給定代數(shù)系統(tǒng)U=，其中ｏ是個二元運算，R是U中的同余關(guān)系。試構(gòu)成一個新的代數(shù)系統(tǒng)W=，其中(1)X/R=｛[x]R │x?X｝；(2)對任意的x1,x2

56、?X,有[x1]R?[x2]R=[x1ｏx2]R則稱代數(shù)系統(tǒng)W為U的商代數(shù)，簡稱商代數(shù)，并記作U/R。,商代數(shù)與積代數(shù)（續(xù)）,設(shè)U＝，V＝是代數(shù)系統(tǒng)，試構(gòu)成一個新的代數(shù)系統(tǒng)：U×V = 其中X×Y是X和Y的笛卡兒乘積，且運算?的定義為：對任意的x1，x2?X和y1，y2?Y有,>＝則稱U×V是U和V的積代數(shù)，U和V是U×V的因子代數(shù)。,9.半群和群,半群：設(shè)是代數(shù)系統(tǒng)，*運算是S上

57、的二元運算，若*運算是可結(jié)合的，則稱為一個半群。群：（1）是代數(shù)系統(tǒng)；（2） “*”運算滿足結(jié)合律；（3）中存在幺元e；（4）中任意一個元素都有逆元素； 則稱代數(shù)系統(tǒng)是群。,子群,設(shè)是一個群，H是A的非空子集，若也是一個群，則稱是的子群。,阿貝爾群和循環(huán)群,若群對運算“*”滿足交換律，則稱是阿貝爾群（交換群）。若群中每個元素均是它的某個 元素a的整數(shù)冪，則

58、稱是由a生成的循環(huán)群。a稱為的生成元素。,二、本章要點,(1)理解代數(shù)運算以及代數(shù)運算的性質(zhì)（結(jié)合律、交換律、分配律、等冪律、消去律）。(2)掌握代數(shù)系統(tǒng)和子代數(shù)系統(tǒng)的定義，理解運算的封閉性。(3)給定集合和運算，會判別運算對該集合是否封閉。,本章要點（續(xù)）,(4)給定二元運算，說明運算是否滿足交換律、結(jié)合律、等冪律、分配律和消去律。 (5)掌握和理解幺元、零元、逆元的概念,給定—個集合和該集合上的二元運算，會求該運算的幺元、零元

59、和逆元。(6)掌握和理解同態(tài)、滿同態(tài)、單一同態(tài)和同構(gòu)的概念和性質(zhì),并會求解（證）相關(guān)問題。,(7)掌握半群、獨異點、群、子群的概念及相關(guān)的證明。(8)理解阿貝爾群、循環(huán)群的概念。,本章要點（續(xù)）,P166#4,設(shè)*運算是X中的可結(jié)合的二元運算，并且對任意的x,y? X,若x*y=y*x，則x=y。證明：X中的每個元素都是等冪的。,證明,對任意的x ? X,要證明x是等冪的，即證明：x*x=x因為：*運算是X中的可結(jié)合的二元運

60、算所以：x*(x*x)=(x*x)*x由已知：x*y=y*x?x=y得：x*x=x,P167#9,左式＝a*(b*c)（因為a*a=a）=(a*a)*(b*c) （因為(a*b)*(c*d)=(a*c)*(b*d)）=(a*b)*(a*c)=右式,P167#13,已知：*運算可交換，f1,f2均為同態(tài)映射，且：g(a)=f1(a)*f2(a)證明：g也為同態(tài)映射對任意的a,b屬于A，證明:g(a °b)=g(a)*g(b)

61、g(a °b)=f1(a °b)*f2(a °b )= (f1(a)*f1(b))*(f2(a)*f2(b))=(f1(a)*f2(a))*(f1(b)*f2(b))=g(a)*g(b),P168#17,對任意的X的子集S?ρ(X),設(shè)f(S)=～S運算的像＝f(S1∩S2)=~(S1∩S2)=~S1∪~S2=f(S1)∪f(S2)=像的運算,5、P196#5,設(shè)是半群，對于A中的每一個元素a和b，若a≠b，則有：a*b

62、≠b*a（1）證明對于A中的一切a，有a*a=a。（2）對于A中任意的a和b，證明a*b*a=a。（3）對于A中任意的a,b和c，證明a*b*c=a*c。,提示：a*b=b*a?a=b,證明（1）a*a=a,要證明:a*a=a，由提示可知，只需要證明：(a*a)*a=a*(a*a)證明： 因為是半群，*運算可結(jié)合，所以：(a*a)*a=a*(a*a)?a*a=a,證明（2） a*b*a=a,要證明: a*b*a=a ，由

63、提示可知，只需要證明：(a*b*a)*a=a*(a*b*a)證明：(a*b*a)*a（*運算可結(jié)合）＝a*b*(a*a)（由（1））=a*b*a （由（1））=(a*a)*b*a（*運算可結(jié)合）=a*(a*b*a)（由提示）? a*b*a=a,證明（3） a*b*c=a*c,要證明: a*b*c=a*c ，由提示可知，只需要證明：(a*b*c)*(a*c)=(a*c)*(a*b*c)證明：(

64、a*b*c)*(a*c) （*運算可結(jié)合）=a*b*(c*a*c) （由（2））=a*b*c （由（2））=(a*c*a)*b*c （*運算可結(jié)合）=(a*c)*(a*b*c) （由提示）? a*b*c=a*c,P197#6,設(shè)是半群，其中A=?a,b?，且a*a=b。證明：⑴ *是可交換運算。⑵ b=b2。,解答,⑴因為a*b=a*a2=a3=a2*a=b*a所以*是可交換運算。⑵b*b=(a*

65、a)*b=a*(a*b)①若a*b=a,則：a*(a*b)=a*a=b②若a*b=b,則：a*(a*b)=a*b=b所以： b*b=b,P198#17,設(shè)是個有限可交換含幺半群，對任意的 a,b,c?S，若a*b=a*c，則b=c。證明：是個阿貝爾群。,證明,只需證明S中的每一個元素均可逆即可。是個有限可交換含幺半群，所以S是個有限集合，設(shè):S={a1,a2,…,an}對任意的a?S，則：a*a1?S,…,a*an?S,所以

66、：{a*a1,a*a2,…,a*an}?S 由已知：a*b=a*c?b=c所以：逆反命題也成立，即：b≠c?a*b≠a*c所以：{a*a1,a*a2,…,a*an}=S,證明： （續(xù)）,因為：是個有限可交換含幺半群，所以：存在幺元e,且必存在某個元素ak?S,使得： a*ak =e (1≤k≤n)因為：*運算可交換所以： a*ak=ak*a=e，即：a的逆元是ak由a的任意性可知：S中的每一個元素都可逆所以： 是群。

67、,P198#18,證明：如果群中每個元素的逆元是其自身，則該群必是阿貝爾群。,證明,對任意的a, b?G，則a*b?G因為：群中每個元素的逆元是其自身所以：a*a=e,b*b=e,…(a*b)*(a*b)=(a*b)2=ea*b=e*(a*b)*e=b2*(a*b)*a2=b*(b*a)*(b*a)*a=b*e*a=b*a所以是交換群。,P198#19,試證明，在群中：（1）如果對任意的a?G,有a2=e,則是個阿貝爾群；（

68、同P198#18）（2）如果對任意的a,b?G,有(a*b)2=a2*b2,則是個阿貝爾群；,證明（2）,對任意的a,b?G,因為：(a*b)2=a2*b2?(a*b)*(a*b)=a*a*b*b?(a-1*a)*b*a*(b*b-1)=(a-1*a)*a*b*(b*b-1)?e*b*a*e =e*a*b*e?b*a=a*b,P198#25,(1)顯然S?G(2)封閉性：對任意的a,b ?S，證明a*b ?S,即證明對任意