2020年电大离散数学(本)期末考试题库及答案

2020年电大离散数学（本）期末考试题库及答案

一、单项选择题

1．设P：a是偶数，Q：b是偶数。R：a + b是偶数，则命题“若a是偶数，b是偶数，则a + b 也是偶数”符号化为（D． P Q→R）。 2．表达式x（P（x，y）Q（z））3．设S1）中x的辖域是（P（x，y） Q（z））。 y（Q（x，y）→zQ（z）

,S2{},S3P({}),S4P()则命题为假的是（S2S4）。

4．设G是有n个结点的无向完全图，则G的边数（ 1/2 n（n-1））。 5．设G是连通平面图，有v个结点，e条边，r个面，则r=（ e-v+2）。 6．若集合A={1，{2}，{1，2}}，则下列表述正确的是( {1}A )．

7．已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为( 5 )．

018．设无向图G的邻接矩阵为11111110011则G的边数为( 7 )． 0000100110109．设集合A={a}，则A的幂集为({，{a}} )． 10．下列公式中 (AB  (AB) )为永真式． 11．若G是一个汉密尔顿图，则G一定是( 连通图 )．

12．集合A={1, 2, 3, 4}上的关系R={|x=y且x, yA}，则R的性质为（传递的 ）．

13．设集合A={1，2，3，4，5}，偏序关系是A上的整除关系，则偏序集上的元素5是集合A的（极大元 ）．

14．图G如图一所示，以下说法正确的是 ( {(a, d) ,(b, d)}是边割集 ) ．

16．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是(AB，且AB )．

图一

15．设A（x）：x是人，B（x）：x是工人，则命题“有人是工人”可符号化为（(x)(A(x)∧B(x)) ）． 17．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( （d）是强连通的 )．

0118．设图G的邻接矩阵为10011000011则G的边数为( 5 )． 00001001101019．无向简单图G是棵树，当且仅当(G连通且边数比结点数少1 )． 20．下列公式 ((P(QP))(P(PQ)) )为重言式． 21．若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是({a}A)． 22．设图G＝，vV，则下列结论成立的是 (

deg(v)2E ) ．

vV23．命题公式（P∨Q）→R的析取范式是 (（P∧Q）∨R ) 24．下列等价公式成立的为(P(QP) P(PQ) )．

25．设A={a, b}，B={1, 2}，R1，R2，R3是A到B的二元关系，且R1={, }，R2={, , }，R3={, }，则（ R2 ）不是从A到B的函数．

26．设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为 (无、2、无、2)． .

.

27．若集合A的元素个数为10，则其幂集的元素个数为（1024）．

28．如图一所示，以下说法正确的是 (e是割点)．图一

29．设完全图Kn有n个结点(n≥2)，m条边，当（ n为奇数）时，Kn中存在欧拉回路．

30．已知图G的邻接矩阵为

二、填空题（每小题3分，共15分）

，则G有（ 5点，7边 ）．

1．设A，B为任意命题公式，C为重言式，若A 2．命题公式（P→Q）P的主合取范式为

CBC，那么AB是 重言 式（重言式、矛盾式或可满足式）。

(PQ)(PQ) 。

3．设集合A={，{a}}，则P（A）= {,{},{{a}},{,{a}}} 。 4．设图G =〈V，E〉， G ′=〈V′，E′〉，若 V′=V,E′ E ,则G′是G的生成子图。 5．在平面G =〈V，E〉中，则

deg(r)= 2|E| ，其中r（i=1，2，…，r）是G的面。6．命题公式PP的真值是 假（或F，或0）

iri．

i17．若无向树T有5个结点，则T的边数为 4 ．

8．设正则m叉树的树叶数为t，分支数为i，则(m-1)i= t-1 ．

9．设集合A={1，2}上的关系R＝{<1, 1>,<1, 2>}，则在R中仅需加一个元素 <2, 1> ，就可使新得到的关系为对称的． 10．(x)(A(x)→B(x，z)∨C(y))中的自由变元有 z，y ．

11．若集合A={1，3，5，7}，B={2，4，6，8}，则A∩B= 空集（或） ．

12．设集合A={1，2，3}上的函数分别为：f={<1,2>,<2,1>,<3,3>,}，g={<1,3>,<2,2>,<3,2>,}，则复合函数gf = {<1, 2>, <2, 3>, <3, 2>,} ． 13．设G是一个图，结点集合为V，边集合为E，则G的结点度数之和为 2|E|（或“边数的两倍”） ． 14．无向连通图G的结点数为v，边数为e，则G当v与e满足 e=v-1 关系时是树． 15．设个体域D＝{1, 2, 3}， P(x)为“x小于2”，则谓词公式(x)P(x) 的真值为 假（或F，或0） ． 16．命题公式P(QP)的真值是

T （或1） ．

17．若图G=中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为 W|S| ．

