《离散数学考试试题(a卷及答案)》由会员分享，可在线阅读，更多相关《离散数学考试试题(a卷及答案)（5页珍藏版）》请在金锄头文库上搜索。
1、1离散数学考试试题（离散数学考试试题（A A 卷及答案）卷及答案）一、 （10 分）判断下列公式的类型（永真式、永假式、可满足式）？ 1)(PQ)Q)(QR)Q) 2)(QP)P)(PR)3)(PQ)R)(PQ)R)解：1)永真式；2）永假式；3)可满足式。二、 （8 分）个体域为1，2，求xy（x+y=4）的真值。解：xy（x+y=4）x（x+1=4）（x+2=4） ）（1+1=4）（1+2=4） ）（2+1=4）（2+1=4） ）（00）（01）110三、 （8 分）已知集合 A 和 B 且|A|=n，|B|=m，求 A 到 B 的二元关系数是多少？A 到 B 的函数数是多少？ 解：因为|
2、P(AB)|=2|AB|=2|A|B|=2mn，所以 A 到 B 的二元关系有 2mn 个。因为|BA|=|B|A|=mn，所以 A 到 B 的函数 mn 个。四、 （10 分）已知 A=1,2,3,4,5和 R=,，求 r(R)、s(R)和 t(R)。解：r(R)=,s(R)=,t(R)=,五、(10 分) 75 个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中 20 人这三种东西都乘过，其中 55 人至少乘坐过其中的两种。若每样乘坐一次的费用是 0.5 元，公园游乐场总共收入 70 元，求有多少儿童没有乘坐过其中任何一种。解 设、分别表示骑旋转木马、坐滑行铁道
3、、乘宇宙飞船的儿童组成的集合，|ABCAB|20，|2|55，|70/0.5140CABACBCABCABC。由容斥原理，得|ABCABCABACBCABC所以|75|75(|)(|ABCABCABCABACB|2|)|75140552010CABCABC没有乘坐过其中任何一种的儿童共 10 人。六、 （12 分）已知 R 和 S 是非空集合 A 上的等价关系，试证：1）RS 是 A 上的等价关系；2）对aA，aRS=aRaS。解：xA，因为 R 和 S 是自反关系，所以R、S，因而RS，故 RS 是自反的。x、yA，若RS，则R、S，因为 R 和 S 是对称关系，所以因2R、S，因而RS，故
4、 RS 是对称的。x、y、zA，若RS 且RS，则R、S 且R、S，因为 R 和 S 是传递的，所以因R、S，因而RS，故 RS 是传递的。总之 RS 是等价关系。2）因为 xaRSRSRS xaRxaS xaRaS所以aRS=aRaS。七（10 分）设 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 是满射。
5、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 分）是个群，uG，定义 G 中的运算“”为 ab=a*u-1*b，对任意 a,bG，求证：也是个群。证明：1）a,bG，ab=a*u-1*bG，运算是封闭的。2）a,b,cG， （ab）c=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=a（bc） ，运算是可结合的。3）aG，设 E 为的单位元，则 aE=a*u-1*E
6、=a，得 E=u，存在单位元。4）aG，ax=a*u-1*x=E，x=u*a-1*u，则 xa=u*a-1*u*u-1*a=u=E，每个元素都有逆元。所以也是个群。九、 （10 分）已知：D=，V=1,2,3,4,5，E=,，求 D 的邻接距阵 A 和可达距阵 P。解：D 的邻接距阵 A 和可达距阵 P 如下：01010111110010011111A=00011P=1111100000000001000011111十、 （10 分）求叶的权分别为 2、4、6、8、10、12、14 的最优二叉树及其权。解：最优二叉树为3权148离散数学考试试题（离散数学考试试题（B B 卷及答案）卷及答案）一
7、、 （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、三、 （8 分）已知 A、B、C 是三个集合，证明 A(BC)=(AB)(AC)证明：x A（BC） x Ax（BC） x A（xBxC）（ x AxB）（x AxC） 4 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
9、且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)，iiR 1U六、(15 分) 设 A、B、C、D 是集合，f 是 A 到 B 的双射，g 是 C 到 D 的双射，令 h：ACBD 且AC，h()。证明 h 是双射。证明：1）先证 h 是满射。BD，则 bB，dD，因为 f 是 A 到 B
10、 的双射，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 是双射。5七、(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
11、,bH 及 b-1H，a*b=a*（b-1）-1HHG 且 H,*在 H 上满足结合律 是的子群。八、 （10 分）设 G=是简单的无向平面图，证明 G 至少有一个结点的度数小于等于 5。解：设 G 的每个结点的度数都大于等于 6，则 2|E|=d(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 的最优二叉树及其权。解：最优二叉树为6权148
