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

1离散数学考试试题（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元，求有多少儿童没有乘坐过其中任何一种。解设A、B、C分别表示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合，|A∩B∩C|＝20，|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|＝55，|A|＋|B|＋|C|＝70/0.5＝140。由容斥原理，得|A∪B∪C|＝|A|＋|B|＋|C|―|A∩B|―|A∩C|―|B∩C|＋|A∩B∩C|所以|A∩B∩C|＝75－|A∪B∪C|＝75－(|A|＋|B|＋|C|)＋(|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|)＋|A∩B∩C|＝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是自反关系，所以x,x∈R、x,x∈S，因而x,x∈R∩S，故R∩S是自反的。x、y∈A，若x,y∈R∩S，则x,y∈R、x,y∈S，因为R和S是对称关系，所以因y,x∈R、y,x∈S，因而y,x∈R∩S，故R∩S是对称的。2x、y、z∈A，若x,y∈R∩S且y,z∈R∩S，则x,y∈R、x,y∈S且y,z∈R、y,z∈S，因为R和S是传递的，所以因x,z∈R、x,z∈S，因而x,z∈R∩S，故R∩S是传递的。总之R∩S是等价关系。2）因为x∈[a]R∩Sx,a∈R∩Sx,a∈R∧x,a∈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∈A×C，h(a,c)＝f(a),g(c)。证明h是双射。证明：1）先证h是满射。b,d∈B×D，则b∈B，d∈D，因为f是A到B的双射，g是C到D的双射，所以存在a∈A，c∈C，使得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的双射，所以a1＝a2，c1＝c2，所以a1,c1＝a2,c2，所以h是单射。综合1）和2），h是双射。八、（12分）G,*是个群，u∈G，定义G中的运算“”为ab=a*u-1*b，对任意a,b∈G，求证：G,也是个群。证明：1）a,b∈G，ab=a*u-1*b∈G，运算是封闭的。2）a,b,c∈G，（ab）c=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=a（bc），运算是可结合的。3）a∈G，设E为的单位元，则aE=a*u-1*E=a，得E=u，存在单位元。4）a∈G，ax=a*u-1*x=E，x=u*a-1*u，则xa=u*a-1*u*u-1*a=u=E，每个元素都有逆元。所以G,也是个群。九、（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的最优二叉树及其权。解：最优二叉树为3权＝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）4∴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是自反关系，所以x,x∈R、x,x∈S，因而x,x∈R∩S，故R∩S是自反的。x、y∈A，若x,y∈R∩S，则x,y∈R、x,y∈S，因为R和S是对称关系，所以因y,x∈R、y,x∈S，因而y,x∈R∩S，故R∩S是对称的。x、y、z∈A，若x,y∈R∩S且y,z∈R∩S，则x,y∈R、x,y∈S且y,z∈R、y,z∈S，因为R和S是传递的，所以因x,z∈R、x,z∈S，因而x,z∈R∩S，故R∩S是传递的。总之R∩S是等价关系。2）因为x∈[a]R∩Sx,a∈R∩Sx,a∈R∧x,a∈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＝{a，b，b，a，b，c，c，d}，求r(R)、s(R)和t(R)。解r(R)＝R∪IA＝{a，b，b，a，b，c，c，d，a，a，b，b，c，c，d，d}s(R)＝R∪R-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)＝iiR1＝{a，b，b，a，b，c，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，则b∈B，d∈D，因为f是A到B的双射，g是C到D的双射，所以存在a∈A，c∈C，使得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的双射，所以a1＝a2，c1＝c2，所以a1,c1＝a2,c2，所以h是单射。综合1）和2），h是双射。七、(12分)设G，*是群，H是G的非空子集，证明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∈H5a-1=e*a-1∈H∵a,b∈H及b-1∈H，∴a*b=a*（b-1）-1∈H∵HG且H≠,∴*在H上满足结合律∴H，*是G，*的子群。八、（10分）设G=V，E是简单的无向平面图，证明G至少有一个结点的度数小于等于5。解：设G的每个结点的度数都大于等于6，则2|E|=d(v)≥6|V|，即|E|≥3|V|，与简单无向平面图的|E|≤3|V|-6矛盾，所以G至少有一个结点的度数小于等于5。九.G=A,*,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