离散数学试题及答案
一、填空题
1 设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; r(A) - r(B)＝ __________________________ .
2. 设有限集合A, |A| = n, 则 |r(A×A)| = __________________________.
3. 设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________.
4. 已知命题公式G＝Ø(P®Q)∧R，则G的主析取范式是_______________________________
__________________________________________________________.
5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________.
6 设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从AÇB＝_________________________; AÈB＝_________________________;A－B＝ _____________________ .
7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________.
8. 设命题公式G＝Ø(P®(QÙR))，则使公式G为真的解释有__________________________，_____________________________, __________________________.
9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1·R2 = ________________________,R2·R1 =____________________________, R12 =________________________.
10. 设有限集A, B，|A| = m, |B| = n, 则| |r(A´B)| = _____________________________.
11 设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, xÎR}, B = {x | 0≤x < 2, xÎR},则A-B = __________________________ , B-A = __________________________ ,
A∩B = __________________________ , .
13. 设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________.
14. 设一阶逻辑公式G = "xP(x)®$xQ(x)，则G的前束范式是__________________________ _____.
15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。
16. 设谓词的定义域为{a, b},将表达式"xR(x)→$xS(x)中量词消除，写成与之对应的命题公式是__________________________________________________________________________.
17. 设集合A＝{1, 2, 3, 4}，A上的二元关系R＝{(1,1),(1,2),(2,3)}, S＝{(1,3),(2,3),(3,2)}。则R×S＝_____________________________________________________,
R2＝______________________________________________________.
二、选择题
1 设集合A={2,{a},3,4}，B = {{a},3,4,1}，E为全集，则下列命题正确的是( )。
(A){2}ÎA (B){a}ÍA (C)ÆÍ{{a}}ÍBÍE (D){{a},1,3,4}ÌB.
2 设集合A={1,2,3},A上的关系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，则R不具备( ).
(A)自反性 (B)传递性 (C)对称性 (D)反对称性
3 设半序集(A,≤)关系≤的哈斯图如下所示，若A的子集B = {2,3,4,5},则元素6为B的( )。
(A)下界 (B)上界 (C)最小上界 (D)以上答案都不对
4 下列语句中，( )是命题。
(A)请把门关上 (B)地球外的星球上也有人
(C)x + 5 > 6 (D)下午有会吗？
5 设I是如下一个解释：D＝{a,b},
则在解释I下取真值为1的公式是( ).
(A)$x"yP(x,y) (B)"x"yP(x,y) (C)"xP(x,x) (D)"x$yP(x,y).
6. 若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是( ).
(A)(1,2,2,3,4,5) (B)(1,2,3,4,5,5) (C)(1,1,1,2,3) (D)(2,3,3,4,5,6).
7. 设G、H是一阶逻辑公式，P是一个谓词，G＝$xP(x), H＝"xP(x),则一阶逻辑公式G®H是( ).
(A)恒真的 (B)恒假的 (C)可满足的 (D)前束范式.
8 设命题公式G＝Ø(P®Q)，H＝P®(Q®ØP)，则G与H的关系是( )。
(A)GÞH (B)HÞG (C)G＝H (D)以上都不是.
9 设A, B为集合，当( )时A－B＝B.
(A)A＝B (B)AÍB (C)BÍA (D)A＝B＝Æ.
10 设集合A = {1,2,3,4}, A上的关系R＝{(1,1),(2,3),(2,4),(3,4)}, 则R具有( )。
(A)自反性 (B)传递性 (C)对称性 (D)以上答案都不对
11 下列关于集合的表示中正确的为( )。
(A){a}Î{a,b,c} (B){a}Í{a,b,c} (C)ÆÎ{a,b,c} (D){a,b}Î{a,b,c}
12 命题"xG(x)取真值1的充分必要条件是( ).
(A) 对任意x，G(x)都取真值1. (B)有一个x0，使G(x0)取真值1.
(C)有某些x，使G(x0)取真值1. (D)以上答案都不对.
13. 设G是连通平面图，有5个顶点，6个面，则G的边数是( ).
(A) 9条 (B) 5条 (C) 6条 (D) 11条.
14. 设G是5个顶点的完全图，则从G中删去( )条边可以得到树.
(A)6 (B)5 (C)10 (D)4.
15. 设图G的相邻矩阵为
，则G的顶点数与边数分别为( ).
(A)4, 5 (B)5, 6 (C)4, 10 (D)5, 8.
三、计算证明题
1.设集合A＝{1, 2, 3, 4, 6, 8, 9, 12}，R为整除关系。
(1) 画出半序集(A,R)的哈斯图；
(2) 写出A的子集B = {3,6,9,12}的上界，下界，最小上界，最大下界；
(3) 写出A的最大元，最小元，极大元，极小元。
1. 设集合A＝{1, 2, 3, 4}，A上的关系R＝{(x,y) | x, yÎA 且 x ³ y}, 求
(1) 画出R的关系图；
(2) 写出R的关系矩阵.
2. 设R是实数集合，s,t,j是R上的三个映射，s(x) = x+3, t(x) = 2x, j(x) ＝ x/4,试求复合映射s•t，s•s, s•j, j•t，s•j•t.
4. 设I是如下一个解释：D = {2, 3},
a
b
f (2)
f (3)
P(2, 2)
P(2, 3)
P(3, 2)
P(3, 3)
3
2
3
2
0
0
1
1
试求 (1) P(a, f (a))∧P(b, f (b));
(2) "x$y P (y, x).
5. 设集合A＝{1, 2, 4, 6, 8, 12}，R为A上整除关系。
(1) 画出半序集(A,R)的哈斯图；
(2) 写出A的最大元，最小元，极大元，极小元；
(3) 写出A的子集B = {4, 6, 8, 12}的上界，下界，最小上界，最大下界.
6. 设命题公式G = Ø(P→Q)∨(Q∧(ØP→R)), 求G的主析取范式。
7. (9分)设一阶逻辑公式：G = ("xP(x)∨$yQ(y))→"xR(x)，把G化成前束范式.
9. 设R是集合A = {a, b, c, d}. R是A上的二元关系, R = {(a,b), (b,a), (b,c), (c,d)},
(1) 求出r(R), s(R), t(R)；
(2) 画出r(R), s(R), t(R)的关系图.
11. 通过求主析取范式判断下列命题公式是否等价：
(1) G = (P∧Q)∨(ØP∧Q∧R)
(2) H = (P∨(Q∧R))∧(Q∨(ØP∧R))
13. 设R和S是集合A＝{a, b, c, d}上的关系，其中R＝{(a, a),(a, c),(b, c),(c, d)}, S＝{(a, b),(b, c),(b, d),(d, d)}.
(1) 试写出R和S的关系矩阵；
(2) 计算R•S, R∪S, R－1, S－1•R－1.
四、证明题
1. 利用形式演绎法证明：{P→Q, R→S, P∨R}蕴涵Q∨S。
2. 设A,B为任意集合，证明：(A-B)-C = A-(B∪C).
3. (本题10分)利用形式演绎法证明：{ØA∨B, ØC→ØB, C→D}蕴涵A→D。
4. (本题10分)A, B为两个任意集合，求证：
A－(A∩B) = (A∪B)－B .
参考答案
一、填空题
1. {3}; {{3},{1,3},{2,3},{1,2,3}}.
2.
.
3. a1= {(a,1), (b,1)}, a2= {(a,2), (b,2)},a3= {(a,1), (b,2)}, a4= {(a,2), (b,1)}; a3, a4.
4. (P∧ØQ∧R).
5. 12, 3.
6. {4}, {1, 2, 3, 4}, {1, 2}.
7. 自反性；对称性；传递性.
8. (1, 0, 0), (1, 0, 1), (1, 1, 0).
9. {(1,3),(2,2),(3,1)}; {(2,4),(3,3),(4,2)}; {(2,2),(3,3)}.
10. 2m´n.
11. {x | -1≤x < 0, xÎR}; {x | 1 < x < 2, xÎR}; {x | 0≤x≤1, xÎR}.
12. 12; 6.
13. {(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)}.
14. $x(ØP(x)∨Q(x)).
15. 21.
16. (R(a)∧R(b))→(S(a)∨S(b)).
17. {(1, 3),(2, 2)}; {(1, 1),(1, 2),(1, 3)}.
二、选择题
1. C. 2. D. 3. B. 4. B.
5. D. 6. C. 7. C.
8. A. 9. D. 10. B. 11. B.
13. A. 14. A. 15. D
三、计算证明题
1.
(1)
(2) B无上界，也无最小上界。下界1, 3; 最大下界是3.
(3) A无最大元，最小元是1，极大元8, 12, 90+; 极小元是1.
2.R = {(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)}.
(1)
(2)
3. (1)s•t＝s(t(x))＝t(x)+3＝2x+3＝2x+3.
(2)s•s＝s(s(x))＝s(x)+3＝(x+3)+3＝x+6,
(3)s•j＝s(j(x))＝j(x)+3＝x/4+3,
(4)j•t＝j(t(x))＝t(x)/4＝2x/4 = x/2,
(5)s•j•t＝s•(j•t)＝j•t+3＝2x/4+3＝x/2+3.
4. (1) P ( a , f ( a ))∧ P ( b , f ( b )) = P (3, f (3))∧ P (2, f (2))
= P(3, 2)∧P(2, 3)
= 1∧0
= 0.
(2) "x$y P (y, x) = "x (P (2, x)∨P (3, x))
= (P (2, 2)∨P (3, 2))∧(P (2, 3)∨P (3, 3))
= (0∨1)∧(0∨1)
= 1∧1
= 1.
5. (1)
(2) 无最大元，最小元1，极大元8, 12; 极小元是1.
(3) B无上界，无最小上界。下界1, 2; 最大下界2.
6. G = Ø(P→Q)∨(Q∧(ØP→R))
= Ø(ØP∨Q)∨(Q∧(P∨R))
= (P∧ØQ)∨(Q∧(P∨R))
= (P∧ØQ)∨(Q∧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)∨(P∧Q∧ØR)∨(ØP∧Q∧R)
= m3∨m4∨m5∨m6∨m7 = S(3, 4, 5, 6, 7).
7. G = (" xP ( x )∨$ yQ ( y ))→" xR ( x )
= Ø("xP(x)∨$yQ(y))∨"xR(x)
= (Ø"xP(x)∧Ø$yQ(y))∨"xR(x)
= ($xØP(x)∧"yØQ(y))∨"zR(z)
= $x"y"z((ØP(x)∧ØQ(y))∨R(z))
9. (1) r(R)＝R∪IA＝{(a,b), (b,a), (b,c), (c,d), (a,a), (b,b), (c,c), (d,d)},
s(R)＝R∪R－1＝{(a,b), (b,a), (b,c), (c,b) (c,d), (d,c)},
t(R)＝R∪R2∪R3∪R4＝{(a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d), (c,d)}；
(2)关系图:
11. G＝(P∧Q)∨(ØP∧Q∧R)
＝(P∧Q∧ØR)∨(P∧Q∧R)∨(ØP∧Q∧R)
＝m6∨m7∨m3
＝å (3, 6, 7)
H = (P∨(Q∧R))∧(Q∨(ØP∧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)
＝m6∨m3∨m7
＝å (3, 6, 7)
G,H的主析取范式相同，所以G = H.
13. (1)
(2)R•S＝{(a, b),(c, d)},
R∪S＝{(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d)},
R－1＝{(a, a),(c, a),(c, b),(d, c)},
S－1•R－1＝{(b, a),(d, c)}.
四 证明题
1. 证明：{P→Q, R→S, P∨R}蕴涵Q∨S
(1) P∨R P
(2) ØR→P Q(1)
(3) P→Q P
(4) ØR→Q Q(2)(3)
(5) ØQ→R Q(4)
(6) R→S P
(7) ØQ→S Q(5)(6)
(8) Q∨S Q(7)
2. 证明：(A-B)-C = (A∩~B)∩~C
= A∩(~B∩~C)
= A∩~(B∪C)
= A-(B∪C)
3. 证明：{ØA∨B, ØC→ØB, C→D}蕴涵A→D
(1) A D(附加)
(2) ØA∨B P
(3) B Q(1)(2)
(4) ØC→ØB P
(5) B→C Q(4)
(6) C Q(3)(5)
(7) C→D P
(8) D Q(6)(7)
(9) A→D D(1)(8)
所以 {ØA∨B, ØC→ØB, C→D}蕴涵A→D.
3. 证明：A－(A∩B)
= A∩~(A∩B)
＝A∩(~A∪~B)
＝(A∩~A)∪(A∩~B)
＝Æ∪(A∩~B)
＝(A∩~B)
＝A－B
而 (A∪B)－B
= (A∪B)∩~B
= (A∩~B)∪(B∩~B)
= (A∩~B)∪Æ
= A－B
所以：A－(A∩B) = (A∪B)－B.
离散数学试题（A卷及答案）
一、（10分）某项工作需要派 A 、 B 、 C 和 D 4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？
(1)若 A 去，则 C 和 D 中要去1个人；
(2) B 和 C 不能都去；
(3)若 C 去，则 D 留下。
解 设 A ： A 去工作； B ： B 去工作； C ： C 去工作； D ： D 去工作。则根据题意应有： A ® C Å D ，Ø( B ∧ C )， C ®Ø D 必须同时成立。因此
( A ® C Å D )∧Ø( B ∧ C )∧( C ®Ø D )
Û(Ø A ∨( C ∧Ø D )∨(Ø C ∧ D ))∧(Ø B ∨Ø C )∧(Ø C ∨Ø D )
Û(Ø A ∨( C ∧Ø D )∨(Ø C ∧ D ))∧((Ø B ∧Ø C )∨(Ø B ∧Ø D )∨Ø C ∨(Ø C ∧Ø D ))
Û(Ø A ∧Ø B ∧Ø C )∨(Ø A ∧Ø B ∧Ø D )∨(Ø A ∧Ø C )∨(Ø A ∧Ø C ∧Ø D )
∨( C ∧Ø D ∧Ø B ∧Ø C )∨( C ∧Ø D ∧Ø B ∧Ø D )∨( C ∧Ø D ∧Ø C )∨( C ∧Ø D ∧Ø C ∧Ø D )
∨(Ø C ∧ D ∧Ø B ∧Ø C )∨(Ø C ∧ D ∧Ø B ∧Ø D )∨(Ø C ∧ D ∧Ø C )∨(Ø C ∧ D ∧Ø C ∧Ø D )
ÛF∨F∨(Ø A ∧Ø C )∨F∨F∨( C ∧Ø D ∧Ø B )∨F∨F∨(Ø C ∧ D ∧Ø B )∨F∨(Ø C ∧ D )∨F
Û(Ø A ∧Ø C )∨(Ø B ∧ C ∧Ø D )∨(Ø C ∧ D ∧Ø B )∨(Ø C ∧ D )
Û(Ø A ∧Ø C )∨(Ø B ∧ C ∧Ø D )∨(Ø C ∧ D )
ÛT
故有三种派法： B ∧ D ， A ∧ C ， A ∧ D 。
二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。
解：论域：所有人的集合。
(
)：
是专家；
(
)：
是工人；
(
)：
是青年人；则推理化形式为：
(
(
)∧
(
))，
(
)
(
(
)∧
(
))
下面给出证明：
(1)
(
) P
(2)
( c ) T(1)，ES
(3)
(
(
)∧
(
)) P
(4)
( c )∧
( c ) T(3)，US
(5)
( c ) T(4)，I
(6)
( c )∧
( c ) T(2)(5)，I
(7)
(
(
)∧
(
)) T(6) ，EG
三、（10分）设 A 、 B 和 C 是三个集合，则 A Ì B ÞØ( B Ì A )。
证明： A Ì B Û" x ( x ∈ A → x ∈ B )∧$ x ( x ∈ B ∧ x Ï A )Û" x ( x Ï A ∨ x ∈ B )∧$ x ( x ∈ B ∧ x Ï A )
ÛØ$ x ( x ∈ A ∧ x Ï B )∧Ø" x ( x Ï B ∨ x ∈ A )ÞØ$ x ( x ∈ A ∧ x Ï B )∨Ø" x ( x ∈ A ∨ x Ï B )
ÛØ($ x ( x ∈ A ∧ x Ï B )∧" x ( x ∈ A ∨ x Ï B ))ÛØ($ x ( x ∈ A ∧ x Ï B )∧" x ( x ∈ B → x ∈ A ))
ÛØ( B Ì A )。
四、（15分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。
解 r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>}
s(R)＝R∪R－1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>}
R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}
R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>}
R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2
t(R)＝
Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，5>}。
五、（10分） R是非空集合A上的二元关系，若R是对称的，则r(R)和t(R)是对称的。
证明 对任意的x、y∈A，若xr(R)y，则由r(R)＝R∪IA得，xRy或xIAy。因R与IA对称，所以有yRx或yIAx，于是yr(R)x。所以r(R)是对称的。
下证对任意正整数n，Rn对称。
因R对称，则有xR2yÛ$z(xRz∧zRy)Û$z(zRx∧yRz)ÛyR2x，所以R2对称。若
对称，则x
yÛ$z(x
z∧zRy)Û$z(z
x∧yRz)Ûy
x，所以
对称。因此，对任意正整数n，
对称。
对任意的x、y∈A，若xt(R)y，则存在m使得xRmy，于是有yRmx，即有yt(R)x。因此，t(R)是对称的。
六、（10分）若 f ： A → B 是双射，则 f －1： B → A 是双射。
证明 因为 f ： A → B 是双射，则 f －1是 B 到 A 的函数。下证 f －1是双射。
对任意 x ∈ A ，必存在 y ∈ B 使 f ( x) ＝ y ，从而 f －1( y )＝ x ，所以 f －1是满射。
对任意的 y 1、 y 2∈ B ，若 f －1( y 1)＝ f －1( y 2)＝ x ，则 f ( x) ＝ y 1， f ( x) ＝ y 2。因为 f ： A→B 是函数，则 y 1＝ y 2。所以 f －1是单射。
综上可得， f －1： B → A 是双射。
七、（10分）设<S，*>是一个半群，如果S是有限集，则必存在a∈S，使得a*a＝a。
证明 因为<S，*>是一个半群，对任意的b∈S，由*的封闭性可知，b2＝b*b∈S，b3＝b2*b∈S，…，bn∈S，…。
因为S是有限集，所以必存在j＞i，使得
＝
。令p＝j－i，则
＝
*
。所以对q≥i，有
＝
*
。
因为p≥1，所以总可找到k≥1，使得kp≥i。对于
∈S，有
＝
*
＝
*(
*
)＝…＝
*
。
令a＝，则a∈S且a*a＝a。
八、（20分）（1）若G是连通的平面图，且G的每个面的次数至少为l(l≥3)，则G的边数m与结点数n有如下关系：
m≤
(n－2)。
证明 设G有r个面，则2m＝
≥lr。由欧拉公式得，n－m＋r＝2。于是， m≤
(n－2)。
（2）设平面图G＝<V，E，F>是自对偶图，则| E|＝2(|V|－1)。
证明 设G*＝<V*，E*>是连通平面图G＝<V，E，F>的对偶图，则G*@ G，于是|F|＝|V*|＝|V|，将其代入欧拉公式|V|－|E|＋|F|＝2得，|E|＝2(|V|－1)。
离散数学试题（B卷及答案）
一、（10分）证明( P ∨ Q )∧( P ® R )∧( Q ® S )
S ∨ R
证明 因为 S ∨ R ÛØ R ® S ，所以，即要证( P ∨ Q )∧( P ® R )∧( Q ® S )
Ø R ® S 。
(1)Ø R 附加前提
(2) P ® R P
(3)Ø P T (1)(2)， I
(4) P ∨ Q P
(5) Q T (3)(4)， I
(6) Q ® S P
(7) S T (5)(6)， I
(8)Ø R ® S CP
(9) S ∨ R T (8)， E
二、（15分）根据推理理论证明：每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所作为，所以，一定有些考生是聪明的。
设 P ( e )： e 是考生， Q ( e )： e 将有所作为， A ( e )： e 是勤奋的， B ( e )： e 是聪明的，个体域：人的集合，则命题可符号化为：" x ( P ( x )®( A ( x )∨ B ( x )))，" x ( A ( x )® Q ( x ))，Ø" x ( P ( x )® Q ( x ))
$ x ( P ( x )∧ B ( x ))。
(1)Ø" x ( P ( x )® Q ( x )) P
(2)Ø" x (Ø P ( x )∨ Q ( x )) T (1)， E
(3)$ x ( P ( x )∧Ø Q ( x )) T (2)， E
(4) P ( a )∧Ø Q ( a ) T (3)， ES
(5) P ( a ) T (4)， I
(6)Ø Q ( a ) T (4)， I
(7)" x ( P ( x )®( A ( x )∨ B ( x )) P
(8) P ( a )®( A ( a )∨ B ( a )) T (7)， US
(9) A ( a )∨ B ( a ) T (8)(5)， I
(10)" x ( A ( x )® Q ( x )) P
(11) A ( a )® Q ( a ) T (10)， US
(12)Ø A ( a ) T (11)(6)， I
(13) B ( a ) T (12)(9)， I
(14) P ( a )∧ B ( a ) T (5)(13)， I
(15)$ x ( P ( x )∧ B ( x )) T (14)， EG
三、（10分）某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。
解 设 A 、 B 、 C 分别表示会打排球、网球和篮球的学生集合。则：
| A |＝12，| B |＝6，| C |＝14，| A ∩ C |＝6，| B ∩ C |＝5，| A ∩ B ∩ C |＝2，|( A ∪ C )∩ B |＝6。
因为|( A ∪ C )∩ B |＝( A ∩ B )∪( B ∩ C )|＝|( A ∩ B )|＋|( B ∩ C )|－| A ∩ B ∩ C |＝|( A ∩ B )|＋5－2＝6，所以|( A ∩ B )|＝3。于是| A ∪ B ∪ C |＝12＋6＋14－6－5－3＋2＝20，
＝25－20＝5。故，不会打这三种球的共5人。
四、（10分）设 A 1、 A 2和 A 3是全集 U 的子集，则形如
Ai ¢( Ai ¢为 Ai 或
)的集合称为由 A 1、 A 2和 A 3产生的小项。试证由 A 1、 A 2和 A 3所产生的所有非空小项的集合构成全集 U 的一个划分。
证明 小项共8个，设有 r 个非空小项 s 1、 s 2、…、 sr ( r ≤8)。
对任意的 a ∈ U ，则 a ∈ A i或 a ∈
，两者必有一个成立，取 A i¢为包含元素 a 的 A i或
，则 a ∈
Ai ¢，即有 a ∈
si ，于是 U Í
si 。又显然有
si Í U ，所以 U ＝
si 。
任取两个非空小项 sp 和 sq ，若 sp ≠ sq ，则必存在某个 Ai 和
分别出现在 sp 和 sq 中，于是 sp ∩ sq ＝Æ。
综上可知，{ s 1， s 2，…， sr }是 U 的一个划分。
五、（15分）设 R 是 A 上的二元关系，则： R 是传递的Û R * R Í R 。
证明 (5)若 R 是传递的，则< x ， y >∈ R * R Þ$ z ( xRz ∧ zSy )Þ xRc ∧ cSy ，由 R 是传递的得 xRy ，即有< x ， y >∈ R ，所以 R * R Í R 。
反之，若 R * R Í R ，则对任意的 x 、 y 、 z ∈ A ，如果 xRz 且 zRy ，则< x ， y >∈ R * R ，于是有< x ， y >∈ R ，即有 xRy ，所以 R 是传递的。
六、（15分）若 G 为连通平面图，则 n － m ＋ r ＝2，其中， n 、 m 、 r 分别为 G 的结点数、边数和面数。
证明 对 G 的边数 m 作归纳法。
当 m ＝0时，由于 G 是连通图，所以 G 为平凡图，此时 n ＝1， r ＝1，结论自然成立。
假设对边数小于 m 的连通平面图结论成立。下面考虑连通平面图 G 的边数为 m 的情况。
设 e 是 G 的一条边，从 G 中删去 e 后得到的图记为 G ¢，并设其结点数、边数和面数分别为 n ¢、 m ¢和 r ¢。对 e 分为下列情况来讨论：
若 e 为割边，则 G ¢有两个连通分支 G 1和 G 2。 Gi 的结点数、边数和面数分别为 ni 、 mi 和 ri 。显然 n 1＋ n 2＝ n ¢＝ n ， m 1＋ m 2＝ m ¢＝ m －1， r 1＋ r 2＝ r ¢＋1＝ r ＋1。由归纳假设有 n 1－ m 1＋ r 1＝2， n 2－ m 2＋ r 2＝2，从而( n 1＋ n 2)－( m 1＋ m 2)＋( r 1＋ r 2)＝4， n －( m －1)＋( r ＋1)＝4，即 n － m ＋ r ＝2。
若 e 不为割边，则 n ¢＝ n ， m ¢＝ m －1， r ¢＝ r －1，由归纳假设有 n ¢－ m ¢＋ r ¢＝2，从而 n －( m －1)＋ r －1＝2，即 n － m ＋ r ＝2。
由数学归纳法知，结论成立。
七、（10分）设函数 g ： A → B ， f ： B → C ，则：
(1) f o g 是 A 到 C 的函数；
(2)对任意的 x ∈ A ，有 f o g ( x )＝ f ( g ( x ))。
证明 (1)对任意的 x ∈ A ，因为 g ： A → B 是函数，则存在 y ∈ B 使< x ， y >∈ g 。对于 y ∈ B ，因 f ： B → C 是函数，则存在 z ∈ C 使< y ， z >∈ f 。根据复合关系的定义，由< x ， y >∈ g 和< y ， z >∈ f 得< x ， z >∈ g * f ，即< x ， z >∈ f o g 。所以 Df o g ＝ A 。
对任意的 x ∈ A ，若存在 y 1、 y 2∈ C ，使得< x ， y 1>、< x ， y 2>∈ f o g ＝ g * f ，则存在 t 1使得< x ， t 1>∈ g 且< t 1， y 1>∈ f ，存在 t 2使得< x ， t 2>∈ g 且< t 2， y 2>∈ f 。因为 g ： A → B 是函数，则 t 1＝ t 2。又因 f ： B → C 是函数，则 y 1＝ y 2。所以 A 中的每个元素对应 C 中惟一的元素。
综上可知， f o g 是 A 到 C 的函数。
(2)对任意的 x ∈ A ，由 g ： A → B 是函数，有< x ， g ( x )>∈ g 且 g ( x )∈ B ，又由 f ： B → C 是函数，得< g ( x )， f ( g ( x ))>∈ f ，于是< x ， f ( g ( x ))>∈ g * f ＝ f o g 。又因 f o g 是 A 到 C 的函数，则可写为 f o g ( x )＝ f ( g ( x ))。
八、（15分）设< H ，*>是< G ，*>的子群，定义 R ＝{< a ， b >| a 、 b ∈ G 且 a －1* b ∈ H }，则 R 是 G 中的一个等价关系，且[ a ] R ＝ aH 。
证明 对于任意 a ∈ G ，必有 a －1∈ G 使得 a －1* a ＝ e ∈ H ，所以< a ， a >∈ R 。
若< a ， b >∈ R ，则 a －1* b ∈ H 。因为 H 是 G 的子群，故( a －1* b )－1＝ b －1* a ∈ H 。所以< b ， a >∈ R 。
若< a ， b >∈ R ，< b ， c >∈ R ，则 a －1* b ∈ H ， b －1* c ∈ H 。因为 H 是 G 的子群，所以( a －1* b )*( b －1* c )＝ a －1* c ∈ H ，故< a ， c >∈ R 。
综上可得， R 是 G 中的一个等价关系。
对于任意的 b ∈[ a ] R ，有< a ， b >∈ R ， a －1* b ∈ H ，则存在 h ∈ H 使得 a －1* b ＝ h ， b ＝ a * h ，于是 b ∈ aH ，[ a ] R Í aH 。对任意的 b ∈ aH ，存在 h ∈ H 使得 b ＝ a * h ， a －1* b ＝ h ∈ H ，< a ， b >∈ R， 故 aH Í[ a ] R 。所以，[ a ] R ＝ aH 。