12．子集公理的逻辑表达式为 (\x)(x萎Ax?B) 。
13．A上的二元关系R = {,
?110???M?00114．设集合B = {a,b,c}上的二元关系R的关系矩阵R??，则R具有的性质是 反对称?000???性 ，且它的对称闭包S(R)＝ {,,
A = {a,b}，B = {1,2}，则从
<{a,2>
f1={,
16．完全图Kn是平面图的充要条件是n? ?4 17．在布尔代数中，有a?(a?b)?a?b成立，则其对偶式 a?(a?b)?a?b 成立。 18．已知下图，它的点连通度?(G)为 1 ，边连通度?(G)为 1 。
19．给定平面图G，如下图所示，则G的面数为 4 ，G中面的总次数为 18 。
n 20．若二部图Km,n为完全二部图，则其边数为 m×三．计算题(一)
21．符号化下述两个语句，并说明其区别：
（1）如果天不下雨，我们就去旅游；（2）只有不下雨，我们才去旅游。 答：解：（1）令P：天下雨，Q：我们去郊游。
31
该命题可符号化为?P?Q。 天不下雨是去郊游的充分条件 （2）令P：天下雨，Q：我们去郊游。
该命题可符号化为Q??P或P??Q。 天不下雨是去郊游的必要条件
22．将下命题化为主析取范式和主合取范式： (p?(q?r))?(p?q?r). 答：解：设题中的公式为A，则 A?(p?(q?r))?(p?q?r)
??(p?(q?r))?(p?q?r) ??p?(?q??r)?(p?q?r)
?(?p??q)?(?p??r)?(p?q?r) ?(?p??q?(?r?r))?(?p?(?q?q)??r)?(p?q?r)
?(?p??q??r)?(?p??q?r)?(?p??q??r)?(?p?q??r)?(p?q?r) ?(?p??q??r)?(?p??q?r)?(?p?q??r)?(p?q?r)
?m0?m1?m2?m7,此即该公式的主析取范式.由此即推得它的主合取范式为 M3?M4?M5?M6
=(p??q??r)?(?p?q?r)?(?p?q??r)?(?p??q?r)
23．设R={<0,1>,<1,0>,<0,2>,<2,0>}，求：⑴ R*R；⑵ R*R-1； ⑶ R-{f,{f}}；⑷ R[{f,{f}}] 答：解： ⑴ R?R?{?0,0??,⑵ R?R?1?{?0,0??,⑶ R?{?,?{}?}R?⑷ R[{f,f{}=}]R 1,?1?,?1,?2?,?2,1?, 2 } 1,?1?,?1,?2?,?2,1?, 2, 2{0?,1}?[{0,=1}]{??0,1?,?0,2? ,
0{
24．设集合Ａ＝｛１，２，３，４｝，Ａ上的二元关系Ｒ，其中Ｒ＝｛<1,1>,<1,4>,<2,2>, <2,3>,<3,2>,<3,3>,<4,1>,<4,4>｝，说明Ｒ是否Ａ上的等价关系。
32
答：解：从Ｒ的表达式可知，x∈A，（x，x）∈R，即Ｒ具有自反性， 由Ｒ的表达式，x，y∈A,(x,y)∈R,则(y,x)∈Ｒ，Ｒ具有对称性。 又有x，y，z∈Ａ，(x，y)∈R且（y，ｚ）∈Ｒ，则（x，ｚ）∈Ｒ， 于是Ｒ具有传递性。故Ｒ是Ａ上的等价关系。 25．分别画下图中的强分图、单向分图。
答：解：强分图为 2分。单向分图为：
26．设代数系统(Z,?),其中Z是整数集，二元运算定义为?a,b?Z,a?b?a?b?2。?a?Z,求a的逆元.
答：解：易知，二元运算满足交换律
.? 对?a?Z,a?2?a?2?2?a?2?a 即2?Z是单位元.
?a?Z, a的逆元记作a?1，有 a?a?1?a?a?1?2?2（单位元）
?1a?4?a． ?
三．计算题(二)
27．设(B,?,?, ,0,1)是布尔代数，?a,b,c?B，化简a+agb(cga+b)。 答：解：a?ab(ca?b)
?a?abca?abb ?a?ab
?(a?a)(a?b) （加法对乘法的分配律）
33
?a?b
28．求下图D的邻接矩阵A(D)，并算出其可达矩阵P(D) 答：解：
?1?1 A(D)???1??1??16??11A4(D)??10??7?
100011000??0?1??0??
?3??22A(D)??2??1?121??111?110??110??
?7??5A3(D)??4??3?11111??1? ?1?1?322143322??1? ?1?1??7104??11??573?11(1)(2)(3)(4) P(D)?A?A?A?A???11463???342??11?
四．证明题
29．试证明：(\x)(P(x)?Q(x)),(x)?P(x)┣ ($x)Q(x) 答：证明：
用反证法，假设??xQ(x)成立。
（1）?x?P(x) 前提 （2）?P(y) （1）；US （3）??xQ(x) 假设 （4）?x?Q(x) （3） （5）?Q(y) （4）；US （6）?P(y)??Q(y) （2），（5） （7）?(P(y) ?Q(y)) （6） （8）?x(P(x)?Q(x)) 前提 （9）P(y) ?Q(y) （8），US （10）(P(y) ?Q(y)) ??(P(y) ?Q(y)) （7），（9）
因为(P(y) ?Q(y)) ??(P(y) ?Q(y))是恒假公式，所以?x(P(x)?Q(x))，?x?P(x)??xQ(x)。
30．给定正整数m，令G={km|k?Z}，证明：(G,+)是一个群，其中+是数的普通加法。
34
答：证明
?a,b?G，存在k,l?Z使a?km,b?lm。由于k?l?Z，得知
a?b?km?lm?(k?l)m?G，即?在G上是封闭的。
由整数运算的性质可知，?是可结合的。
0?0?m?G，对?a?G，有a?0?0?a?a，故0是G的单位元。
?a?G，存在k?Z使a?km，由于?k?Z，?a?(?k)m?G，且a?(?a)?(?a)?a?0。故?a是a的逆元。
综上所述，(G,?)是一个群。
复习题十
一．单项选择题
1．下列哪个语句是真命题（ A ）。
A．我正在说谎 B．如果1+2 = 3，则雪是黑色的 C．如果1+2 = 5，则雪是黑色的 D．上网了吗
2．设L(x)：x是演员，J(x)：x是教师，A(x，y)：x佩服y，命题“所有演员都佩服某些 教师”可符号化为（ B ）。
A．?xL(x)?A(x,y) B．?x(L(x)??y(J(y)?A(x,y))) C．?x?y(L(x)?J(y)?A(x,y)) D．?x?y(L(x)?J(y)?A(x,y)) 3．设A，B，C为任意三个集合，下列命题正确的是（ C ）。
A．若A?B?A?C，则B?C B．若A?B?A?C，则B?C C．若~A?B?E且A?B，则A?B D．若A?B??，则A?B 4．设集合A = {a，b}上的二元关系R = {,
35