04-05(2)《离散数学》期末考试试卷(A)

北京交通大学的离散数学考试试卷

北 京 交 通 大 学

2004-2005学年第二学期离散数学期末考试试卷

一、填空题（每空3分，共30分）

1、设p：三角形三条边相等；q：三个角相等．则“仅当三角形三条边相等时三个角相等”的符号化形式为 ．

2、设A是含n个命题变量的命题公式，则A为重言式的充分必要条件是A的主析取范式中含有极小项的个数是 ．

3、设个体域是{1，2}，命题 x y(x+y=3)的真值为

4、设A、B为集合，则命题“A－B= A=B” 的真值为

5、设A = {a,b,c}，R为A上的二元关系．如果R = {(a,b)}，那么R的传递闭包t(R) = .

6、设Q为有理数集，S=Q×Q， 是S上的二元运算． (a, b)，(x, y) S有(a, b) (x, y)=(ax, y+b)，则 运算的单位元是．

(a, b) S; a 0，则(a, b)的逆元是．

7、完全图Kn的边数m =

8、设无向树T有4片树叶，2个2度顶点，其余顶点的度数都是4，则T中4度顶点的个数是 ．

9、命题“符号串集合{1，01，001，000}是前缀码”的真值是

二、(8分) 对下列命题公式

(( p q ) r ) p

(1) 求其主析取范式和主合取范式；

(2) 写出其成真赋值和成假赋值；

(3) 判断公式的类型．

三、(8分)设个体域D ={2, 3, 6}，P(x)为x 3；Q(x)为x>5．消去下列公式中的量词，并讨论其真值，

x( P(x) yQ(y) )．

四、(8分)求下面公式的前束范式：

x yP(x, y) zQ(x, y, z)

并写出该前束范式的类型．

五、(12分)设集合A={1, 2, 3, 4}，回答下列问题，并说明理由：

(1) A上有多少个不同的二元关系？

(2) 上述二元关系中，有多少个等价关系？并写出所有的等价关系．

六、（10分）B是含有8个元素的布尔代数，

(1) 画出B的哈斯图；

(2) 给出B的全部子代数。

北京交通大学的离散数学考试试卷

七、(10分) 图中实边所示的子图为G的一棵生成树，

(1) 求基本回路系统， v e v并求出所有的初级回路， e5

画出它们的图形；

(2) 求基本割集系统. v1 e6 e7 e3

e1

2 e2 v3

八、(14分)设7个符号在通讯中出现的频率如下： O：35%； C：20%； D：15%；

G：10%； K：10%； L：5%； U：5%

(1) 编一个最佳前缀码；

(2) 画出相应的最优二元树；

(3) 问传输1,000个符号需要多少个二进制位；

(4) 写出短语“good luck”所对应的编码信息．

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