18．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素 0 ，则该序列集合构成前缀码． 19．已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为 5 ． 20．(x)(P(x)→Q(x)∨R(x，y))中的自由变元为 R(x，y )中的y ． 21．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系，R{<2, 2>，<2, 3>，<3, 2>}，<3, 3> ．

22．设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v，e和r满足的关系式 v-e+r=2 ． 23．设G＝是有6个结点，边的连通图，则从G中删去 3 条边，可以确定图G的一棵生成树． 24．无向图G存在欧拉回路，当且仅当G连通且 所有结点的度数全为偶数 ． 25．设个体域D＝{1,2}，则谓词公式xA(x)消去量词后的等值式为 A(1)A(2) ． 26．设集合A＝{a，b}，那么集合A的幂集是 {,{a,b},{a},{b }} ．

27．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有 2 个．

28．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去 4 条边后使之变成树． .

{x,yxA且yB且x,yAB}则R的有序对集合为

.

29．设连通平面图G的结点数为5，边数为6，则面数为 3 ．

30．设个体域D＝{a, b}，则谓词公式(x)A(x)∧（x）B（x）消去量词后的等值式为 (A (a)∧A (b))∧(B（a）∨B（b）) ． 31. 设集合A={0，1 ，2} ，B={l ，2 ，3 ， 剖，R 是A到B 的二元关系，R= { |x∈A且y∈B且x， y∈A∩B} 则R的有序对集合为___{<1,1>,<1,2>,<2,1>,<2,2>}___

32. 设G是连通平面图，v， e ， r 分别表示G的结点数， 边数和面数， 则 v， e 和r 满足的关系式__v-e+r=2_____ 33.G=是有20个结点，25 条边的连通图,则从G中删去__6__条边，可以确定图G的一棵生成树. 34. 无向图G存在欧拉回路， 当且仅当G所有结点的度数全为偶数且_ 连通____ 35. 设个体域D={ 1, 2 } ， 则谓词公式 xA(x)消去量词后的等值式为__A(1)∧A(2)___

三、化简解答题

11．设集合A={1，2，3，4}，A上的二元关系R，R={〈1，1〉，〈1，4〉，〈2，2〉，〈2，3〉，〈3，2〉，〈3，3〉，〈4，1〉，〈4，4〉}，说明R是A上的等价关系。 解 从R的表达式知，三、逻辑公式翻译

1．将语句“今天上课．”翻译成命题公式．

设P：今天上课， 则命题公式为：P．

2．将语句“他去操场锻炼，仅当他有时间．”翻译成命题公式．

设 P：他去操场锻炼，Q：他有时间， 则命题公式为：P Q． 设P：他是学生， 则命题公式为： P．

4．将语句“如果明天不下雨，我们就去郊游．”翻译成命题公式．

设P：明天下雨，Q：我们就去郊游， 则命题公式为： P Q． 5．将语句“他不去学校．”翻译成命题公式．

设P：他去学校，  P．

6．将语句“他去旅游，仅当他有时间．”翻译成命题公式．

设 P：他去旅游，Q：他有时间， P Q． 7．将语句“所有的人都学习努力．”翻译成命题公式．

设P(x)：x是人，Q(x)：x学习努力， （x）(P(x)Q(x))． 8．将语句“如果你去了，那么他就不去．”翻译成命题公式．

设P：你去，Q：他去， PQ． 9．将语句“小王去旅游，小李也去旅游．”翻译成命题公式．

设P：小王去旅游，Q：小李去旅游， PQ． 10．将语句“所有人都去工作．”翻译成谓词公式．

设P(x)：x是人，Q(x)：x去工作， (x)(P(x)Q(x))．

11．将语句“如果所有人今天都去参加活动，则明天的会议取消．”翻译成命题公式．

设P：所有人今天都去参加活动，Q：明天的会议取消， P Q． 12．将语句“今天没有人来．” 翻译成命题公式．

设 P：今天有人来，  P．

13．将语句“有人去上课．” 翻译成谓词公式．

设P(x)：x是人，Q(x)：x去上课， (x)(P(x) Q(x))．

1 1. 将语句\"如果小李学习努力，那么他就会取得好成绩. \"翻译成命题公式.

设P：小李学习努力，Q:小李会取得好成绩，P→Q 12. 将语句\"小张学习努力,小王取得好成绩. \"翻译成命题公式.

设P：小张学习努力，Q:小王取得好成绩，P∧Q

四、判断说明题

1．设集合A={1，2}，B={3，4}，从A到B的关系为f={<1, 3>}，则f是A到B的函数．

错误． 因为A中元素2没有B中元素与之对应，故f不是A到B的函数． 2．设G是一个有4个结点10条边的连通图，则G为平面图． .

错误． 不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．” 3．将语句“他是学生．”翻译成命题公式．

xA,(x,x)R,即R具有自反性；

.

3．设N、R分别为自然数集与实数集，f：N→R，f (x)=x+6，则f是单射．

正确． 设x1，x2为自然数且x1x2，则有f(x1)= x1+6 x2+6= f(x2)，故f为单射．

4．下面的推理是否正确，试予以说明．

(1) （x）F（x）→G（x） 前提引入

(2) F（y）→G（y） US（1）． 错误．

（2）应为F（y）→G（x），换名时，约束变元与自由变元不能混淆． 5．如图二所示的图G存在一条欧拉回路．

图二

错误． 因为图G为中包含度数为奇数的结点．

6．设G是一个有6个结点14条边的连通图，则G为平面图．

错误． 不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．” 7．如果R1和R2是A上的自反关系，则R1∪R2是自反的．

正确． R1和R2是自反的，x A，  R1， R2，则  R1R2，所以R1∪R2是自反的． 8．如图二所示的图G存在一条欧拉回路．

v5 e v1

a v2 f h d g v4 n c

b 图二

v3 正确． 因为图G为连通的，且其中每个顶点的度数为偶数． 9．┐P∧（P→┐Q）∨P为永真式．

正确． ┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式， 如果P的值为真，则┐P∧（P→┐Q）∨P为真， 如果P的值为假，则┐P与P→┐Q为真，即┐P∧（P→┐Q）为真，

也即┐P∧（P→┐Q）∨P为真，

所以┐P∧（P→┐Q）∨P是永真式．

另种说明：

┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式，

只要其中一项为真，则整个公式为真． 可以看到，不论P的值为真或为假，┐P∧（P→┐Q）与P总有一个为真， 所以┐P∧（P→┐Q）∨P是永真式．

或用等价演算┐P∧（P→┐Q）∨PT

10．若偏序集的哈斯图如图一所示，则集合A的最大元为a，最小元不存在．

图一

正确． .

.

对于集合A的任意元素x，均有R（或xRa），所以a是集合A中的最大元．按照最小元的定义，在集合A中不存在最小元． 11. 如果R1和R2是A上的自反关系， 则R1∩R2是自反的。

正确，R1和R2，是自反的，x∈A,∈R1,∈R2,则 ∈R1∩R2，所以R1∩R2是自反的. 12. 如图二所示的图中存在一条欧拉回路.

图二

正确，因为图G为连通的，且其中每个顶点的度数为偶数。

五．计算题（每小题12分，本题共36分） 1．试求出（P∨Q）→（R∨Q）的析取范式．

（P∨Q）→（R∨Q） ┐(P∨Q)∨（R∨Q）

 (┐P∧┐Q)∨（R∨Q）

 (┐P∧┐Q)∨R∨Q（析取范式）

2．设A={{1}, 1, 2}，B={ 1, {2}}，试计算（1）（A∩B） （2）（A∪B） （3）A （A∩B）．

（1）（A∩B）={1} （2）（A∪B）={1, 2, {1}, {2}} （3） A（A∩B）={{1}, 1, 2}

3．图G=，其中V={ a, b, c, d }，E={ (a, b), (a, c) , (a, d), (b, c), (b, d), (c, d)}，对应边的权值依次为1、2、3、1、4及5，试 （1）画出G的图形； （2）写出G的邻接矩阵；

（3）求出G权最小的生成树及其权值．

（1）G的图形表示如图一所示：

a  1  b 2 3 4  d 5

1 图一

 c

01（2）邻接矩阵：11111011 101110 （3）最小的生成树如图二中的粗线所示：

a  1

3 2 4  d 5

 b 权为：1+1+3=5

1

图二

 c

4．画一棵带权为1, 2, 2, 3, 4的最优二叉树,计算它们的权．

最优二叉树如图三所示

12  7  3   5

   3 4 2 图三

  1 2

权为13+23+22+32+42=27

.

.

5．求（P∨Q）→R的析取范式与合取范式．

（P∨Q）→R  （P∨Q）∨R

 (P∧Q)∨R （析取范式）  (P∨R)∧(Q∨R) （合取范式）

6．设A={0，1，2，3}，R={|xA，yA且x+y<0}，S={|xA，yA且x+y2}，试求R，S，R•S，S ，r(R)． R=, S={<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<2,0>}

R•S=，

S -1= S，

-1

r(R)=IA={<0,0>,<1,1>,<2,2>,<3,3>}．

7．试求出（P∨Q）→R的析取范式，合取范式，主合取范式．

（P∨Q）→R┐(P∨Q)∨R (┐P∧┐Q)∨R（析取范式）  (┐P∨R)∧ (┐Q∨R)（合取范式）  ((┐P∨R)∨(Q∧┐Q))∧ ((┐Q∨R)∨(P∧┐P))  (┐P∨R∨Q)∧(┐P∨R∨┐Q)∧ (┐Q∨R∨P)

∧(┐Q∨R∨┐P)  (┐P∨Q∨R)∧(┐P∨┐Q∨R)∧ (P∨┐Q∨R) 8．设A={{a, b}, 1, 2}，B={ a, b, {1}, 1}，试计算

（1）（AB） （2）（A∪B） （3）（A∪B）（A∩B）．

（1）（AB）={{a, b}, 2} （2）（A∪B）={{a, b}, 1, 2, a, b, {1}} （3）（A∪B）（A∩B）={{a, b}, 2, a, b, {1}}

9．图G=，其中V={ a, b, c, d, e}，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) }，对应边的权值依次为2、1、2、3、6、1、4及5，试

