离散数学模拟题一套及答案

离散数学考试（试题及答案）

一、（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 )) ，∃x Y (x ) ∃x (S (x ) ∧Y (x ))

下面给出证明：

(1)∃x Y (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 )

⇔⌝∃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 ＝{，，，，，}，求r (R ) 、s (R ) 和t (R ) 。

解 r (R ) ＝R ∪I A ＝{，，，，，，，，，，}

s (R ) ＝R ∪R ＝{，，，，，，，，} R ＝{，，，，，，}

R ＝{，，，，，，}

R ＝{，，，，，，}＝R

t (R ) ＝ R i ＝{，，，，，，，，，

i =1∞4232－1

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 对称。

因R 对称，则有xR y ⇔∃z (xRz ∧zRy ) ⇔∃z (zRx ∧yRz ) ⇔yR x ，所以R 对称。若R n 对称，则x R n +1y ⇔∃z (x R n z ∧zRy ) ⇔∃z (z R n x ∧yRz ) ⇔y R n +1x ，所以R n +1对称。因此，对任意正整数n ，R n 对称。 对任意的x 、y ∈A ，若xt (R ) y ，则存在m 使得xR y ，于是有yR x ，即有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 是满射。

对任意的y 1、y 2∈B ，若f (y 1) ＝f (y 2) ＝x ，则f (x) ＝y 1，f (x) ＝y 2。因为f ：A→B是函数，则y 1＝y 2。所以f 是单射。

综上可得，f ：B →A 是双射。

七、（10分）设是一个半群，如果S 是有限集，则必存在a ∈S ，使得a *a ＝a 。

证明 因为是一个半群，对任意的b ∈S ，由*的封闭性可知，b ＝b *b ∈S ，b ＝b *b ∈S ，…，b n ∈S ，…。

因为S 是有限集，所以必存在j ＞i ，使得b i ＝b j 。令p ＝j －i ，则b j ＝b p *b j 。所以对q ≥i ，有b q ＝b p *b q 。

因为p ≥1，所以总可找到k ≥1，使得kp ≥i 。对于b kp ∈S ，有b kp ＝b p *b kp ＝b p *(b p *b kp ) ＝…＝232－1－1－1－1－1－1－1－1－1m m 222n

b kp *b kp 。

令a ＝b kp ，则a ∈S 且a *a ＝a 。

八、（20分）（1）若G 是连通的平面图，且G 的每个面的次数至少为l (l ≥3) ，则G 的边数m 与结点数n 有如下关系：

m ≤

r l (n －2) 。 l -2l 证明 设G 有r 个面，则2m ＝

2) 。 ∑d (f ) ≥lr 。由欧拉公式得，n －m ＋r ＝2。于是， m ≤l -2(n －i i =1

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

四、（10分）设A 1、A 2和A 3是全集U 的子集，则形如 A i '(A i '为A i 或A i ) 的集合称为由A 1、A 2和

i =13

A 3产生的小项。试证由A 1、A 2和A 3所产生的所有非空小项的集合构成全集U 的一个划分。

证明 小项共8个，设有r 个非空小项s 1、s 2、…、s r (r ≤8) 。

对任意的a ∈U ，则a ∈A i 或a ∈A i ，两者必有一个成立，取A i '为包含元素a 的A i 或A i ，则a ∈ A i '，i =13即有a ∈ s i ，于是U ⊆ s i 。又显然有 s i ⊆U ，所以U ＝ s i 。

i =1i =1i =1i =1r r r r

任取两个非空小项s p 和s q ，若s p ≠s q ，则必存在某个A i 和A i 分别出现在s p 和s q 中，于是s p ∩s q ＝∅。 综上可知，{s 1，s 2，…，s r }是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 分为下列情况来讨论：

若e 为割边，则G '有两个连通分支G 1和G 2。G i 的结点数、边数和面数分别为n i 、m i 和r i 。显然n 1＋n 2＝n '＝n ，m 1＋m 2＝m '＝m －1，r 1＋r 2＝r '＋1＝r ＋1。由归纳假设有n 1－m 1＋r 1＝2，n 2－m 2＋r 2＝2，从而(n 1＋n 2) －(m 1＋m 2) ＋(r 1＋r 2) ＝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 。所以D f g ＝A 。

对任意的x ∈A ，若存在y 1、y 2∈C ，使得、∈f g ＝g *f ，则存在t 1使得∈g 且∈f ，存在t 2使得∈g 且∈f 。因为g ：A →B 是函数，则t 1＝t 2。又因f ：B →C 是函数，则y 1＝y 2。所以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 且a 1*b ∈H }，则R 是G 中的－

一个等价关系，且[a ]R ＝aH 。

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

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

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

－1*c ∈H ，故∈R 。

综上可得，R 是G 中的一个等价关系。

对于任意的b ∈[a ]R ，有∈R ，a 1*b ∈H ，则存在h ∈H 使得a 1*b ＝h ，b ＝a *h ，于是b ∈aH ，－－

[a ]R ⊆aH 。对任意的b ∈aH ，存在h ∈H 使得b ＝a *h ，a 1*b ＝h ∈H ，∈R ，故aH ⊆[a ]R 。所以，[a ]R －

＝aH 。