离散数学考试试题（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对称。若对称，则xy z(xz∧zRy) z(zx∧yRz) yx，所以对称。因此，对任意正整数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的一个划分。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议