（1）画出G的图形； （2）写出G的邻接矩阵；

（3）求出G权最小的生成树及其权值． （1）G的图形表示为：

（2）邻接矩阵：

01101110100110011

11011110（3）粗线表示最小的生成树，

权为7： .

.

10．设谓词公式x(P(x,y)变元．

（1）x量词的辖域为(P(x,y)zQ(y,x,z))yR(y,z)F(y)，试（1）写出量词的辖域； （2）指出该公式的自由变元和约束

zQ(y,x,z))，

z量词的辖域为Q(y,x,z),

y量词的辖域为R(y,z)． （2）自由变元为(P(x,y)zQ(y,x,z))与F(y)中的y，以及R(y,z)中的z

约束变元为x与Q(y,x,z)中的z，以及R(y,z)中的y． 11．设A={{1},{2},1,2}，B={1,2,{1,2}}，试计算

（1）（AB）； （2）（A∩B）； （3）A×B． （1）AB ={{1},{2}} （2）A∩B ={1,2}

（3）A×B={<{1},1>，<{1},2>，<{1},{1,2}>，<{2},1>，<{2},2>， <{2},{1,2}>，<1,1>，<1,2>，<1, {1,2}>，<2,1>，<2,2>, <2, {1,2}>}

12．设G=，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，试

