离散数学试题及答案

由天下分享时间：2025/3/10 18:09:15 加入收藏我要投稿点赞

(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，|A?B?C|＝25－20＝5。故，不会打这三种球的共5人。

四、（10分）设A1、A2和A3是全集U的子集，则形如?Ai?(Ai?为Ai或Ai)的集合称为由A1、

i?13A2和A3产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。

证明小项共8个，设有r个非空小项s1、s2、…、sr(r≤8)。

对任意的a∈U，则a∈Ai或a∈Ai，两者必有一个成立，取Ai?为包含元素a的Ai或Ai，则a∈

i?1?3Ai?，即有a∈

i?1?si，于是

rU?

i?1?si。又显然有?si?U，所以

i?1rrU＝

i?1?si。

r任取两个非空小项sp和sq，若sp≠sq，则必存在某个Ai和Ai分别出现在sp和sq中，于是sp

∩sq＝?。

综上可知，{s1，s2，…，sr}是U的一个划分。

五、（15分）设R是A上的二元关系，则：R是传递的?R*R?R。

证明 (5)若R是传递的，则∈R*R??z(xRz∧zSy)?xRc∧cSy，由R是传递的得xRy，即有∈R，所以R*R?R。

反之，若R*R?R，则对任意的x、y、z∈A，如果xRz且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分为下列情况来讨论：

16 / 17第 16 页共 17 页

若e为割边，则G?有两个连通分支G1和G2。Gi的结点数、边数和面数分别为ni、mi和ri。显然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。

若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是函数，则存在z∈C使∈f。根据复合关系的定义，由∈g和∈f得∈g*f，即∈f?g。所以Df?g＝A。

对任意的x∈A，若存在y1、y2∈C，使得、∈f?g＝g*f，则存在t1使得∈g且∈f，存在t2使得∈g且∈f。因为g：A→B是函数，则t1＝t2。又因f：B→C是函数，则y1＝y2。所以A中的每个元素对应C中惟一的元素。

综上可知，f?g是A到C的函数。

(2)对任意的x∈A，由g：A→B是函数，有∈g且g(x)∈B，又由f：B→C是函数，得∈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＝aH。

证明对于任意a∈G，必有a1∈G使得a1*a＝e∈H，所以∈R。

若∈R，则a1*b∈H。因为H是G的子群，故(a1*b)1＝b1*a∈H。所以∈R。若∈R，∈R，则a1*b∈H，b1*c∈H。因为H是G的子群，所以(a1*b)*(b

－