习题参考解答.docx

习题参考解答离散数学部分课后习题答案 离散数学部分课后习题答案 习题1.1 1、P：银行利率降低 Q：股价没有上升 PQ P：他今天乘火车去了北京 Q：他随旅行团去了九寨沟 PÑQ P：不识庐山真面目 Q：身在此山中 QP，或 PQ P：一个整数能被6整除 Q：一个整数能被3整除 R：一个整数能被2整除 T：一个整数的各位数字之和能被3整除 PQR ，QT 2、T F F T F T T 悖论 习题 1.3 1、 P®(QÚR)ÛØPÚ(QÚR)Û(ØPÚQ)Ú(ØPÚR)Û(P®Q)Ú(P®R)(PÙQ)Ú(QÙR)Ú(RÙP)=(PÚR)ÙQ)Ú(RÙP)=(PÚR)Ú(RÙP)Ù(QÚ(RÙP)=(PÚR)Ù(PÚR)Ù(QÚR)Ù(QÚP)=右2、不， 不， 能 习题 1.4 2、 1 离散数学部分课后习题答案 离散数学部分课后习题答案 3、，4、 习题 1.5 1、(3) P®(RÙ(Q®P)=PÚ(RÙ(QÚP)=(PÚR)Ù(T)=PÚR=(PÚRÚ(QÙQ) =(PÚRÚQ)Ù(PÚRÚQ) 主合取范式 P®(RÙ(Q®P)=ØPÚ(RÙ(ØQÚP)=ØPÚ(RÙØQ)Ú(RÙP)=(ØPÙ(ØQÚQ)Ù(ØRÚR)Ú(RÙØQÙ(ØPÚP)Ú(RÙPÙ(ØQÚQ)=(ØPÙØQÙØR)Ú(ØPÙQÙØR)Ú(ØPÙØQÙR)Ú(ØPÙØQÙR)Ú (RÙØQÙØP)Ú(RÙØQÙP)Ú(RÙPÙØQ)Ú(RÙPÙQ)=(ØPÙØQÙØR)Ú(ØPÙQÙØR)Ú(ØPÙØQÙR)Ú(RÙØQÙØP)Ú(RÙØQÙP)Ú(RÙPÙQ)主析取范式 2、(2) Q(P®Q)Ù(P®R)=(PÚQ)Ù(PÚR)=(PÚQÚ(RÙR)Ù(PÚRÚ(QÙQ) =(PÚQÚR)Ù(PÚQÚR)Ù(PÚRÚQ) P®(QÙR)=PÚ(QÙR)=(PÚQ)Ù(PÙR)=(PÚQÚR)Ù(PÚQÚR)Ù(PÚRÚQ)等价3、解：根据给定的条件有下述命题公式： ） 2 离散数学部分课后习题答案 离散数学部分课后习题答案 Û） Û ） Û ） Û Û Û Û 三种方案：A和D、 B和D、 A和C 习题 1.6 1、 需证(P®Q)®(P®(PÙQ)为永真式 Q(P®Q)®(P®(PÙQ)=(PÚQ)Ú(PÚ(PÙQ)PÚP)Ù(PÚQ)T=(PÚQ)Ú(PÚQ)=T=(PÚQ)Ú(P®QÞP®(PÙQ)需证PÙØPÙR®S为永真式 3 离散数学部分课后习题答案 离散数学部分课后习题答案 QPÙØPÙR®SÛFÙR®SÛF®SÛT PÙØPÙRÞS3、QAÞBA®B为永真式。即AÚB永真 QAÚBÛBÚAÛB®A永真 AÞB当且仅当BÞA 4、设： P：珍宝藏在东厢房 Q：藏宝的房子靠近池塘 R：房子的前院栽有大柏树 S：珍宝藏在花园正中地下 t：后院栽有香樟树 m：珍宝藏在附近 命题化后进行推理： (Q®p)Ù(R®P)ÙQÙ(RÚS)Ù(t®m)ÞpÙ(R®P)Ù(RÚS)Ù(t®m)ÞRÙ(RÚS)Ù(t®m) ÞSÙ(t®m)即S为真，珍宝藏在花园正中地下 5、(1)F (P=0,Q=1) (2)F (P=1,Q=R=0) (3)F (P=0,Q=1) 习题 1.7 1.PÚQ,R®QÞP®R 证：利用CP规则 P P(附加前提) PÚQP QTI R®QP RTI 4 离散数学部分课后习题答案 离散数学部分课后习题答案 结论成立 CP规则 (PÚQ)®(RÙS),(SVE®)BÞP® B证： PP(附加) PQ T (PÚQ)®(RÙS)P RÙST ST SE T SEB P BT P®BCP() 2. (2) P：无任何痕迹 Q：失窃时，小花在OK厅 R：失窃时，小英在OK厅 S：失窃时，小胖在附近 T：金刚是偷窃者 M：瘦子是偷窃者 命题可符号化为： P, QÚR, S®ØP, Q®T, ØS®ØR, R®M 证： P P S®P P S T S®R P R T QÚR P Q T Q®T P T T 5 离散数学部分课后习题答案 离散数学部分课后习题答案 金刚是窃贼。 3. (1) 不相容 (2) 相容 (P=1,R=Q=S=0) 不相容 不相容 4. (1)证：(P®Q)Ù(RÚS)Ù(S®Q)Ù(P®Q)ÙP Û(PÚQ)Ù(RÚS)Ù(SÚQ)Ù(PÚQ)ÙP 即 F=PÚQ, RÚS, SÚQ, PÚQ, P 利用消解原理： P P PÚQ P Q PÚQ P P PÙP=F 习题 2.1 1. (1)A(x)：x是实数 B(x)：x是有理数 "(x)(B(x)®A(x) Ø"x(A(x)®B(x) $x(A(x)ÙB(x) (2)A(x)：x是直线 F(x,y)：x与y平行 G(x,y)：x与y相交 "a"bA(a)ÙA(b)®(F(a,b)«ØG(a,b) (3)A(x)：x是会员 F(x)：x参加活动 P®"x(A(x)®F(x) P: 这个活动有意义 或者 Ø"x(A(x)®F(x)®ØP 6 离散数学部分课后习题答案 离散数学部分课后习题答案 A(x)：x是正整数 "x(A(x)®B(x)ÑC(x) B(x)：x是合数 C(x)：x是质数 A(x)：x是存钱的人 B：x想有利息 P:存钱没有利息 Q：人们不存钱 2.(1)P(0)ÙP(1)ÙP(2)Ù(R(0)ÚR(1)ÚQ(2) (2)P(0)®Q(0)ÙP(1)®Q(1)ÙP(2)®Q(2) 4.(1) ("x)($y)P(x,y)®Q(y,t)Ú("z)R(x,y,z) 习题 2.2 1.D：数 A(x):x=0f(x,y)=xy "x"yA(f(x,y)®A(x)ÚA(y)ÙØA(x-1)®ØA(f(x-1,x+1) 可满足式 (2)A(x):x是诚实的人，B(x):x讲实话 ，a：小林 "xB(x)®A(x)ÙØA(a)®ØB(a) T (3) A(x):x不便宜，B(x):x是好货，a：小王买的衣服 "xA(x)®B(x)Ù A(a)®B(a) T A(x):x是懂得人性本质的作家 B(x):x是真正的诗人 D(x):x很高明 a：莎士比亚 C(x):x能刻画人们内心世界 P(x,y):x创作了y b：哈姆雷特 2.(1) T 3.(1) F T (2) T 7 离散数学部分课后习题答案 离散数学部分课后习题答案 4. D: 实数 P(x,y):y=ex, Q(y):y>0 习题 2.3 1.$x$yP(x)®Q(y) Û$x$yP(x)ÚQ(y) Û$x$yP(x)Ú$yQ(y) Û$xP(x)Ú$yQ(y) Û"xP(x)Ú$yQ(y) Û(Ax)P(x)®($y)Q(y) 2. 不成立 P(0)P(1)P(2)Q(0)Q(1)Q(2), ,D=0,1,2 0101013.(1)("x)P(x)®($y)P(y) Û("x)P(x)Ú($y)P(y) Û($x)(P(x)Ú($y)P(y) Û("x)P(x)Ù("y)(P(y) Û("x)("y)(P(x)ÙP(y) skolem范式 (2)("x)P(x)®($y)("z)Q(y,z) Û("x)P(x)Ú$(y)("z)Q(y,z) Û("x)P(x)Ù("y)($z)Q(y,z) Û("x)("y)($z)(P(x)ÙQ(y,z) 前束范式 Û("x)("y)(P(x)ÙQ(y,f(x,y) skolem范式 习题 2.4 1. 证：在某个解释下，($x)($y)P(x)ÙQ(y)取值1，必有a,bÎD, 8 离散数学部分课后习题答案 离散数学部分课后习题答案 P(a)ÙQ(b)，取值1，因此，$aÎD P(a)取值1。 ($x)P(x)取值1，由定义，蕴含关系成立。 ($x)P(x)ÙQ(a)Û($x)P(x)ÚQ(a) Û($x)P(x)®Q(a) (2) 证: 在某个解释下，($x)P(x)ÙQ(a)取值1 即($x)P(x)ÙQ(a)取值0，分二种情况： i)($x)P(x)=0，则无论Q(a)为何值，($x)P(x)®Q(a)取值1。 ii) Q(a)=0($x)P(x)=1，则($x)P(x)®Q(a)取值1 由定义，蕴含关系成立。 习题 2.5 1 ($x)P(x)®Q(x) P ("x)P(x)®Q(x) T,E ("x)(P(x)®ÚQ(x) T,I ("x)(P(x)ÙQ(x) T,I P(x)ÙQ(x) US P(x) T,I ("x)P(x) UG ("x)P(x)®("x)Q(x) P ("x)Q(x) T,I Q(x) T,I 11Q(x) US 9 离散数学部分课后习题答案 离散数学部分课后习题答案 12 T11I 2. (1) 错误，应换元，即 ("x)P(x)®Q(x)， P(y)®Q(x) 正确 错误，a、b应是同一个常元 错误，因为在P(x)Ú($x)Q(x)ÙR(x) 中x并不是自由出现 (5) 错误，因为在($x)P(x)®Q(x)中，前件是命题， 而后件不是命题 错误，因为a、b并不是同一个常量 错误，和的顺序不对 应先使用ES，再使用US 3(1)解：设F(x,y):xy; G(z):z0 ; f(x,y)=x-y 前提： "(x)"(y) 证明： Ø "(x)"(y) Ø ØG(f(a,b) ØG(f(b,a) 10 离散数学部分课后习题答案 离散数学部分课后习题答案 "(x)"(y) 证：首先，将结论否定否作为前提加入到原有前提中 ($x)P(x)®("x)(P(x)ÚQ(x)®R(x)Ù($x)P(x)Ù($x)Q(x)Ù ($x)($y)R(x)ÙR(x) Û("x)P(x)Ú("x)(P(x)ÚQ(x)ÚR(x)Ù($u)P(u)Ù($v)Q(v)Ù ($w)($y)R(w)ÙR(y) Û("x)($u)($v)("w)("y)(P(x)ÚR(x)Ù(P(x)ÚQ(x)ÚR(x) ÙP(u)ÙR(u)Ù(R(w)ÚR(w) Û("x)("w)("y)(P(x)ÚR(x)Ù(P(x)ÚQ(x)ÚR(x)ÙP(a)ÙQ(b) Ù(R(w)ÚR(y) Skolem 范式 子句集为P(x)ÚR(x),P(x)ÚQ(x)ÚR(x),P(a),R(b),R(w)ÚR(y) P(x)ÚR(x) P(a) 11 离散数学部分课后习题答案 离散数学部分课后习题答案 R(x) ,代换a/x R(c) 代换c/x R(w)ÚR(y) R(y) ,代换c/w R(c) 代换c/y 习题 3.3 5、 (1)xÎ2AU2BÞxÎ2A或xÎ2BÞxÍA或xÍBÞxÍAUB ÞxÎ2AUB等号成立的条件为：AIB=f“Þ”xÎ2AI2BÞxÎ2A和xÎ2BÞxÍA和xÍBÞxÍAIBÞxÎ2AIB“Ü”如xÎ2AIB，由于上述过程可逆ÞxÎ2AI2B习题 4.2 2. 关系 性质 自反性 × × × × × × × × × R1 R2 R3 R4 R5 反自反性 × 对称性 × 反对称性 传递性 习题 4.3 12 离散数学部分课后习题答案 离散数学部分课后习题答案 2. “Þ”R是对称的，设Q<y,x>ÎR-1x,yÎR则 y,xÎRÞx,yÎR-1 <x,y>ÎRÞ<y,x>ÎR，即R-1=R "x,yÎR，由R-1“Ü” R=R-1的定义，y,xÎR-1 y,xÎR，即R是对称的。 “Þ”R是传递的，对"<x,z>ÎR2 $yÎA '即R2ÍR <x,y>ÎR<y,z>ÎR<x,z>ÎR “Ü”R2ÍR，对"<x,y>ÎR有<x,z>ÎR2ÍR<y,z>ÎR，由R的定义， 2<x,z>ÎR，即R是可传递的。 4. 解：QR=R1UR2，且R1IR2=F Rm=Rm1URm23R1=IA15R2=IA2,A=A1UA2 需3|m，5|m Þm=15，即 n=16 1616R16=R1UR2=R1UR2=R 故使Rm=Rn的最小正整数m=1,n=16 习题 4.4 2、解： æ0çç0ç1çç0MR=çç0ç0çç0ç0è1000010000000001000000000ö÷0÷0÷÷0÷Mt(R)÷0÷0÷÷1÷0÷ø000 010000001000000000100æ1çç1ç1çç0=çç0ç0çç0ç0è13 1110111000010001000100010011110011110011110011110ö÷0÷0÷÷1÷÷ 1÷1÷÷1÷1÷ø离散数学部分课后习题答案 离散数学部分课后习题答案 iR3. (3)证：Qt(R1)=iU=11t(R1UR2)=U(R1UR2)i i=1+¥it(R2)=UR i=12¥¥由归纳法可证：对" iÎNiiRURÍ(R1UR2)i 12¥æ¥iöæ¥iö¥ii÷UçUR÷=U(RUR)ÍU(R1UR2)i=t(R1UR2) t(R1)Ut(R2)=çURçi=11÷çi=12÷i=112i=1èøèø(4)证：(R+)=R+QR=t(R)=URi i=1+¥(R)(R)+=(t(R)=U(t(R)j +j=1¥由归纳法可证："jÎN+¥j¥(t(R)j=t(R) =U(t(R)=U(t(R)=t(R)=R+ j=1j=1RoR*=R+QR*=IAUt(R) RoR*=Ro(IAUt(R)=RoIAURot(R) =RURot(R)=t(R)=R+ 习题 5.1 1. 证：QA=(a,b)|a,bÎN+ R=(a,b),(c,d)|ad=bc 自反性 由A的定义，ab=baa,bÎN (a,b),(a,b)ÎR 对称性 设(a,b),(c,d)ÎR，则ad=bc 即 cb=da(c,d),(a,b)ÎR 传递性 设(a1,b1),(c1d1)ÎR，则a1d1=b1c1 14 离散数学部分课后习题答案 离散数学部分课后习题答案 (c1,d1),(c2d2)ÎR，则c1d2=d1c2 Þa1d1d2=b1c1d2=b1d1c2Þa1d2=b1c2 (a1,b1),(c2,d2)ÎR 3. 解：QA=1,2,3,4, S0=1,2,4,3 设A1=1,2,3,4,A2=3 (1，(1，(2，(2，(4，(4，(4，(3，R=(1，1)，2)，4)(2，1)，2)，4)，1)，2)，4)，3) 4. 解：每个集合的划分就可以确定一个等价关系 集合有多少个划分就可以确定多少个等价关系 4321C+C+C+C=15种。 44445. 解： R1UR2不是A上的等价关系 R1ÇR2是A上的等价关系 r(R1-R2) 是A上的等价关系 R1oR2不是A上的等价关系 习题 5.2 2. 解：A=a,b,c 2A=F,(a),(b),(c),(a,b),(a,c),(b,c),(a,b,c) a,b,c a,b a,c a F Cb b,c c <2,Í> 3. 解：集合A上的空关系F、恒等关系IA都是等价关系和偏序关系。 15 离散数学部分课后习题答案 离散数学部分课后习题答案 6. 证：i）自反性，对"bÎBÍA,显然(b,b)ÎB´B (b,b)ÎR，(b,b)ÎRI(B´B) ii)反对称性，对"a,bÎB,(a,b)ÎRI(B´B),(b,a)ÎRI(B´B) 即(a,b)ÎR,(b,a)ÎR，由R的反对称性，Þa=b iii)传递性，对"a,b,cÎB，设(a,b)ÎRI(B´B),(b,c)ÎRI(B´B)， 则(a,b)ÎR，(b,c)ÎR。 由R的传递性，(a,c)ÎR，显然(a,c)ÎB´B (a,c)ÎRI(B´B) 习题 5.3 2. 解：A=(a,b,c,d) 2A=F,(a),(b),(c),(d),(a,b),(a,c),(a,d),(b,c),(b,d),(c,d),(a,b,c),(a,b,d),(b,c,d),(a,c,d),(a,b,c,d)F£(a)£(b)£(c)£(d)£(a,b)£(a,c)£(a,d)£(b,c)£(b,d)£(c,d)£(a,b,c)£(a,b,d)£(a,c,d)£(b,c,d)£(a,b,c,d) 习题6.2 4、证： 1）对"b1、b2ÎB，b1¹b2 Qf(x)是满射，$a1、a2ÎA,'f(a1)=b1,f(a2)=b2 由g(x)的定义，a1Îg(b1),a2Îg(b2)，且a1Ïg(b2),a2Ïg(b1) 否则，如 a1Îg(b2), a2Îg(b1)，有 f(a1)=b2, f(a2)=b与函数的定义相矛盾， g(b1)¹g(b2), 即g(x)为单射 2）而g(x)为单射时，对"bÎB,并不能保证 g(b)¹f,f(x)不一定是满射习题6.3 16 离散数学部分课后习题答案 离散数学部分课后习题答案 4、证： f:A®B,g:B®C 反证法：设不是单射 $，x1¹x2ÎA,'f(x1)=f(x2) 即gof(x1)=g(f(x1)=g(f(x2)=gof(x2) 与gof为单射矛盾Qgof为满射 对"zÎC, $xÎA, 'gof(x)=g(f(x)=z 令f(x)=yÎB $ yÎB, 'g(y)=z 即g为满射(3)由的结论可得习题10.1 1、Q G=(n,m) 由Euler定理 2m=åd(k) d(k)表示第k个结点的度数k=1nQ2m=åd(k)£å(n-1)k=1k=1nn(G是简单图，d(k)£n-1,等号成立当且仅号G是完全图时）n(n-1)2 2m£n(n-1) 即 £=Cn23、解：不是图的序列，因为奇数度结点的 个数不是偶数。 、都是图的序列。 4、证： 习题10.3 由欧拉定理， 2m=åd(v)vÎGQåd£åd(v)£åDvÎGvÎGvÎGnd£åd(v)=2m£nDvÎG2mÞd££Dn17 离散数学部分课后习题答案 离散数学部分课后习题答案 1、证：设v与u不连通 G=V1，V2 ，v与u分别属于V1，V2二个子图 v与u是G中仅有的二个奇数度结点 v与u即是V1与V2中仅有的一个奇数度结点，与 欧拉定理的推论相矛盾，故v与u必连通 3、证： n=2时, m>0 二个结点至少有一条边，即G是连通图 1设 n=k 时，结论成立,即 时， G是连通图 m>(k-1)(k-2) 21证n=k+1时，结论成立，即 m>k(k-1)时， G是连通图 2 如果G是非连通图，必存在一个结点v，使1d(v)<k(否则，如d(v)=0，则G-v是一个有11k个结点的简单图，其边数 如d(v)=k,则G是一个m£k(k-1)与 m>k(k-1)矛盾；22完全图，与假设矛盾） 从G中删除该结点v所得子图G=G-v 11'其边数 m³m-(k-1)>2k(k-1)-(k-1)=2(k-1)(k-2)由归纳假设，G=G-v的结点数为k，所以G是简单图， G=G+v ，G连通 故由归纳法，结论成立 习题10.4 3、解： e1v1e2e3v3v6e9e5e6v5e8e10e11e12e7v2e4v4v7v5 v6 v7ùév1 v2 v3 v4 êú0 1 1 0 0 0 0êúê0 0 0 1 0 0 0úêú0 0 0 1 1 0 0úA=êê1 0 1 0 1 0 0úêú0 0 0 0 0 0úê0 ê0 0 0 0 1 0 1úêú0 0 0 0 1 1 0êúëûév1 v2 v3 v4 v5 v6 v7ùêú1 1 1 1 1 0 0êú1 1 1 1 0 0ú ê1 êú1 1 1 1 1 0 0êúP= ê1 1 1 1 1 0 0úêú0 0 0 0 0 0 0ú êê0 0 0 0 1 1 1úêú0 0 0 1 1 1úêë0 ûPQPT18 év1 v2 v3 v4 v5 v6 v7ùêú1 1 1 1 0 0 0êúê1 1 1 1 0 0 0úêú1 1 1 1 0 0 0ú=êê1 1 1 1 0 0 0úêú0 0 0 0 1 0 0êúê0 0 0 0 0 1 1úêú 0 0 0 1 êë0 0离散数学部分课后习题答案û 1ú离散数学部分课后习题答案 三个强分图 ée1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12ùêú1 1 -1 0 0 0 0 0 0 0 0 0êúê-1 0 0 1 0 0 0 0 0 0 0 0úêú0 -1 0 0 1 -1 1 0 0 0 0 0úMG=êê0 0 1 -1 -1 1 0 1 0 0 0 0úêúê0 0 0 0 0 0 -1 -1 -1 -1 0 0úê0 0 0 0 0 0 0 0 1 0 -1 1úêú1 1 -1úêë0 0 0 0 0 0 0 0 0 û习题11.1 1、解：设L是叶的数目，m是树的边数 由Euler定理 åknk+L=2mk=2 im=nk+L-1å 由树的定义 k=2iÞåknk+L=2ånk+2L-2k=2k=2iiÞL=å(k-2)nk+2 (i³k³2)k=2i2、证明： 习题11.3 6、证明：由正则二叉树的定义，其叶结点的个数必为偶数，设叶数为t，分支数为i 由定理10-2.1 (m-1)i=t-1 m=1 i=t-1 有分支点数是奇数 故结点数=i+t=奇数 习题12.2 1、证： 设G=和G=都是平面图 由G的定义 m+m=n(n-1)/2 由定理10-4.2 m3n-6 , m3n-6 m+m=n(n-1)/2 6n-12 有 n2-13n+24=(n-11)2+9n-97 0 又 设所有顶点的度数5 由Euler公式， 由定理10-4.2 m3n-6 3n-65n/2 即n12 则 m5n/25×12/2=30 与 m30矛盾 至少存在一个顶点的度数不超过4 习题13.2 2、证： G是2k正则图， 对任意的u、vG，d(u)+d(v)=4k 由定理10-6-2 在G中存在一条Hamilton道路，设为： v1v2,v4k+1 1) v1v4k+1E， 则v1v2,v4k+1v1构成一个Hamilton圈 2) v1v4k+1 ÏE， 则$vi1,vi2,L,vi2k与v1邻接 G的阶数为4k+1 v4k+1必与vi1-1,vi2-1,L,vi2k-1中的一个点邻接， 假设G不是哈密尔顿图，则 $s,tÎG,'deg(s)+deg(t)<nQ2m=ådeg(v)=v)+deg(s)+deg(t) ådeg(vÎGvÎG-s,t2m<vÎG-s,tv)+ådeg(n因为G除结点s,t外的其余n-2结点之间最多可以构成完全 图，所以 2m<(n-2)(n-3)+n+n<n2-3n+6=(n-1)(n-2)+4 从而 12 m<(n-1)(n-2)+2=Cn-1+2 22m³Cn-1+220 离散数学部分课后习题答案 离散数学部分课后习题答案 与已知 矛盾，故结论成立。 习题15.1 4、证： 设$aÎA,'a·a¹a 构造 b=a·a ，则 a·b=a·a·a=b·a 即 a、b可交换，与已知条件相矛盾 "aÎA，a·a=a 习题15.2 1、证明：群中只有幺元是幂等元。 证： 设$aÎA,a¹e,'a2=a，Qa-1 $, a=a2·a-1=a·a-1=e Þ矛盾 5、写出s,o中的全部子群。 3解：á，ñ，á，ñ，á，ñ， á，ñ和二个平凡子群。 6、证明：1） S、T是G的子群 eÎS , eÎT 即 eÎS T 设 a，bÎS T，即a，bÎS 和a，bÎT b-1 ÎS 和b-1ÎT a×b-1 ÎS 和a×b-1ÎT 即 a×b-1 ÎST ST，×是G的子群 2） eÎST，设c、dÎST 则 $ a1ÎS，b1ÎT ，' c=a1b1， $ a2ÎS，b2ÎT ，' d=a2b2， d-1=b2-1a2-1 又 S和T中的元素关于“×” 可交换 c×d-1= a1b1b2-1a2-1= a1a2-1b1b2-1 ÎST 即 ST是子群 习题15.3 2、证明：设G是阶数大于1的群， 21 离散数学部分课后习题答案 离散数学部分课后习题答案 则 $ aeÎG 构造G=e,aÍG， 则 G是G的交换群。 3、证明： 设 G=(a),G是G的子群，则G中的每个元素具有am的形式，设k是所有m中最小的正整数，则 G= 即 (a)=e,a,a2 或 (a)=e Q G=U(a)aÎG G 的阶数n必是奇数 习题16.2 5、证：1）对任何 aÎR，由已知 对 由定理16-1.1， 2222） (a*b)=a*b=a*b 由定理15-3.1 áR，*ñ为交换半群 故áR，+，*ñ为交换环 22 离散数学部分课后习题答案