资源描述
离散数学试题(B卷答案1)一、证明题(10分)1)(P(QR)(QR)(PR)R证明: 左端(PQR)(QP)R)(PQ)R)(QP)R)(PQ)R)(QP)R)(PQ)(QP)R(PQ)(PQ)RTR(置换)R2) $x (A(x)B(x) xA(x)$xB(x)证明 :$x(A(x)B(x)$x(A(x)B(x)$xA(x)$xB(x)xA(x)$xB(x)xA(x)$xB(x)二、求命题公式(P(QR)(PQR)的主析取范式和主合取范式(10分)。证明:(P(QR)(PQR)(P(QR)(PQR)(P(QR))(PQR)(PQ)(PR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)m0m1m2m7M3M4M5M6三、推理证明题(10分)1) CD, (CD) E, E(AB), (AB)(RS)RS证明:(1) (CD)E P(2) E(AB) P(3) (CD)(AB) T(1)(2),I(4) (AB)(RS) P(5) (CD)(RS) T(3)(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四、某班有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-B)(A-C) (10分)。证明:x A-(BC) x Ax(BC) x A(xBxC)(x AxB)(x AxC) x(A-B)x(A-C) x(A-B)(A-C)A-(BC)=(A-B)(A-C)六、已知R、S是N上的关系,其定义如下:R=| x,yNy=x2,S=| x,yNy=x+1。求R-1、R*S、S*R、R1,2、S1,2(10分)。解:R-1=| x,yNy=x2R*S=| x,yNy=x2+1S*R=| x,yNy=(x+1)2,R1,2=,S1,2=1,4。七、设R=,求r(R)、s(R)和t(R) (15分)。解:r(R)=,s(R)=,R2= R5=,R3=,R4=,t(R)=,八、证明整数集I上的模m同余关系R=|xy(mod m)是等价关系。其中,xy(mod m)的含义是x-y可以被m整除(15分)。证明:1)xI,因为(x-x)/m=0,所以xx(mod m),即xRx。2)x,yI,若xRy,则xy(mod m),即(x-y)/m=kI,所以(y - x)/m=-kI,所以yx(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 I,因此xRz。九、若f:AB和g:BC是双射,则(gf)-1=f-1g-1(10分)。证明:因为f、g是双射,所以gf:AC是双射,所以gf有逆函数(gf)-1:CA。同理可推f-1g-1:CA是双射。因为f-1g-1存在z(g-1f-1)存在z(fg)gf(gf)-1,所以(gf)-1=f-1g-1。离散数学试题(B卷答案2)一、证明题(10分)1)(PQ)(P(QR)(PQ)(PR)T证明: 左端(PQ)(P(QR)(PQ)(PR)(摩根律) (PQ)(PQ)(PR)(PQ)(PR)(分配律) (PQ)(PR)(PQ)(PR) (等幂律) T(代入)2) xy(P(x)Q(y) ($xP(x)yQ(y)证明:xy(P(x)Q(y)xy(P(x)Q(y)x(P(x)yQ(y)xP(x)yQ(y)$xP(x)yQ(y)($xP(x)yQ(y)二、求命题公式(PQ)(PQ) 的主析取范式和主合取范式(10分)解:(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ) (PPQ)(QPQ)(PQ)M1m0m2m3三、推理证明题(10分)1)(P(QS)(RP)QRS证明:(1)R(2)RP(3)P(4)P(QS)(5)QS(6)Q(7)S(8)RS2) $x(A(x)yB(y),x(B(x)$yC(y)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分)。解 设P:今天天气好,Q:考试准时进行,A(e):e提前进入考场,个体域:考生的集合,则命题可符号化为:P$xA(x),xA(x)QQP。(1)P$xA(x) P(2)PxA(x) T(1),E(3)xA(x)P T(2),E (4)xA(x)Q P(5)(xA(x)Q)(QxA(x) T(4),E(6)QxA(x) T(5),I(7)QP T(6)(3),I五、已知A、B、C是三个集合,证明A(BC)=(AB)(AC) (10分)证明:x A(BC) x Ax(BC) x A(xBxC)( x AxB)(x AxC) x(AB)x AC x(AB)(AC)A(BC)=(AB)(AC)六、A= x1,x2,x3 ,B= y1,y2,R=,,求其关系矩阵及关系图(10分)。七、设R=,,求r(R)、s(R)和t(R),并作出它们及R的关系图(15分)。解:r(R)=,s(R)=,R2=R5=,R3=,R4=,t(R)=,八、设R1是A上的等价关系,R2是B上的等价关系,A且B。关系R满足:,RR1且R2,证明R是AB上的等价关系(10分)。证明 对任意的AB,由R1是A上的等价关系可得R1,由R2是B上的等价关系可得R2。再由R的定义,有,R,所以R是自反的。对任意的、AB,若R,则R1且R2。由R1对称得R1,由R2对称得R2。再由R的定义,有,R,即R,所以R是对称的。对任意的、AB,若R且R,则R1且R2,R1且R2。由R1、R1及R1的传递性得R1,由R2、R2及R2的传递性得R1。再由R的定义,有,R,即R,所以R是传递的。综上可得,R是AB上的等价关系。九、设f:AB,g:BC,h:CA,证明:如果hogofIA,fohogIB,gofohIC,则f、g、h均为双射,并求出f1、g1和h1(10分)。解 因IA恒等函数,由hogofIA可得f是单射,h是满射;因IB恒等函数,由fohogIB可得g是单射,f是满射;因IC恒等函数,由gofohIC可得h是单射,g是满射。从而f、g、h均为双射。由hogofIA,得f1hog;由fohogIB,得g1foh;由gofohIC,得h1gof。离散数学试题(B卷答案3)一、(10分)判断下列公式的类型(永真式、永假式、可满足式)?(写过程)1)P(PQR) 2)(QP)P)(PR) 3)(PQ)R)(PQ)R)解:1)重言式;2)矛盾式;3)可满足式二、(10分)求命题公式(P(QR)(PQR)的主析取范式,并求成真赋值。解:(P(QR)(PQR)(P(QR)PQRP(QR)PQR(PQ)(PR)(PQ)R(PQ)(PQ)(PR)R1(PR)R)1m0m1m2m3m4m5m6m7该式为重言式,全部赋值都是成真赋值。三、(10分)证明 (PQA)C)(A(PQC)(A(PQ)C证明:(PQA)C)(A(PQC)(PQA)C)(A(PQC)(PQA)C)(APQ)C)(PQA)(APQ)C(PQA)(APQ)C(PQA)(APQ)C(PQA)(APQ)C(A(PQ)(PQ)C(A(PQ)(PQ)C(A(QP)(PQ)C(A(PQ)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)010五、(10分)对于任意集合A,B,试证明:P(A)P(B)=P(AB)解:xP(A)P(B),xP(A)且xP(B),有xA且xB,从而xAB,xP(AB),由于上述过程可逆,故P(A)P(B)=P(AB)六、(10分)已知A=1,2,3,4,5和R=,求r(R)、s(R)和t(R)。解:r(R)=,s(R)=,t(R)=,七、(10分)设函数f:RRRR,R为实数集,f定义为:f()=。1)证明f是双射。解:1),RR,若f()=f(),即=,则x1+y1=x2+y2且x1-y1=x2-y2得x1=x2,y1=y2从而f是单射。2)RR,由f()=,通过计算可得x=(p+q)/2;y=(p-q)/2;从而的原象存在,f是满射。八、(10分)是个群,uG,定义G中的运算“D”为aDb=a*u-1*b,对任意a,bG,求证:也是个群。证明: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,每个元素都有逆元。所以也是个群。九、(10分)已知:D=,V=1,2,3,4,5,E=,求D的邻接距阵A和可达距阵P。解:1)D的邻接距阵A和可达距阵P如下:01010111110010011111A=00011P=1111100000000001000011111十、(10分)求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。解:最优二叉树为权(2+4)4+63+122+(8+10)3+142148离散数学试题(B卷答案4)一、证明题(10分)1)(PQ)(P(QR)(PQ)(PR)T证明: 左端(PQ)(P(QR)(PQ)(PR)(摩根律) (PQ)(PQ)(PR)(PQ)(PR)(分配律) (PQ)(PR)(PQ)(PR) (等幂律) T(代入)2)x(P(x)Q(x)xP(x)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)二、求命题公式(PQ)(PQ) 的主析取范式和主合取范式(10分)解:(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ) (PPQ)(QPQ)(PQ)M1m0m2m3三、推理证明题(10分)1)(P(QS)(RP)QRS证明:(1)R 附加前提(2)RP P(3)P T(1)(2),I(4)P(QS) P(5)QS T(3)(4),I(6)Q P(7)S T(5)(6),I(8)RS CP2) x(P(x)Q(x),xP(x)$x Q(x)证明:(1)xP(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的正方形分成四个全等的小正方形,则至少有一个小正方形内有三个点,它们组成的三角形(可能是退化的)面积不超过小正方形的一半,即1/8。五、已知A、B、C是三个集合,证明A(BC)=(AB)(AC) (10分)证明:x A(BC) x Ax(BC) x A(xBxC)( x AxB)(x AxC) x(AB)x AC x(AB)(AC)A(BC)=(AB)(AC)六、p=A1,A2,An是集合A的一个划分,定义R=|a、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,使f,f-1。所以,f-1是满射。对任意的xA,若存在y1,y2B,使得f-1且f-1,则有f且f。因为f是函数,则y1=y2。所以,f-1是单射。因此f-1是双射。八、设是群,和是的子群,证明:若ABG,则AG或BG(10分)。证明 假设AG且BG,则存在aA,aB,且存在bB,bA(否则对任意的aA,aB,从而AB,即ABB,得BG,矛盾。)对于元素a*bG,若a*bA,因A是子群,a-1A,从而a-1 * (a*b)b A,所以矛盾,故a*bA。同理可证a*bB,综合有a*bABG。综上所述,假设不成立,得证AG或BG。九、若无向图G是不连通的,证明G的补图是连通的(10分)。证明 设无向图G是不连通的,其k个连通分支为、。任取结点、G,若和不在图G的同一个连通分支中,则,不是图G的边,因而,是图的边;若和在图G的同一个连通分支中,不妨设其在连通分支(1)中,在不同于的另一连通分支上取一结点,则,和,都不是图G的边,因而,和,都是的边。综上可知,不管那种情况,和都是可达的。由和的任意性可知,是连通的。离散数学试题(B卷答案5)一、(10分)求命题公式(PQ)(PR)的主合取范式。解:(PQ)(PR)((PQ)(PR))((PR)(PQ))((PQ)(PR))((PR)(PQ))(PQ)(PR)(PR)(QP)(QR)(PQR)(PQR)(PQR)(PQR)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、C是三个集合,证明A(BC)=(AB)(AC)证明:x A(BC) x Ax(BC) x A(xBxC)( x AxB)(x AxC) 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是自反关系,所以R、S,因而RS,故RS是自反的。x、yA,若RS,则R、S,因为R和S是对称关系,所以因R、S,因而RS,故RS是对称的。x、y、zA,若RS且RS,则R、S且R、S,因为R和S是传递的,所以因R、S,因而RS,故RS是传递的。总之RS是等价关系。2)因为xaRSRSRS xaRxaS xaRaS所以aRS=aRaS。五、(10分) 设Aa,b,c,d,R是A上的二元关系,且R,求r(R)、s(R)和t(R)。解 r(R)RIA,s(R)RR-1,R2,R3,R4,R2t(R),六、(15分) 设A、B、C、D是集合,f是A到B的双射,g是C到D的双射,令h:ACBD且AC,h()。证明h是双射。证明:1)先证h是满射。BD,则bB,dD,因为f是A到B的双射,g是C到D的双射,所以存在aA,cC,使得f(a)=b,f(c)=d,亦即存在AC,使得h(),所以h是满射。2)再证h是单射。、AC,若h()h(),则 ,所以f(a1)f(a2),g(c1)g(c2),因为f是A到B的双射,g是C到D的双射,所以a1a2,c1c2,所以,所以h是单射。综合1)和2),h是双射。七、(12分)设是群,H是G的非空子集,证明是的子群的充要条件是若a,bH,则有a*b-1H。证明: 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)-1HHG且HF,*在H上满足结合律 是的子群。八、(10分)设G=是简单的无向平面图,证明G至少有一个结点的度数小于等于5。解:设G的每个结点的度数都大于等于6,则2|E|=Sd(v)6|V|,即|E|3|V|,与简单无向平面图的|E|3|V|-6矛盾,所以G至少有一个结点的度数小于等于5。九.G=,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)因为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)(PQ)(PQ)(2)(PQ)(P(QR)解:(1)因为(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)所以,公式(PQ)(PQ)为可满足式。(2)因为(PQ)(P(QR)( PQ)(PQR)(PQ)(PQR)(PQP)(PQQ)(PQR)(PQ)(PQR)(PQ(RR)(PQR)(PQR)(PQR)(PQR)所以,公式(PQ)(P(QR)为可满足式。二、(15分)在谓词逻辑中构造下面推理的证明:每个科学家都是勤奋的,每个勤奋又身体健康的人在事业中都会获得成功。存在着身体健康的科学家。所以,存在着事业获得成功的人或事业半途而废的人。解:论域:所有人的集合。():是勤奋的;():是身体健康的;():是科学家;():是事业获得成功的人;():是事业半途而废的人;则推理化形式为:()(),()()(),()()()()下面给出证明:(1)()() P(2)()() T(1),ES(3)()() P(4)()() T(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)B,0,0,0,00,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,S,则R和S是反自反的,但R*S不是反自反的。(3)不成立。例如,令1,2,3,R,S,则R和S是对称的,但R*S,不是对称的。(4)不成立。例如,令1,2,3,R,S,则R和S是传递的,但R*S,不是传递的。(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)(nm1)个。(3)显然当|m|n|时,才存在双射。此时Y中元素的任一不同的全排列都形成X到Y的不同的双射,故不同的双射有m!个。六、(5分)集合X上有m个元素,集合Y上有n个元素,问X到Y的二元关系总共有多少个?解 X到Y的不同的二元关系对应XY的不同的子集,而XY的不同的子集共有个,所以X到Y的二元关系总共有个。七、(10分)若是群,则对于任意的a、bG,必有惟一的xG使得a*xb。证明 设e是群的幺元。令xa1*b,则a*xa*(a1*b)(a*a1)*be*bb。所以,xa1*b是a*xb的解。若xG也是a*xb的解,则xe*x(a1*a)*xa1*(a*x)a1*bx。所以,xa1*b是a*xb的惟一解。八、(10分)给定连通简单平面图G,且|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表示灯亮。(1)写出F在全功能联结词组中的命题公式。(2)写出F的主析取范式与主合取范式。解 (1)设A:开关A关闭;B:开关B关闭;C:开关C关闭;F(AC)(BC)。在全功能联结词组中:A(AA)AAAC( AC)( AC)(AC)(AC) AB(AB)( AA)(BB)( AA)(BB)所以F(AC)(AC)(BC)(BC)(AC)(AC)(AC)(AC)(BC)(BC)(BC)(BC)(2)F(AC)(BC) (A(BB)C)(AA)BC)(ABC)(ABC)(ABC)(ABC) 主析取范式 主合取范式二、(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)($xA(x)$xB(x)$xA(x)$xB(x)($xA(x)$xA(x)$xB(x)($xB(x)$xA(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)为假,所以x(A(x)B(x)也为假,因此公式(xA(x)xB(x)x(A(x)B(x)为假。该公式不是永真式。三、(15分)设X为集合,AP(X)X且A,若|X|n,问(1)偏序集是否有最大元?(2)偏序集是否有最小元?(3)偏序集中极大元和极小元的一般形式是什么?并说明理由。解 偏序集不存在最大元和最小元,因为n2。考察P(X)的哈斯图,最底层的顶点是空集,记作第0层,由底向上,第一层是单元集,第二层是二元集,由|X|n,则第n1层是X的n1元子集,第n层是X。偏序集与偏序集相比,恰好缺少第0层和第n层。因此的极小元就是X的所有单元集,即x,xX;而极大元恰好是比X少一个元素,即Xx,xX。四、(10分)设A1,2,3,4,5,R是A上的二元关系,且R,求r(R)、s(R)和t(R)。解 r(R)RIA,s(R)RR1,R2,R3,R4,R2t(R)Ri,。五、(10分)设函数g:AB,f:BC, (1)若fog是满射,则f是满射。(2)若fog是单射,则g是单射。证明 因为g:AB,f:BC,由定理5.5知,fog为A到C的函数。(1)对任意的zC,因fog是满射,则存在xA使fog(x)z,即f(g(x)z。由g:AB可知g(x)B,于是有yg(x)B,使得f(y)z。因此,f是满射。(2)对任意的x1、x2A,若x1x2,则由fog是单射得fog(x1)fog(x2),于是f(g(x1)f(g(x2),必有g(x1)g(x2)。所以,g是单射。六、(10分)有幺元且满足消去律的有限半群一定是群。证明 设是一个有幺元且满足消去律的有限半群,要证是群,只需证明G的任一元素a可逆。考虑a,a2,ak,。因为G只有有限个元素,所以存在kl,使得akal。令mkl,有al*eal*am,其中e是幺元。由消去率得ame。于是,当m1时,ae,而e是可逆的;当m1时,a*am-1am-1*ae。从而a是可逆的,其逆元是am-1。总之,a是可逆的。七、(20分)有向图G如图所示,试求:(1)求G的邻接矩阵A。(2)求出A2、A3和A4,v1到v4长度为1、2、3和4的路有多少?(3)求出ATA和AAT,说明ATA和AAT中的第(2,2)元素和第(2,3)元素的意义。(4)求出可达矩阵P。(5)求出强分图。解 (1)求G的邻接矩阵为:(2)由于 所以v1到v4长度为1、2、3和4的路的个数分别为1、1、2、3。(3)由于 再由定理10.19可知,所以ATA的第(2,2)元素为3,表明那些边以为终结点且具有不同始结点的数目为3,其第(2,3)元素为0,表明那些边既以为终结点又以为终结点,并且具有相同始结点的数目为0。AAT中的第(2,2)元素为2,表明那些边以为始结点且具有不同终结点的数目为2,其第(2,3)元素为1,表明那些边既以为始结点又以为始结点,并且具有相同终结点的数目为1。(4)因为+,所以求可达矩阵为。(5)因为,所以,构成G的强分图。离散数学试题(B卷答案8)一、(10分)证明(PQ)(PR)(QS)SR证明 因为SRRS,所以,即要证(PQ)(PR)(QS)RS。(1)R 附加前提(2)PR P(3)P T(1)(2),I(4)PQ P(5)Q T(3)(4),I(6)QS P(7)S T(5)(6),I(8)RS CP(9)SR 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,|AC|6,|BC|5,|ABC|2,|(AC)B|6。因为|(AC)
展开阅读全文