狼孩图片-四叶草的折法

离散数学考试（试题及答案）

一、（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分）在谓词逻辑中构造下面推理的证明 ：某学术会议的每个成员都是专家并且是工人，有
些成员是青年人，所以，有些成员是青年专家。 解：论域：所有人的集合。
S
(
x
)：
x
是专家；W
(
x
)：
x
是工人；
Y
(
x
)：
x
是青年人；则推理化
形式为：

x
(
S
(
x
)∧
W
(
x
))，

xY
(
x
)

x
(
S
(
x)∧
Y
(
x
))
下面给出证明：
(1)

x
Y
(
x
) P
(2)
Y
(c) T(1)，ES
(3)

x
(
S
(
x
) ∧
W
(
x
)) P
(4)
S
( c)∧
W
( c) T(3)，US
(5)
S
( c) T(4)，I
(6)
S
( c)∧
Y
(c) T(2)(5)，I
(7)

x
(
S
(
x
)∧
Y
(
x
)) 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)

1

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)。
四、（1 5分）设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∪I
A
＝{<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＝ {<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，< 4，3>}
R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}
R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>}
R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝ R
t(R)＝

R
i
＝{<2，1>，<2，5>，<2，4>， <3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，
i1

42
3
2
－1
5>}。
五、（10分）R是非空集合A上的二元关系，若R是对称的，则r(R)和t(R)是对称的。
证明 对任意的x、y∈A，若xr(R)y，则由r(R)＝R∪I
A
得，xRy 或xI
A
y。因R与I
A
对称，所以有
yRx或yI
Ax，于是yr(R)x。所以r(R)是对称的。
下证对任意正整数n，R对称。
因R 对称，则有xRyz(xRz∧zRy)z(zRx∧yRz)yRx，所以R对称。若
R< br>n
对称，则
x
R
n1
yz(x
R
n< br>z∧zRy)z(z
R
n
x∧yRz)y
R
n1x，所以
R
n1
对称。因此，对任意正整数n，
R
n
对称。
对任意的x、y∈A，若xt(R)y，则存在m使得xRy，于是有yRx，即有yt(R) x。因此，t(R)是对称的。
六、（10分）若f：A→B是双射，则f：B→A是双射。
证明 因为f：A→B是双射，则f是B到A的函数。下证f是双射。
对任意x∈A，必存在y∈B使f(x)＝y，从而f(y)＝x，所以f是满射。
对任意的 y
1
、y
2
∈B，若f(y
1
)＝f(y
2
)＝x，则f(x)＝y
1
，f(x)＝y
2
。因为f：A→B是函数，则 y
1
＝y
2
。
所以f是单射。
综上可得，f：B→A是双射。
七、（10分）设是一个半群，如果S是有限集，则必存在a∈S，使得a*a＝a。
证明 因为是一个半群，对任意的b∈S，由*的封闭性可知，b＝b*b∈S，b＝b* b∈S，…，
b
n
∈S，…。
因为S是有限集，所以必存在j＞i，使得< br>b
i
＝
b
j
。令p＝j－i，则
b
j
＝
b
p
*
b
j
。所以对q≥i，有
b
q
＝
b
p
*
b
q
。
因为p≥1，所以总可 找到k≥1，使得kp≥i。对于
b
kp
∈S，有
b
kp
＝
b
p
*
b
kp
＝
b
p
*(
b
p
*
b
kp
)＝…＝

2
232< br>－1
－1
－1－1
－1－1
－1－1
－1
mm
222
n

b
kp
*
b
kp
。
令a＝
b
kp
，则a∈S且a*a＝a。

八、（20分） （1）若G是连通的平面图，且G的每个面的次数至少为l(l≥3)，则G的边数m与结
点数n有如下 关系：
m≤
r
l
(n－2)。
l2
l
证明 设G有r个面，则2m＝
2)。

