离散数学考试卷

课程名称：离散数学； 试卷编号：B； 考试时间：120分钟

题号 一 二 三 四 应得分 16 12 10 62 实得分

总分 离散数学教程考试试题 （A卷）

一、 判断题（共10分,每小题2分）

1．一个不是自反的关系，一定是反自反的。（ ）

2．设人的集合A上的朋友关系为R，则R是A上的相容关系。（ ） 3．设A={￠}，B=P（P（A）），则有{￠}∈B。（ ） 4．任一图G的△（G）必小于其结点数。（ ） 5．若有向图D强连通，则D必为欧拉图。（ ）

二、填空题（共28分，每小题4分）

1. 下列语句中，是简单命题的为（ ），是复合命题的为（ ），是真命题的为（ ），是假命题的为（ ），真值待定（真值客观存在，只是现在不知道）的命题是（ ）。 ①2是素数。 ②圆的面积等于半径的平方与π乘积。 ③明年5月1日是晴天。 ④如果2+2=6，则8是偶数。 ⑤10能被2整除当且仅当3是偶数。

2．下列命题公式中，重言式的为（ ），矛盾式的为（ ）。 ①（p∧q）→(p∨q) ② ~(p→q)∧q ③(p∧~q) q ④p→(p∨q)

3. 设A={1，2，3}，则A上所有的等价关系个数为（ ）。 4．试判断下面三个图中关系性质：

（1）图具有（ ）， （2）图具有（ ）， （3）图具有（ ）。

1

5．给定下面5个函数，其中入射而非满射的有（ ），满射而非入射的有（ ），双射的有（ ），既不是入射又不是满射的有（ ）。 ① f:I→I,f(j)=j (mod 3); ② f:I→N, f(i)=|2i|+1; ③ f:R→R, f(r)=2r-15; ④ f:I+→I+, f(x)=x+1;

⑤ f:A→B, A={1,2,3,4,5},B={6,8,9,10},

f={<1,8>,<3,9>,<4,10>,<2,6>,<5,9>}.

6. 下面所示的三个图中，强连通图为（ ），单侧连通图为（ ），弱连通图为（ ）。

7．“每列火车都比某些汽车快”的符号化公式为（ ）。 令F（x）:x是火车，G（y）:y是汽车，H（x,y）:x比y快。 ①x(F(x)∧ y(G(y) ∧H(x,y))); ②xy(F(x)→(G(y)→H(x,y))); ③x(F(x)→y(G(y)∧H(x,y))); ④yx(F(x)→(G(y)∧H(x,y))); ⑤xy(F(x)→(G(y)∧H(x,y))).

三．设有下列情况，结论是否有效？ （10分） 甲，乙，丙，丁四人参加拳击比赛 （a） 如果甲获胜，则乙失败。 （b） 如果丙获胜，则乙也获胜。

（c） 如果甲不获胜，则丁不失败。 结论：如果丙获胜，则丁不失败。

四．求下式的主析取范式及主合取范式 （10分）

2

（P∧Q）∨(（~P∨~R）∧(Q∨F))

（10分）

五．设A，B，C为任意三个集合，求证：A∩（B-C）=（A∩B）-（A∩C）。

六．设S={1，2，3，4，6，8，12，24}，“≤”是S上的整除关系（即“≤”={|x,y∈S，x整除y}，请画出的哈斯图，并找出它的极小元，最小元，极大元，最大元。找出子集{1，2，3，6}，{4，8，12}的上界，下界，上确界，下确界。（15分）

七．已知n个结点的无向图G中有m条边，各结点的度数均为3，又已知2n-3=m, 问在同构的意义下，G是唯一的吗？ （5分）

八．用Huffman算法求带权为2，3，5，7，8，9的最优叶加权二元树T，并且指出T的叶加权路径长度为（ ），T中有（ ）片树叶，（ ）个2度结点，（ ）个3度结点，（ ）个4度结点，T的高度为（ ）。 （6分）

九．指出下面推理中的错误。（6分） ① x(F(x)∧G(x)) P ② y(H(y) ∧R(y)) P ③ F(c) ∧G(c) ES① ④ F(c) T③, I ⑤ H(c ) ∧R(c ) ES② ⑥ H(c ) T⑤, I ⑦ F(c ) ∧H(c ) T④⑥, I ⑧ x(F(x) ∧H(x)) EG⑦

3