离散数学期末复习纲要

〔1〕需要熟练掌握的知识点包括：命题的定义、逻辑联结词、命题变元、命题公式〔合式公式〕、永真式、永假式、可满足式、等价式、蕴涵式、极小项、极大项、主析取范式、主合取范式。第1章命题逻辑重点〔2〕掌握根本的等价式和蕴涵式，并掌握常用的等价式和蕴涵式的证明方法〔替换规那么和推论规那么〕。第1章命题逻辑重点〔续〕〔3〕要能准确地求出命题公式的主析取范式和主合取范式。掌握主析取范式和主合取范式与真值表的对应关系，主析取范式和主合取范式的关系。第1章命题逻辑重点〔续〕〔4〕掌握命题符号化的原那么；〔5〕熟练掌握四个推论规那么〔P、T、CP、F〕进行有效性论证。第1章命题逻辑重点〔续〕证明等价式: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↔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

∧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)011011∑(m1,m2,m3)

∏(M0)

P∨Q求命题公式的主范式P42#17(6)(P→Q∧R))∧(

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)

∏(M1,M2,M3,M4,M5,M6)∑(m0,m7)(P∧

Q∧

R)∨(P∧Q∧R)CP规那么的使用P42#22(3)(P∨Q)→R(P∧Q)→RP∧Q P规那么〔附加前提〕P T规那么(1)Q T规那么(1)P∨Q T规那么(2)(3)(P∨Q)→R P规那么R T规那么(4)(5)(P∧Q)→R CP规那么(1)(6)F规那么的使用P43#23(2)S→Q,R∨S,R,P↔QPP P规那么〔假设前提〕P↔Q P规那么Q T规那么〔1〕〔2〕S→Q P规那么S T规那么〔3〕〔4〕R∨S P规那么R T规那么〔5〕〔6〕R P规那么R∧R T规那么〔1〕〔8〕矛盾式P F规那么〔1〕〔9〕符号化并验证结论的有效P43#25(1)1〕如果6是偶数，那么2不能整除7；2〕或者5不是素数，或者2整除7；3〕5是素数；结论：因此6是奇数。符号化P:6是偶数;Q:2能整除7;R:5是素数;如果6是偶数，那么2不能整除7:P→Q或者5不是素数，或者2整除7:R∨Q5是素数:R

6是奇数:P证明R P规那么R∨Q P规那么Q T规那么(1)(2)P→Q P规那么P T规那么(3)(4)P→QR∨QR

PP43#25(6)符号化:P:今天是星期二;Q:我们有离散数学测验;R:我们有高等数学测验;S:高等数学老师生病;P→Q∨RS→RP∧S

QP43#25(6)(续)P→Q∨RS→RP∧S

Q(1)P∧S (P规那么)(2)P (T规那么(1))(3)S (T规那么(1))(4)S→R (P规那么)(5)R (T规那么(3)(4))(6)P→Q∨R (P规那么)(7)Q∨R (T规那么(2)(6))(8)Q (T规那么(5)(7))第2章 谓词逻辑重点〔1〕需要熟练掌握的知识点包括：谓词、全称量词(x)、存在量词(x)、个体、个体域、个体变元〔约束变元和自由变元〕、谓词公式的解释〔永真、永假、可满足〕、谓词公式的根本的等价式和蕴涵式。第2章 谓词逻辑重点〔续〕〔2〕在符号化时要特别注意量词和逻辑联结词的搭配：全称量词对应逻辑联结词“→〞，存在量词对应逻辑联结词“∧〞。〔3〕在谓词逻辑推理的证明中，要特别注意US，ES，UG，EG规那么成立的条件〔用ES规那么指定的个体不能用UG规那么加以推广〕。符号化并证明结论的有效性P64#18(1)1〕所有有理数是实数；2〕某些有理数是整数；结论：某些实数是整数。

符号化特性谓词:Q(x):x是有理数；I(x):x是整数；R(x):x是实数；(

x)(∧)所有有理数是实数：(

x)(→)Q(x)R(x)某些有理数是整数:(

x)(∧)Q(x)I(x)

某些实数是整数: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规那么(2)Q(a)∧I(a) ES规那么(3)Q(a) T规那么〔2〕(4)I(a) T规那么〔2〕(5)(x)(Q(x)→R(x)) P规那么 (6)Q(a)→R(a) US规那么(5)(7)R(a) T规那么〔3〕(6)(8)R(a)∧I(a) T规那么〔4〕(7)(9)(x)(R(x)∧I(x)) UG规那么(8)首先使用含有存在量词的前提符号化并证明结论的有效性P64#18(2) 任何人如果他喜欢步行，他就不喜欢乘车。每个人或者喜欢乘车或者喜欢骑自行车；有的人不爱骑自行车，因而有的人不爱步行。符号化特性谓词: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)每个人或者喜欢乘车或者喜欢骑自行车:(

