离散数学试题与答案试卷一

结论：?x(P(x)?Q(x))

2. 设A是正整数集合，在A?A上定义二元关系R如下：

??x,y?,?u,v???R当且仅当xv?yu,证明：R为等价关系。

3. 设R为实数集，+为普通加法，?为普通乘法，是一个代数系统，*是R上的一个二元运算，使得?x,y?R，都有

x*y=x+y+x?y

证明:是含幺独异点。

4.设f1，f2都是一从代数系统到代数系统的同态。设g是从A到B的一个映射，使得对任意a?A，都有g(a)=f1(a) ?f2(a)；证明：如果为一个可交换半群，那么g是一个由到的同态映射

卷号：十 离散数学

本题得分 一、

选择题（选择正确答案，并将其代号写在题干后面的括号里，本

题共6小题,每小题3分，共18分)

1 下列语句中 哪个是真命题？ （） (A) 我正在说谎。 (B) 请讲普通话。

(C) 如果1＋2＝5，那么雪是黑的。 (D) 如果1+2=3,那么雪是黑的。

2 集合A?{1,2,???,10}上的关系R?{(x,y)|x?y?10,x?A,y?A},则R的性质为：（ ） (A) 自反的 (B)对称的 (C) 传递的、对称的 (D) 反自反的、传递的 3下面集合( )关于减法运算是封闭的。

(A) N (B) {x|x是质数}； (C) {2x?1|x?I}； (D) {2x|x?I}。

4设G1??{0,1,2},??，G2??{0,1},*?，其中?表示模3加法，*表示模2加法，则积代数G1?G2的单位元是（ ）。

(A)<0,0>； (B) <0,1>； (C) <1,0>； (D) <1,1> 5 下列偏序集中能构成格的是 （ ）。

6 图G和G?的结点和边分别存在一一对应关系是G和G?同构的 ( ) 。 (A) 必要条件 (B) 充分条件 (C) 充要条件 (D) 既不充分也不必要条件

本题得分 二、填空题（请将正确答案填入空格内，每小题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个叶结点。