内容发布更新时间 : 2024/6/16 20:08:45星期一 下面是文章的全部内容请认真阅读。

精品文档

离散数学考试试题（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元，求有多少儿童没有乘坐过其中任何一种。

CCBBAA|∩分别表示骑旋转木马、坐滑行铁道、解 设乘宇宙飞船的儿童组成的集合，、|、∩CCCCBBBAAAAB|＝70/0.5＝|140|。|＋|＋||∩ |－2||∩∩＋|＝＝20，|55∩＋||，∩由容斥原理，得

CCCCCBAAABBABBA| |―|∩|∩|―|∩∩|―|||∩∪＋∪|＝|||＋||＋所以 CBACCCBAAABBAB∩|＋|||＋|∩||)＋∩(|∩＋|＝75－|∪∩∪(||＝75－||＋|CCCBBAA|＝75－140＋＋|55∩＋∩20|－2|∩＝∩10

|)没有乘坐过其中任何一种的儿童共10人。

六、（12分）已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，[a]=[a]∩[a]。

R

S∩SR

解：?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? x∈[a]∧x∈[a]? x∈[a]∩[a][a]=[a]∩[a]。

SRR∩S

S ∩RSSRR

所以

七（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中的运算“?”为a?b=a*u-1*b，对任意a,b∈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，每个元素都有逆元。 所以也是个群。

九、（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如下：

1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 1 P= 1 1 1 A= 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 1 1

十、（10分）求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。 解：最优二叉树为

精品文档． 精品文档