离散数学试题与答案试卷一(5)

本题得分 二、填空题（请将正确答案填入空格内，每小题3分，共18分）

1 命题公式p→q的真值为假，当且仅当_________________。

2 设 G(x):x是金子,F(x):x是闪光的,则命题“金子是闪光的,但闪光的不一定是金子”

符号化为: 。

3 设整数集合I上的二元关系R?{(a,b)|a?b},则R的对称闭包为： 。

?))?(b?x1?x2)是布尔代数?{0,a,b,1}, 4 f(x1,x2)?((a?x1)?(x1?x2?,?,?,0,1?上的布尔表达式，则 f(a,b)? 。

5 设树T有m个顶点，n条边，则T中顶点与边的关系为: 。 6 不同构的5阶无向树有_______棵。 本题得分 三、判断题（请在你认为正确的题后括号内打“√”，错误的打“×”，本题共6小题，每小题1分，共6分）

1 （P?Q）?（P?Q）是永真式。（ ） 2 {?}?{?,{?}}且{?}?{?,{?}}。（ ）

3 一种关系，不是自反的，就是反自反的。（ ） 4代数系统中一个元素的左逆元并一定等于该元素的右逆元。（ ） 5 设G为无向图，若G无回路，则G必为一棵树。 （ ） 6 5阶完全图是平面图。（ ） 本题得分 四、计算题（本题共4小题,每小题6分，共24 分）

1 给定3个命题：P：北京比天津人口多；Q：2大于1；R：15是素数。 求复合命题：

(Q?R)?(P??R)的真值。

2 集合A?{1,2,3,4}上的关系R?{(1,1),(1,3),(2,2),(3,1),(3,3),(3,4),

(4,3),(4,4)}，写出关系矩阵MR，并讨论R的性质。

3 设是一个群，这里+6是模6加法，Z6={[0 ]，[1]，[2]，[3]，[4]，[5]}，试求出

的所有子群及其相应左陪集。

4 给定一组权值为：2，3，5，7，8，9，请构造一棵最优二叉树，并求W（T）。 本题得分 五、应用题（本题共1小题,每小题10分，共10分）

下列前提下结论是否有效？

今天或者天晴或者下雨。如果天晴，我去看电影；若我去看电影，我就不看书。故我在看书时，说明今天下雨。

本题得分 六、证明题（本题共3小题,每小题8分，共24分）

1 设R是集合A上的一个具有传递和自反性质的关系，T是A上的关系，使得?T当且仅当?R且?R,证明T是一个等价关系。

2 设?A,?,?,??是一个布尔代数，如果在A上定义二元运算“☆”为：a☆

b?(a?b)?(a?b)，则是一阿贝尔群。

3 设T是非平凡无向树，T中结点数大于等于2，T中度数最大的结点有2个，它们的度

数为k(k?2)，证明：T中至少有2k?2个叶结点。