离散数学考试试题(A卷及答案).doc
《离散数学考试试题(A卷及答案).doc》由会员分享，可在线阅读，更多相关《离散数学考试试题(A卷及答案).doc（5页珍藏版）》请在冰点文库上搜索。
离散数学考试试题（A卷及答案）
一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？
1）（（P®Q）∧Q）«（（Q∨R）∧Q）2）Ø（（Q®P）∨ØP）∧（P∨R）
3）（（ØP∨Q）®R）®（（P∧Q）∨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））
Û（0∨0）∧（0∨1）
Û1∧1Û0
三、（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>,<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个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘坐过其中的两种。
若每样乘坐一次的费用是0.5元，公园游乐场总共收入70元，求有多少儿童没有乘坐过其中任何一种。
解设、、分别表示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合，|∩∩|＝20，|∩|＋|∩|＋|∩|－2|∩∩|＝55，||＋||＋||＝70/0.5＝140。
由容斥原理，得
|∪∪|＝||＋||＋||―|∩|―|∩|―|∩|＋|∩∩|
所以
|∩∩|＝75－|∪∪|＝75－（||＋||＋||）＋（|∩|＋|∩|＋|∩|－2|∩∩|）＋|∩∩|＝75－140＋55＋20＝10
没有乘坐过其中任何一种的儿童共10人。
六、（12分）已知R和S是非空集合A上的等价关系，试证：
1）R∩S是A上的等价关系；2）对a∈A，[a]R∩S=[a]R∩[a]S。
解：
"x∈A，因为R和S是自反关系，所以∈R、∈S，因而∈R∩S，故R∩S是自反的。
"x、y∈A，若∈R∩S，则∈R、∈S，因为R和S是对称关系，所以因∈R、∈S，因而∈R∩S，故R∩S是对称的。
"x、y、z∈A，若∈R∩S且∈R∩S，则∈R、∈S且∈R、∈S，因为R和S是传递的，所以因∈R、∈S，因而∈R∩S，故R∩S是传递的。
总之R∩S是等价关系。
2）因为x∈[a]R∩SÛ∈R∩SÛ∈R∧∈SÛx∈[a]R∧x∈[a]SÛx∈[a]R∩[a]S
所以[a]R∩S=[a]R∩[a]S。
七（10分）设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：
A×C®B×D且"∈A×C，h（）＝。
证明h是双射。
证明：
1）先证h是满射。
"∈B×D，则b∈B，d∈D，因为f是A到B的双射，g是C到D的双射，所以存在a∈A，c∈C，使得f（a）=b，f（c）=d，亦即存在∈A×C，使得h（）＝＝，所以h是满射。
2）再证h是单射。
"、∈A×C，若h（）＝h（），则＝，所以f（a1）＝f（a2），g（c1）＝g（c2），因为f是A到B的双射，g是C到D的双射，所以a1＝a2，c1＝c2，所以＝，所以h是单射。
综合1）和2），h是双射。
八、（12分）是个群，u∈G，定义G中的运算“D”为aDb=a*u-1*b，对任意a,b∈G，求证：
也是个群。
证明：
1）"a,b∈G，aDb=a*u-1*b∈G，运算是封闭的。
2）"a,b,c∈G，（aDb）Dc=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=aD（bDc），运算是可结合的。
3）"a∈G，设E为D的单位元，则aDE=a*u-1*E=a，得E=u，存在单位元。
4）"a∈G，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={<1,2>,<1,4>,<2,3>,<3,4>,<3,5>,<5,1>}，求D的邻接距阵A和可达距阵P。
解：
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的最优二叉树及其权。
解：
最优二叉树为
权＝148
离散数学考试试题（B卷及答案）
一、（10分）求命题公式Ø（P∧Q）«Ø（ØP®R）的主合取范式。
解：
Ø（P∧Q）«Ø（ØP®R）Û（Ø（P∧Q）®Ø（ØP®R））∧（Ø（ØP®R）®Ø（P∧Q））
Û（（P∧Q）∨（ØP∧ØR））∧（（P∨R）∨（ØP∨ØQ））
Û（P∧Q）∨（ØP∧ØR）
Û（P∨ØR）∧（Q∨ØP）∧（Q∨ØR）
Û（P∨Q∨ØR）∧（P∨ØQ∨ØR）∧（ØP∨Q∨R）∧（ØP∨Q∨ØR）
ÛM1∧M3∧M4∧M5
二、（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∩（B∪C）=（A∩B）∪（A∩C）
证明：
∵xÎA∩（B∪C）ÛxÎA∧xÎ（B∪C）
ÛxÎA∧（xÎB∨xÎC）
Û（xÎA∧xÎB）∨（xÎA∧xÎC）
ÛxÎ（A∩B）∨xÎA∩C
ÛxÎ（A∩B）∪（A∩C）
∴A∩（B∪C）=（A∩B）∪（A∩C）
四、（10分）已知R和S是非空集合A上的等价关系，试证：
1）R∩S是A上的等价关系；2）对a∈A，[a]R∩S=[a]R∩[a]S。
解：
"x∈A，因为R和S是自反关系，所以∈R、∈S，因而∈R∩S，故R∩S是自反的。
"x、y∈A，若∈R∩S，则∈R、∈S，因为R和S是对称关系，所以因∈R、∈S，因而∈R∩S，故R∩S是对称的。
"x、y、z∈A，若∈R∩S且∈R∩S，则∈R、∈S且∈R、∈S，因为R和S是传递的，所以因∈R、∈S，因而∈R∩S，故R∩S是传递的。
总之R∩S是等价关系。
2）因为x∈[a]R∩SÛ∈R∩SÛ
∈R∧∈SÛx∈[a]R∧x∈[a]SÛx∈[a]R∩[a]S
所以[a]R∩S=[a]R∩[a]S。
五、（10分）设A＝{a，b，c，d}，R是A上的二元关系，且R＝{，，，}，求r（R）、s（R）和t（R）。
解r（R）＝R∪IA＝{，，，，，，，}
s（R）＝R∪R-1＝{，，，，，}
R2＝{，，，}
R3＝{，，，}
R4＝{，，，}＝R2
t（R）＝＝{，，，，，，，，}
六、（15分）设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：
A×C®B×D且"∈A×C，h（）＝。
证明h是双射。
证明：
1）先证h是满射。
"∈B×D，则b∈B，d∈D，因为f是A到B的双射，g是C到D的双射，所以存在a∈A，c∈C，使得f（a）=b，f（c）=d，亦即存在∈A×C，使得h（）＝＝，所以h是满射。
2）再证h是单射。
"、∈A×C，若h（）＝h（），则＝，所以f（a1）＝f（a2），g（c1）＝g（c2），因为f是A到B的双射，g是C到D的双射，所以a1＝a2，c1＝c2，所以＝，所以h是单射。
综合1）和2），h是双射。
七、（12分）设是群，H是G的非空子集，证明是的子群的充要条件是若a，bÎH，则有a*b-1ÎH。
证明：
Þ"a,b∈H有b-1∈H，所以a*b-1∈H。
Ü"a∈H，则e=a*a-1∈H
a-1=e*a-1∈H
∵a,b∈H及b-1∈H，∴a*b=a*（b-1）-1∈H
∵HÍG且H≠F,∴*在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=aa*b=b*a=ba*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
5
升级会员 