（1）给出G的图形表示； （2）写出其邻接矩阵； （3）求出每个结点的度数； （4）画出其补图的图形．

（1）G的图形表示为：

（2）邻接矩阵：

00100（4）补图如下：

010001101011

11010110（3）v1，v2，v3，v4，v5结点的度数依次为1，2，4，3，2

13．设集合A={1，2，3，4}，R={|x, yA；|xy|=1或xy=0}，试 .

.

（1）写出R的有序对表示； （2）画出R的关系图；

（3）说明R满足自反性，不满足传递性．

（1）R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>} （2）关系图为

1  2 3  

4 

3）因为<1,1>,<2,2>,<3,3>,<4,4>均属于R，即A的每个元素构成的有序对均在R中，故R在A上是自反的。 因有<2,3>与<3,4>属于R，但<2,4>不属于R，所以R在A上不是传递的。

14．求PQR的析取范式，合取范式、主析取范式，主合取范式．

P→（R∨Q）

┐P∨(R∨Q)

 ┐P∨Q∨R （析取、合取、主合取范式）

(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R) ∨(┐P∧Q∧R) ∨(P∧┐Q∧┐R) ∨(P∧┐Q∧R) ∨(P∧Q∧┐R) ∨(P∧Q∧R) （主析取范式）

15．设图G=，V={ v1，v2，v3，v4，v5}，E={ (v1, v2)，(v1, v3)，(v2, v3)，(v2, v4)，(v3, v4)，(v3, v5)，(v4, v5) }，试

(1) 画出G的图形表示； (2) 写出其邻接矩阵； (3) 求出每个结点的度数； (4) 画出图G的补图的图形．

（1）关系图

v2   v5

  v4 v3

v1

01（2）邻接矩阵 10011000110 101111010110（3）deg(v1)=2

deg(v2)=3 deg(v3)=4 deg(v4)=3

deg(v5)=2 （4）补图

v1 v2   v5

 

v4 v3

16．设谓词公式x(A(x,y)∧ zB(x,y, z)) ∧ yC(y,z) 试 (1)写出量词的辖域; .

x量词的辖域为(A(x,y)∧ zB(x,y, z)),  z量词的辖域为B(x,y,z),  y量词的辖域为C(y,z) 自由变元为(A(x,y) ∧ zB(x,y, z))中的y,以及C(y,z)中的z. (2)指出该公式的自由变元和约束变元.

.

约束变元为(A(x,y) ∧ zB(x,y, z))中的x与B(x,y,z)中的z,以及C(y,z)中的y。 六、证明题

1．试证明：若R与S是集合A上的自反关系，则R∩S也是集合A上的自反关系．

证明：设xA，因为R自反，所以x R x，即< x, x>R；

又因为S自反，所以x R x，即< x, x >S． 即< x, x>R∩S 故R∩S自反．

2．试证明集合等式A (BC)=(AB)  (AC) ．

证明：设S= A (BC)，T=(AB)  (AC)，若x∈S，则x∈A或x∈BC，即 x∈A或x∈B 且 x∈A或x∈C． 也即x∈AB 且 x∈AC ，即 x∈T，所以ST．