x)(→)P(x)(T(x)∨R(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)),(x)(P(x)∧R(x))(x)(P(x)∧W(x))(x)(P(x)∧R(x)) P规那么P(a)∧R(a) ES规那么P(a) T规那么(2)R(a) T规那么(2)(x)(P(x)→(T(x)∨R(x)) P规那么P(a)→(T(a)∨R(a)) US规那么(5)T(a)∨R(a) T规那么(3)(6)T(a) T规那么(4)(7)(x)(P(x)→(W(x)→T(x)) P规那么P(a)→(W(a)→T(a)) US规那么(9)W(a)→T(a) T规那么(3)(10)W(a) T规那么(8)(11)P(a)∧W(a) T规那么(3)(12)(x)(P(x)∧W(x)) EG规那么(13)首先使用含有存在量词的前提符号化并证明结论的有效性P64#18(3)任何人违反交通规那么，都要被罚款，因此，如果没有罚款，那么没有人违反交通规那么。符号化特性谓词:M(x):x是人；P(x):x违反交通规那么；Q(x):x被罚款。任何人违反交通规那么，都要被罚款：(

x)(→)M(x)(P(x)→Q(x)(

x)(→)(M(x)∧P(x)Q(x)如果没有罚款，那么没有人违反交通规那么：

(

x)Q(x)→

(

x)(M(x)∧P(x))证明(x)(M(x)→(P(x)→Q(x))(x)Q(x)→(x)(M(x)∧P(x))(x)Q(x) P规那么〔附加前提〕(x)Q(x) T规那么(1)Q(a) US规那么(2)(x)(M(x)→(P(x)→Q(x)) P规那么M(a)→(P(a)→Q(a)) US规那么(4)M(a)∨P(a)∨Q(a) T规那么(5)M(a)∨P(a) T规那么(3)(6)(M(a)∧P(a)) T规那么(7)(x)(M(a)∧P(a)) UG规那么(8)(x)(M(x)∧P(x)) T规那么(9)(x)Q(x)→(x)(M(x)∧P(x)) CP规那么(1)(10)第三章 集合(1)掌握集合的根本概念及其表示，集合之间的关系〔子集、真子集〕、元素与集合的关系〔属于〕、全集、空集、幂集、笛卡尔乘积等概念。(2)能熟练地证明集合中的相等关系、包含关系。(3)掌握集合的五种根本运算：~A、A∩B、A∪B、A-B、A⊕B及集合运算的根本定律。P84#4A={1}B={{1}}C={{{1}}}满足：A∈B,B∈C,但是A

CP84#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∴B-A=C-AB=(A∩B)∪(B-A)=(A∩C)∪(C-A)=CP84#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=CP85#11证明：对任意的x

A

x

Bx

A①x

C

xA∩C (A∩C

B∩C)

xB∩C

xB

②x

C

x~C

xA∩~C (A∩~CB∩~C)

xB∩~C

xB

P85#12(1)必要性：CA，证明(A∩B)∪C=A∩(B∪C)左式＝(A∩B)∪C=(C∪B)∩(A∪C)(∵CA)=A∩(B∪C)=右式

P85#12〔续〕(2)充分性：(A∩B)∪C=A∩(B∪C)证明CA对任意的xCx(A∩B)∪CxA∩(B∪C)(∵(A∩B)∪C=A∩(B∪C))xA∴CAP85#17(1)A-(B∪C)=A∩~(B∪C)=A∩~B∩~C=(A∩~B)∩(A∩~C)=(A-B)∩(A-C)第四章二元关系(1)掌握关系矩阵和关系图的表示方法。(2)掌握合成运算、逆运算、闭包运算的概念。(3)熟练掌握关系的性质〔自反性、反自反性、对称性、反对称性、可传递性〕及其判别方法。第四章二元关系〔续〕(4)掌握等价关系〔自反、对称、可传递〕和偏序关系〔自反、反对称、可传递〕的概念及证明。(5)掌握等价关系和划分之间的相互关系。(6)掌握偏序关系和哈斯图，并会求极大〔小〕元、最大〔小〕元、上〔下〕界、上〔下〕确界。P125#10(2)对任意的<x,y>R∩S<x,y>R∧<x,y>S<y,x>R∧<y,x>S

(∵R、S是对称的)<y,x>R∩S∴R∩S是对称的P125#12(1)对任意的<x,z>R1∘R3(y)(<x,y>R1∧<y,z>R3)(y)(<x,y>R2∧<y,z>R3)(∵R1R2)

<x,z>R2∘R3∴

R1∘R3

R2∘R3P125#13(1)T.对任意的xX∵R1和R2都是自反的，∴<x,x>R1∧<x,x>R2

<x,x>R1∘R2

∴R1∘R2都是自反的P125#13(2)F.R1={<a,b>,<b,a>}是对称的；R2={<b,c>,<c,b>}是对称的；但是R1∘R2={<a,c>}不是对称的。P125#13(3)F.R1={<a,b>,<c,a>}是反对称的；R2={<b,c>,<a,a>}是反对称的；但是R1∘R2={<a,c>,<c,a>}不是反对称的。P125#13(4)F.R1={<a,d>,<b,e>}是可传递的；R2={<d,b>,<e,c>}是可传递的；但是R1∘R2={<a,b>,<b,c>}不是可传递的。P126#22(1)必要性：R是等价关系

R是循环的对于任意的<x,y>R∧<y,z>R(R是可传递的)

<x,z>R(R是对称的)

<z,x>R R是循环的证明〔续〕(2)充分性：R是自反和循环的

R是等价关系对称性:对于任意的<x,y>R〔R是自反的〕

<x,x>R∧<x,y>R〔R是循环的〕

<y,x>RR是对称的可传递性:对于任意的<x,y>R∧<y,z>R〔R是循环的〕

<z,x>R(R是对称的)

<x,z>RR是可传递的P126#23只需证明自反性：对任意的aA<a,b>R (由定义可知〕<a,b>R∧<b,a>R 〔R是对称的〕<a,a>R 〔R是可传递的〕P126#24〔1〕自反性：R是自反的对任意的aX

<a,a>

R等幂率

<a,a>

R∧<a,a>

R(S的定义)

<a,a>S S是自反的证明〔续〕〔2〕对称性：对任意的<a,b>

S(S的定义)(c)(<a,c>

R∧<c,b>

R)R是对称的(c)(<b,c>

R∧<c,a>

R)(S的定义)

<b,a>

SS是对称的证明〔续〕(3)可传递性：对任意的<a,b>

S∧<b,c>

S(S的定义)(d)(<a,d>

R∧<d,b>

R))∧(e)(<b,e>

R∧<e,c>

R))〔R是可传递的〕

<a,b>

R∧<b,c>

R(S的定义)

<a,c>SR是可传递的P126#25(1)充分性：R是自反的，<a,b>R∧<a,c>R→<b,c>R证明：R是等价关系①对任意的<a,b>R 〔R是自反的〕<a,b>R∧<a,a>R 〔定义〕<b,a>R所以：R是对称的；②对任意的<a,b>R∧<b,c>R<b,a>R∧<b,c>R 〔R是对称的〕<a,c>R 〔定义〕所以：R是可传递的。证明〔续〕(2)必要性：R是等价关系，证明：<a,b>R∧<a,c>R→<b,c>R对任意的<a,b>R∧<a,c>R〔R是对称的〕<b,a>R∧<a,c>R 〔R是可传递的〕<b,c>RP126#26(1)自反性：∵R是集合X上的等价关系，∴R是自反的，即：对任意的x

X，均有：<x,x>R<x,x>R-1

∴R-1是自反的P126#26(2)对称性：对任意的<x,y>R-1<y,x>R (由逆关系的定义)

<x,y>R (∵R是对称的)<y,x>R-1 (由逆关系的定义)∴R-1是对称的P126#26(3)可传递性：对任意的<x,y>R-1∧<y,z>R-1<y,x>R

∧<z,y>R (由逆关系的定义)<z,y>R∧<y,x>R

<z,x>R (∵R是可传递的)<x,z>R-1 (由逆关系的定义)∴R-1是可传递的∴R-1是集合X上的等价关系。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,19},{5,10,15,20}}P127#42(2)A={1,3,5,9,15,18,27,36,45,54}R={<1,1>,<1,3>,<1,5>,<1,9>,<1,15>,<1,18>,<1,27>,<1,36>,<1,45>,<1,54>,<3,3>,<3,9>,<3,15>,<3,18>,<3,27>,<3,36>,<3,45>,<3,54>,<5,5>,<5,15>,<5,45>,<9,9>,<9,18>,<9,27>,<9,36>,<9,45>,<9,54>,<15,15>,<15,45>,<18,18>,<18,36>,<18,54>,<27,27>,<27,54>,<36,36>,<45,45>,<54,54>}COV(A)={<1,3>,<1,5>,<3,9>,<3,15>,<5,15>,<9,18>,<9,27>,<9,45>,<15,45>,<18,36>,<18,54>,<27,54>}P127#42(3)A={1,2,3,4,5,6,7,8,9,10,11,12}R={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<1,7>,<1,8>,<1,9>,<1,10>,<1,11>,<1,12>,<2,2>,<2,4>,<2,6>,<2,8>,<2,10>,<2,12>,<3,3>,<3,6>,<3,9>,<3,12>,<4,4>,<4,8>,<4,12>,<5,5>,<5,10>,<6,6>,<6,12>,<7,7>,<8,8>,<9,9>,<10,10>,<11,11>,<12,12>}COV(A)={<1,2>,<1,3>,<1,5>,<1,7>,<1,11>,<2,4>,<2,6>,<3,6>,<3,9>,<4,8>,<4,12>,<5,10>,<6,12>}P127#43

={<S0,S0>,<S1,S0>,<S2,S0>,<S3,S0>,<S4,S0>,<S5,S0>,<S6,S0>,<S7,S0>,<S1,S1>,<S3,S1>,<S4,S1>,<S5,S1>,<S6,S1>,<S7,S1>,<S2,S2>,<S3,S2>,<S4,S2>,<S5,S2>,<S6,S2>,<S7,S2>,<S3,S3>,<S4,S3>,<S5,S3>,<S6,S3>,<S7,S3>,<S4,S4>,<S5,S4>,<S6,S4>,<S7,S4>,<S5,S5>,<S7,S5>,<S6,S6>,<S7,S6>,<S7,S7>}解答〔续〕COV(L)={<S1,S0>,<S2,S0>,<S3,S1>,<S3,S2>,<S4,S3>,<S5,S4>,<S6,S4>,<S7,S5>,<S7,S6>}P127#44(1)x4Rx1、x3Rx3、x1Rx1、x5Rx1是真的；(2)、(3)最大元素最小元素极大元素极小元素P集合x1无x1x4、x5P127#44上界下界上确界下确界{x2、x3、x4}x1x4x1x4{x3、x4、x5}x1、x3无x3无{x1、x2、x3}x1x4x1x4P127#45(1)R1={<1,1>,<1,2>,<1,3>,<1,4>,<2,2>,<3,3>,<4,2>,<4,4>}COV(X)={<1,3>,<1,4>,<4,2>}P127#45(2)R2={<1,1>,<1,3>,<1,4>,<2,2>,<2,3>,<2,4>,<3,3>,<4,4>}COV(X)={<1,3>,<1,4>,<2,3>,<2,4>}P127#45(3)R3={<1,1>,<1,2>,<1,3>,<2,2>,<3,2>,<3,3>,<4,1>,<4,2>,<4,3><4,4>}COV(X)={<1,3>,<3,2>,<4,1>}P127#45(4)R4={<1,1>,<2,2>,<3,1>,<3,2>,<3,3>,<3,4>,<4,1>,<4,4>}COV(X)={<3,2>,<3,4>,<4,1>}第四章 函数一、主要内容二、本章要点一、主要内容1、函数的根本概念2、函数的性质3、特种函数4、复合函数5、逆函数1、函数的根本概念 设f是从集合X到Y上关系，假设对任意的xX都存在唯一的yY，使<x，y>f，那么称关系f为函数〔或映射〕，记作：f:X→Y。(1)对于函数f:X→Y，如果﹤x，y﹥f，也写成y=f(x),并称x为自变量，y称为函数在x处的值，或称y为在函数f的作用下x的像点，相应地称x为y的原像。(2)对于函数f:X→Y，那么称X为函数f的定义域，Y称为f的陪域；Rf是f的值域。2、函数的性质 设函数f:X→Y,那么f满足下面两个性质：(1)任意性：函数的定义域必须是集合X，即：Df=X；(2)唯一性：对任意的xX，必存在唯一的yY，使<x，y>f，即：对任意的xX，y，zY，有：<x，y>f∧<x，z>fy=z。3、特种函数设函数f:X→Y,那么：(1)假设f(X)=Rf=Y,那么称f是滿射的；(2)对任意x1,x2X，如果:x1≠x2f(x)≠f(y),或:f(x1)=f(x2)x1=x2；那么称f是单射的；(3)假设f是既是满射的，又是单射的，那么称f是双射的。4、复合函数 给定函数f:X→Y，g:X→Z，那么：gｏf=｛<x，z>│xX∧zZ∧(y)(<x，y>f∧<y，z>g)｝那么称gｏf为f和g的合成函数〔或复合函数〕。5、逆函数 如果f是个双射函数，那么f的逆关系称为f的逆函数〔或反函数〕，并记作：f–1。相关定理定理1设函数f:A→B，所有从A到B的函数的集合{f|f:A→B}，记作BA，如果|A|＝m,|B|=n,那么|BA|＝nm。定理2设函数f:X→Y，g:Y→Z，那么复合函数gｏf是从X→Z上的函数，并对任意的xX，都有：〔gｏf〕〔x〕=g(f(x))。相关定理〔续〕定理3函数的复合运算是可结合的，即如果f、g和h都是函数，那么有：〔gｏf〕ｏh=gｏ(fｏh)=gｏfｏh定理4设函数f:X→Y，f的逆关系f–1是从Y→X上函数，当且仅当f是个双射函数。二、本章要点1、掌握函数的定义〔任意性、唯一性〕: 设f是从集合X到Y的关系，即f:X→Y，假设对任意的xX都存在唯一的yY，使<x，y>f，或y=f(x)，那么称关系f为函数〔或映射〕注意：函数和关系的联系和区别。本章要点〔续〕2、掌握合成函数的概念：设函数f:X→Y,g:Y→Z,那么:g◦f={<x,z>|x∈X∧z∈Z∧(y)(y∈Y∧y=f(x)∧z=g(y))}称为f和g的合成函数〔复合函数〕。注意：合成关系和合成函数书写格式的区别。本章要点〔续〕3、掌握反函数的概念及其存在的条件： 设f:X→Y是双射函数，那么f的逆关系称f的反函数，记作f-1注意：只有双射函数才有反函数。本章要点〔续〕4、掌握特种函数的定义〔单射、满射、双射〕及证明：①滿射函数：设函数f:X→Y，假设f(X)=Rf=Y〔值域＝陪域〕。 ②单射函数：设函数f:X→Y，对任意x1，x2∈X，如果：x1≠x2f(x1)≠f(x2)或f(x1)=f(x2)x1=x2；P148#3(1)任意性：对于ρ(E)×ρ(E)中的任意一个元素<S1,S2>,根据f的定义有：f(<S1,S2>)=S1∩S2

E,即：S1∩S2

ρ(E)(2)惟一性：假设ρ(E)×ρ(E)中的某一个元素<S1,S2>在ρ(E)中有两个象点S和S′,即：f(<S1,S2>)=S1∩S2=S和f(<S1,S2>)=S1∩S2=S′即：S1∩S2=S=S′(3)满射：对任意的S

ρ(E)，在ρ(E)×ρ(E)中至少有一个原像<S,S>，使得：f(<S,S>)=S∩S＝SP148#6(1)从X到Y的不同的单射函数：P|X||Y|(2)从X到Y的不同的双射函数：m!(3)存在单射函数的必要条件:|X|≤|Y|(4)存在满射函数的必要条件:|X|≥|Y|(5)存在双射函数的必要条件:|X|=|Y|P148#10(1)必要性：g∘f=IX、f∘g=IY证明：g=f-1先证明f是双射函数：∵恒等函数IX是双射，所以g∘f：X→X是双射，∴f是单射。∵恒等函数IY是双射，所以f∘g：Y→Y是双射，∴f是满射。∴f是双射函数，即：f反函数存在。P148#10再证明：g=f-1∵g：Y→X，f-1：Y→X对于任意的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-1P148#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(y)=Iy(y)∴f∘g=IYP148#11f(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◦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=16x2+24x+9-2=16x2+24x+7P148#12f(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)=g(h(n))P148#12〔续〕h◦g(n)=h(g(n))=h(2n)=0f◦g◦h(n)P149#15设f={<1,2>,<2,3>,<3,1>}是单射函数，且f≠IXf◦f={<1,3>,<2,1>,<3,2>}f◦f◦f={<1,1>,<2,2>,<3,3>}f-1={<2,1>,<3,2>,<1,3>}f◦f-1={<1,1>,<2,2>,<3,3>}=IXg={<1,2>,<2,1>,<3,3>}是单射函数，且f≠IXg◦g={<1,1>,<2,2>,<3,3>}=IX第五章 代数结构一、主要内容二、本章要点一、主要内容1.代数运算2.二元运算的性质3．二元运算的特异元4.可约的或可消去的5.代数系统的概念6.同态与同构的概念7.代换性质和同余关系8.商代数与积代数9.半群和群1.代数运算 设X集合，f是从Xn→X上映射，那么称f为集合X中的n元运算。特别是：(1)当n=1时，f：X→X称为集合X中的一元运算；(2)当n=2时，f：X×X→X称为集合X中的二元运算。 如果对给定的集合中的元素进行运算，从而产生了像点，而该像点又是该集合中的元素，那么称给定的运算对该集合封闭。在上述的代数运算的定义中蕴含着对集合的封闭性。2.二元运算的性质 设∘和*为集合X上的二元运算，与这些运算相关的性质有：(1)交换律：x，y

Ｘ，有x∘y=y∘x；(2)结合律：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)幺元(2)零元(3)逆元(1)幺元设*为Ｘ上的二元运算，那么:(1)如果(el)(elX∧(x)(xX→el*x=x))，那么称el为集合X关于运算*的左幺元；(2)如果(er)(erX∧(x)(xX→x*er=x))，那么称er为集合X关于运算*的右幺元；(3)如果运算的左幺元和右幺元同时存在，那么必有el=er=e，使得对任意的xX，有:x*e=e*x=x并称e为运算*的幺元且幺元e是惟一的。(2)零元(1)如果(0l)(0lX∧(x)(xX→0l*x=0l))，那么称0l为集合X关于运算*的左零元；(2)如果(0r)(0rX∧(x)(xX→x*0r=0r))，那么称0r为集合X关于运算*的右零元；