d(f)
≥lr。由欧拉公式得，n
－
m＋r＝2。于是， m≤
l2
(n－
i
i1
（2）设平面图G＝是自对偶 图，则| E|＝2(|V|－1)。
证明 设G＝是连通平面图G＝的对偶图，则G G，于是|F|＝|V*|＝|V| ，
将其代入欧拉公式|V|－|E|＋|F|＝2得，|E|＝2(|V|－1)。
**
















3

离散数学考试试题（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个会打网球的人都会打另外一种球， 求不会打这三种球的
人数。

4

解 设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，
|ABC|
＝25－20＝5。故，不会打这三种球的
共5人。
四、（10分）设A
1
、A
2
和A
3
是全集U的子集，则 形如

A
i
(A
i
为A
i
或
A
i
)的集合称为由A
1
、A
2
和
i1
3
A
3
产生的小项。试证由A
1
、A
2
和A
3
所产生的所有非空小项的集合构成全集U的一个划分。
证明 小项共8个，设有r个非 空小项s
1
、s
2
、…、s
r
(r≤8)。
对任 意的a∈U，则a∈A
i
或a∈
A
i
，两者必有一个成立，取Ai
为包含元素a的A
i
或
A
i
，则a∈
< br>A
i
，
i1
3
即有a∈

s
i
，于是U

s
i
。又显然有

s
iU，所以U＝

s
i
。
i1i1i1i1
rrrr
任取两个非空小项s
p
和s
q
，若s
p
≠ s
q
，则必存在某个A
i
和
A
i
分别出现在sp
和s
q
中，于是s
p
∩s
q
＝。
综上可知，{s
1
，s
2
，…，s
r
}是U的一个划分。
五、（15分）设R是A上的二元关系，则：R是传递的R*RR。
证明 (5)若R 是传递的，则∈R*Rz(xRz∧zSy)xRc∧cSy，由R是传递的得xRy，即有< x，
y>∈R，所以R*RR。
反之，若R*RR，则对任意的x、y、z∈A，如果x Rz且zRy，则∈R*R，于是有∈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
。G
i
的结点数、边数和面数分别为n
i
、m
i
和 r
i
。显然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g是A到C的函数；
(2)对任意的x∈A，有fg(x)＝f(g(x))。
证明 (1)对任意的x∈A ，因为g：A→B是函数，则存在y∈B使∈g。对于y∈B，因f：B→C

5

是函数，则存在z∈C使∈f。根据复合关系的定义，由∈g和< y，z>∈f得∈g*f，即
∈fg。所以D
f

g
＝A。
对任意的x∈A，若存在y
1
、y
2
∈C，使得< x，y
1
>、2
>∈fg＝g*f，则存在t
1
使得1
>∈g且
1
， y
1
>∈f， 存在t
2
使得2
>∈g且2
，y
2< br>>∈f。因为g：A→B是函数，则t
1
＝t
2
。又因f：B→C是< br>函数，则y
1
＝y
2
。所以A中的每个元素对应C中惟一的元素。
综上可知，fg是A到C的函数。
(2)对任意的x∈A，由g：A→B是函数，有∈g且g(x)∈B，又由f：B→C是函数，得f(g(x))>∈f，于是 ∈g*f＝fg。又因fg是A到C的函数，则可写为fg(x)＝f(g(x) )。
八、（15分）设是的子群，定义R＝{|a、b∈G且a1
*b∈H}，则R是G中的
－
一个等价关系，且[a]
R
＝a H。
证明 对于任意a∈G，必有a
1
∈G使得a
1
*a＝e∈ H，所以∈R。
－－
若∈R，则a
1
*b∈H。因为 H是G的子群，故(a
1
*b)
1
＝b
1
*a∈H。所以< b，a>∈R。
－－－－
若∈R，∈R，则a
1
*b ∈H，b
1
*c∈H。因为H是G的子群，所以(a
1
*b)*(b
1
*c)＝a
－－－－
－
1
*c∈H，故∈R。
综上可得，R是G中的一个等价关系。
对于任意的b∈[a]
R
，有∈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，∈R
，
故aH[a]
R< br>。所以，[a]
R
－
＝aH。



6