反之，若x∈T，则x∈AB 且 x∈AC， 即x∈A或x∈B 且 x∈A或x∈C， 也即x∈A或x∈BC，即x∈S，所以TS．

因此T=S．

3．试证明集合等式A (BC)=(AB)  (AC)．

证明：设S=A∩(B∪C)，T=(A∩B)∪(A∩C)， 若x∈S，则x∈A且x∈B∪C，即 x∈A且x∈B 或 x∈A且x∈C， 也即x∈A∩B 或 x∈A∩C ，即 x∈T，所以ST． 反之，若x∈T，则x∈A∩B 或 x∈A∩C， 即x∈A且x∈B 或 x∈A且x∈C

也即x∈A且x∈B∪C，即x∈S，所以TS． 因此T=S．

4．试证明集合等式A (BC)=(AB)  (AC) ．

证明：设S= A (BC)，T=(AB)  (AC)，若x∈S，则x∈A或x∈BC，即 x∈A或x∈B 且 x∈A或x∈C． 也即x∈AB 且 x∈AC ，即 x∈T，所以ST． 反之，若x∈T，则x∈AB 且 x∈AC， 即x∈A或x∈B 且 x∈A或x∈C， 也即x∈A或x∈BC，即x∈S，所以TS．

因此T=S．

5．试证明（x）（P（x）∧R（x）） （x）P（x）∧（x）R（x）．

证明：

（1）（x）（P（x）∧R（x）） P

（2）P（a）∧R（a） ES(1) （3）P（a） T(2)I （4）（x）P（x） EG(3) （5）R（a） T(2)I （6）（x）R（x） EG(5) （7）（x）P（x）∧（x）R（x） T(5)(6)I

6．设m是一个取定的正整数，证明：在任取m＋1个整数中，至少有两个整数，它们的差是m的整数倍 证明 设

a1，a2，…，am1为任取的m＋1个整数，用m去除它们所得余数只能是0，1，…，m－1，由抽屉原理可知，a1，a2，…，am1as和

这m＋1个整数中至少存在两个数

at，它们被m除所得余数相同，因此

as和

at的差是m的整数倍。

7．已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C)

证明 ∵x A-（B∪C） x A∧x（B∪C） x A∧（xB∧xC） （x A∧xB）∧（x A∧xC） x（A-B）∧x（A-C） x（A-B）∩（A-C）∴A-（B∪C）=（A-B）∩（A-C）

8．（15分）设是半群，对A中任意元a和b，如a≠b必有a*b≠b*a，证明：

(1)对A中每个元a，有a*a＝a。 (2)对A中任意元a和b，有a*b*a＝a。 (3)对A中任意元a、b和c，有a*b*c＝a*c。 证明 由题意可知，若a*b＝b*a，则必有a＝b。 (1)由(a*a)*a＝a*(a*a)，所以a*a＝a。

(2)由a*(a*b*a)＝(a*a)*(b*a)＝a*b*(a*a)＝(a*b*a)*a，所以有a*b*a＝a。

(3)由(a*c)*(a*b*c)＝(a*c*a)*(b*c)＝a*(b*c)＝(a*b)*c＝(a*b)*(c*a*c)＝(a*b*c)*(a*c)，所以有a*b*c＝a*c。 13. 设A,B为任意集合，证明：(A-B)-C = A-(B∪C).

证明：(A-B)-C = (A∩~B)∩~C .

= A∩(~B∩~C)

.

= A∩~(B∪C) = A-(B∪C)

9．求命题公式(PQ)(P∨Q) 的主析取范式和主合取范式

解：(PQ)(P∨Q)(PQ)∨(P∨Q)(P∨Q)∨(P∨Q)(P∧Q)∨(P∨Q) (P∨P∨Q)∧(Q∨P∨Q)(P∨Q)M1m0∨m2∨m3

10．例5在边长为1的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超过1/8。 证明：把边长为1的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形（可能是退化的）面积不超过小正方形的一半，即1/8。

11. 试证明集合等式AU( B∩C)=(AUB) ∩(AUC).

证明：设S=AU(B∩C),T=(AUB) ∩(AUC),若x∈S,则x∈A或x∈B∩C， 即x∈A或x∈B且x∈A或x∈C,也即x∈AUB且x∈AUC, 即x∈T,所以sT.

反之，若x∈T,则x∈AUB且x∈AUC, 即x∈A或x∈B且x∈A或x∈C, 也即x∈A或x∈B∩C，即x∈S,所以TS. 因此T=S.

12. 利用形式演绎法证明：{P→Q, R→S, P∨R}蕴涵Q∨S。 证明：{P→Q, R→S, P∨R}蕴涵Q∨S

(1) P∨R (2) R→P (3) P→Q (4) R→Q (5) Q→R (6) R→S (7) Q→S (8) Q∨S P Q(1) P

