loading离散数学考试（试题及答案）
一、（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)?xY(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)。
四、（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＝{<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)＝?Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，
i?1?4
2
32
－1
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，R对称。
因R对称，则有xRy??z(xRz∧zRy)??z(zRx∧yRz)?yRx，所以R对称。若Rn对称，则xRn?1y??z(xRnz∧zRy)??z(zRnx∧yRz)?yRn?1x，所以Rn?1对称。因此，对任意正整数n，Rn对称。 对任意的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是满射。
对任意的y1、y2∈B，若f(y1)＝f(y2)＝x，则f(x)＝y1，f(x)＝y2。因为f：A→B是函数，则y1＝y2。所以f是单射。
综上可得，f：B→A是双射。
七、（10分）设
证明 因为
因为S是有限集，所以必存在j＞i，使得bi＝bj。令p＝j－i，则bj＝bp*bj。所以对q≥i，有bq＝bp*bq。
因为p≥1，所以总可找到k≥1，使得kp≥i。对于bkp∈S，有bkp＝bp*bkp＝bp*(bp*bkp)＝…＝
2
2
3
2
－1
－1
－1
－1
－1
－1
－1
－1
－1
m
m
2
2
2
n
bkp*bkp。
令a＝bkp，则a∈S且a*a＝a。
八、（20分）（1）若G是连通的平面图，且G的每个面的次数至少为l(l≥3)，则G的边数m与结点数n有如下关系：
m≤
rl(n－2)。 l?2l证明 设G有r个面，则2m＝2)。
?d(f)≥lr。由欧拉公式得，n－m＋r＝2。于是， m≤l?2(n－
ii?1（2）设平面图G＝
证明 设G＝
*
*
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