离散数学考试（试题及答案）一、（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∧DF∨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>}＝R2t(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，*>是一个半群，如果S是有限集，则必存在a∈S，使得a*a＝a。
证明 因为<S，*>是一个半群，对任意的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＝<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)∧(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(5)Q T(3)(4)，I(6)QS P(7)S T(5)(6)，I(8)RS 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的子集，则形如A i(A i为A i或)的集合称为由A1、A2和A3产生的小项。
试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。
证明小项共8个，设有r个非空小项s1、s2、…、s r(r≤8)。
对任意的a∈U，则a∈A i或a∈，两者必有一个成立，取A i为包含元素a的A i或，则a∈A i，即有a∈s i，于是Us i。
又显然有s i U，所以U＝s i。
任取两个非空小项s p和s q，若s p≠s q，则必存在某个A i和分别出现在s p 和s q中，于是s p∩s q＝。
综上可知，{s1，s2，…，s r}是U的一个划分。
五、（15分）设R是A上的二元关系，则：R是传递的R*RR。
证明 (5)若R是传递的，则<x，y>∈R*Rz(xRz∧zSy)xRc∧cSy，由R 是传递的得xRy，即有<x，y>∈R，所以R*RR。
反之，若R*RR，则对任意的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。
G i的结点数、边数和面数分别为n i、m i和r i。
显然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。