离散数学试题及答案.doc
《离散数学试题及答案.doc》由会员分享,可在线阅读,更多相关《离散数学试题及答案.doc(17页珍藏版)》请在咨信网上搜索。
离散数学试题及答案 一、填空题 1 设集合A,B,其中A={1,2,3}, B= {1,2}, 则A - B=____________________; r(A) - r(B)= __________________________ . 2. 设有限集合A, |A| = n, 则 |r(A×A)| = __________________________. 3. 设集合A = {a, b}, B = {1, 2}, 则从A到B所有映射是__________________________ _____________, 其中双射是__________________________. 4. 已知命题公式G=Ø(P®Q)∧R,则G主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树,G有7个点,其中4个叶点,则G总度数为__________,分枝点数为________________. 6 设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从AÇB=_________________________; AÈB=_________________________;A-B= _____________________ . 7. 设R是集合A上等价关系,则R所具有关系三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G=Ø(P®(QÙR)),则使公式G为真解释有__________________________,_____________________________, __________________________. 9. 设集合A={1,2,3,4}, A上关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1·R2 = ________________________,R2·R1 =____________________________, R12 =________________________. 10. 设有限集A, B,|A| = m, |B| = n, 则| |r(A´B)| = _____________________________. 11 设A,B,R是三个集合,其中R是实数集,A = {x | -1≤x≤1, xÎR}, B = {x | 0≤x < 2, xÎR},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13. 设集合A={2, 3, 4, 5, 6},R是A上整除,则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = "xP(x)®$xQ(x),则G前束范式是__________________________ _____. 15.设G是具有8个顶点树,则G中增长_________条边才能把G变成完全图。 16. 设谓词定义域为{a, b},将体现式"xR(x)→$xS(x)中量词消除,写成与之对应命题公式是__________________________________________________________________________. 17. 设集合A={1, 2, 3, 4},A上二元关系R={(1,1),(1,2),(2,3)}, S={(1,3),(2,3),(3,2)}。则R×S=_____________________________________________________, R2=______________________________________________________. 二、选择题 1 设集合A={2,{a},3,4},B = {{a},3,4,1},E为全集,则下列命题对是( )。 (A){2}ÎA (B){a}ÍA (C)ÆÍ{{a}}ÍBÍE (D){{a},1,3,4}ÌB. 2 设集合A={1,2,3},A上关系R={(1,1),(2,2),(2,3),(3,2),(3,3)},则R不具有( ). (A)自反性 (B)传递性 (C)对称性 (D)反对称性 1 2 3 4 5 6 3 设半序集(A,≤)关系≤哈斯图如下所示,若A子集B = {2,3,4,5},则元素6为B( )。 (A)下界 (B)上界 (C)最小上界 (D)以上答案都不对 4 下列语句中,( )是命题。 (A)请把门关上 (B)地球外星球上也有人 (C)x + 5 > 6 (D)下午有会吗? 5 设I是如下一种解释:D={a,b}, 则在解释I下取真值为1公式是( ). (A)$x"yP(x,y) (B)"x"yP(x,y) (C)"xP(x,x) (D)"x$yP(x,y). 6. 若供选择答案中数值表达一种简朴图中各个顶点度,能画出图是( ). (A)(1,2,2,3,4,5) (B)(1,2,3,4,5,5) (C)(1,1,1,2,3) (D)(2,3,3,4,5,6). 7. 设G、H是一阶逻辑公式,P是一种谓词,G=$xP(x), H="xP(x),则一阶逻辑公式G®H是( ). (A)恒真 (B)恒假 (C)可满足 (D)前束范式. 8 设命题公式G=Ø(P®Q),H=P®(Q®ØP),则G与H关系是( )。 (A)GÞH (B)HÞG (C)G=H (D)以上都不是. 9 设A, B为集合,当( )时A-B=B. (A)A=B (B)AÍB (C)BÍA (D)A=B=Æ. 10 设集合A = {1,2,3,4}, A上关系R={(1,1),(2,3),(2,4),(3,4)}, 则R具有( )。 (A)自反性 (B)传递性 (C)对称性 (D)以上答案都不对 11 下列有关集合表达中对为( )。 (A){a}Î{a,b,c} (B){a}Í{a,b,c} (C)ÆÎ{a,b,c} (D){a,b}Î{a,b,c} 12 命题"xG(x)取真值1充足必要条件是( ). (A) 对任意x,G(x)都取真值1. (B)有一种x0,使G(x0)取真值1. (C)有某些x,使G(x0)取真值1. (D)以上答案都不对. 13. 设G是连通平面图,有5个顶点,6个面,则G边数是( ). (A) 9条 (B) 5条 (C) 6条 (D) 11条. 14. 设G是5个顶点完全图,则从G中删去( )条边可以得到树. (A)6 (B)5 (C)10 (D)4. 15. 设图G相邻矩阵为,则G顶点数与边数分别为( ). (A)4, 5 (B)5, 6 (C)4, 10 (D)5, 8. 三、计算证明题 1.设集合A={1, 2, 3, 4, 6, 8, 9, 12},R为整除关系。 (1) 画出半序集(A,R)哈斯图; (2) 写出A子集B = {3,6,9,12}上界,下界,最小上界,最大下界; (3) 写出A最大元,最小元,极大元,极小元。 2. 设集合A={1, 2, 3, 4},A上关系R={(x,y) | x, yÎA 且 x ³ y}, 求 (1) 画出R关系图; (2) 写出R关系矩阵. 3. 设R是实数集合,s,t,j是R上三个映射,s(x) = x+3, t(x) = 2x, j(x) = x/4,试求复合映射s•t,s•s, s•j, j•t,s•j•t. 4. 设I是如下一种解释:D = {2, 3}, a b f (2) f (3) P(2, 2) P(2, 3) P(3, 2) P(3, 3) 3 2 3 2 0 0 1 1 试求 (1) P(a, f (a))∧P(b, f (b)); (2) "x$y P (y, x). 5. 设集合A={1, 2, 4, 6, 8, 12},R为A上整除关系。 (1) 画出半序集(A,R)哈斯图; (2) 写出A最大元,最小元,极大元,极小元; (3) 写出A子集B = {4, 6, 8, 12}上界,下界,最小上界,最大下界. 6. 设命题公式G = Ø(P→Q)∨(Q∧(ØP→R)), 求G主析取范式。 7. (9分)设一阶逻辑公式:G = ("xP(x)∨$yQ(y))→"xR(x),把G化成前束范式. 9. 设R是集合A = {a, b, c, d}. R是A上二元关系, R = {(a,b), (b,a), (b,c), (c,d)}, (1) 求出r(R), s(R), t(R); (2) 画出r(R), s(R), t(R)关系图. 11. 通过求主析取范式判断下列命题公式与否等价: (1) G = (P∧Q)∨(ØP∧Q∧R) (2) H = (P∨(Q∧R))∧(Q∨(ØP∧R)) 13. 设R和S是集合A={a, b, c, d}上关系,其中R={(a, a),(a, c),(b, c),(c, d)}, S={(a, b),(b, c),(b, d),(d, d)}. (1) 试写出R和S关系矩阵; (2) 计算R•S, R∪S, R-1, S-1•R-1. 四、证明题 1. 运用形式演绎法证明:{P→Q, R→S, P∨R}蕴涵Q∨S。 2. 设A,B为任意集合,证明:(A-B)-C = A-(B∪C). 3. (本题10分)运用形式演绎法证明:{ØA∨B, ØC→ØB, C→D}蕴涵A→D。 4. (本题10分)A, B为两个任意集合,求证: A-(A∩B) = (A∪B)-B . 参照答案 一、填空题 1. {3}; {{3},{1,3},{2,3},{1,2,3}}. 2. . 3. a1= {(a,1), (b,1)}, a2= {(a,2), (b,2)},a3= {(a,1), (b,2)}, a4= {(a,2), (b,1)}; a3, a4. 4. (P∧ØQ∧R). 5. 12, 3. 6. {4}, {1, 2, 3, 4}, {1, 2}. 7. 自反性;对称性;传递性. 8. (1, 0, 0), (1, 0, 1), (1, 1, 0). 9. {(1,3),(2,2),(3,1)}; {(2,4),(3,3),(4,2)}; {(2,2),(3,3)}. 10. 2m´n. 11. {x | -1≤x < 0, xÎR}; {x | 1 < x < 2, xÎR}; {x | 0≤x≤1, xÎR}. 12. 12; 6. 13. {(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)}. 14. $x(ØP(x)∨Q(x)). 15. 21. 16. (R(a)∧R(b))→(S(a)∨S(b)). 17. {(1, 3),(2, 2)}; {(1, 1),(1, 2),(1, 3)}. 二、选择题 1. C. 2. D. 3. B. 4. B. 5. D. 6. C. 7. C. 8. A. 9. D. 10. B. 11. B. 13. A. 14. A. 15. D 三、计算证明题 1. (1) (2) B无上界,也无最小上界。下界1, 3; 最大下界是3. (3) A无最大元,最小元是1,极大元8, 12, 90+; 极小元是1. 2.R = {(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)}. (1) (2) 3. (1)s•t=s(t(x))=t(x)+3=2x+3=2x+3. (2)s•s=s(s(x))=s(x)+3=(x+3)+3=x+6, (3)s•j=s(j(x))=j(x)+3=x/4+3, (4)j•t=j(t(x))=t(x)/4=2x/4 = x/2, (5)s•j•t=s•(j•t)=j•t+3=2x/4+3=x/2+3. 4. (1) P(a, f (a))∧P(b, f (b)) = P(3, f (3))∧P(2, f (2)) = P(3, 2)∧P(2, 3) = 1∧0 = 0. (2) "x$y P (y, x) = "x (P (2, x)∨P (3, x)) = (P (2, 2)∨P (3, 2))∧(P (2, 3)∨P (3, 3)) = (0∨1)∧(0∨1) = 1∧1 = 1. 5. (1) (2) 无最大元,最小元1,极大元8, 12; 极小元是1. (3) B无上界,无最小上界。下界1, 2; 最大下界2. 6. G = Ø(P→Q)∨(Q∧(ØP→R)) = Ø(ØP∨Q)∨(Q∧(P∨R)) = (P∧ØQ)∨(Q∧(P∨R)) = (P∧Ø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)∨(P∧ØQ∧ØR)∨(P∧Q∧R)∨(P∧Q∧ØR)∨(ØP∧Q∧R) = m3∨m4∨m5∨m6∨m7 = S(3, 4, 5, 6, 7). 7. G = ("xP(x)∨$yQ(y))→"xR(x) = Ø("xP(x)∨$yQ(y))∨"xR(x) = (Ø"xP(x)∧Ø$yQ(y))∨"xR(x) = ($xØP(x)∧"yØQ(y))∨"zR(z) = $x"y"z((ØP(x)∧ØQ(y))∨R(z)) 9. (1) r(R)=R∪IA={(a,b), (b,a), (b,c), (c,d), (a,a), (b,b), (c,c), (d,d)}, s(R)=R∪R-1={(a,b), (b,a), (b,c), (c,b) (c,d), (d,c)}, t(R)=R∪R2∪R3∪R4={(a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d), (c,d)}; (2)关系图: 11. G=(P∧Q)∨(ØP∧Q∧R) =(P∧Q∧ØR)∨(P∧Q∧R)∨(ØP∧Q∧R) =m6∨m7∨m3 =å (3, 6, 7) H = (P∨(Q∧R))∧(Q∨(ØP∧R)) =(P∧Q)∨(Q∧R))∨(ØP∧Q∧R) =(P∧Q∧ØR)∨(P∧Q∧R)∨(ØP∧Q∧R)∨(P∧Q∧R)∨(ØP∧Q∧R) =(P∧Q∧ØR)∨(ØP∧Q∧R)∨(P∧Q∧R) =m6∨m3∨m7 =å (3, 6, 7) G,H主析取范式相似,因此G = H. 13. (1) (2)R•S={(a, b),(c, d)}, R∪S={(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d)}, R-1={(a, a),(c, a),(c, b),(d, c)}, S-1•R-1={(b, a),(d, c)}. 四 证明题 1. 证明:{P→Q, R→S, P∨R}蕴涵Q∨S (1) P∨R P (2) ØR→P Q(1) (3) P→Q P (4) ØR→Q Q(2)(3) (5) ØQ→R Q(4) (6) R→S P (7) ØQ→S Q(5)(6) (8) Q∨S Q(7) 2. 证明:(A-B)-C = (A∩~B)∩~C = A∩(~B∩~C) = A∩~(B∪C) = A-(B∪C) 3. 证明:{ØA∨B, ØC→ØB, C→D}蕴涵A→D (1) A D(附加) (2) ØA∨B P (3) B Q(1)(2) (4) ØC→ØB P (5) B→C Q(4) (6) C Q(3)(5) (7) C→D P (8) D Q(6)(7) (9) A→D D(1)(8) 因此 {ØA∨B, ØC→ØB, C→D}蕴涵A→D. 4. 证明:A-(A∩B) = A∩~(A∩B) =A∩(~A∪~B) =(A∩~A)∪(A∩~B) =Æ∪(A∩~B) =(A∩~B) =A-B 而 (A∪B)-B = (A∪B)∩~B = (A∩~B)∪(B∩~B) = (A∩~B)∪Æ = A-B 因此:A-(A∩B) = (A∪B)-B. 离散数学试题(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去工作。则根据题意应有:A®CÅD,Ø(B∧C),C®ØD必须同步成立。因此 (A®CÅD)∧Ø(B∧C)∧(C®ØD) Û(Ø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分)在谓词逻辑中构造下面推理证明:某学术会议每个组员都是专家并且是工人,有些组员是青年人,因此,有些组员是青年专家。 解:论域:所有人集合。():是专家;():是工人;():是青年人;则推理化形式为: (()∧()),()(()∧()) 下面给出证明: (1)() P (2)(c) T(1),ES (3)(()∧()) P (4)( c)∧( c) T(3),US (5)( c) T(4),I (6)( c)∧(c) T(2)(5),I (7)(()∧()) T(6) ,EG 三、(10分)设A、B和C是三个集合,则AÌBÞØ(BÌA)。 证明:AÌBÛ"x(x∈A→x∈B)∧$x(x∈B∧xÏA)Û"x(xÏA∨x∈B)∧$x(x∈B∧xÏA) ÛØ$x(x∈A∧xÏB)∧Ø"x(xÏB∨x∈A)ÞØ$x(x∈A∧xÏB)∨Ø"x(x∈A∨xÏB) ÛØ($x(x∈A∧xÏB)∧"x(x∈A∨xÏB))ÛØ($x(x∈A∧xÏB)∧"x(x∈B→x∈A)) ÛØ(BÌA)。 四、(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-1={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>} R2={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>} R3={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<5,4>} R4={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>}=R2 t(R)=Ri={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,5>}。 五、(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,Rn对称。 因R对称,则有xR2yÛ$z(xRz∧zRy)Û$z(zRx∧yRz)ÛyR2x,因此R2对称。若对称,则xyÛ$z(xz∧zRy)Û$z(zx∧yRz)Ûyx,因此对称。因此,对任意正整数n,对称。 对任意x、y∈A,若xt(R)y,则存在m使得xRmy,于是有yRmx,即有yt(R)x。因此,t(R)是对称。 六、(10分)若f:A→B是双射,则f-1:B→A是双射。 证明 由于f:A→B是双射,则f-1是B到A函数。下证f-1是双射。 对任意x∈A,必存在y∈B使f(x)=y,从而f-1(y)=x,因此f-1是满射。 对任意y1、y2∈B,若f-1(y1)=f-1(y2)=x,则f(x)=y1,f(x)=y2。由于f:A→B是函数,则y1=y2。因此f-1是单射。 综上可得,f-1:B→A是双射。 七、(10分)设<S,*>是一种半群,假如S是有限集,则必存在a∈S,使得a*a=a。 证明 由于<S,*>是一种半群,对任意b∈S,由*封闭性可知,b2=b*b∈S,b3=b2*b∈S,…,bn∈S,…。 由于S是有限集,因此必存在j>i,使得=。令p=j-i,则=*。因此对q≥i,有=*。 由于p≥1,因此总可找到k≥1,使得kp≥i。对于∈S,有=*=*(*)=…=*。 令a=,则a∈S且a*a=a。 八、(20分)(1)若G是连通平面图,且G每个面次数至少为l(l≥3),则G边数m与结点数n有如下关系: m≤(n-2)。 证明 设G有r个面,则2m=≥lr。由欧拉公式得,n-m+r=2。于是, m≤(n-2)。 (2)设平面图G=<V,E,F>是自对偶图,则| E|=2(|V|-1)。 证明 设G*=<V*,E*>是连通平面图G=<V,E,F>对偶图,则G*@ G,于是|F|=|V*|=|V|,将其代入欧拉公式|V|-|E|+|F|=2得,|E|=2(|V|-1)。 离散数学试题(B卷及答案) 一、(10分)证明(P∨Q)∧(P®R)∧(Q®S)S∨R 证明 由于S∨RÛØR®S,因此,即要证(P∨Q)∧(P®R)∧(Q®S)ØR®S。 (1)ØR 附加前提 (2)P®R P (3)ØP T(1)(2),I (4)P∨Q P (5)Q T(3)(4),I (6)Q®S P (7)S T(5)(6),I (8)ØR®S CP (9)S∨R T(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,=25-20=5。故,不会打这三种球共5人。 四、(10分)设A1、A2和A3是全集U子集,则形如Ai¢(Ai¢为Ai或)集合称为由A1、A2和A3产生小项。试证由A1、A2和A3所产生所有非空小项集合构成全集U一种划分。 证明 小项共8个,设有r个非空小项s1、s2、…、sr(r≤8)。 对任意a∈U,则a∈Ai或a∈,两者必有一种成立,取Ai¢为包括元素aAi或,则a∈Ai¢,即有a∈si,于是UÍsi。又显然有siÍU,因此U=si。 任取两个非空小项sp和sq,若sp≠sq,则必存在某个Ai和分别出目前sp和sq中,于是sp∩sq=Æ。 综上可知,{s1,s2,…,sr}是U一种划分。 五、(15分)设R是A上二元关系,则:R是传递ÛR*RÍR。 证明 (5)若R是传递,则<x,y>∈R*RÞ$z(xRz∧zSy)ÞxRc∧cSy,由R是传递得xRy,即有<x,y>∈R,因此R*RÍR。 反之,若R*RÍR,则对任意x、y、z∈A,假如xRz且zRy,则<x,y>∈R*R,于是有<x,y>∈R,即有xRy,因此R是传递。 六、(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)fog是A到C函数; (2)对任意x∈A,有fog(x)=f(g(x))。 证明 (1)对任意x∈A,由于g:A→B是函数,则存在y∈B使<x,y>∈g。对于y∈B,因f:B→C是函数,则存在z∈C使<y,z>∈f。根据复合关系定义,由<x,y>∈g和<y,z>∈f得<x,z>∈g*f,即<x,z>∈fog。因此Dfog=A。 对任意x∈A,若存在y1、y2∈C,使得<x,y1>、<x,y2>∈fog=g*f,则存在t1使得<x,t1>∈g且<t1, y1>∈f,存在t2使得<x,t2>∈g且<t2,y2>∈f。由于g:A→B是函数,则t1=t2。又因f:B→C是函数,则y1=y2。因此A中每个元素对应C中惟一元素。 综上可知,fog是A到C函数。 (2)对任意x∈A,由g:A→B是函数,有<x,g(x)>∈g且g(x)∈B,又由f:B→C是函数,得<g(x),f(g(x))>∈f,于是<x,f(g(x))>∈g*f=fog。又因fog是A到C函数,则可写为fog(x)=f(g(x))。 八、(15分)设<H,*>是<G,*>子群,定义R={<a,b>|a、b∈G且a-1*b∈H},则R是G中一种等价关系,且[a]R=aH。 证明 对于任意a∈G,必有a-1∈G使得a-1*a=e∈H,因此<a,a>∈R。 若<a,b>∈R,则a-1*b∈H。由于H是G子群,故(a-1*b)-1=b-1*a∈H。因此<b,a>∈R。 若<a,b>∈R,<b,c>∈R,则a-1*b∈H,b-1*c∈H。由于H是G子群,因此(a-1*b)*(b-1*c)=a-1*c∈H,故<a,c>∈R。 综上可得,R是G中一种等价关系。 对于任意b∈[a]R,有<a,b>∈R,a-1*b∈H,则存在h∈H使得a-1*b=h,b=a*h,于是b∈aH,[a]RÍaH。对任意b∈aH,存在h∈H使得b=a*h,a-1*b=h∈H,<a,b>∈R,故aHÍ[a]R。因此,[a]R=aH。- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 试题 答案
咨信网温馨提示:
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。
关于本文