Q(2)(3) Q(4) P

Q(5)(6) Q(7)

14.利用形式演绎法证明：{A∨B, C→B, C→D}蕴涵A→D。 证明：{A∨B, C→B, C→D}蕴涵A→D (1) A (3) B

D(附加) P Q(1)(2)

P Q(4) P D(1)(8)

(2) A∨B (4) C→B (5) B→C (6) C (8) D

(7) C→D (9) A→D

Q(3)(5) Q(6)(7)

所以 {A∨B, C→B, C→D}蕴涵A→D.

15. A, B为两个任意集合，求证：A－(A∩B) = (A∪B)－B . 证明：A－(A∩B) = A∩~(A∩B) ＝A∩(~A∪~B) ＝(A∩~A)∪(A∩~B) ＝∪(A∩~B) ＝(A∩~B) ＝A－B 而 (A∪B)－B = (A∪B)∩~B = (A∩~B)∪(B∩~B) = (A∩~B)∪

= A－B 所以：A－(A∩B) = (A∪B)－B. .

.

《离散数学》复习资料

一、单项选择题（每小题3分，本题共15分）

1．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( A )．

A． AB，且AB B．BA，且AB C．AB，且AB D．AB，且AB 2．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( D )．

图一 A．（a）是强连通的 B．（b）是强连通的

C．（c）是强连通的 D．（d）是强连通的 3．设图G的邻接矩阵为

0110010011

100000100101010则G的边数为( B )．

A．6 B．5 C．4 D．3

4．无向简单图G是棵树，当且仅当( A )．

A．G连通且边数比结点数少1 B．G连通且结点数比边数少1 C．G的边数比结点数少1 D．G中没有回路． 5．下列公式 ( C )为重言式．

A．PQPQ B．(Q(PQ)) (Q(PQ))

C．(P(QP))(P(PQ)) D．(P(PQ)) Q

6．设A={a, b}，B={1, 2}，R1，R2，R3是A到B的二元关系，且R1={, }，R2={, , }，R3={, }，则（ B ）不是从A到B的函数．

A．R1和R2 B．R2 C．R3 D．R1和R3 7．设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为 ( B )． A．8、2、8、2 B．无、2、无、2 C．6、2、6、2 D．8、1、6、1

8．若集合A的元素个数为10，则其幂集的元素个数为（ A ）． A．1024 B．10 C．100 D．1

9．设完全图Kn有n个结点(n≥2)，m条边，当（ C ）时，Kn中存在欧拉回路．

A．m为奇数 B．n为偶数 C．n为奇数 D．m为偶数 10．已知图G的邻接矩阵为

.

.

，

则G有（ D ）．

A．5点，8边 B．6点，7边 C．6点，8边 D．5点，7边

11.无向完全图K3的不同构的生成子图的个数为（ C ） (A) 6 (B) 5 (C) 4 (D) 3

12 n阶无向完全图Kn中的边数为（ A ）

(A)

n(n1)n(n1) (B) (C) n (D)n(n+1) 2213.在图G＝中，结点总度数与边数的关系是( C ) A deg(vi)=2E (B) deg(vi)=E C

deg(v)2E Ddeg(v)E

vVvV

二、填空题（每小题3分，本题共15分）

1．命题公式P(QP)的真值是 1 ．

2．若A={1,2}，R={|xA, yA, x+y<4}，则R的自反闭包为 {<1,1>,<2,2>,<1,2>,<2,1>} ． 3．已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为 5 ． 4．(x)(P(x)→Q(x)∨R(x，y))中的自由变元为 R(x，y )中的y ．

5．设集合A＝{a，b}，那么集合A的幂集是 {,{a,b},{a},{b }}

6．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有 2 个．

7．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去 4 条边后使之变成树． 8．无向图G存在欧拉回路，当且仅当G所有结点的度数全为偶数且 连通 9．设连通平面图G的结点数为5，边数为6，则面数为 3 ．

10．设个体域D＝{a, b}，则谓词公式(x)A(x)∧（x）B（x）消去量词后的等值式为 (A (a)∧A (b))∧(B（a）∨B（b）) ．

三、逻辑公式翻译（每小题6分，本题共12分）

1．将语句“雪是黑色的．”翻译成命题公式．

设P：雪是黑色的， （2分） 则命题公式为：P．

2．将语句“他不去学校．”翻译成命题公式．

解：设P：他去学校， 则命题公式为：  P．

3．将语句“小王是个学生，小李是个职员，而小张是个军人．”翻译成命题公式．

设P：小王是个学生，Q：小李是个职员，R：小张是个军人． （2分） 则命题公式为：P∧Q∧R．

4．将语句“如果所有人今天都去参加活动，则明天的会议取消．”翻译成命题公式． 解：设P：所有人今天都去参加活动，

.

.

