中南大学离散考试试卷

中南大学考试试卷

2009 -- 2010 学年 一 学期期末考试试题 时间100分钟

离散数学课程48学时3学分 考试形式：闭卷

一、

判断（本大题共10小题，每小题1分，共10分）

（ ）1．ρ(A)?? ρ(B) <=> A是B的子集

（ ）2．Q∧R∨P∧R∨T∧?P∧R的对偶式为Q∨R∧P∨R∧F∨?P∨R （ ）3．设Ａ和Ｂ是两个命题公式，若Ａ=＞B且B是重言式，则A是重言式。 （ ）4．R和S都是集合A上的关系，若R和S是自反的，则R?S是自反的。 （ ）5．设A、B和C是集合，若A∩B=A∩C，且A??，则B=C。

（ ）6．若R和S都是集合A上的二元关系，则dom(R)∪dom(S)=dom(R∪S)。 （ ）7．是全序集，则A的任何非空子集必有唯一极小元。 （ ）8．有限集上的全序关系必是良序关系。 （ ）9．连通的4度正则图一定没有桥。

（ ）10.设无向图G具有割点，则G中一定不存在哈密尔顿通路。 二、

单项选择（本大题共6小题，每小题2分，共12分）

（ ）1．若公式A(P,Q,R)的主合取范式为∏（0，1，4，5），则下列公式哪个是A(P,Q,R)的主析取范式

① ∑（0，1，4，5） ② ∏（0，1，4，5） ③ ∑（2，3，6，7） ④ ∏（2，3，6，7）

（ ）2．设∏1和∏2都是非空集合A的划分，则下列集合哪个必定是A的划分

① ∏1∪∏2 ② ∏1∩∏2 ③ ∏1—∏2 ④（∏1∩（∏2—∏1））∪∏2

（ ）3．设A-B=?，则下列命题中正确的是?

① B=? ② B≠? ③ A??B

④ B ? A

（ ）4．设R是集合A上的偏序关系，R-1 是R的逆关系，则R∪R-1是

①偏序关系 ②等价关系

③非自反关系

④非传递关系

（ ）5．若f、g是A上的双射，则

①

f?g是双射

②

(f?g)-1 =f-1?g-1

③

f?g?g?f ④ 以上答案都不对

（ ）6．任何无向图中结点间的可达关系是 三、 1． 2． 3．

若用谓词R(x)表示“x是实数”，L(x, y)表示“x

填空（本大题共9小题，每空2分，共24分）

若简单连通平面图G有4个结点，3个面，则G有______条边。 下图G最少需要_____种颜色进行点着色。

① 偏序关系 ③ 全序关系

② 等价关系 ④ 拟序关系

式为：_________________。

4． 给定论域D={1,2}和谓词P：

P(1,1)TP(1,2)TP(2,1)TP(2,2)F。则公式

?x?y(P(x,y)?P(y,x))的真值为

_____。 5． 6． 7．

若A是n元集合（n>0），则有______个不同的A上的即对称又反对称的关系。 一棵树有两个2度顶点，一个3 度顶点，三个4 度顶点，则该树有______片树叶 设集合A={a,b,c,d,e}上的偏序关系R的哈斯图如下图所示：

e b a c d

则A的最大元是________；A的最小元是________；A的极大元是________；A的极小元是________； 8． 9． 四、 1． 2． 3．

分别作出R，r (R )，sr(R )和tsr(R )的关系矩阵。 4．

2

设N是自然数集合，f和g是N到N的函数，f (n)=2n+1,g (n)=n，则复合函数f2?g (n)= ______

集合Ａ={1,2,3,4,5}上的等价关系Ｒ= 将导致集合Ａ的划分，即商集Ａ/Ｒ={{1,2},{3},{4,5}}。

计算与作图（共36分）

(8分) 设Ａ={ 2, 3, 12, 18, 24, 30, 36, 72}，｜为自然数的整除关系。画出<Ａ;｜>的Ｈasse图，并求{12, 24, 36}的上、下确界。 (8分) 设Ａ＝{a, b, c, d},Ｂ＝{1,2}，f＝{,,,}是Ａ到Ｂ的函数，试找出f的所有左逆和右逆（如果存在的话）。 (8分)设集合A={a,b,c,d}上的关系R的关系矩阵M (R )=

