离散数学-期末考试试卷答案.pdf

离散数学试题（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)R TR(置换)R 2)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)m0m1m2m7 M3M4M5M6 三、推理证明题(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)|+52,|（AB）=3。于是ABC|=12+6+14-653+2=20。不会打这三种球的人数 2520=5。五、已知 A、B、C 是三个集合，证明 A(BC)=（AB)（AC）（10 分）.证明：x A（BC）x Ax（BC）x A(xBxC）（x AxB）(x AxC）x（AB）x(A-C）x（A-B）（AC）A（BC）=（AB）（AC）六、已知 R、S 是 N 上的关系,其定义如下:R=|x，yNy=x2 R*S=|x，yNy=x2+1 S*R=x，y|x，yNy=(x+1）2，R 1，2=1,1，S 1，2=1，4。七、设 R=a，b，b，c，,求 r（R）、s(R)和 t（R）（15 分）。解：r(R）=,b，c,，a，a,b，b，c，c s（R)=，c，a，b，a，c，b，a，c R2=R5=a，c，,R3=a，a，,R4=a，b,，c,c t(R)=a，b，b，c,，a，c，,c，c 八、证明整数集 I 上的模 m 同余关系 R=x，y xy（mod m)是等价关系。其中，xy(mod m)的含义是 xy 可以被 m 整除（15 分)。证明：1）xI，因为（xx）/m=0，所以 xx(mod m），即 xRx。2)x,yI，若 xRy，则 xy（mod m)，即(xy）/m=kI，所以（y x）/m=kI，所以 yx(mod m)，即 yRx。3）x，y，zI，若 xRy，yRz，则(xy）/m=uI，（y-z)/m=vI，于是（xz）/m=（x-y+y-z）/m=u+v I，因此 xRz。九、若 f：AB 和 g：BC 是双射，则（gf）-1=f1g-1（10 分）。证明：因为 f、g 是双射，所以 gf：AC 是双射,所以 gf 有逆函数(gf)1：CA.同理可推 f-1g-1：CA 是双射.因为f1g-1存在 z(x，zg1f-1）存在 z（y，zfg）(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）M1 m0m2m3 三、推理证明题（10 分）1)（P（QS）(RP)QRS 证明：（1）R（2)RP(3）P(4)P（QS)（5）QS(6）Q（7）S（8)RS 2）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（c)T（3)，ES(5）B(b）C（c）T(4)，US（6)A(a)B(b)T（2)，US（7）A（a）C(c）T(5）(6），I(8）xA(x）C(c）T（7），UG(9)xA(x）yC(y）T(8），EG 四、只要今天天气不好,就一定有考生不能提前进入考场,当且仅当所有考生提前进入考场，考试才能准时进行.所以,如果考试准时进行，那么天气就好（15 分）。解 设 P：今天天气好，Q：考试准时进行，A（e）：e 提前进入考场,个体域：考生的集合,则命题可符号化为：PxA(x)，xA（x）QQP。(1)PxA（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=，x3,y2，求其关系矩阵及关系图（10 分）.七、设 R=2,1,，2,4，3，4,4，4，5，2 ，求 r(R）、s(R）和 t(R)，并作出它们及 R 的关系图(15 分）。解：r（R）=2,1,，1，1，2,2,3，3，5,5 s（R)=，,，3,4，4,4，,1,2，,4,3 R2=R5=2,2,4，4,R3=2,1，2，5,2,4，4，4，,3，4,4，4，5，1，5，5,5,4 t(R)=2,1,2,5,2,4,3,4，4,4，,5，1，5，4，5,5 八、设 R1是 A 上的等价关系，R2是 B 上的等价关系,A且 B。关系 R 满足：,x2，y2Rx1,x2R1且R2，证明 R 是 AB 上的等价关系（10 分）.证明 对任意的x,yAB,由 R1是 A 上的等价关系可得x,xR1,由 R2是 B上的等价关系可得y，yR2。再由 R 的定义，有，x，y R,所以 R 是自反的。对任意的AB,若x，yR，则x，uR1且R2。由 R1对称得u,xR1,由 R2对称得R2。再由 R 的定义，有u，v,R，即R,所以 R 是对称的.对任意的、u，v、s，tAB，若x，yRu，v且Rs，t,则R1且R2。由R1、u，sR1及R1的传递性得x，sR1，由y，vR2、v,tR2及 R2的传递性得y，tR1。再由 R 的定义，有,s，t R,即x，yR，2，3,3，4，5,4，求 r（R）、s(R)和 t（R）。解：r(R)=，2,3，3，4，5,4，1，1，3，3，5，5 s(R）=1，2,，3，4，,，4，5 t(R）=,2,1，2,3，3，4，2，2，2，4，1,4 七、（10 分）设函数 f：RRRR,R 为实数集，f 定义为：f（x，y)=x+y，x-y。1)证明 f 是双射。解：1）RR，若 f（x1,y1）=f(），即x1+y1,x1-y1=x2+y2，x2y2，则 x1+y1=x2+y2且 x1y1=x2-y2得 x1=x2，y1=y2从而 f 是单射。2)=p，q，通过计算可得 x=(p+q)/2；y=（p-q)/2；从而的原象存在,f 是满射。八、（10 分)是个群，uG，定义 G 中的运算“”为 ab=au-1*b，对任意 a,bG，求证：也是个群.证明：1）a，bG，ab=a*u1*bG，运算是封闭的。2)a，b，cG，（ab）c=（a*u1*b）u-1c=a*u-1（b*u-1c)=a（bc）,运算是可结合的.3）aG，设 E 为的单位元，则 aE=a*u-1E=a，得 E=u，存在单位元 u。4）aG，ax=a*u1*x=E，x=u*a1*u，则 xa=u*a-1*uu1a=u=E，每个元素都有逆元.所以G，也是个群。九、（10 分)已知：D=，V=1，2，3，4，5,E=1，2，1，4，2，3，3，5，5，1 ，求 D 的邻接距阵 A 和可达距阵 P。解:1)D 的邻接距阵 A 和可达距阵 P 如下：0 1 0 1 0 1 1 1 1 1 0 0 1 0 0 1 1 1 1 1 A=0 0 0 1 1 P=1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 十、（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 CP 2）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）六、=A1,A2，,An是集合 A 的一个划分,定义 R=a，ba、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=,故i=j，即 a，b,cAi,所以 aRc，故 R 传递。总之 R 是 A 上的等价关系.七、若 f:AB 是双射，则 f1:BA 是双射(15 分).证明:对任意的 xA,因为 f 是从 A 到 B 的函数,故存在 yB，使x,yf，y,xf1。所以，f-1是满射。对任意的 xA，若存在 y1，y2B,使得y1，xf-1且f-1，则有x,y1f 且f。因为 f 是函数，则 y1=y2。所以，f1是单射。因此 f-1是双射.八、设G,是群，A，和B，*是G，的子群，证明:若 ABG,则 AG 或 BG（10 分）。证明 假设 AG 且 BG，则存在 aA，aB，且存在 bB，bA（否则对任意的aA，aB，从而 AB，即 ABB,得 BG，矛盾。）对于元素 a*bG，若 a*bA，因 A 是子群，a-1A，从而 a-1*（ab）b A，所以矛盾，故 a*bA。同理可证 a*bB，综合有 abABG。综上所述,假设不成立，得证 AG 或 BG。九、若无向图 G 是不连通的,证明 G 的补图G是连通的（10 分)。证明 设无向图 G 是不连通的，其 k 个连通分支为1G、2G、kG。任取结点u、vG，若u和v不在图 G 的同一个连通分支中，则u，v不是图 G 的边，因而u，v是图G的边;若u和v在图 G 的同一个连通分支中，不妨设其在连通分支iG（1ik）中,在不同于iG的另一连通分支上取一结点w，则u,w和w，v都不是图 G 的边，因而u，w和w,v都是G的边。综上可知,不管那种情况，u和v都是可达的。由u和v的任意性可知，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 是自反关系，所以RS，故 RS 是自反的.x、yA，若S,因为 R 和 S 是对称关系,所以因y,xR、y,xS，因而y,xRS,故 RS 是对称的.x、y、zA，若x,yRS 且RS，则R、S 且y,z R、y，zS,因为 R 和 S 是传递的,所以因x，zR、x,zS,因而RS，故 RS 是传递的。总之 RS 是等价关系。2）因为 xaRSx，aRS x，aRx,aS xaRxaS xaRaS 所以aRS=aRaS。五、(10 分）设 Aa，b，c，d，R 是 A 上的二元关系,且 R，b，a，c,d ，求 r（R)、s（R）和 t（R)。解 r（R）RIA a，b，b，a，c，c，d，d s(R）RR1a，b,b，a，c，d,c，b,R2 a，a,b,b，b，d R3a，b，b,c R4,a，c，b,b，b，dR2 t（R）iiR1，b，c，c，d,a，c，b，b，六、（15 分)设 A、B、C、D 是集合，f 是 A 到 B 的双射，g 是 C 到 D 的双射，令 h：ACBD 且a，cAC，h(）.证明 h 是双射。证明：1）先证 h 是满射.)f(a),g（c）b，d，所以 h 是满射。2)再证 h 是单射。、AC，若 h（a1，c1）h（a2,c2)，则f(a2），g(c2)，所以 f(a1)f(a2),g(c1）g(c2），因为 f 是 A 到 B 的双射,g 是C 到 D 的双射，所以 a1a2，c1c2，所以a1,c1，所以 h 是单射。综合 1）和 2），h 是双射。七、（12 分）设是群，H 是 G 的非空子集,证明H，是G，*的子群的充要条件是若 a，bH，则有 a*b-1H。证明：a，bH 有 b1H，所以 a*b-1H。aH，则 e=a*a1H a1=ea1H a，bH 及 b-1H，a*b=a（b-1）-1H HG 且 H，*在 H 上满足结合律 是G，的子群.八、（10 分）设 G=V，E是简单的无向平面图，证明 G 至少有一个结点的度数小于等于5。解:设 G 的每个结点的度数都大于等于 6,则 2E=d（v）6|V|，即|E|3V|，与简单无向平面图的|E|3|V6 矛盾，所以 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=ab=(aa)*（cc）（a*b）(a*b)=bb=c=ac=(aa）*(b*b)(bc)*（b*c）=a*a=a=cb=(bb)（c*c）所以 G 是阿贝尔群 （2）因为 aa=a a*b=b*a=b a*c=ca=c 所以 G 的单位元是 a （3）因为 aa=a 所以 G 的幂等元是 a （4）因为 bc=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）1m2m3m 0M 所以，公式(PQ)（PQ)为可满足式。（2)因为（PQ）(P(QR）(（PQ）(PQR)）(PQ)(PQR）)(PQP）（PQQ）(PQR）（PQ)(PQR)(PQ(RR)）（PQR)(PQR)(PQR）（PQR)0M1M 2m3m4m5m6m7m 所以，公式(PQ)（P（QR)为可满足式.二、（15 分）在谓词逻辑中构造下面推理的证明：每个科学家都是勤奋的，每个勤奋又身体健康的人在事业中都会获得成功.存在着身体健康的科学家。所以，存在着事业获得成功的人或事业半途而废的人。解：论域：所有人的集合.Q（x)：x是勤奋的；H（x)：x是身体健康的；S（x）：x是科学家；C(x)：x是事业获得成功的人;F(x）：x是事业半途而废的人;则推理化形式为:x（S（x)Q(x)）,x(Q（x）H（x）C(x)），x（S（x)H（x)）x（C(x)F(x)下面给出证明：（1）x(S(x）H(x）)P(2）S(a）H(a)T(1),ES(3)x（S(x)Q(x）)P（4）S（a）Q（a)T(1），US(5）S（a）T(2)，I(6)Q（a)T(4)(5),I(7）H（a)T(2)，I(8）Q（a）H(a）T（6)(7)，I（9)x（Q(x）H(x）C(x)P（10)Q（a）H（a）C(a）T(9），Us（11)C（a）T(8）（10)，I（12）xC(x）T(11），EG（13)x（C(x）F（x）)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，1 P(B)0，0,0，0，0 0，0，0，0，0 P(B)B，0,0 ，0,00，0，0,0，0，0 四、（15 分）设 R 和 S 是集合 A 上的任意关系，判断下列命题是否成立？(1)若 R 和 S 是自反的，则 R*S 也是自反的。（2）若 R 和 S 是反自反的,则 RS 也是反自反的。（3）若 R 和 S 是对称的，则 R*S 也是对称的。（4)若 R 和 S 是传递的,则 RS 也是传递的。（5）若 R 和 S 是自反的，则 RS 是自反的。（6）若 R 和 S 是传递的，则 RS 是传递的。解 （1）成立.对任意的aA,因为 R 和 S 是自反的,则R，S，于是R*S，故 RS 也是自反的。（2）不成立。例如，令A1,2，R1,2，S2，1,则 R 和 S 是反自反的，但 R*S不是反自反的。(3)不成立.例如,令A1，2，3，R1，2,2，1，3，3，S2,3，3,2，则 R 和 S 是对称的，但 R*S1,3，3,2 不是对称的。(4）不成立.例如，令A1，2，3，R,，,S，2，1，则 R 和 S 是传递的，但 RS1,3，1，1,2，1不是传递的.（5)成立。对任意的aA，因为 R 和 S 是自反的，则a，aR，S，于是a,aRS，所以 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 的不同的单射，故不同的单射有mnCm!n（n1)（nm1）个.(3）显然当|m|n时,才存在双射。此时 Y 中元素的任一不同的全排列都形成 X到 Y 的不同的双射,故不同的双射有 m!个。六、（5 分）集合 X 上有 m 个元素,集合 Y 上有 n 个元素，问 X 到 Y 的二元关系总共有多少个？解 X 到 Y 的不同的二元关系对应 XY 的不同的子集，而 XY 的不同的子集共有 个mn2,所以 X 到 Y 的二元关系总共有mn2个。七、（10 分)若的幺元.令 xa1*b，则 axa*（a1b）（aa1)*be*bb。所以，xa1*b 是 axb 的解。若 xG 也是 a*xb 的解，则 xex（a1a）*xa1*（ax)a1*bx。所以，xa1*b 是 axb 的惟一解.八、（10 分）给定连通简单平面图 G,且V|6，E12。证明：对任意 fF，d（f）3。证明 由偶拉公式得|V|E|F|2，所以F2V|E|8,于是Fffd)(2|E|24。若存在 fF，使得 d(f）3，则 3|F2|E24,于是|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）AA AC(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）3m5m7m 主析取范式 0M1M2M4M6M 主合取范式 二、(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）偏序集A，是否有最大元？(2）偏序集A，是否有最小元？(3）偏序集A，中极大元和极小元的一般形式是什么？并说明理由。解 偏序集A，不存在最大元和最小元，因为 n2。考察 P（X）的哈斯图，最底层的顶点是空集，记作第 0 层，由底向上,第一层是单元集，第二层是二元集，由|X|n，则第 n1 层是 X 的 n1 元子集，第 n 层是 X。偏序集与偏序集P(X），相比，恰好缺少第 0 层和第 n 层.因此A，的极小元就是 X 的所有单元集，即x，xX;而极大元恰好是比 X 少一个元素，即 Xx，xX。四、（10 分）设 A1，2,3,4，5，R 是 A 上的二元关系，且 R,2,5，,5，2 ，求 r（R）、s（R）和 t(R）.解 r（R)RIA，,，4，4，5，2，1，1，2，2，4，4，s(R）RR12，1，2，5，2，4，5,2,，4,2，4,3 R2，3,4,4，4，5，1，5，5，R32，1，2,4，4，4,5,2，5，4 R42，2，2，4，4，4，5，5，5，4 R2 t（R）1iRi,，2，4，3，4，5,2，2，2，5,1,，。五、（10 分）设函数 g:AB，f:BC，（1)若 fg 是满射，则 f 是满射。(2)若 fg 是单射，则 g 是单射。证明 因为 g:AB，f：BC，由定理 5。5 知,fg 为 A 到 C 的函数。（1）对任意的 zC，因 fg 是满射,则存在 xA 使 fg(x)z，即 f(g(x）z。由 g：AB 可知 g（x）B，于是有 yg(x）B，使得 f(y)z。因此，f 是满射。（2）对任意的 x1、x2A，若 x1x2，则由 fg 是单射得 fg(x1）fg（x2)，于是 f(g（x1）)f（g（x2)），必有 g(x1)g（x2）。所以，g 是单射。六、（10 分）有幺元且满足消去律的有限半群一定是群。证明 设G,*是一个有幺元且满足消去律的有限半群，要证G，是群，只需证明 G 的任一元素 a 可逆。考虑 a,a2,，ak，。因为 G 只有有限个元素，所以存在 kl，使得 akal。令 mkl，有 al*ealam,其中 e 是幺元.由消去率得 ame。于是,当 m1 时,ae，而 e 是可逆的;当 m1 时,aam1am-1*ae.从而 a 是可逆的，其逆元是 am1。总之，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 的邻接矩阵为：0010101011001010A(2)由于 11001110102011102A 10202120221021203A 22103230314032304A 所以 v1到 v4长度为 1、2、3 和 4 的路的个数分别为 1、1、2、3.(3)由于 3120110021300000AAT 1201121201211212TAA 再由定理 10.19 可知，所以 ATA 的第(2，2)元素为 3,表明那些边以2v为终结点且具有不同始结点的数目为 3，其第(2，3）元素为 0，表明那些边既以2v为终结点又以3v为终结点，并且具有相同始结点的数目为 0。AAT中的第(2，2)元素为 2，表明那些边以2v为始结点且具有不同终结点的数目为 2,其第(2，3)元素为 1，表明那些边既以2v为始结点又以3v为始结点，并且具有相同终结点的数目为 1.（4)因为4324AAAAB0010101011001010+1100111010201110+1020212022102120+22103230314032304340747074701470，所以求可达矩阵为1110111011101110P。（5)因为TPP111011101110111011111111111100001110111011100000，所以1v，2v，3v,4v构成 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，B6,C|14，|AC6，|BC|5，|ABC2，|(AC)B|6。因为|（AC）B（AB）(BC）|（AB)|（BC）ABC|(AB）|526，所以|(AB)3.于是|ABC12614653220，|CBA25205。故,不会打这三种球的共 5 人。四、（10 分）设 A1、A2和 A3是全集 U 的子集，则形如31iAi(Ai为 Ai或iA）的集合称为由 A1、A2和 A3产生的小项。试证由 A1、A2和 A3所产生的所有非空小项的集合构成全集 U 的一个划分。证明 小项共 8 个，设有 r 个非空小项 s1、s2、sr（r8)。对任意的 aU,则 aAi或 aiA，两者必有一个成立,取 Ai为包含元素 a 的 Ai或iA，则 a31iAi，即有 ari 1si,于是 Uri 1si。又显然有ri 1siU，所以 Uri 1si。任取两个非空小项 sp和 sq，若 spsq，则必存在某个 Ai和iA分别出现在 sp和 sq中，于是 spsq。综上可知，s1，s2，sr是 U 的一个划分.五、（15 分)设 R 是 A 上的二元关系，则：R 是传递的RRR。证明 (5）若 R 是传递的，则x,yR*Rz(xRzzSy)xRccSy，由 R 是传递的得 xRy,即有x,yR，所以 R*RR。反之,若 RRR，则对任意的 x、y、zA，如果 xRz 且 zRy，则x，yRR,于是有R，即有 xRy,所以 R 是传递的.六、（15 分）若 G 为连通平面图,则 nmr2，其中，n、m、r 分别为 G 的结点数、边数和面数。证明 对 G 的边数 m 作归纳法。当 m0 时,由于 G 是连通图,所以 G 为平凡图，此时 n1，r1，结论自然成立。假设对边数小于 m 的连通平面图结论成立。下面考虑连通平面图 G 的边数为 m 的情况。设 e 是 G 的一条边，从 G 中删去 e 后得到的图记为 G，并设其结点数、边数和面数分别为 n、m和 r。对 e 分为下列情况来讨论：若 e 为割边，则 G有两个连通分支 G1和 G2。Gi的结点数、边数和面数分别为 ni、mi和 ri.显然 n1n2nn，m1m2mm1，r1r2r1r1。由归纳假设有 n1m1r12，n2m2r22，从而(n1n2）（m1m2）(r1r2）4，n（m1）(r1)4，即 nmr2。若 e 不为割边,则 nn，mm1,rr1，由归纳假设有 nmr2，从而 n(m1)r12，即 nmr2.由数学归纳法知，结论成立。七、（10 分）设函数 g：AB，f：BC，则：(1）fg 是 A 到 C 的函数;(2）对任意的 xA，有 fg(x)f（g(x）)。证明 （1）对任意的 xA,因为 g：AB 是函数，则存在 yB 使x，yg.对于 yB，因 f:BC 是函数，则存在 zC 使f.根据复合关系的定义,由x，yg和y，zf 得fg。所以 DfgA.对任意的 xA，若存在 y1、y2C，使得x，y1、x,y2fggf，则存在 t1使得x，t1g 且f，存在 t2使得g 且t2,y2f。因为 g：AB 是函数，则 t1t2。又因 f：BC 是函数，则 y1y2。所以 A 中的每个元素对应 C 中惟一的元素。综上可知，fg 是 A 到 C 的函数。(2）对任意的 xA，由 g：AB 是函数，有x，g(x)g 且 g（x)B，又由 f：BC 是函数，得g（x),f(g(x)f，于是x，f(g(x）)g*ffg。又因 fg 是 A 到 C 的函数,则可写为 fg(x)f(g(x）)。八、（15 分）设是G，*的子群，定义 Ra,b|a、bG 且 a1*bH,则 R 是 G 中的一个等价关系，且aRaH。证明 对于任意 aG，必有 a1G 使得 a1aeH，所以R.若a，bR，则 a1bH。因为 H 是 G 的子群,故(a1*b)1b1*aH。所以R，则 a1bH，b1*cH。因为 H 是 G 的子群，所以(a1*b）*（b1*c）a1*cH，故a，cR.综上可得，R 是 G 中的一个等价关系.对于任意的 baR，有R，a1bH，则存在 hH 使得 a1bh，ba*h,于是 baH，aRaH.对任意的 baH，存在 hH 使得 bah,a1bhH,(AB）(CD）x(AB)y（CD）xAxByCyD(xAyC）（xByD）x，yAC（AC)(BD），所以(AB）(CD)（AC)（BD）。五、（15 分）设 A1，2，3，4,5，R 是 A 上的二元关系,且 R2，1，2,5，2，4，3，4,4，4,求 r(R)、s（R）和 t(R）.解 r（R）RIA2，1,2,5，2,4,4,4,5,2，2,2,3，3,4,4，5，5 s（R)RR1，2，5，2，4，3，4，4，4,，1，2,4,2,4，3 R2，2，4，3，4，,，2，4，3,4，4，4