北 京 交 通 大 学
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) 求基本回路系统， v5 e4 v4 并求出所有的初级回路， e5 画出它们的图形；
(2) 求基本割集系统. v1 e6 e7 e3
e1
v2 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”所对应的编码信息．