0 1 0 0 1 0 (12分) 有 8 种化学品 a, b, c, d, e, f, g, h 要放进贮藏室保管. 下列各对化学品不能贮藏在同一室内: a-c, a-f, a-h, b-d, b-f, b-h, c-d, c-g, d-e, d-g,

1 1 0 e-f, e-g, f-g, g-h

(1) (5分)画一个图表示这些化学品不能混放的情况，并对你的图加以文字说明；

(2) (4分)贮藏这 8 种化学药物至少需要几个房间. 一个房间最多贮藏多少种化学品，请写出一种方案；

(3) (3分)假如每种化学品的专家一定熟悉与该种化学品不能混放的化学品的特性(例如化学品a的专家熟悉化学品c, f, h), 则至少需要聘任多少位专家, 才能使每种化学品都有对其特性熟悉的人，请给出一种聘任方案。 五、 1．

证明（本大题共3小题，每小题6分，共18分） 用形式推理的标准格式证明：

A?B?C?D,D?E?P?A?P2． 3．

判断?x(P(x)

是否是重言式，并说明理由。

?Q(x))?(?xP(x)??xQ(x))证明: 任意一场聚会, 至少有两个人与相同数目的人握过手。

评分标准

一、

判断

(1)T (2)F (3)F (4)T (5)F (6)T (7)F 二、 单项选择

1. ③ 三、 填空

1. 5

2. 3

3. ?x?y(R(x)∧R(y)∧L(x,y)→?z(R(z)∧L(x,z)∧L(z,y)))_或?x?y(R(x)∧R(y)→(L(x,y)→?z(R(z)∧L(x,z)∧L(z,y))))或

2. ④

3. ③

4. ②

5.①

6. ②

(8)T (9)T (10)F

与之等价的其他形式。 4. T 8. 2n2+1

5. 2

n

6. 9 7. 最大元：无；最小元：a；极大元：b,e,d；极小元：a

9. {<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<1,2>,<2,1>,<4,5>,<5,4>}

四、 计算与作图 1.

72 24

36 （4分）

12 18 30 2 3

（上下确界各2分）

{12, 24, 36}的上确界：72；下确界：12 2. 有右逆无左逆（2分）

g1={<1,a>,<2,c>}；g2={<1,b>,<2,c>}；g3={<1,d>,<2,c>} （每个2分） 3. R2=

0 1 0

0 1 0

0 1 0 sr(R )= 1 1 1 1 1 1

（每个2分） 1 1 1 r (R )= tsr(R )=

1 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 4. (1) 节点表示化学药品，如果两种药品不能混放就在其间连一条边，图略；或者节点表示化学药品，如果两种药品能混放就在其间连一条边 (2) 如果是上述第一种画图法，即在图中寻找极大顶点无关集；如果是第二种画图法，即在图中寻找极大完全子图。至少需要3个房间，每个房间最多放3中药品。一种放置方案：{a,b,g}, {c,e,h}, {d,f}（不唯一）

(3) 至少需要2人，比如请g和f的专家 五、 证明

1.

A?B?C?D,D?E?P?A?PT⑴ I P

⑴ A P (附加前提) ⑵ A∨B ⑶ (A∨B)?(C∧D)

⑷ C∧D T⑵⑶ I ⑸ D ⑹ D∨E ⑺ (D∨E)?P P

⑻ P T ⑹⑺ I

T⑷ I T⑸ I

⑼ A?P （格式不对酌情扣分）

CP

2. 不是永真式，取解释如下

D= {1,2}

P(1) P(2) Q(1) Q(2) F T F T

在该解释下?xP(x) 为T，?xQ(x)为F，所以?xP(x) →?xQ(x)为F；而(P(1) →Q(1))为T， (P(2) →Q(2))为T，所以?x(P(x) →Q(x))为T；

综上该公式不是永真式

3. 因为一个人若与同一人握手多次不会影响其握手的人数，所以该问题即证任一无向简单图中必有两个点的度相等 证明略

离散数学考试试题（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是自反关系，所以∈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中的运算“?”为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如下：

A=

0 1 0 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0

P=

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 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＝{，，，} R＝{，，，}＝R

t(R)＝?Ri＝{，，，，，，，，

i?1?42

}

六、(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=e*a∈H ∵a,b∈H及b∈H，∴a*b=a*（b）∈H ∵H?G且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

-1

-1

-1

-1

（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分)求叶的权分别为最优二叉树及其权。

解：最优二叉树为 权

＝148

2、4、6、8、10、12、14的

本文来源：https://www.bwwdw.com/article/na06.html