第一篇:离散数学及其应用集合论部分课后习题答案
作业答案:集合论部分
P90:习题六
5、确定下列命题是否为真。(2)(4){}
(6){a,b}{a,b,c,{a,b}} 解答:(2)假(4)真(6)真
8、求下列集合的幂集。(5){{1,2},{2,1,1},{2,1,1,2}}(6){{,2},{2}} 解答:
(5)集合的元素彼此互不相同,所以{2,1,1,2}{1,2},所以该题的结论应该为
{,{{1,2}},{{2,1,1}},{{1,2},{2,1,1}}}
(6){,{{,2}},{{2}},{{,2},{2}}}
9、设E{1,2,3,4,5,6},A{1,4},B{1,2,5},C{2,4},求下列集合。(1)A(2)解答:(1)A(2)
31、设A,B,C为任意集合,证明 B
(AB)
B{1,4}{3,4,6}{4}
(AB){1}{2,3,4,5,6}
(AB)证明:
(BA)(AB)(AB)
(AB)(BA){x|xABxBA}{x|(xAxB)(xBxA)}{x|(xAxB)(xBxB)(xAxA)(xBxA)} {x|(xAxB)(xBxA)}{x|(xA{x|(xAA
B)(xAxB)}{x|(xAB)(xABB)}{x|(xAB)(xAxB)}B)}B)(xABA34、设A,B为集合,证明:如果(AB)证明:(反证法)
设aA(BA)AB,则AB。
B,则aA,aB,所以aAB,aBA; 所以a(AB)但是aA与(AB)
37、设A,B,C为任意集合,证明:CACBC(A证明:
对任意xC,由于CA,CB,所以xA且xB所以xA因此,C(A
(BA)
B矛盾。
B)。
B B。
(BA)AB)。
P121:习题七
5、设A,B为任意集合,证明
若AABB,则AB。
证明:
xAx,xAA
x,xBBxB所以有AB
9、设A{1,2,4,6},列出下列关系R(2)R{x,y|x,yA|xy|1}(3)R{x,y|x,yAy为素数} 解答:
11、Ri是X上的二元关系,对于xX定义集合(2)R{1,2,2,1}
(3)R{1,2,2,2,4,2,6,2}
Ri(x){y|xRy}
显然Ri(x)X。如果X{4,3,2,1,0,1,2,3,4},且令
R1{x,y|x,yXxy}
R2{x,y|x,yXy1xy2} R3{x,y|x,yXx2y}
求R1(0),R1(1),R2(0),R2(1),R3(3)。解答:
R1(0){1,2,3,4}R1(1){2,3,4}R2(0){1,0}R2(1){2,1}R3(3),B{1,3,2,4,4,2}。求A13、设A{1,2,2,4,3,3}
B,AB,domA,domB,dom(A解答:
B),ranA,ranB,ran(AB),fld(AB).AAB{1,2,2,4,3,3,1,3,4,2} B{2,4}
domA{1,2,3} domB{1,2,4} dom(AB){1,2,3,4}
ranA{2,3,4} ranB{2,3,4} ran(A B){4}
fld(AB){1,2,3}
16、设A{a,b,c,d},R1,R2为A上的关系,其中
R1{a,a,a,b,b,d},R2{a,d,b,c,b,d,c,b}。求R1R2,R2R1,R12,R23。
解答:
R1R2{a,d,a,c,a,d} R2R1{c,d}
R12{a,a,a,b,a,d} R22{b,b,c,c,c,d} R23{b,c,b,d,c,b}
20、给定A{1,2,3,4},A上的关系R{1,3,1,4,2,3,2,4,3,4}(1)画出R的关系图。(2)说明R的性质。解答:
(1)
(2)R具有反自反性,反对称性,传递性
21、设A{1,2,3},图7.11给出12种A上的关系,对于每种关系写出相应的关系矩阵,并说明它所具有的性质。
解答:
110(a)111,具有自反性。101110(b)001,具有反对称性和传递性。100111(c)111,具有自反性,对称性和传递性。111
23、设R的关系图如图7.12所示,试给出r(R),s(R)和t(R)的关系图。
25、设A{1,2,3,4},R是A上的等价关系,且R是A上所构成的等价类为{1},{2,3,4}。(1)求R。(2)求RR(3)求R传递闭包。解答:
(1)R{1,1,2,2,3,3,4,4,2,3,3,2,2,4,4,2,3,4, 14,3}
(2)由于等价关系满足对称性,所以R所以RR11R
R
(3)由于等价关系满足传递性,所以传递闭包为其自身,即t(R)R
26、对于给定的A和R,判断R是否为A上的等价关系。(1)A为实数集,x,yA,xRyxy2。(2)A{1,2,3},x,yA,xRyxy3。(3)AZ,x,yA,xRyxy为奇数。
(5)AP(X),CX,x,yA,xRyxyC 解答:
(1)不是,不满足自反性、对称性、传递性。(2)不是,由于A{1,2,3}集合较小,①自反性:xA,xx3x,xR
②对称性,x,yR,xy3yx3y,xR 但是传递性不满足,1,3,3,2R,但是1,2R。(3)不是,满足对称性、传递性,但是不满足自反性 取x2,但是224不为奇数,所以2,2R。
(5)满足
①自反性:xAxXxxCx,xR ②对称性:x,yRyxxyCy,xR ③传递性:x,y,y,zR
xyC,yzC (xy)(yx)C,(yz)(zy)C(xy)C,(yx)C,(yz)C,(zy)C下面证明(xz)C
a(xz)ax,az
若ay,则ayz,所以aC 若ay,则axy,所以aC
所以(xz)C,同理可证,(zx)C 所以xz(xz)(zx)C 所以x,zR。因此满足传递性。
27、设A{a,b,c,d},A上的等价关系
R{a,b,b,a,c,d,d,c}IA
画出R的关系图,并求出A中各元素的等价类。解答:关系图为
等价类[a][b]{a,b};[c][d]{c,d}
30、设A{1,2,3,4},,在AA上定义二元关系R,u,v,x,yAA,u,vRx,yuyxv。
(1)证明R为AA上的等价关系。(2)确定由R引起的对AA的划分。解答:(1)证明:
①自反性:x,yAA,由于xyxy,所以x,y,x,yR; ②对称性:x,y,u,vR
有xvuy,所以uyxv 因此u,v,x,yR
③传递性:x,y,u,v,u,v,s,tR
有xvuy,utsv,所以xsty 因此x,y,s,tR。
(2)等价类有
[1,1]{1,1,2,2,3,3,4,4} [1,2]{1,2,2,3,3,4} [1,3]{1,3,2,4} [1,4]{1,4} [2,1]{2,1,3,2,4,3} [3,1]{3,1,4,2} [4,1]{4,1}
37、对于下列集合与整除关系画出哈斯图。(1){1,2,3,4,6,8,12,24}(2){1,2,3,4,5,6,7,8,9,10,11,12} 解答:(1)
(2)
38、针对图7.14中的每个哈斯图,写出集合以及偏序关系的表达式。
解答:
(a)集合为A{1,2,3,4,5},偏序关系为{1,3,1,5,2,4,2,5,3,5,4,5}IA(b)集合为B{a,b,c,d,e,f},偏序关系为{a,b,c,d,e,f}IB(c)集合为C{1,2,3,4,5},偏序关系{1,2,1,3,1,4,1,5,2,4,2,5,3,4,3,5,4,5}IC
40、分别画出下列偏序集A,R的哈斯图,并找出A的极大元、极小元、最大元和最小元。
(1)A{a,b,c,d,e,f},R{a,d,a,c,a,b,a,e,b,e,c,e,d,e}IA
R{c,d}IA(2)A{a,b,c,d,e}
解答:
(1)哈斯图为
极小元为a,f,极大元为e,f,无最大元、最小元(2)哈斯图为
极小元为a,b,c,e,极大元为a,b,d,e,无最大元、最小元
41、A{1,2,3....,12},R为整除关系,B{x|2x4},在偏序集A,R中求B的上界、下界、最小上界和最大下界。
解:下界即为公约数,2,3,4的公约数只有1,所以下界为1,最大下界也为1;
下界即为公倍数,2,3,4的公倍数只有12,所以上界为1,最大上界也为12;
P141:习题八
4、判断下列函数中哪些是满射?哪些是单射?哪些是双射?(2)f:NN,f(x)x22(4)f:N{0,1},f(x)01xisodd
xiseven(6)f:RR,f(x)x22x15
解答:(2)单射;(3)满射;(4)既不为单射也不为满射。
{1,2,3}
5、设X{a,b,c,d},Y,f{a,1,b,2,c,3},判断下列命题的真假。
(1)f是从X到Y的二元关系,但不是X到Y的函数。(3)f是从X到Y的满射,但不是单射。解答:(1)真;(3)假
15、设A{a,b,c},R为A上的等价关系,且R{a,b,b,a}IA,求自然映射g:AA/R。
解答: A/R{{a,b},{c}}
{a,b}g(x)cxa,b xc19、设f,g是从N到N的函数,且
x1f(x)0x(1)求f(2)说明f解答: x0,1,2,3x4x5g
x
g(x)23xiseven
xisoddg是否为单射、满射、双射?
(1)f3x1gg(f(x))20x2x0,2,5,7,9......x1,3x4x6,8,10,12.....(2)为满射,但是不为单射。
20、设f:NNN,f(x)x,x1(1)说明f是否为单射和满射,说明理由。
(2)f的反函数是否存在,如果存在,求出f的反函数;(3)求ranf。解答:
(1)xy时,x,x1y,y1,所以为单射; 而对1,3NN,不存在xN,使得f(x)x,x1,所以不为满射。
(2)不存在反函数,因为不是双射函数;(3)ranf{x,x1|xN}
22、对于以下集合A和B,构造从A到B的双射函数。(1)A{1,2,3},B{a,b,c}(2)A(0,1),B(0,2)
(3)A{x|xZx0},BN(4)AR,BR 解答: a(1)f(x)bc(2)f(x)2xx1x2 x3x(0,1)(3)f(x)x1
(4)f(x)ax(a0,a1)
第二篇:离散数学课后习题答案
第一章部分课后习题参考答案 设p、q的真值为0;r、s的真值为1,求下列各命题公式的真值。
(1)p∨(q∧r) 0∨(0∧1)0(2)(p↔r)∧(﹁q∨s)(0↔1)∧(1∨1)0∧10.(3)(p∧q∧r)↔(p∧q∧﹁r)(1∧1∧1)↔(0∧0∧0)0(4)(r∧s)→(p∧q)(0∧1)→(1∧0)0→01 17.判断下面一段论述是否为真:“是无理数。并且,如果3是无理数,则2也是无理数。另外,只有6能被2整除,6才能被4整除。”
答:p: 是无理数
q: 3是无理数
0
r: 2是无理数
s: 6能被2整除t: 6能被4整除
0
命题符号化为: p∧(q→r)∧(t→s)的真值为1,所以这一段的论述为真。19.用真值表判断下列公式的类型:(4)(p→q)→(q→p)(5)(p∧r)(p∧q)(6)((p→q)∧(q→r))→(p→r)答:
(4)
p
q
p→q
q
p
q→p
(p→q)→(q→p)
0
0
0
0
0
0
0
0
0
0
所以公式类型为永真式
(5)公式类型为可满足式(方法如上例)(6)公式类型为永真式(方法如上例)
第二章部分课后习题参考答案
3.用等值演算法判断下列公式的类型,对不是重言式的可满足式,再用真值表法求出成真赋值.1(1)(p∧q→q)(2)(p→(p∨q))∨(p→r)(3)(p∨q)→(p∧r)答:(2)(p→(p∨q))∨(p→r)(p∨(p∨q))∨(p∨r)p∨p∨q∨r1
所以公式类型为永真式
(3)P
q
r
p∨q
p∧r
(p∨q)→(p∧r)0
0
0
0
0
0
0
0
0
0
0
0
0 0
0
0 1
0
0
0
0 1
0
1
0
0
0 1
所以公式类型为可满足式
4.用等值演算法证明下面等值式:(2)(p→q)∧(p→r)(p→(q∧r))(4)(p∧q)∨(p∧q)(p∨q)∧(p∧q)证明(2)(p→q)∧(p→r)(p∨q)∧(p∨r)p∨(q∧r))p→(q∧r)(4)(p∧q)∨(p∧q)(p∨(p∧q))∧(q∨(p∧q)(p∨p)∧(p∨q)∧(q∨p)∧(q∨q)1∧(p∨q)∧(p∧q)∧1 (p∨q)∧(p∧q)5.求下列公式的主析取范式与主合取范式,并求成真赋值
(1)(p→q)→(q∨p)(2)(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)解:
(1)主析取范式
(p→q)→(qp)(pq)(qp)(pq)(qp)(pq)(qp)(qp)(pq)(pq)(pq)(pq)(pq)m0m2m3
∑(0,2,3)主合取范式:
(p→q)→(qp)(pq)(qp)(pq)(qp)(p(qp))(q(qp))1(pq)(pq) M1
∏(1)(2)主合取范式为:
(p→q)qr(pq)qr (pq)qr0 所以该式为矛盾式.主合取范式为∏(0,1,2,3,4,5,6,7)矛盾式的主析取范式为 0(3)主合取范式为:
(p(qr))→(pqr)(p(qr))→(pqr)(p(qr))(pqr)(p(pqr))((qr))(pqr))11 1 所以该式为永真式.永真式的主合取范式为 1 主析取范式为∑(0,1,2,3,4,5,6,7)第三章部分课后习题参考答案
14.在自然推理系统P中构造下面推理的证明:(2)前提:pq,(qr),r 结论:p(4)前提:qp,qs,st,tr 结论:pq
证明:(2)
①(qr)前提引入 ②qr ①置换 ③qr ②蕴含等值式 ④r 前提引入 ⑤q ③④拒取式 ⑥pq 前提引入 ⑦¬p(3)⑤⑥拒取式
证明(4):
①tr 前提引入 ②t ①化简律 ③qs 前提引入 ④st 前提引入
⑤qt ③④等价三段论 ⑥(qt)(tq)⑤ 置换 ⑦(qt)⑥化简 ⑧q ②⑥ 假言推理 ⑨qp 前提引入 ⑩p ⑧⑨假言推理(11)pq ⑧⑩合取
15在自然推理系统P中用附加前提法证明下面各推理:
4(1)前提:p(qr),sp,q 结论:sr 证明
①s 附加前提引入 ②sp 前提引入 ③p ①②假言推理 ④p(qr)前提引入 ⑤qr ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理
16在自然推理系统P中用归谬法证明下面各推理:
(1)前提:pq,rq,rs 结论:p 证明:
①p 结论的否定引入 ②p﹁q 前提引入 ③﹁q ①②假言推理 ④¬rq 前提引入 ⑤¬r ④化简律 ⑥r¬s 前提引入 ⑦r ⑥化简律 ⑧r﹁r ⑤⑦ 合取
由于最后一步r﹁r 是矛盾式,所以推理正确.
第三篇:离散数学课后习题答案第三章
第六章部分课后习题参考答案
5.确定下列命题是否为真:
(1)
真
(2)
假(3){}
真
(4){}
真(5){a,b}{a,b,c,{a,b,c}}
真(6){a,b}{a,b,c,{a,b}}
真(7){a,b}{a,b,{{a,b}}}
真(8){a,b}{a,b,{{a,b}}}
假
6.设a,b,c各不相同,判断下述等式中哪个等式为真:(1){{a,b},c,} ={{a,b},c}
假(2){a ,b,a}={a,b}
真(3){{a},{b}}={{a,b}}
假(4){,{},a,b}={{,{}},a,b}
假 8.求下列集合的幂集:
(1){a,b,c} P(A)={ ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}(2){1,{2,3}} P(A)={ , {1}, {{2,3}}, {1,{2,3}} }(3){} P(A)={ , {} }
(4){,{}} P(A)={ , {1}, {{2,3}}, {1,{2,3}} } 14.化简下列集合表达式:(1)(AB)B)-(AB)(2)((ABC)-(BC))A 解:(1)(AB)B)-(AB)=(AB)B)~(AB)
=(AB)~(AB))B=B=
(2)((ABC)-(BC))A=((ABC)~(BC))A =(A~(BC))((BC)~(BC))A =(A~(BC))A=(A~(BC))A=A 18.某班有25个学生,其中14人会打篮球,12人会打排球,6人会打篮球和排球,5人会打篮球和网 球,还有2人会打这三种球。已知6个会打网球的人都会打篮球或排球。求不会打球的人数。解: 阿A={会打篮球的人},B={会打排球的人},C={会打 |A|=14, |B|=12, |AB|=6,|AC|=5,| ABC|=2, 如图所示。
25-(5+4+2+3)-5-1=25-14-5-1=5 不会打球的人共5人
21.设集合A={{1,2},{2,3},{1,3},{}},计算下列表达式:(1)A(2)A(3)A(4)A 解:(1)A={1,2}{2,3}{1,3}{}={1,2,3,}
(2)A={1,2}{2,3}{1,3}{}=
(3)A=123=
(4)A=
27、设A,B,C是任意集合,证明(1)(A-B)-C=A-BC(2)(A-B)-C=(A-C)-(B-C)证明
(1)(A-B)-C=(A~B)~C= A(~B~C)= A~(BC)=A-BC(2)(A-C)-(B-C)=(A~C)~(B ~C)=(A~C)(~BC)=(A~C~B)(A~CC)=(A~C~B) = A~(BC)=A-BC 由(1)得证。
网球的人} |C|=6,CAB
第七章部分课后习题参考答案
7.列出集合A={2,3,4}上的恒等关系I A,全域关系EA,小于或等于关系LA,整除关系DA.解:IA ={<2,2>,<3,3>,<4,4>} EA={<2,2>,<2,3>,<2,4>,<3,4>,<4,4>,<3,2>,<3,3>,<4,2>,<4,3>} LA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} DA={<2,4>} 13.设A={<1,2>,<2,4>,<3,3>}
B={<1,3>,<2,4>,<4,2>} 求AB,AB, domA, domB, dom(AB), ranA, ranB, ran(AB), fld(A-B).解:AB={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>} AB={<2,4>} domA={1,2,3} domB={1,2,4} dom(A∨B)={1,2,3,4} ranA={2,3,4} ranB={2,3,4} ran(AB)={4} A-B={<1,2>,<3,3>},fld(A-B)={1,2,3} 14.设R={<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>} 求RR, R-1, R{0,1,}, R[{1,2}] 解:RR={<0,2>,<0,3>,<1,3>} R-1,={<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>} R{0,1}={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>} R[{1,2}]=ran(R|{1,2})={2,3}
16.设A={a,b,c,d},R1,R2为A上的关系,其中
R1=a,a,a,b,b,d
R2a,d,b,c,b,d,c,b23求R1R2,R2R1,R1,R2。
解: R1R2={,,} R2R1={
36.设A={1,2,3,4},在AA上定义二元关系R,,
任意的,
任意的,
∴R是A×A上的等价关系
(2)∏={{<1,1>,<2,2>,<3,3>,<4,4>}, {<2,1>,<3,2>,<4,3>}, {<3,1>,<4,2>}, {<4,1>}, {<1,2>,<2,3>,<3,4>}, {<1,3>,<2,4>}, {<1,4>} }
41.设A={1,2,3,4},R为AA上的二元关系, 〈a,b〉,〈c,d〉 AA ,〈a,b〉R〈c,d〉a + b = c + d(1)证明R为等价关系.(2)求R导出的划分.(1)证明: 任意的, ∴R是 A×A上的等价关系 (2)∏={{<1,1>}, {<1,2>,<2,1>},{<1,3>,<2,2>,<3,1>},{<1,4>,<4,1>,<2,3>,<3,2>}, {<2,4>,<4,2>,<3,3>}, {<3,4>,<4,3>}, {<4,4>}} 43.对于下列集合与整除关系画出哈斯图:(1){1,2,3,4,6,8,12,24}(2){1,2,3,4,5,6,7,8,9,10,11,12} 解: ***19511 42(1)(2)45.下图是两个偏序集的哈斯图.分别写出集合A和偏序关系R的集合表达式.debafc gbcfdeag (a)(b)解:(a)A={a,b,c,d,e,f,g} R={,,,,,,,, (b)A={a,b,c,d,e,f,g} R={,,,,, edbcadeabc (1) (2)项目(1)(2)极大元: e a,b,d,e 极小元: a a,b,c,e 最大元: e 无 最小元: a 无 第八章部分课后习题参考答案 1.设f :NN,且 1,若x为奇数 f(x)=x 若x为偶数2,求f(0), f({0}), f(1), f({1}), f({0,2,4,6,…}),f({4,6,8}), f-1({3,5,7}).解:f(0)=0, f({0})={0}, f(1)=1, f({1})={1}, f({0,2,4,6,…})=N,f({4,6,8})={2,3,4}, f-1({3,5,7})={6,10,14}.4.判断下列函数中哪些是满射的?哪些是单射的?哪些是双射的?(1)f:NN, f(x)=x2+2 不是满射,不是单射 (2)f:NN,f(x)=(x)mod 3,x除以3的余数 不是满射,不是单射 1,若x为奇数(3)f:NN,f(x)= 不是满射,不是单射 0,若x为偶数 0,若x为奇数(4)f:N{0,1},f(x)= 是满射,不是单射 1,若x为偶数(5)f:N-{0}R,f(x)=lgx 不是满射,是单射 (6)f:RR,f(x)=x2-2x-15 不是满射,不是单射 5.设X={a,b,c,d},Y={1,2,3},f={,, 对 (2)f是从X到Y的函数,但不是满射,也不是单射的; 错 (3)f是从X到Y的满射,但不是单射; 错 (4)f是从X到Y的双射.错 第十章部分课后习题参考答案 4.判断下列集合对所给的二元运算是否封闭:(1)整数集合Z和普通的减法运算。 封闭,不满足交换律和结合律,无零元和单位元(2)非零整数集合普通的除法运算。不封闭 (R)和矩阵加法及乘法运算,其中n2。(3)全体nn实矩阵集合封闭 均满足交换律,结合律,乘法对加法满足分配律; 加法单位元是零矩阵,无零元; 乘法单位元是单位矩阵,零元是零矩阵; (4)全体nn实可逆矩阵集合关于矩阵加法及乘法运算,其中n2。不封闭(5)正实数集合和运算,其中运算定义为: 不封闭 因为 1111111R(6)n关于普通的加法和乘法运算。 封闭,均满足交换律,结合律,乘法对加法满足分配律 加法单位元是0,无零元; 乘法无单位元(n1),零元是0;n1单位元是1(7)A = {a1,a2,,an} n运算定义如下: 封闭 不满足交换律,满足结合律,(8)S = 关于普通的加法和乘法运算。 封闭 均满足交换律,结合律,乘法对加法满足分配律(9)S = {0,1},S是关于普通的加法和乘法运算。 加法不封闭,乘法封闭;乘法满足交换律,结合律(10)S = ,S关于普通的加法和乘法运算。 加法不封闭,乘法封闭,乘法满足交换律,结合律 5.对于上题中封闭的二元运算判断是否适合交换律,结合律,分配律。 见上题 7.设 * 为Z上的二元运算x,yZ,X * Y = min(x,y),即x和y之中较小的数.(1)求4 * 6,7 * 3。 4,(2)* 在Z上是否适合交换律,结合律,和幂等律? 满足交换律,结合律,和幂等律 (3)求*运算的单位元,零元及Z中所有可逆元素的逆元。单位元无,零元1, 所有元素无逆元 8.SQQ Q为有理数集,*为S上的二元运算,, < a,b >* (2)*运算是否有单位元,零元? 如果有请指出,并求S中所有可逆元素的逆元。 设是单位元, 10.令S={a,b},S上有四个运算:*,分别有表10.8确定。 (a) (b) (c) (d) (1)这4个运算中哪些运算满足交换律,结合律,幂等律?(a)交换律,结合律,幂等律都满足,零元为a,没有单位元;(b)满足交换律和结合律,不满足幂等律,单位元为a,没有零元 a1a,b1b(c)满足交换律,不满足幂等律,不满足结合律 a(bb)aab, a(bb)(ab)b 没有单位元, 没有零元 (d)不满足交换律,满足结合律和幂等律 没有单位元, 没有零元 (2)求每个运算的单位元,零元以及每一个可逆元素的逆元。见上 (ab)baba 16.设V=〈 N,+,〉,其中+,分别代表普通加法与乘法,对下面给定的每个集合确定它是否构成V的子代数,为什么? (1)S1=(2)S2= 是 不是 加法不封闭 (3)S3 = {-1,0,1} 不是,加法不封闭 第十一章部分课后习题参考答案 8.设S={0,1,2,3},为模4乘法,即 y=(xy)mod 4 “x,y∈S, x问〈S,〉是否构成群?为什么? y=(xy)mod 4S,是S上的代数运算。解:(1)x,y∈S, x(2)x,y,z∈S,设xy=4k+r 0r3 (xy)z =((xy)mod 4) z=r z=(rz)mod 4 =(4kz+rz)mod 4=((4k+r)z)mod 4 =(xyz)mod 4 同理x(yz)=(xyz)mod 4 y)z = x1)=(1(y z),结合律成立。所以,(x(3)x∈S,(xx)=x,,所以1是单位元。 (4)111,313, 0和2没有逆元 所以,〈S,9.设Z为整数集合,在Z上定义二元运算。如下: ” x,y∈Z,xoy= x+y-2 问Z关于o运算能否构成群?为什么? 〉不构成群 解:(1)x,y∈Z, xoy= x+y-2Z,o是Z上的代数运算。(2)x,y,z∈Z,(xoy)oz =(x+y-2)oz=(x+y-2)+z-2=x+y+z-4 同理(xoy)oz= xo(yoz),结合律成立。 (3)设e是单位元,x∈Z, xoe= eox=x,即x+e-2= e+x-2=x, e=2(4)x∈Z , 设x的逆元是y, xoy= yox=e, 即x+y-2=y+x-2=2, 所以,x1y4x 所以〈Z,o〉构成群 101011.设G=01,01,101001,01,证明G关于矩阵乘法构成一个群. 解:(1)x,y∈G, 易知xy∈G,乘法是Z上的代数运算。 (2)矩阵乘法满足结合律 10(3)设01是单位元,(4)每个矩阵的逆元都是自己。所以G关于矩阵乘法构成一个群. 14.设G为群,且存在a∈G,使得 G={ak∣k∈Z} 证明:G是交换群。 证明:x,y∈G,设xak,yal,则 xyakalaklalkalakyx 所以,G是交换群 17.设G为群,证明e为G中唯一的幂等元。 22证明:设e0G也是幂等元,则e0e0,即e0e0e,由消去律知e0e 18.设G为群,a,b,c∈G,证明 ∣abc∣=∣bca∣=∣cab∣ 证明:先证设(abc)ke(bca)ke 设(abc)ke,则(abc)(abc)(abc)(abc)e,即 a(bc)(abc)(abc)a(bc)aa1e 左边同乘a1,右边同乘a得 (bca)(bca)(bca)(bca)(bac)ka1eae 反过来,设(bac)ke,则(abc)ke.由元素阶的定义知,∣abc∣=∣bca∣,同理∣bca∣=∣cab∣ 19.证明:偶数阶群G必含2阶元。 证明:设群G不含2阶元,aG,当ae时,a是一阶元,当ae时,a至少是3阶元,因为群G时有限阶的,所以a是有限阶的,设a是k阶的,则a1也是k阶的,所以高于3阶的元成对出现的,G不含2阶元,G含唯一的1阶元e,这与群G是偶数阶的矛盾。所以,偶数阶群G必含2阶元 20.设G为非Abel群,证明G中存在非单位元a和b,a≠b,且ab=ba.证明:先证明G含至少含3阶元。 若G只含1阶元,则G={e},G为Abel群矛盾; 若G除了1阶元e外,其余元a均为2阶元,则a2e,a1a a,bG,a1a,b1b,(ab)1ab,所以aba1b1(ba)1ba,与G为Abel群矛盾; 所以,G含至少含一个3阶元,设为a,则aa2,且a2aaa2。令ba2的证。 21.设G是Mn(R)上的加法群,n≥2,判断下述子集是否构成子群。(1)全体对称矩阵 是子群(2)全体对角矩阵 是子群 (3)全体行列式大于等于0的矩阵.不是子群(4)全体上(下)三角矩阵。是子群 22.设G为群,a是G中给定元素,a的正规化子N(a)表示G中与a可交换的元素构成的集合,即 N(a)={x∣x∈G∧xa=ax} 证明N(a)构成G的子群。证明:ea=ae,eN(a) x,yN(a),则axxa,ayya a(xy)(ax)y(xa)yx(ay)x(ya)(xy)a,所以xyN(a) 由axxa,得x1axx1x1xax1,x1aeeax1,即x1aax1,所以x1N(a)所以N(a)构成G的子群 31.设1是群G1到G2的同态,2是G2到G3的同态,证明12是G1到G3的同态。证明:有已知1是G1到G2的函数,2是G2到G3的函数,则1·2是G1到G3的函数。 a,bG1,(12)(ab)2(1(ab))2(1(a)1(b)) (2(1(a)))(2(1(b)))(12)(a)(12)(b)所以:1·2是G1到G3的同态。 33.证明循环群一定是阿贝尔群,说明阿贝尔群是否一定为循环群,并证明你的结论。 证明:设G是循环群,令G=,x,yG,令xak,yal,那么 xyakalaklalkalakyx,G是阿贝尔群 克莱因四元群,G{e,a,b,c} eeabceabcaaecb bbceaccbae是交换群,但不是循环群,因为e是一阶元,a,b,c是二阶元。36.设,是5元置换,且 123451234521453,34512 (1)计算,,1,1,1;(2)将,1,1表成不交的轮换之积。 (3)将(2)中的置换表示成对换之积,并说明哪些为奇置换,哪些为偶置换。 1234512345112345解:(1) 4532143125 45123 11234512345121534 54132 )1(14253(2)(1425)(25))1(143(3)(14)(12)(15)奇置换,1(14)(12)(15)(13)偶置换 1(14)(13)(25)奇置换 离散数学考试试题(A卷及答案) 一、(10分)某项工作需要派A、B、C和D 4个人中的2个人去完成,按下面3个条件,有几种派法?如何派? (1)若A去,则C和D中要去1个人; (2)B和C不能都去; (3)若C去,则D留下。 解设A:A去工作;B:B去工作;C:C去工作;D:D去工作。则根据题意应有:ACD,(B∧C),CD必须同时成立。因此 (ACD)∧(B∧C)∧(CD) (A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D) (A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D)) (A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D) ∨(C∧ D∧B∧C)∨(C∧ D∧B∧D)∨(C∧ D∧C)∨(C∧ D∧C∧D)∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D∧C∧D) F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F (A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D) (A∧C)∨(B∧C∧ D)∨(C∧D) T 故有三种派法:B∧D,A∧C,A∧D。 二、(15分)在谓词逻辑中构造下面推理的证明:某学术会议的每个成员都是专家并且是工人,有些成员是青年人,所以,有些成员是青年专家。 解:论域:所有人的集合。S(x):x是专家;W(x):x是工人;Y(x):x是青年人;则推理化形式为: x(S(x)∧W(x)),xY(x)x(S(x)∧Y(x)) 下面给出证明: (1)xY(x)P (2)Y(c)T(1),ES (3)x(S(x)∧W(x))P (4)S(c)∧W(c)T(3),US (5)S(c)T(4),I (6)S(c)∧Y(c)T(2)(5),I (7)x(S(x)∧Y(x))T(6),EG 三、(10分)设A、B和C是三个集合,则AB(BA)。 证明:ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA) x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB) (x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A)) (BA)。 四、(15分)设A={1,2,3,4,5},R是A上的二元关系,且R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>},求r(R)、s(R)和t(R)。 解r(R)=R∪IA={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>} s(R)=R∪R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>} R={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>} R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<5,4>} R={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>}=R t(R)=Ri={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,i14232- 15>}。 五、(10分)R是非空集合A上的二元关系,若R是对称的,则r(R)和t(R)是对称的。 证明对任意的x、y∈A,若xr(R)y,则由r(R)=R∪IA得,xRy或xIAy。因R与IA对称,所以有yRx或yIAx,于是yr(R)x。所以r(R)是对称的。 下证对任意正整数n,R对称。 因R对称,则有xRyz(xRz∧zRy)z(zRx∧yRz)yRx,所以R对称。若Rn对称,则xRn1yz(xRnz∧zRy)z(zRnx∧yRz)yRn1x,所以Rn1对称。因此,对任意正整数n,Rn对称。对任意的x、y∈A,若xt(R)y,则存在m使得xRy,于是有yRx,即有yt(R)x。因此,t(R)是对称的。 六、(10分)若f:A→B是双射,则f:B→A是双射。 证明因为f:A→B是双射,则f是B到A的函数。下证f是双射。 对任意x∈A,必存在y∈B使f(x)=y,从而f(y)=x,所以f是满射。 对任意的y1、y2∈B,若f(y1)=f(y2)=x,则f(x)=y1,f(x)=y2。因为f:A→B是函数,则y1=y2。所以f是单射。 综上可得,f:B→A是双射。 七、(10分)设 证明因为 因为S是有限集,所以必存在j>i,使得bi=bj。令p=j-i,则bj=bp*bj。所以对q≥i,有bq=bp*bq。 因为p≥1,所以总可找到k≥1,使得kp≥i。对于bkp∈S,有bkp=bp*bkp=bp*(bp*bkp)=…=232-1-1-1-1-1-1-1-1-1mm222nbkp*bkp。 令a=bkp,则a∈S且a*a=a。 八、(20分)(1)若G是连通的平面图,且G的每个面的次数至少为l(l≥3),则G的边数m与结点数n有如下关系: m≤ rl(n-2)。l2l证明设G有r个面,则2m= 2)。d(f)≥lr。由欧拉公式得,n-m+r=2。于是,m≤l2(n-ii 1(2)设平面图G= 证明设G= 离散数学考试试题(B卷及答案) 一、(10分)证明(P∨Q)∧(PR)∧(QS)S∨R 证明因为S∨RRS,所以,即要证(P∨Q)∧(PR)∧(QS)RS。 (1)R附加前提 (2)PRP (3)PT(1)(2),I (4)P∨QP (5)QT(3)(4),I (6)QSP (7)ST(5)(6),I (8)RSCP (9)S∨RT(8),E 二、(15分)根据推理理论证明:每个考生或者勤奋或者聪明,所有勤奋的人都将有所作为,但并非所有考生都将有所作为,所以,一定有些考生是聪明的。 设P(e):e是考生,Q(e):e将有所作为,A(e):e是勤奋的,B(e):e是聪明的,个体域:人的集合,则命题可符号化为:x(P(x)(A(x)∨B(x))),x(A(x)Q(x)),x(P(x)Q(x))x(P(x)∧B(x))。 (1)x(P(x)Q(x))P (2)x(P(x)∨Q(x))T(1),E (3)x(P(x)∧Q(x))T(2),E (4)P(a)∧Q(a)T(3),ES (5)P(a)T(4),I (6)Q(a)T(4),I (7)x(P(x)(A(x)∨B(x))P (8)P(a)(A(a)∨B(a))T(7),US (9)A(a)∨B(a)T(8)(5),I (10)x(A(x)Q(x))P (11)A(a)Q(a)T(10),US (12)A(a)T(11)(6),I (13)B(a)T(12)(9),I (14)P(a)∧B(a)T(5)(13),I (15)x(P(x)∧B(x))T(14),EG 三、(10分)某班有25名学生,其中14人会打篮球,12人会打排球,6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数。 解设A、B、C分别表示会打排球、网球和篮球的学生集合。则: |A|=12,|B|=6,|C|=14,|A∩C|=6,|B∩C|=5,|A∩B∩C|=2,|(A∪C)∩B|=6。 因为|(A∪C)∩B|=(A∩B)∪(B∩C)|=|(A∩B)|+|(B∩C)|-|A∩B∩C|=|(A∩B)|+5-2=6,所以|(A∩ B)|=3。于是|A∪B∪C|=12+6+14-6-5-3+2=20,|ABC|=25-20=5。故,不会打这三种球的共5人。 四、(10分)设A1、A2和A3是全集U的子集,则形如Ai(Ai为Ai或Ai)的集合称为由A1、A2和 i1 3A3产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。 证明小项共8个,设有r个非空小项s1、s2、…、sr(r≤8)。 对任意的a∈U,则a∈Ai或a∈Ai,两者必有一个成立,取Ai为包含元素a的Ai或Ai,则a∈Ai,i13即有a∈si,于是Usi。又显然有siU,所以U=si。 i1i1i1i1rrrr 任取两个非空小项sp和sq,若sp≠sq,则必存在某个Ai和Ai分别出现在sp和sq中,于是sp∩sq=。综上可知,{s1,s2,…,sr}是U的一个划分。 五、(15分)设R是A上的二元关系,则:R是传递的R*RR。 证明(5)若R是传递的,则 反之,若R*RR,则对任意的x、y、z∈A,如果xRz且zRy,则 六、(15分)若G为连通平面图,则n-m+r=2,其中,n、m、r分别为G的结点数、边数和面数。证明对G的边数m作归纳法。 当m=0时,由于G是连通图,所以G为平凡图,此时n=1,r=1,结论自然成立。 假设对边数小于m的连通平面图结论成立。下面考虑连通平面图G的边数为m的情况。 设e是G的一条边,从G中删去e后得到的图记为G,并设其结点数、边数和面数分别为n、m和r。对e分为下列情况来讨论: 若e为割边,则G有两个连通分支G1和G2。Gi的结点数、边数和面数分别为ni、mi和ri。显然n1+n2=n=n,m1+m2=m=m-1,r1+r2=r+1=r+1。由归纳假设有n1-m1+r1=2,n2-m2+r2=2,从而(n1+n2)-(m1+m2)+(r1+r2)=4,n-(m-1)+(r+1)=4,即n-m+r=2。 若e不为割边,则n=n,m=m-1,r=r-1,由归纳假设有n-m+r=2,从而n-(m-1)+r-1=2,即n-m+r=2。 由数学归纳法知,结论成立。 七、(10分)设函数g:A→B,f:B→C,则: (1)fg是A到C的函数; (2)对任意的x∈A,有fg(x)=f(g(x))。 证明(1)对任意的x∈A,因为g:A→B是函数,则存在y∈B使 对任意的x∈A,若存在y1、y2∈C,使得 综上可知,fg是A到C的函数。 (2)对任意的x∈A,由g:A→B是函数,有 八、(15分)设 一个等价关系,且[a]R=aH。 证明对于任意a∈G,必有a1∈G使得a1*a=e∈H,所以∈R。-- 若∈R,则a1*b∈H。因为H是G的子群,故(a1*b)1=b1*a∈H。所以∈R。---- 若∈R,∈R,则a1*b∈H,b1*c∈H。因为H是G的子群,所以(a1*b)*(b1*c)=a---- -1*c∈H,故∈R。 综上可得,R是G中的一个等价关系。 对于任意的b∈[a]R,有∈R,a1*b∈H,则存在h∈H使得a1*b=h,b=a*h,于是b∈aH,-- [a]RaH。对任意的b∈aH,存在h∈H使得b=a*h,a1*b=h∈H,∈R,故aH[a]R。所以,[a]R- =aH。第四篇:离散数学课后习题答案第四章
第五篇:离散数学习题及答案
是一个半群,如果S是有限集,则必存在a∈S,使得a*a=a。是一个半群,对任意的b∈S,由*的封闭性可知,b=b*b∈S,b=b*b∈S,…,bn∈S,…。