本科离散数学e.docx

本科离散数学e.docx

《本科离散数学e.docx》由会员分享，可在线阅读，更多相关《本科离散数学e.docx（24页珍藏版）》请在冰点文库上搜索。

本科离散数学e

一、单项选择题

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∧