D．设A?Z,?a,b?A,a?b?a?2b
6．设G是6阶循环群，a是生成元。则下列集合能构成G的子群的是（ C ）。 A．{e,a} B．{e,a2} C．{e,a3} D．{e,a4}
7．设代数系统(K1,?)和(K2,?)，存在映射f:K1?K2，如果?a,b?K1，都有（ B ），称K1与K2同态。
A．f(a?b)?f(a)?f(b) B．f(a?b)?f(a)?f(b) C．f(a?b)?f(a)?f(b) D．f(a?b)?f(a)?f(b)
8．图G有21条边，3个4度结点，其余均为3度结点，则G有（ A ）个结点。 A． 13 B． 15 C． 17 D． 19
9．若连通图G??V,E?，其中|V|?n,|E|?m，则要删去G中（ C ）条边，才能确定G的一棵生成树。
A．n?m?1 B．n?m?1 C．m?n?1 D．m?n?1 10．如下图所示各图，其中存在哈密顿回路的图是（ C ）。
A B C D 二．填空题
11．任意两个不同极小项的合取为 矛盾 式，全体极小项的析取式必为 重言 式。 12．命题“任意实数总能比较大小”可符号化为 ?x?y(R(x)?R(y)?x?y?x?y) 。 13．由集合运算的吸收律，(A?B)?B? B ，A?(A?B)? A 。
14．设集合A = {a,b,c,d}，A上的二元关系R = {,,
15．设集合A = {a,b,c,d}，A上的二元关系R = {,
36
Ran(R) = {b，c，d} 。
?110???16．设集合B = {a,b,c}上的二元关系R的关系矩阵MR??001?，则R具有的性质是 反对称性
?000???17．在布尔代数中，有a?(a?b)?a?b成立，则其对偶式 a?(a?b)?a?b 成立。 18．已知下图，它的点连通度?(G)为 1 ，边连通度?(G)为 1 。
19．给定平面图G，如下图所示，则G的面数为 4 ，G中面的总次数为 18 。
20．二部图G中所有基本圈的长度为 偶数 （奇数或偶数） 三．计算题
21．符号化下述两个语句，并说明其区别： （1）如果天不下雨，我们就去郊游；（2）只有不下雨，我们才去郊游。 答：解：（1）令P：天下雨，Q：我们去郊游。 该命题可符号化为?P?Q。（天不下雨是去郊游的充分条件） （2）令P：天下雨，Q：我们去郊游。
该命题可符号化为Q??P或P??Q。（天不下雨是去郊游的必要条件） 22．试求命题公式P?Q?R的主析取范式和主合取范式。 答：解：P?Q?R
?(P?Q?(R??R))?((P??P)?(Q??Q)?R) ?(P?Q?R)?(P?Q??R)?(P?Q?R)
?(P??Q?R)?(?P?Q?R)?(?P??Q?R)
37
?(?P??Q?R)?(?P?Q?R)?(P??Q?R)?(P?Q??R)?(P?Q?R)
?m001?m011?m101?m110?m111
?m1?m3?m5?m6?m7
??(1,3,5,6,7)
∴命题公式P?Q?R的主析取范式为
(?P??Q?R)?(?P?Q?R)?(P??Q?R)?(P?Q??R)?(P?Q?R)
?m1?m3?m5?m6?m7??(1,3,5,6,7)。
②求主合取范式
由①知命题公式P?Q?R的主合取范式为
?(0,2,4)?M0?M2?M4?(P?Q?R)?(P??Q?R)?(?P?Q?R)
?123．设R={<0,1>,<0,2>,<0,3>,<1,3>,<2,3>}，求：⑴ R*R；⑵ R?R；
⑶ R?1?{1}；⑷ R?1[{1}]
答：解：(1)R?R?{?0,2?,?0,3?,?1,3?}
(2)R?1?{1}?{?1,0?}
(3)R-1?{1}
24．设集合A = {a，b}，B = {1，2，3}，C = {3，4}，求A?(B?C)，(A?B)?(A?C)，并验证
{2,3}
A?(B?C)?(A?B)?(A?C)。
答：解 A?(B?C)?{a,b}?{3}?{?a,3?,?b,3?}
A?B?{?a,1?,?a,2?,?a,3?,?b,1?,?b,2?,?b,3?} A?C?{?a,3?,?a,4?,?b,3?,?b,4?} (A?B)?(A?C)?{?a,3?,?b,3?} ∴A?(B?C)?(A?B)?(A?C)
38
25．设集合A = {0,1,2,3,4,5}上的二元关系R = {<0,0>,<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,
<2,3>,<3,1>,<3,2>,<3,3>,<4,4>,<4,5>,<5,4>,<5,5>}，试说明R在A上是等价关系。 答：解：i)F(R)?{0,1,2,3,4,5}
（1）因为I(F(R))?{?0,0?,?1,1?,?2,2?,?3,3?,?4,4?,?5,5?}?R， 所以R是自反的； （2）因为
R?1?{?0,0?,?1,1?,?2,1?,?3,1?,?1,2?,?2,2?,?3,2?,?1,3?,?2,3?,?3,3?,?4,4?,?5,4?,?4,5?,?5,5?}而(R?1)?1?R?1，所以R是对称的；
（3）因为R?R?R，所以具有传递性．由（1）(2)(3)可知R在A上式等价关系。
26．设Z+是正整数集，?a,b?Z?，a?b?lcm(a,b)（即a,b的最小公倍数）。试问(Z?,?)是半群，是含单位元的半群吗？
答：解：任意两个正整数的最小公倍数仍是一个正整数，即?在Z+上是封闭的，故?是Z+上的二元运算。
?a,b,c?Z?，设m?(a?b)?c，n?a?(b?c)，则有
m?lcm(lcm(a,b),c) ?lcm(a,b)|m, c|m ?a|m, b|m, c|m
(b,c)|m ?a|m, lcm ?lcm(a,lcm(b,c))|m 即 n|m
同理可证m|n。故有m?n，即(a?b)?c?a?(b?c)。所以?是可结合的。从而(Z?,?)是一个半群。 因为?a?Z?，有a?1?lcm(a,1)?a，故1是单位元，即(Z?,?)是含单位元的半群。
三．计算题（二）
27．设(B,?,?, ,0,1)是布尔代数，\a,b,c?B，化简
agbgc+agbgc+bgc+agbgc+agbgc。
39
答：解：abc?abc?bc?abc?abc
?ab(c?c)?bc?ab(c?c) （结合律，分配律） ?ab?bc?ab （c?c?1）
?b((a?a)?c) （交换律，分配律，结合律） ?b （a?a?1, 1?c?1）
28．求图D的邻接矩阵A(D)，计算A3(D)，并找出v1到v4长度为2，3的所有通路。
答：解
?1?1 A(D)???1??1??7??5 A3(D)??4??3?
10003221110043320??3??0??2 A2(D)??21????1?0??2??16??1??11 A4(D)??101?????71??121??111? ?110?110??7104??573? ?463?342?? 从v1到v4长度为2的通路有1条：v1e5v3e7v4。
从v1到v4长度为3的通路有2条：v1e2v2e4v3e7v4，v1e1v1e5v3e7v4。 四证明题
29．试证明：\xA(x)?xB(x)?x((A(x)?B(x))
答：证明 （1）?xA(x)??xB(x) P
（2）?xA(x)??yB(y) T（1）（换名规则） （3）?x?y(A(x)?B(y)) T（2）（前束范式性质2）
40