Q：明天的会议取消， 则命题公式为： P Q．

5．将语句“他去旅游，仅当他有时间．”翻译成命题公式．

解：设 P：他去旅游，Q：他有时间，

则命题公式为： P Q．

6．将语句“41次列车下午五点开或者六点开．”翻译成命题公式．

解：设P：41次列车下午五点开，Q：41次列车下午六点开， （2分）

命题公式为：（P∧Q）∨（P∧Q） 7．将语句“小张学习努力，小王取得好成绩．”翻译成命题

设P：小张学习努力，Q：小王取得好成绩， （2分） 则命题公式为：PQ．

8．将语句“有人去上课．” 翻译成谓词公式．

解：设P(x)：x是人，Q(x)：x去上课， （1分） (x)(P(x) Q(x)

9．将语句“所有的人都学习努力．”翻译成命题公式． 解：设P(x)：x是人，Q(x)：x学习努力，

x）(P(x)Q(x))．

四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．

1．设集合A={1, 2, 3, 4}，B={2, 4, 6, 8}，，判断下列关系f是否构成函数f：AB，并说明理由．

(1) f={<1, 4>, <2, 2,>, <4, 6>, <1, 8>}； (2)f={<1, 6>, <3, 4>, <2, 2>}；

(3) f={<1, 8>, <2, 6>, <3, 4>, <4, 2,>}．

答：（1）不构成函数 因为3A，但f3没有定义，所以不构成函数 （2）不构成函数 因为4A，但f4没有定义，所以不构成函数 （3）满足。 因为任意xA，都有fxB且结果唯一。 2．若集合A = {1，2，3}上的二元关系R={<1, 1>，<2, 2>，<1, 2>}，则 (1) R是自反的关系； (2) R是对称的关系． 答：（1）错误 因为3，3R，所以R不是自反的

（2）错误 因为1，2R，但是2，1R，所以R不是对称的

3．如果R1和R2是A上的自反关系，判断结论：“R11、R1∪R2、R1∩R2是自反的” 是否成立？并说明理由．

答：成立 因为任意aA，有a,aR1,a,aR2 所以a,aR，a,aR11-

R2，a,aR1R2 R-11、R1∪R2、R1∩R2是自反的

a 

 c g

  h

 f 图一

b  d  e  4．若偏序集的哈斯图如图一所示， 则集合A的最大元为a，最小元不存在． 答：错误，集合A没有最大元，也没有最小元

其中a是极大元

.

.

5．若偏序集的哈斯图如图一所示，则集合A的最大元为a，最小元不存在．

解：正确

对于集合A的任意元素x，均有R（或xRa），所以a是集合A中的最大元．按照最小元的定义，在集合A中不存在最小元．

6．如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路．．

答：错误 如果图G是无向图，且图G是连通的，同时结点度数都是偶数 7．设G是一个连通平面图，且有6个结点11条边，则G有7个面．

答案：正确

定理，连通平面图G的结点数为v，边数是e，面数为r，则欧拉公式v-e+r=2成立 所以r=2-v+e=2-6+11=7

则G存在一条欧拉回路

8．设G是一个有6个结点14条边的连通图，则G为平面图．

解：错误，不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．” 9．命题公式P(PQ)P为永真式．

解：正确 因为，由真值表 P 0 0 1 1 Q 0 1 0 1 P 1 1 0 0 Q 1 0 1 0 PQ 1 1 1 0 P∧(P→Q)∨P 1 1 1 1 可知，该命题公式为永真式．

五．计算题（每小题12分，本题共36分）

1．设集合A={a, {b}, c}，B={{a}, c}，试计算

（1）（A∩B）； （2）（B  A）； （3）（A∩B）×B． 解（1）（A∩B）={c}；

（2）（B  A）={{a}}； （3）（A∩B）×B={, < c，c >}

2．设A={0，1，2，3，4，5，6}，R={|xA，yA且x+y<1}，S={|xA，yA且x+y3}，试求R，S，R•S，R-1，S-1，r(R)．

解：R={<0,0>} S={<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>} R•S={<0,0>,<0,1>,<0,2>,<0,3>}

R-1={<0,0>} S-1= S ） r(R)=IA．

3．图G=，其中V={ a, b, c, d, e}，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) }，对应边的权值依次为2、1、2、3、6、1、4及5，试

（1）画出G的图形； （2）写出G的邻接矩阵；

（3）求出G权最小的生成树及其权值．

.

.

解：（1）G的图形表示为：

（3分）

（2）邻接矩阵：

01101110100110011 （6分）

11011110（3）粗线表示最小的生成树，

权为7：

4．设图G=，V={ v1，v2，v3，v4，v5}，E={ (v1, v2)，(v1, v3)，(v2, v3)，(v2, v4)，(v3, v4)，(v3, v5)，(v4, v5) }，试

(1) 画出G的图形表示； (2) 求出每个结点的度数； (3) 画出图G的补图的图形． 解：（1）关系图

