电大离散数学本科期末复习题.docx
《电大离散数学本科期末复习题.docx》由会员分享，可在线阅读，更多相关《电大离散数学本科期末复习题.docx（58页珍藏版）》请在冰点文库上搜索。
电大离散数学本科期末复习题
离散数学（本）
一、单项选择题
1．设P：
a是偶数，Q：
b是偶数。
R：
a+b是偶数，则命题“若a是偶数，b是偶数，则a+b也是偶数”符号化为（D．PQ→R）。
2．表达式
x（P（x，y）
Q（z））
y（Q（x，y）→
zQ（z））中
x的辖域是（P（x，y）Q（z））。
3．设
则命题为假的是（
）。
4．设G是有n个结点的无向完全图，则G的边数（1/2n（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）．
8．设无向图G的邻接矩阵为
则G的边数为（7）．
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）}是边割集）．
图一
15．设A（x）：
x是人，B（x）：
x是工人，则命题“有人是工人”可符号化为（（
x）（A（x）∧B（x）））．
16．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是（A⊂B，且A∈B）．
17．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是（（d）是强连通的）．
18．设图G的邻接矩阵为
则G的边数为（5）．
19．无向简单图G是棵树，当且仅当（G连通且边数比结点数少1）．
20．下列公式（（P→（⌝Q→P））↔（⌝P→（P→Q）））为重言式．
21．若集合A＝{a，{a}，{1，2}}，则下列表述正确的是（{a}⊆A）．
22．设图G＝，v∈V，则下列结论成立的是（
）．
23．命题公式（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．设完全图K
有n个结点（n≥2），m条边，当（n为奇数）时，K
中存在欧拉回路．
30．已知图G的邻接矩阵为
，则G有（5点，7边）．
二、填空题（每小题3分，共15分）
1．设A，B为任意命题公式，C为重言式，若A
C
B
C，那么A
B是重言式（重言式、矛盾式或可满足式）。
2．命题公式（P→Q）
P的主合取范式为
。
3．设集合A={
，{a}}，则P（A）=
。
4．设图G=〈V，E〉，G′=〈V′，E′〉，若V′=V,E′E,则G′是G的生成子图。
5．在平面G=〈V，E〉中，则
=2|E|，其中
（i=1，2，…，r）是G的面。
6．命题公式
的真值是假（或F，或0） ．
7．若无向树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．命题公式
的真值是 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个结点，8条边的连通图，则从G中删去3条边，可以确定图G的一棵生成树．
24．无向图G存在欧拉回路，当且仅当G连通且所有结点的度数全为偶数．
25．设个体域D＝{1,2}，则谓词公式
消去量词后的等值式为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条边后使之变成树．
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的表达式知，
即R具有自反性；
三、逻辑公式翻译
1．将语句“今天上课．”翻译成命题公式．设P：
今天上课，则命题公式为：
P．
2．将语句“他去操场锻炼，仅当他有时间．”翻译成命题公式．设P：
他去操场锻炼，Q：
他有时间，则命题公式为：
PQ．
3．将语句“他是学生．”翻译成命题公式．设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））．
11.将语句"如果小李学习努力，那么他就会取得好成绩."翻译成命题公式.设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．设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存在一条欧拉回路．
正确．因为图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的图形表示如图一所示：
（2）邻接矩阵：
（3）最小的生成树如图二中的粗线所示：
权为：
1+1+3=5
4．画一棵带权为1,2,2,3,4的最优二叉树,计算它们的权．
最优二叉树如图三所示
图三
权为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-1，r（R）．
R=∅,S={<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<2,0>}
R∙S=∅，
S-1=S，
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）邻接矩阵：
（3）粗线表示最小的生成树，
权为7：
10．设谓词公式
，试
（1）写出量词的辖域；
（2）指出该公式的自由变元和约束变元．
（1）∃x量词的辖域为
，
∀z量词的辖域为
∀y量词的辖域为
．
（2）自由变元为
与
中的y，以及
中的z
约束变元为x与
中的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）邻接矩阵：
（3）v1，v2，v3，v4，v5结点的度数依次为1，2，4，3，2
（4）补图如下：
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）关系图为
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）关系图
（2）邻接矩阵
（3）deg（v1）=2
deg（v2）=3
deg（v3）=4
deg（v4）=3
deg（v5）=2
（4）补图
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）
（2）指出该公式的自由变元和约束变元.
自由变元为（A（x,y）∧∀zB（x,y,z））中的y,以及C（y,z）中的z.
约束变元为（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自反，所以xRx，即∈R；
又因为S自反，所以xRx，即∈S．
即∈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的整数倍
证明设
，
，…，
为任取的m＋1个整数，用m去除它们所得余数只能是0，1，…，m－1，由抽屉原理可知，
，
，…，
这m＋1个整数中至少存在两个数
和
，它们被m除所得余数相同，因此
和
的差是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，则必
升级会员 