(3)如果运算的左零元和右零元同时存在，那么必有0l=0r=0，使得对任意的xX，有:x*0=0*x=0并称0为运算*的零元。(3)逆元设*为Ｘ上的二元运算，且X中对于运算存在幺元e。令xX。(1)如果(xl)(xlX∧xl*x=e)，那么称xl是x的左逆元，并称x是左可逆的；(2)如果(xr)(xrX∧x*xr=e)，那么称xr是x的右逆元，并称x是右可逆的；(3)如果元素x既是左可逆的，又是右可逆的，那么称x是可逆的。4.可约的或可消去的设<X,*>为代数系统，且aX，如果对任意的x，yX有：〔a*x=a*y〕∨〔x*a=y*a〕x=y那么称a是可约的或可消去的。5.代数系统 设X是一个非空集合，为X上的代数运算构成的非空集合，那么称序偶<X,>为一个代数系统〔或代数结构〕，其中：(1)集合X为代数系统<X,>的定义域。如果X是个有限集合，那么称<X,>为有限代数系统，│X│=n为代数系统的阶；否那么称<X,>为无限代数系统。(2)=1，2，…n｝为X中的n元运算〔n=1，2，3，…〕构成的集合，如果为有限集合，那么可将<X,>表示为：<X,1，2，…n>。6.同态与同构的概念设U＝<X，ｏ>，V＝<Y，*>是两个代数系统，ｏ和*是二元运算，函数f：X→Y，如果对任意的x，yX有:f(xｏy)=f(x)*f(y)(运算的像=像的运算)那么称f是代数系统U到V同态映射(简称同态)，并称代数系统U与V同态。(1)如果f是满射的，那么称f是从U到V的满同态；(2)如果f是单射的，那么称f是从U到V的单一同态；(3)如果f是双射的，那么称f是从U到V的同构。(4)如果U=V，那么称f是从U到U的自同构。7.代换性质和同余关系代换性质：给定代数系统<X，*>，其中是个二元运算。设R是X中的等价关系，如果对任意的x1，x2X和y1，y2X有：(x1Rx2)∧(y1Ry2)(x1*y1)R(x2*y2)那么称等价关系E对于运算具有代换性质。同余关系：给定代数系统U=<X，*>，且R是集合X中的等价关系。如果等价关系R对运算具有代换性质，那么称R是代数系统U中的同余关系。8.商代数与积代数 给定代数系统U=<X，ｏ>，其中ｏ是个二元运算，R是U中的同余关系。试构成一个新的代数系统W=<X/R，>，其中 (1)X/R=｛[x]R│xX｝； (2)对任意的x1,x2X,有[x1]R[x2]R=[x1ｏx2]R那么称代数系统W为U的商代数，简称商代数，并记作U/R。商代数与积代数〔续〕设U＝<X，ｏ>，V＝<Y，*>是代数系统，试构成一个新的代数系统：U×V=<X×Y，>其中X×Y是X和Y的笛卡儿乘积，且运算的定义为：对任意的x1，x2X和y1，y2Y有<<x1,y1>,<x2,y2>>＝<x1ｏx2，y1*y2>那么称U×V是U和V的积代数，U和V是U×V的因子代数。9.半群和群半群：设<S,*>是代数系统，*运算是S上的二元运算，假设*运算是可结合的，那么称<S,*>为一个半群。群：〔1〕<S，*>是代数系统；〔2〕“*〞运算满足结合律；〔3〕<A，*>中存在幺元e；〔4〕<A，*>中任意一个元素都有逆元素；那么称代数系统<A，*>是群。子群 设<A，*>是一个群，H是A的非空子集，假设<H，*>也是一个群，那么称<H，*>是<A，*>的子群。阿贝尔群和循环群 假设群<A，*>对运算“*〞满足交换律，那么称<A，*>是阿贝尔群〔交换群〕。

