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

《离散数学-期末考试试卷答案.doc》由会员分享，可在线阅读，更多相关《离散数学-期末考试试卷答案.doc（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学试题(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)(

2、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

3、(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）|+

4、|（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=

5、| 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，则（

6、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)(分配律)

7、(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

8、(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提前进

9、入考场，个体域：考生的集合，则命题可符号化为：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、阵及关系图（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及R

11、1的传递性得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）一、

12、（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

13、)(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

14、，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=（

15、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

16、、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) 的主析

17、取范式和主合取范式（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)

18、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

19、，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是双射。八

20、、设是群，和是的子群，证明：若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的同一个连通分支中，不妨设其在连通分支（

21、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

22、（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，

23、因为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到

24、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上满足结合律 是的子

25、群。八、（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)*(

26、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

27、)(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)，U

28、S(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和

29、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，所

30、以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的二元关系总共有多少