离散数学考试（试题及答案）
一、（10分）某项工作需要派A、B、C和D4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？
(1)若A去，则C和D中要去1个人；
(2)B和C不能都去；
(3)若C去，则D留下。
解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此
(ACD)∧(B∧C)∧(CD)
(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
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是三个集合，则AB(BA)。
证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA) x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB)
(x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A))
(BA)。
四、（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∪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－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)＝R i＝{<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∪I A得，xRy
或xI A y。因R与I A对称，所以有yRx或yI A x，于是yr(R)x。所以r(R)是对称的。
下证对任意正整数n，R n对称。
因R对称，则有xR2yz(xRz∧zRy)z(zRx∧yRz)yR2x，所以R2对称。若对称，则xyz(xz∧zRy)z(zx∧yRz)yx，所以对称。因此，对任意正整
数n，对称。
对任意的x、y∈A，若xt(R)y，则存在m使得xR m y，于是有yR m x，即
有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是有限集，则必存
在a∈S，使得a*a＝a。
证明 因为是一个半群，对任意的b∈S，由*的封闭性可知，b2＝b*b∈S，b3＝b2*b∈S，…，b n∈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＝是自对偶图，则| E|＝2(|V|－1)。
证明 设G*＝是连通平面图G＝的对偶图，
则G*G，于是|F|＝|V*|＝|V|，将其代入欧拉公式|V|－|E|＋|F|＝2得，|E|＝2(|V|－1)。
离散数学考试试题（B卷及答案）
一、（10分）证明(P∨Q)∧(PR)∧(QS)S∨R
证明因为S∨RRS，所以，即要证(P∨Q)∧(PR)∧(QS)RS。
(1)R附加前提
(2)PR P
(3)P T(1)(2)，I
(4)P∨Q P