假设群<A，*>中每个元素均是它的某个元素a的整数幂，那么称<A，*>是由a生成的循环群。a称为<A，*>的生成元素。二、本章要点(1)理解代数运算以及代数运算的性质〔结合律、交换律、分配律、等幂律、消去律〕。(2)掌握代数系统和子代数系统的定义，理解运算的封闭性。(3)给定集合和运算，会判别运算对该集合是否封闭。本章要点〔续〕(4)给定二元运算，说明运算是否满足交换律、结合律、等幂律、分配律和消去律。(5)掌握和理解幺元、零元、逆元的概念,给定—个集合和该集合上的二元运算，会求该运算的幺元、零元和逆元。(6)掌握和理解同态、满同态、单一同态和同构的概念和性质,并会求解〔证〕相关问题。(7)掌握半群、独异点、群、子群的概念及相关的证明。(8)理解阿贝尔群、循环群的概念。本章要点〔续〕P166#4 设*运算是X中的可结合的二元运算，并且对任意的x,yX,假设x*y=y*x，那么x=y。证明：X中的每个元素都是等幂的。证明 对任意的xX,要证明x是等幂的，即证明：x*x=x因为：*运算是X中的可结合的二元运算所以：x*(x*x)=(x*x)*x由：x*y=y*xx=y得：x*x=xP167#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均为同态映射，且：g(a)=f1(a)*f2(a)证明：g也为同态映射对任意的a,b属于A，证明:g(a∘b)=g(a)*g(b)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),设f(S)=～S运算的像＝f(S1∩S2)=~(S1∩S2)=~S1∪~S2=f(S1)∪f(S2)=像的运算5、P196#5设<A,*>是半群，对于A中的每一个元素a和b，假设a≠b，那么有：a*b≠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)证明：因为<A,*>是半群，*运算可结合，所以：(a*a)*a=a*(a*a)

