离散数学期末考试试题及答案

1、离散数学试题(B卷答案1）一、证明题（10分）1)(ØP(ØQR)(QR)(PR)ÛR证明: 左端Û(ØPØQR)(QP)R)Û(ØPØQ)R)(QP)R)Û(Ø(PQ)R)(QP)R)Û(Ø(PQ)(QP)RÛ(Ø(PQ)(PQ)RÛTR(置换)ÛR2) $x (A(x)®B(x)Û "xA(x)®$xB(x)证明 ：$x(A(x)®B(x)Û$x(ØA(

2、x)B(x)Û$xØA(x)$xB(x)ÛØ"xA(x)$xB(x)Û"xA(x)®$xB(x)二、求命题公式(P(QR)®(PQR)的主析取范式和主合取范式（10分）。证明：(P(QR)®(PQR)ÛØ(P(QR)(PQR)Û（ØP(ØQØR)）(PQR)Û(ØPØQ)(ØPØR)(PQR)Û(ØPØQR)(ØPØQØR)(&

3、#216;PQØR)(ØPØQØR)(PQR)Ûm0m1m2m7ÛM3M4M5M6三、推理证明题（10分）1） CD， (CD)® ØE， ØE®(AØB)， (AØB)®(RS)ÞRS证明：(1) (CD)®ØE P(2) ØE®(AØB) P(3) (CD)®(AØB) T(1)(2)，I(4) (AØB)®(RS) P(5) (CD)®(RS) T(3

4、)(4)， I(6) CD P(7) RS T(5)，I 2) "x(P(x)®Q(y)R(x)，$xP(x)ÞQ(y)$x(P(x)R(x)证明(1)$xP(x) P(2)P(a) T(1)，ES(3)"x(P(x)®Q(y)R(x) P(4)P(a)®Q(y)R(a) T(3)，US(5)Q(y)R(a) T(2)(4)，I(6)Q(y) T(5)，I(7)R(a) T(5)，I(8)P(a)R(a) T(2)(7)，I(9)$x(P(x)R(x) T(8)，EG(10)Q(y)$x(P(x)R(x) T(6)(9)，I四、某班有

5、25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数（10分）。解：A，B，C分别表示会打排球、网球和篮球的学生集合。则|A|=12，|B|=6，|C|=14，|AC|=6，|BC|=5，|ABC|=2。先求|AB|。6=|（AC）B|=|（AB）（BC）|=|（AB）|+|（BC）|-|ABC|=|（AB）|+5-2，|（AB）|=3。于是|ABC|=12+6+14-6-5-3+2=20。不会打这三种球的人数25-20=5。五、已知A、B、C是三个集合，证明A-(BC)=(A-

6、B)(A-C) （10分）。证明：xÎ A-（BC）Û xÎ AxÏ（BC）Û xÎ A（xÏBxÏC）Û（xÎ AxÏB）（xÎ AxÏC）Û xÎ（A-B）xÎ（A-C）Û xÎ（A-B）（A-C）A-（BC）=（A-B）（A-C）六、已知R、S是N上的关系，其定义如下：R=<x，y>| x，yÎNy=x2，S=<x，y>| x，yÎNy=x+1。求R-1、R*S、S*

7、R、R1，2、S1，2（10分）。解：R-1=<y，x>| x，yÎNy=x2R*S=<x，y>| x，yÎNy=x2+1S*R=<x，y>| x，yÎNy=（x+1）2，R1，2=<1，1>，<2，4>，S1，2=1，4。七、设R=<a，b>，<b，c>，<c，a>，求r(R)、s(R)和t(R) （15分）。解：r(R)=<a，b>，<b，c>，<c，a>，<a，a>，<b，b>，<c，c>s(

8、R)=<a，b>，<b，c>，<c，a>，<b，a>，<c，b>，<a，c>R2= R5=<a，c>，<b，a>，<c，b>R3=<a，a>，<b，b>，<c，b>R4=<a，b>，<b，c>，<c，c>t(R)=<a，b>，<b，c>，<c，a>，<a，c>，<b，a>，<a，a>，<b，b>，<c，b>，<c，c

9、>八、证明整数集I上的模m同余关系R=<x，y>|xºy(mod m)是等价关系。其中，xºy(mod m)的含义是x-y可以被m整除（15分）。证明：1）"xI，因为（x-x）/m=0，所以xºx(mod m)，即xRx。2）"x，yI，若xRy，则xºy(mod m)，即（x-y）/m=kI，所以（y - x）/m=-kI，所以yºx(mod m)，即yRx。3）"x，y，zI，若xRy，yRz，则（x-y）/m=uI，（y-z）/m=vI，于是（x-z）/m=（x-y+y-z）/m=u+v

10、I，因此xRz。九、若f:AB和g:BC是双射，则（gf）-1=f-1g-1（10分）。证明：因为f、g是双射，所以gf：AC是双射，所以gf有逆函数（gf）-1：CA。同理可推f-1g-1：CA是双射。因为<x，y>f-1g-1Û存在z（<x，z>g-1Ù<z，y>f-1）Û存在z（<y，z>fÙ<z，x>g）Û<y，x>gfÛ<x，y>（gf）-1，所以（gf）-1=f-1g-1。离散数学试题(B卷答案2）一、证明题（10分）1)(PQ)Ø

11、;(ØP(ØQØR)(ØPØQ)(ØPØR)ÛT证明: 左端Û(PQ)(P(QR)Ø(PQ)(PR)(摩根律) Û (PQ)(PQ)(PR)Ø(PQ)(PR)(分配律) Û (PQ)(PR)Ø(PQ)(PR) (等幂律) ÛT(代入)2) "x"y(P(x)®Q(y)Û Û($xP(x)®"yQ(y)证明："x"y(P(x)®Q(y)Û&

12、quot;x"y(ØP(x)Q(y)Û"x(ØP(x)"yQ(y)Û"xØP(x)"yQ(y)ÛØ$xP(x)"yQ(y)Û($xP(x)®"yQ(y)二、求命题公式(ØP®Q)®(PØQ) 的主析取范式和主合取范式（10分）解：(ØP®Q)®(PØQ)ÛØ(ØP®Q)(PØQ)ÛØ(PQ

13、)(PØQ)Û(ØPØQ)(PØQ) Û(ØPPØQ)(ØQPØQ)Û(PØQ)ÛM1Ûm0m2m3三、推理证明题（10分）1)(P®(Q®S)(ØRP)QÞR®S证明：(1)R(2)ØRP(3)P(4)P®(Q®S)(5)Q®S(6)Q(7)S(8)R®S2) $x(A(x)®"yB(y)，"x(B(x)®$yC(y

14、)"xA(x)®$yC(y)。证明：(1)$x(A(x)®"yB(y) P (2)A(a)®"yB(y) T(1)，ES(3)"x(B(x)®$yC(y) P(4)"x(B(x)®C() T(3)，ES(5)B()®C() T(4)，US(6)A(a)®B() T(2)，US(7)A(a)®C() T(5)(6)，I(8)"xA(x)®C() T(7)，UG(9)"xA(x)®$yC(y) T(8)，EG四、只要今天天气不好，

15、就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好（15分）。解 设P：今天天气好，Q：考试准时进行，A(e)：e提前进入考场，个体域：考生的集合，则命题可符号化为：ØP®$xØA(x)，"xA(x)«QQ®P。(1)ØP®$xØA(x) P(2)ØP®Ø"xA(x) T(1)，E(3)"xA(x)®P T(2)，E (4)"xA(x)«Q P(5)("

16、xA(x)®Q)(Q®"xA(x) T(4)，E(6)Q®"xA(x) T(5)，I(7)Q®P T(6)(3)，I五、已知A、B、C是三个集合，证明A(BC)=(AB)(AC) （10分）证明：xÎ A（BC）Û xÎ AxÎ（BC）Û xÎ A（xÎBxÎC）Û（ xÎ AxÎB）（xÎ AxÎC）Û xÎ（AB）xÎ ACÛ xÎ（AB）（AC）A（B

17、C）=（AB）（AC）六、A= x1,x2,x3 ，B= y1,y2，R=<x1, y1>,<x2, y2>,<x3, y2>，求其关系矩阵及关系图（10分）。七、设R=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>，求r(R)、s(R)和t(R)，并作出它们及R的关系图（15分）。解：r(R)=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,&

18、lt;2,2>,<3,3>,<4,4>,<5,5>s(R)=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>R2=R5=<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>R3=<2,1>,<2,5>,<2,4>,<3,4>,&l

19、t;4,4>,<5,2>,<5,4>R4=<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>t(R)=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,5>八、设R1是A上的等价关系，R2是B上的等价关系，AÆ且BÆ。关系R满足：<<x1

20、，y1>，<x2，y2>>RÛ<x1，x2>R1且<y1，y2>R2，证明R是A×B上的等价关系（10分）。证明 对任意的<x，y>A×B，由R1是A上的等价关系可得<x，x>R1，由R2是B上的等价关系可得<y，y>R2。再由R的定义，有<<x，y>，<x，y>>R，所以R是自反的。对任意的<x，y>、<u，v>A×B，若<x，y>R<u，v>，则<x，u>R1且<y，

21、v>R2。由R1对称得<u，x>R1，由R2对称得<v，y>R2。再由R的定义，有<<u，v>，<x，y>>R，即<u，v>R<x，y>，所以R是对称的。对任意的<x，y>、<u，v>、<s，t>A×B，若<x，y>R<u，v>且<u，v>R<s，t>，则<x，u>R1且<y，v>R2，<u，s>R1且<v，t>R2。由<x，u>R1、<u，s&g

22、t;R1及R1的传递性得<x，s>R1，由<y，v>R2、<v，t>R2及R2的传递性得<y，t>R1。再由R的定义，有<<x，y>，<s，t>>R，即<x，y>R<s，t>，所以R是传递的。综上可得，R是A×B上的等价关系。九、设f：A®B，g：B®C，h：C®A，证明：如果hogofIA，fohogIB，gofohIC，则f、g、h均为双射，并求出f1、g1和h1（10分）。解 因IA恒等函数，由hogofIA可得f是单射，h是满射；因IB恒等

23、函数，由fohogIB可得g是单射，f是满射；因IC恒等函数，由gofohIC可得h是单射，g是满射。从而f、g、h均为双射。由hogofIA，得f1hog；由fohogIB，得g1foh；由gofohIC，得h1gof。离散数学试题(B卷答案3）一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？(写过程)1)P®(PQR) 2)Ø(Q®P)ØP)(PR) 3)(ØPQ)®R)®(PQ)R)解：1)重言式；2)矛盾式；3)可满足式二、（10分）求命题公式（P(QR)®(PQR)的主析取范式，并求成真赋值

24、。解：（P(QR)®(PQR)ÛØ(P(QR)PQRÛØP(ØQØR)PQRÛ(ØPØQ)(ØPØR)(PQ)RÛ(Ø(PQ)(PQ)(ØPØR)RÛ1(ØPØR)R)Û1Ûm0m1m2m3m4m5m6m7该式为重言式，全部赋值都是成真赋值。三、（10分）证明 (PQA)®C)(A®(PQC)Û(A(P«Q)®C证明：(PQA)®

25、;C)(A®(PQC)Û(Ø(PQA)C)(ØA(PQC)Û(ØPØQØA)C)(ØAPQ)C)Û(ØPØQØA)(ØAPQ)CÛØ(ØPØQØA)(ØAPQ)®CÛ(Ø(ØPØQØA)Ø(ØAPQ)®CÛ(PQA)(AØPØQ)®CÛ(A(PQ)(Ø

26、;PØQ)®CÛ(A(PØQ)(ØPQ)®CÛ(A(Q®P)(P®Q)®CÛ(A(P«Q)®C四、（10分）个体域为1，2，求"x$y（x+y=4）的真值。解："x$y（x+y=4）Û"x（x+1=4）（x+2=4）Û（1+1=4）（1+2=4）（2+1=4）（2+2=4）Û（00）（01）Û01Û0五、（10分）对于任意集合A，B，试证明：P(A)P(B)=P(AB)解："x

27、ÎP(A)P(B)，xÎP(A)且xÎP(B)，有xÍA且xÍB，从而xÍAB，xÎP(AB)，由于上述过程可逆，故P(A)P(B)=P(AB)六、（10分）已知A=1，2，3，4，5和R=<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，求r(R)、s(R)和t(R)。解：r(R)=<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<1，1>，<2，2>，<

28、;3，3>，<4，4>，<5，5>s(R)=<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<3，2>，<4，3>，<4，5>t(R)=<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<1，1>，<1，3>，<2，2>，<2，4>，<1，4>七、（10分）设函数f：R×R®R×R，R为实数集，f定义

29、为：f(<x，y>)=<x+y，x-y>。1)证明f是双射。解：1）"<x1，y1>，<x2，y2>R×R，若f(<x1，y1>)=f(<x2，y2>)，即<x1+y1，x1-y1>=<x2+y2，x2-y2>，则x1+y1=x2+y2且x1-y1=x2-y2得x1=x2，y1=y2从而f是单射。2）"<p，q>R×R，由f(<x，y>)=<p，q>，通过计算可得x=(p+q)/2；y=(p-q)/2；从而<p，q&g

30、t;的原象存在，f是满射。八、（10分）<G，*>是个群，uG，定义G中的运算“D”为aDb=a*u-1*b，对任意a，bG，求证：<G， D>也是个群。证明：1）"a，bG，aDb=a*u-1*bG，运算是封闭的。2）"a，b，cG，（aDb）Dc=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=aD（bDc），运算是可结合的。3）"aG，设E为D的单位元，则aDE=a*u-1*E=a，得E=u，存在单位元u。4）"aG，aDx=a*u-1*x=E，x=u*a-1*u，则xDa=u*a-1*u*u-1*a=u=E

31、，每个元素都有逆元。所以<G， D>也是个群。九、（10分）已知：D=<V，E>，V=1，2，3，4，5，E=<1，2>，<1，4>，<2，3>，<3，4>，<3，5>，<5，1>，求D的邻接距阵A和可达距阵P。解：1）D的邻接距阵A和可达距阵P如下：01010111110010011111A=00011P=1111100000000001000011111十、（10分）求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。解：最优二叉树为权(2+4)×4+6×3+1

32、2×2+(8+10)×3+14×2148离散数学试题(B卷答案4）一、证明题（10分）1)(PQ)Ø(ØP(ØQØR)(ØPØQ)(ØPØR)ÛT证明: 左端Û(PQ)(P(QR)Ø(PQ)(PR)(摩根律) Û (PQ)(PQ)(PR)Ø(PQ)(PR)(分配律) Û (PQ)(PR)Ø(PQ)(PR) (等幂律) ÛT(代入)2)"x(P(x)®Q(x)"xP(x)

33、9;"x(P(x)Q(x)证明："x(P(x)®Q(x)"xP(x)Û"x(P(x)®Q(x)P(x)Û"x(ØP(x)Q(x)P(x)Û"x(P(x)Q(x)Û"xP(x)"xQ(x)Û"x(P(x)Q(x)二、求命题公式(ØP®Q)®(PØQ) 的主析取范式和主合取范式（10分）解：(ØP®Q)®(PØQ)ÛØ(Ø

34、P®Q)(PØQ)ÛØ(PQ)(PØQ)Û(ØPØQ)(PØQ) Û(ØPPØQ)(ØQPØQ)Û(PØQ)ÛM1Ûm0m2m3三、推理证明题（10分）1)(P®(Q®S)(ØRP)QÞR®S证明：（1）R 附加前提(2)ØRP P(3)P T(1)(2),I(4)P®(Q®S) P(5)Q®S T(3)(4),I(6)Q P(

35、7)S T(5)(6),I(8)R®S CP2) "x(P(x)Q(x)，"xØP(x)Þ$x Q(x)证明：(1)"xØP(x) P(2)ØP(c) T(1),US(3)"x(P(x)Q(x) P(4)P(c)Q(c) T(3),US(5)Q(c) T(2)(4),I(6)$x Q(x) T(5),EG四、例5在边长为1的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超过1/8（10分）。证明：把边长为1的正方形分成四个全等的小正方形，则至少有一个小正方形内有

36、三个点，它们组成的三角形（可能是退化的）面积不超过小正方形的一半，即1/8。五、已知A、B、C是三个集合，证明A(BC)=(AB)(AC) （10分）证明：xÎ A（BC）Û xÎ AxÎ（BC）Û xÎ A（xÎBxÎC）Û（ xÎ AxÎB）（xÎ AxÎC）Û xÎ（AB）xÎ ACÛ xÎ（AB）（AC）A（BC）=（AB）（AC）六、p=A1，A2，An是集合A的一个划分，定义R=<a，b>|a

37、、bAi，I=1，2，n，则R是A上的等价关系（15分）。证明："aA必有i使得aAi，由定义知aRa，故R自反。"a,bA，若aRb ，则a,bAi，即b,aAi，所以bRa，故R对称。"a,b,cA，若aRb 且bRc，则a,bAi及b,cAj。因为ij时AiAj=F，故i=j，即a,b,cAi，所以aRc，故R传递。总之R是A上的等价关系。七、若f:AB是双射，则f-1:BA是双射（15分）。证明:对任意的xA，因为f是从A到B的函数，故存在yB，使<x,y>f，<y,x>f-1。所以,f-1是满射。对任意的xA，若存在y1,y2B，

38、使得<y1,x>f-1且<y2,x>f-1,则有<x,y1>f且<x,y2>f。因为f是函数，则y1=y2。所以，f-1是单射。因此f-1是双射。八、设<G，*>是群，<A，*>和<B，*>是<G，*>的子群，证明：若ABG，则AG或BG（10分）。证明 假设AG且BG，则存在aÎA，aÏB，且存在bÎB，bÏA（否则对任意的aÎA，aÎB，从而AÍB，即ABB，得BG，矛盾。）对于元素a*bÎG，若a*bÎA

39、，因A是子群，a-1ÎA，从而a-1 * (a*b)b ÎA，所以矛盾，故a*bÏA。同理可证a*bÏB，综合有a*bÏABG。综上所述，假设不成立，得证AG或BG。九、若无向图G是不连通的，证明G的补图是连通的（10分）。证明 设无向图G是不连通的，其k个连通分支为、。任取结点、G，若和不在图G的同一个连通分支中，则，不是图G的边，因而，是图的边；若和在图G的同一个连通分支中，不妨设其在连通分支（1）中，在不同于的另一连通分支上取一结点，则，和，都不是图G的边，因而，和，都是的边。综上可知，不管那种情况，和都是可达的。由和的任意性可知，是连通

40、的。离散数学试题（B卷答案5）一、（10分）求命题公式Ø(PQ)«Ø(ØP®R)的主合取范式。解：Ø(PQ)«Ø(ØP®R)Û（Ø(PQ)®Ø(ØP®R)）（Ø(ØP®R)®Ø(PQ)）Û（(PQ)(ØPØR)）（(PR)(ØPØQ)）Û(PQ)(ØPØR)Û(PØR)（QØP）

41、（QØR）Û(PQØR)(PØQØR)（ØPQR）（ØPQØR）ÛM1M3M4M5二、（8分）叙述并证明苏格拉底三段论解：所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。符号化：F（x）：x是一个人。G（x）：x要死的。A：苏格拉底。命题符号化为"x（F（x）®G（x），F（a）ÞG（a）证明：（1）"x(F(x)®G(x) P（2）F(a)®G(a) T(1),US（3）F(a) P（4）G(a) T(2)(3),I三、（8分）已知A、B

42、、C是三个集合，证明A(BC)=(AB)(AC)证明：xÎ A（BC）Û xÎ AxÎ（BC）Û xÎ A（xÎBxÎC）Û（ xÎ AxÎB）（xÎ AxÎC） Û xÎ（AB）xÎ AC Û xÎ（AB）（AC） A（BC）=（AB）（AC）四、（10分）已知R和S是非空集合A上的等价关系，试证：1）RS是A上的等价关系；2）对aA，aRS=aRaS。解："xA，因为R和S是自反关系，所以<x,x

43、>R、<x,x>S，因而<x,x>RS，故RS是自反的。"x、yA，若<x,y>RS，则<x,y>R、<x,y>S，因为R和S是对称关系，所以因<y,x>R、<y,x>S，因而<y,x>RS，故RS是对称的。"x、y、zA，若<x,y>RS且<y,z>RS，则<x,y>R、<x,y>S且<y,z>R、<y,z>S，因为R和S是传递的，所以因<x,z>R、<x,z>S，因而<

44、x,z>RS，故RS是传递的。总之RS是等价关系。2）因为xaRSÛ<x,a>RSÛ<x,a>R<x,a>SÛ xaRxaSÛ xaRaS所以aRS=aRaS。五、(10分) 设Aa，b，c，d，R是A上的二元关系，且R<a，b>，<b，a>，<b，c>，<c，d>，求r(R)、s(R)和t(R)。解 r(R)RIA<a，b>，<b，a>，<b，c>，<c，d>，<a，a>，<b，b>，<

45、c，c>，<d，d>s(R)RR-1<a，b>，<b，a>，<b，c>，<c，d>，<c，b>，<d，c>R2<a，a>，<a，c>，<b，b>，<b，d>R3<a，b>，<a，d>，<b，a>，<b，c>R4<a，a>，<a，c>，<b，b>，<b，d>R2t(R)<a，b>，<b，a>，<b，c>，<c，d>，&

46、lt;a，a>，<a，c>，<b，b>，<b，d>，<a，d>六、(15分) 设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：A×C®B×D且"<a,c>A×C，h(<a,c>)<f(a),g(c)>。证明h是双射。证明：1）先证h是满射。"<b,d>B×D，则bB，dD，因为f是A到B的双射，g是C到D的双射，所以存在aA，cC，使得f(a)=b，f(c)=d，亦即存在<a,c>A×

47、C，使得h(<a,c>)<f(a),g(c)><b,d>，所以h是满射。2）再证h是单射。"<a1,c1>、<a2,c2>A×C，若h(<a1,c1>)h(<a2,c2>)，则<f(a1),g(c1)><f(a2),g(c2)> ，所以f(a1)f(a2)，g(c1)g(c2)，因为f是A到B的双射，g是C到D的双射，所以a1a2，c1c2，所以<a1,c1><a2,c2>，所以h是单射。综合1）和2），h是双射。七、(12分)设<G，*

48、>是群，H是G的非空子集，证明<H，*>是<G，*>的子群的充要条件是若a，bÎH，则有a*b-1ÎH。证明：Þ "a,bH有b-1H，所以a*b-1H。Ü"aH，则e=a*a-1H a-1=e*a-1H a,bH及b-1H，a*b=a*（b-1）-1HHÍG且HF,*在H上满足结合律 <H，*>是<G，*>的子群。八、（10分）设G=<V，E>是简单的无向平面图，证明G至少有一个结点的度数小于等于5。解：设G的每个结点的度数都大于等于6，则2|E|=Sd(v

49、)6|V|，即|E|3|V|，与简单无向平面图的|E|3|V|-6矛盾，所以G至少有一个结点的度数小于等于5。九.G=<A,*>,A=a,b,c,*的运算表为：(写过程，7分) （1）G是否为阿贝尔群？（2）找出G的单位元；（3）找出G的幂等元（4）求b的逆元和c的逆元解：（1）(a*c)*(a*c)=c*c=b=a*b=(a*a)*(c*c)(a*b)*(a*b)=b*b=c=a*c=(a*a)*(b*b) (b*c)*(b*c)=a*a=a=c*b=(b*b)*(c*c) 所以G是阿贝尔群 （2）因为a*a=a a*b=b*a=b a*c=c*a=c 所以G的单位元是a （3）

50、因为a*a=a 所以G的幂等元是a （4）因为b*c=c*b=a，所以b的逆元是c且c的逆元是b 十、(10分)求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。解：最优二叉树为权148 离散数学试题（B卷答案6）一、（20分）用公式法判断下列公式的类型：(1)(ØPØQ)®(P«ØQ)(2)(P¯Q)®(PØ(QØR)解：（1）因为(ØPØQ)®(P«ØQ)ÛØ(ØPØQ)(PØQ)(&#

51、216;PQ)Û(PQ)(PØQ)(ØPQ)ÛÛ所以，公式(ØPØQ)®(P«ØQ)为可满足式。（2）因为(P¯Q)®(PØ(QØR)ÛØ(Ø( PQ)(PØQR)Û(PQ)(PØQR)Û(PQP)(PQØQ)(PQR)Û(PQ)(PQR)Û(PQ(RØR)(PQR)Û(PQR)(PQØR)(PQR)ÛÛ所以

52、，公式(P¯Q)®(PØ(QØR)为可满足式。二、（15分）在谓词逻辑中构造下面推理的证明：每个科学家都是勤奋的，每个勤奋又身体健康的人在事业中都会获得成功。存在着身体健康的科学家。所以，存在着事业获得成功的人或事业半途而废的人。解：论域：所有人的集合。()：是勤奋的；()：是身体健康的；()：是科学家；()：是事业获得成功的人；()：是事业半途而废的人；则推理化形式为：()®()，()()®()，()()()()下面给出证明：(1)()() P(2)()() T(1)，ES(3)()®() P(4)()®() T

53、(1)，US(5)() T(2)，I(6)() T(4)(5)，I(7)() T(2)，I(8)()() T(6)(7)，I(9)()()®() P(10)()()®() T(9)，Us(11)() T(8)(10)，I(12)() T(11)，EG(13)()() T(12)，I三、（10分）设AÆ，1，1，B0，0，求P(A)、P(B)0、P(B)ÅB。解 P(A)Æ，Æ，1，1，Æ，1，Æ，1，1，1，Æ，1，1P(B)0Æ，0，0，0，00Æ，0，0，0，0P(B)Å

54、BÆ，0，0，0，0Å0，0Æ，0，0，0，0四、（15分）设R和S是集合A上的任意关系，判断下列命题是否成立？(1)若R和S是自反的，则R*S也是自反的。(2)若R和S是反自反的，则R*S也是反自反的。(3)若R和S是对称的，则R*S也是对称的。(4)若R和S是传递的，则R*S也是传递的。(5)若R和S是自反的，则RS是自反的。(6)若R和S是传递的，则RS是传递的。解 (1)成立。对任意的，因为R和S是自反的，则<，>R，<，>S，于是<，>R*S，故R*S也是自反的。(2)不成立。例如，令1，2，R<1，2>，

55、S<2，1>，则R和S是反自反的，但R*S<1，1>不是反自反的。(3)不成立。例如，令1，2，3，R<1，2>，<2，1>，<3，3>，S<2，3>，<3，2>，则R和S是对称的，但R*S<1，3>，<3，2>不是对称的。(4)不成立。例如，令1，2，3，R<1，2>，<2，3>，<1，3>，S<2，3>，<3，1>，<2，1>，则R和S是传递的，但R*S<1，3>，<1，1>，<2，

56、1>不是传递的。(5)成立。对任意的，因为R和S是自反的，则<，>R，<，>S，于是<，>RS，所以RS是自反的。五、（15分）令Xx1，x2，xm，Yy1，y2，yn。问(1)有多少个不同的由X到Y的函数？(2)当n、m满足什么条件时，存在单射，且有多少个不同的单射？(3)当n、m满足什么条件时，存在双射，且有多少个不同的双射？解 (1)由于对X中每个元素可以取Y中任一元素与其对应，每个元素有n种取法，所以不同的函数共nm个。(2)显然当|m|n|时，存在单射。由于在Y中任选m个元素的任一全排列都形成X到Y的不同的单射，故不同的单射有m!n(n1)(

57、nm1)个。(3)显然当|m|n|时，才存在双射。此时Y中元素的任一不同的全排列都形成X到Y的不同的双射，故不同的双射有m!个。六、（5分）集合X上有m个元素，集合Y上有n个元素，问X到Y的二元关系总共有多少个？解 X到Y的不同的二元关系对应X×Y的不同的子集，而X×Y的不同的子集共有个，所以X到Y的二元关系总共有个。七、（10分）若<G，*>是群，则对于任意的a、bG，必有惟一的xG使得a*xb。证明 设e是群<G，*>的幺元。令xa1*b，则a*xa*(a1*b)(a*a1)*be*bb。所以，xa1*b是a*xb的解。若x¢G也是a*

58、xb的解，则x¢e*x¢(a1*a)*x¢a1*(a*x¢)a1*bx。所以，xa1*b是a*xb的惟一解。八、（10分）给定连通简单平面图G<V，E，F>，且|V|6，|E|12。证明：对任意fF，d(f)3。证明 由偶拉公式得|V|E|F|2，所以|F|2|V|E|8，于是2|E|24。若存在fF，使得d(f)3，则3|F|2|E|24，于是|F|8，与|F|8矛盾。故对任意fF，d(f)3。离散数学试题（B卷答案7）一、（15分）设计一盏电灯的开关电路，要求受3个开关A、B、C的控制：当且仅当A和C同时关闭或B和C同时关闭时灯亮。设F表

59、示灯亮。(1)写出F在全功能联结词组­中的命题公式。(2)写出F的主析取范式与主合取范式。解 (1)设A：开关A关闭；B：开关B关闭；C：开关C关闭；F(AC)(BC)。在全功能联结词组­中：ØAÛØ(AA)ÛA­AACÛØØ( AC)ÛØ( A­C)Û(A­C)­(A­C) ABÛØ(ØAØB)ÛØ( A­A)(B­B)Û( A

60、3;A)­(B­B)所以FÛ(A­C)­(A­C)(B­C)­(B­C)Û(A­C)­(A­C)­(A­C)­(A­C)­(B­C)­(B­C)­(B­C)­(B­C)(2)FÛ(AC)(BC) Û(A(BØB)C)(AØA)BC)Û(ABC)(AØBC)(ABC)(ØABC)&

61、#219; 主析取范式Û 主合取范式二、（10分）判断下列公式是否是永真式？(1)($xA(x)®$xB(x)®$x(A(x)®B(x)。(2)("xA(x)®"xB(x)®"x(A(x)®B(x)。解 (1)($xA(x)®$xB(x)®$x(A(x)®B(x)Û(Ø$xA(x)$xB(x)®$x(A(x)®B(x)ÛØ(Ø$xA(x)$xB(x)$x(ØA(x)B(x)Û(

62、$xA(x)Ø$xB(x)$xØA(x)$xB(x)Û($xA(x)$xØA(x)$xB(x)(Ø$xB(x)$xØA(x)$xB(x)Û$x(A(x)ØA(x)$xB(x)ÛT 所以，($xA(x)®$xB(x)®$x(A(x)®B(x)为永真式。(2)设论域为1，2，令A(1)T；A(2)F；B(1)F；B(2)T。则"xA(x)为假，"xB(x)也为假，从而"xA(x)®"xB(x)为真；而由于A(1)®B(1

63、)为假，所以"x(A(x)®B(x)也为假，因此公式("xA(x)®"xB(x)®"x(A(x)®B(x)为假。该公式不是永真式。三、（15分）设X为集合，AP(X)ÆX且AÆ，若|X|n，问(1)偏序集<A，Í>是否有最大元？(2)偏序集<A，Í>是否有最小元？(3)偏序集<A，Í>中极大元和极小元的一般形式是什么？并说明理由。解 偏序集<A，Í>不存在最大元和最小元，因为n2。考察P(X)的哈斯图，最底层

64、的顶点是空集，记作第0层，由底向上，第一层是单元集，第二层是二元集，由|X|n，则第n1层是X的n1元子集，第n层是X。偏序集<A，Í>与偏序集<P(X)，Í>相比，恰好缺少第0层和第n层。因此<A，Í>的极小元就是X的所有单元集，即x，xX；而极大元恰好是比X少一个元素，即Xx，xX。四、（10分）设A1，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(

65、R)RIA<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>s(R)RR1<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>，