离散数学考试试题A卷及答案

1、离散数学考试试题（A卷及答案）一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？ 1)(P®Q)Q)«(QR)Q) 2)Ø(Q®P)ØP)(PR)3)(ØPQ)®R)®(PQ)R)解：1)永真式；2）永假式；3)可满足式。二、（8分）个体域为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+1=4）Û（00）（01）Û11Û0

2、三、（8分）已知集合A和B且|A|=n，|B|=m，求A到B的二元关系数是多少？A到B的函数数是多少？ 解：因为|P(A×B)|=2|A×B|=2|A|B|=2mn，所以A到B的二元关系有2mn个。因为|BA|=|B|A|=mn，所以A到B的函数mn个。四、（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&g

3、t;,<1,1>,<2,2>,<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分) 75个儿童到

4、公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元，公园游乐场总共收入70元，求有多少儿童没有乘坐过其中任何一种。解 设、分别表示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合，|20，|2|55，|70/0.5140。由容斥原理，得|所以|75|75(|)(|2|)|75140552010没有乘坐过其中任何一种的儿童共10人。六、（12分）已知R和S是非空集合A上的等价关系，试证：1）RS是A上的等价关系；2）对aA，aRS=aRaS。解："xA，因为R和S是自反关系，所以

5、<x,x>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

6、，因而<x,z>RS，故RS是传递的。总之RS是等价关系。2）因为xaRSÛ<x,a>RSÛ<x,a>R<x,a>SÛ xaRxaSÛ xaRaS所以aRS=aRaS。七（10分）设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，

7、因为f是A到B的双射，g是C到D的双射，所以存在aA，cC，使得f(a)=b，f(c)=d，亦即存在<a,c>A×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，c1

8、c2，所以<a1,c1><a2,c2>，所以h是单射。综合1）和2），h是双射。八、（12分）<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，存在单位元。4）"aG，aDx=a*u-

9、1*x=E，x=u*a-1*u，则xDa=u*a-1*u*u-1*a=u=E，每个元素都有逆元。所以<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。解：D的邻接距阵A和可达距阵P如下：01010111110010011111A=00011P=1111100000000001000011111十、（10分）求叶的权分别为2、4、6、8、10、12、14的最优二叉树

10、及其权。解：最优二叉树为权148离散数学考试试题（B卷及答案）一、（10分）求命题公式Ø(PQ)«Ø(ØP®R)的主合取范式。解：Ø(PQ)«Ø(ØP®R)Û（Ø(PQ)®Ø(ØP®R)）（Ø(ØP®R)®Ø(PQ)）Û（(PQ)(ØPØR)）（(PR)(ØPØQ)）Û(PQ)(ØPØR)Û(P&#

11、216;R)（QØP）（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)

12、(3),I三、（8分）已知A、B、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和

13、S是自反关系，所以<x,x>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、<

14、;x,z>S，因而<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>，

15、<b，b>，<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&g

16、t;，<c，d>，<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，亦即存在&l

17、t;a,c>A×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是双射

18、。七、(12分)设<G，*>是群，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)6|V|，即|E|3|V|，与简单无向平面图的|E|3|V|-6矛盾，所以G至少有一个结点的度数小于等于5。九.G=<A,*>,A=a,b,c,*的运算表为：(写过程，7分) （1）G是否为阿贝尔群？（2）找