v 1 v2   v5

  v4 v3

（2）deg(v1)=2 deg(v2)=3 deg(v3)=4

deg(v4)=3 deg(v5)=2

（3）补图 v1 v5 v2

 

v3

 

v4

5．设集合A={1，2，3，4}，R={|x, yA；|xy|=1或xy=0}，试

（1）写出R的有序对表示； （2）画出R的关系图；

（3）说明R满足自反性，不满足传递性．

解:（1）R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>} （3分）

.

.

（2）关系图为

1  2 3   均属于R，即A的每个元素构成的有序对均在R中，故R在A上是自反的。 （3）因为<1,1>,<2,2>,<3,3>,<4,4>因有<2,3>与<3,4>属于R4 ，但 <2,4>不属于R，所以R在A上不是传递的。

6．设集合A={1, 2, 3}，R={<1，1>, <2，1>,<3，1>}，S={<1，2>, <2，2>}试计算 （1）R•S； （2）R 1； （3）r（R）．

解： （1）R•S =={<1，2>, <2，2>,<3，2>}； （4分）

（2）R 1={<1，1>, <1，2>, <1，3> }； （8分） （3）r（R）={<1，1>, <2，2> , <3，3>, <2，1>,<3，1>}

7、求出如图一所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树的权．解 用Kruskal算法求产生的最小生成树．步骤为： w(v1,v7)1 选e1v1v7 w(v3,v4)3 选e2v3v4 w(v2,v7)4 选e3v2v7 w(v3,v7)9 选e4v3v7 w(v4,v5)18 选e5v4v5

w(v1,v6)22 选e6v1v6 （6分）

最小生成树如图四所示：

图四

（9分）

最小生成树的权为：w(T)=22+1+4+9+3+18=57． （12分）

8．试画一棵带权为2, 3, 3, 4, 5,的最优二叉树,并计算该最优二叉树的权． 解： 最优二叉树如图二所示． 17



10  7  5     4 5 3   （10分）

2 3 图二

权为23+33+32+42+52=39

9．设谓词公式x(A(x,y)zB(x,y,z))yC(y,z)，试

.

.

（1）写出量词的辖域； （2）指出该公式的自由变元和约束变元．

（1）x量词的辖域为(A(x,y)zB(x,y,z))， （2分）

z量词的辖域为B(x,y,z), （4分） y量词的辖域为C(y,z)． （6分） （2）自由变元为(A(x,y)zB(x,y,z))中的y，以及C(y,z)中的z （9分） 约束变元为(A(x,y)zB(x,y,z))中的x与B(x,y,z)中的z，以及C(y,z)中的y． 10．设谓词公式(x)P(x,y)(z)Q(x,y,z)，试

（1）写出量词的辖域； （2）指出该公式的自由变元和约束变元． （1）x量词的辖域为P(x,y)， （3分）

z量词的辖域为Q(x,y,z), （6分） （2）自由变元为公式中的y与Q(x,y,z)中的x， （9分）

约束变元为P(x,y)的x与Q(x,y,z)z．

11．求命题公式(PQ)(RQ) 的主析取范式、主合取范式． 解：

P Q R PQ RQ 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 0 1 1 1 (PQ)(RQ) 1 1 1 1 0 1 1 1 极小项 PQR PQR PQR PQR PQR PQR PQR 极大项 PQR 主析取范式（极小项析取）： （PQR）（PQR）（PQR）（PQR）

（PQR）（PQR ）（PQR）

主合取范式（极大项合取）：PQR

12．求（P∨Q）→（R∨Q）的析取范式，合取范式．

解：（P∨Q）→（R∨Q）

（P∨Q）∨（R∨Q） （4分） (P∧Q)∨（R∨Q）

(P∨R∨Q)∧(Q∨R∨Q)

(P∨R∨Q) 析取、合取范式

六、证明题（本题共8分）

1．试证明集合等式A (BC)=(AB)  (AC)．

证明：设S=A∩(B∪C)，T=(A∩B)∪(A∩C)， 若x∈S，则x∈A且x∈B∪C，即 x∈A且x∈B 或 x∈A且x∈C， 也即x∈A∩B 或 x∈A∩C ，即 x∈T，所以ST． 反之，若x∈T，则x∈A∩B 或 x∈A∩C， 即x∈A且x∈B 或 x∈A且x∈C

也即x∈A且x∈B∪C，即x∈S，所以TS．

.

.

因此T=S．

2．试证明（x）（P（x）∧R（x）） （x）P（x）∧（x）R（x）． 证明： （1）（x）（P（x）∧R（x）） P

（2）P（a）∧R（a） ES(1) （3）P（a） T(2)I （4）（x）P（x） EG(3) （5）R（a） T(2)I （6）（x）R（x） EG(5) （7）（x）P（x）∧（x）R（x） T(5)(6)I

.