离散数学试题及答案

一、填空题

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是满射
。

对任意的y1
、y2∈B，若f－1(y1)＝f－1(y2)＝x ，则f(x)＝y1
，f(x)＝y2。因为f：A→B是函数，则y1＝y2 。所以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分）设A1
、A2和A3是全集U的子集 ，则形如

Ai¢(Ai¢为Ai或

)的集合称为由A1、A2和A3产生的小项
。试证由A1 、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。

证明 小项共8个
，设有r个非空小项s1
、s2、… 、sr(r≤8) 。

对任意的a∈U，则a∈Ai或a∈

 ，两者必有一个成立
，取Ai¢为包含元素a的Ai或

，则a∈

Ai¢ ，即有a∈

si，于是UÍ

si
。又显然有

siÍU
，所以U＝

si。

任取两个非空小项sp和sq，若sp≠sq ，则必存在某个Ai和

分别出现在sp和sq中
，于是sp∩sq＝Æ 。

综上可知，{s1 ，s2
，…，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¢有两个连通分支G1和G2
。Gi的结点数 、边数和面数分别为ni
、mi和ri。显然n1＋n2＝n¢＝n
，m1＋m2＝m¢＝m－1，r1＋r2＝r¢＋1＝r＋1 。由归纳假设有n1－m1＋r1＝2 ，n2－m2＋r2＝2
，从而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝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)fog是A到C的函数；

(2)对任意的x∈A ，有fog(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>∈fog 。所以Dfog＝A
。

对任意的x∈A，若存在y1 、y2∈C
，使得<x，y1>
、<x ，y2>∈fog＝g*f
，则存在t1使得<x，t1>∈g且<t1 ， y1>∈f
，存在t2使得<x，t2>∈g且<t2 ，y2>∈f。因为g：A→B是函数
，则t1＝t2 。又因f：B→C是函数，则y1＝y2
。所以A中的每个元素对应C中惟一的元素。

综上可知 ，fog是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＝fog
。又因fog是A到C的函数，则可写为fog(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 。