a*a=a证明〔2〕a*b*a=a要证明:a*b*a=a，由提示可知，只需要证明：(a*b*a)*a=a*(a*b*a)证明：(a*b*a)*a 〔*运算可结合〕＝a*b*(a*a) 〔由〔1〕〕=a*b*a 〔由〔1〕〕=(a*a)*b*a 〔*运算可结合〕=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)证明：(a*b*c)*(a*c) 〔*运算可结合〕=a*b*(c*a*c) 〔由〔2〕〕=a*b*c 〔由〔2〕〕=(a*c*a)*b*c 〔*运算可结合〕=(a*c)*(a*b*c) 〔由提示〕a*b*c=a*cP197#6设<A,*>是半群，其中A=

a,b

，且a*a=b。证明：⑴

*是可交换运算。⑵

b=b2。解答⑴因为a*b=a*a2=a3=a2*a=b*a所以*是可交换运算。⑵b*b=(a*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 设<S,*>是个有限可交换含幺半群，对任意的a,b,cS，假设a*b=a*c，那么b=c。证明：<S,*>是个阿贝尔群。证明只需证明S中的每一个元素均可逆即可。<S,*>是个有限可交换含幺半群，所以S是个有限集合，设:S={a1,a2,…,an}对任意的aS，那么：a*a1S,…,a*anS,所以：{a*a1,a*a2,…,a*an}S由：a*b=a*cb=c所以：逆反命题也成立，即：b≠ca*b≠a*c所以：{a*a1,a*a2,…,a*an}=S证明：〔续〕因为：<S,*>是个有限可交换含幺半群，所以：存在幺元e,且必存在某个元素ak

S,使得：a*ak=e(1≤k≤n)因为：*运算可交换所以：a*ak=ak*a=e，即：a的逆元是ak由a的任意性可知：S中的每一个元素都可逆所以：<S,*>是群。

P198#18 证明：如果群<G,*>中每个元素的逆元是其自身，那么该群必是阿贝尔群。证明对任意的a,bG，那么a*bG因为：群<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所以<G,*>是交换群。P198#19试证明，在群<G,*>中：〔1〕如果对任意的aG,有a2=e,那么<G,*>是个阿贝尔群；〔同P198#18〕〔2〕如果对任意的a,bG,有(a*b)2=a2*b2,那么<G,*>是个阿贝尔群；证明〔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*bP198#25(1)显然SG(2)封闭性：对任意的a,bS，证明a*bS,即证明对任意的xG，有:(a*b)*x=x*(a*b)因为：a,bS，所以：a*x=x*a，b*x=x*b(a*b)*x=a*(b*x) 〔*可结合〕=a*(x*b) 〔b*x=x*b〕=(a*x)*b 〔*可结合〕=(x*a)*b 〔a*x=x*a〕=x*(a*b) 〔*可结合〕证明〔续〕(3)S中存在幺元： 设e是G中的幺元，由幺元的定义可知：对任意的xG，均有：e*x=x*e由S的定义可知：eS证明〔续〕(4)可逆性： 对任意的aS，证明a的逆元a-1S,即证明对任意的xG，有:a-1

*x=x*a-1aSa*x=x*a

a-1*(a*x)*a-1=a-1*(x*a)*a-1

(a-1*a)*x*a-1=a-1*x*(a*a-1)

x*a-1=a-1*x综上：<S,*>是<G,*>的子群P198#26 设<H1，*>和<H2，*>是群<G，*>的两个子群。试证明：<H1∩H2，*>也是<G，*>的子群。证明〔1〕封闭性：对任意的x,yH1∩H2x,yH1∧x,yH2 〔封闭性〕x*yH1∧x*yH2x*yH1∩H2证明：〔续〕〔2〕可逆性：对于任意的xH1∩H2xH1∧xH2 〔可逆性〕x-1H1∧x-1H2x-1H1∩H2证明 给定代数系统U=<X,∘>,V=<Y,*>,W=<Z,⊗>,设f:X→Y是从U到V的同态，g:Y→Z是从V到W的同态，那么g∘f:X→Z必是从U到W的同态。证明对任意的a,bX，证明：g∘f(a∘b)=g∘f(a)⊗g∘f(b)g∘f(a∘b)=g(f(a∘b))=g(f(a)*f(b)) (f是同态映射)=g(f(a))⊗g(f(b)) (g是同态映射)=g∘f(a)⊗g∘f(b)证明 设<A,*>是代数系统，其中：A=

a,b,c,d

且有：b=a2，c=a3，d=a4证明：运算*是可交换运算。解答证明：a*b=a*a2=a3=a2*a=b*aa*c=a*a3=a4=a3*a=c*aa*d=a*a4=a5=a4*a=d*ab*c=a2*a3=a5=a3*a2=c*bb*d=a2*a4=a6=a4*a2=d*bc*d=a3*a4=a7=a4*a3=d*c即：对任意的x,y

A，均有：x*y=y*x所以：*运算是可交换的运算。证明 设<G,*>是群，如果对于群G中任意元素a,b，都有(a*b)−1=a−1*b−1，证明<G,*>是阿贝尔群。证明方法一由定理:(a*b)−1=b−1*a−1可知:(b*a)−1=a−1*b−1由题设可知:(a*b)−1=a−1*b−1所以有:(a*b)−1=(b*a)−1因为*运算可结合，所以逆元存在必惟一，即：

a*b=b*a<G,*>是阿贝尔群。证明方法二因为：(a*b)−1=a−1*b−1所以:(a*b)*(a−1*b−1)=ea*b*a−1*b−1*b=e*ba*b*a−1*e=ba*b*a−1=ba*b*a−1*a=b*aa*b*e=b*aa*b=b*a 设<S,*>是群,任取a

S,定义函数f:S→S使得对每个x

S有:f(x)=a*x*a-1试证明：f是<S,*>的自同构映射。证明证明〔1〕显然<S,*>与<S,*>同类型；〔2〕单射：对任意的x,yS,证明：f(x)=f(y)x=yf(x)=f(y)a*x*a-1=a*y*a-1 〔消去律〕x*a-1=y*a-1 〔消去律〕x=y证明〔续〕〔3〕满射：对任意的yS,证明：在S中至少存在一个原像a-1*y*a，使得：f(a-1*y*a)=a*(a-1*y*a)*a-1=(a*a-1)*y*(a*a-1)=e*y*e=y证明〔续〕〔4〕运算的像=像的运算：对任意的x,ySf(x*y)=a*(x*y)*a-1 (由f的定义)=a*(x*e*y)*a-1 (群中存在幺元e)=a*(x*a-1*a*y)*a-1=(a*x*a-1)*(a*y*a-1) (结合律)=f(x)*f(y) (由f的定义)证明 设<G,*>是一个具有幺元e的群，如果对于某个元素aG有a2=a，那么a=e。证明任取aG,如果有a2=a，即a*a=aa=a*e(群中每个元素均可逆〕=a*(a*a-1) 〔结合律〕=(a*a)*a-1 =a