离散数学试卷及答案一Word文件下载.doc

离散数学试卷及答案一Word文件下载.doc

《离散数学试卷及答案一Word文件下载.doc》由会员分享，可在线阅读，更多相关《离散数学试卷及答案一Word文件下载.doc（7页珍藏版）》请在冰点文库上搜索。

〉

5.设Z为整数集，A为集合，A的幂集为P（A）,+、-、/为数的加、减、除运算，∩为集合的交运算，下列系统中是代数系统的有（）

A.〈Z，+，/〉B.〈Z，/〉

C.〈Z，-，/〉D.〈P（A），∩〉

6.下列各代数系统中不含有零元素的是（）

A.〈Q，*〉Q是全体有理数集，*是数的乘法运算

B.〈Mn（R）,*〉,Mn（R）是全体n阶实矩阵集合，*是矩阵乘法运算

C.〈Z，〉，Z是整数集，定义为xxy=xy,x,y∈Z

D.〈Z，+〉，Z是整数集，+是数的加法运算

7.设A={1,2,3}，A上二元关系R的关系图如下：

R具有的性质是

A.自反性

B.对称性

C.传递性

D.反自反性

8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S（R）是（）

A.R∪IAB.RC.R∪{〈c,a〉}D.R∩IA

9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的等价关系，R应取（）

A.｛〈c,a〉，〈a,c〉｝B.{〈c,b〉，〈b,a〉}

C.{〈c,a〉，〈b,a〉}D.{〈a,c〉，〈c,b〉}

10.下列式子正确的是（）

A.∈B.C.{}D.{}∈

11.设解释R如下：

论域D为实数集，a=0,f（x,y）=x-y,A（x,y）:

x<

y.下列公式在R下为真的是（）

A.（x）（y）（z）（A（x,y））→A（f（x,z）,f（y,z））

B.（x）A（f（a,x）,a）

C.（x）（y）（A（f（x,y）,x））

D.（x）（y）（A（x,y）→A（f（x,a）,a））

12.设B是不含变元x的公式，谓词公式（x）（A（x）→B）等价于（）

A.（x）A（x）→BB.（x）A（x）→B

C.A（x）→BD.（x）A（x）→（x）B

13.谓词公式（x）（P（x,y））→（z）Q（x,z）∧（y）R（x,y）中变元x（）

A.是自由变元但不是约束变元

B.既不是自由变元又不是约束变元

C.既是自由变元又是约束变元

D.是约束变元但不是自由变元

14.若P：

他聪明；

Q：

他用功；

则“他虽聪明，但不用功”，可符号化为（）

A.P∨QB.P∧┐QC.P→┐QD.P∨┐Q

15.以下命题公式中，为永假式的是（）

A.p→（p∨q∨r）B.（p→┐p）→┐p

C.┐（q→q）∧pD.┐（q∨┐p）→（p∧┐p）

二、填空题（每空1分，共20分）

16.在一棵根树中，仅有一个结点的入度为__0____，称为树根，其余结点的入度均为__1____。

17.A={1,2,3,4}上二元关系R={〈2，4〉，〈3，3〉，〈4，2〉}，R的关系矩阵MR中m24=___1___,m34=___0___。

18.设〈s,*〉是群，则那么s中除__幺元____外，不可能有别的幂等元；

若〈s,*〉有零元，则|s|=___1___。

19.设A为集合，P（A）为A的幂集，则〈P（A），〉是格，若x,y∈P（A）,则x,y最大下界是______，最小上界是______。

20.设函数f:

X→Y,如果对X中的任意两个不同的x1和x2，它们的象y1和y2也不同，我们说f是___入射___函数，如果ranf=Y，则称f是___满射___函数。

21.设R为非空集合A上的等价关系，其等价类记为〔x〕R。

x,y∈A，若〈x,y〉∈R，则

〔x〕R与〔y〕R的关系是______，而若〈x,y〉R，则〔x〕R∩〔y〕R=______。

22.使公式（x）（y）（A（x）∧B（y））（x）A（x）∧（y）B（y）成立的条件是______不含有y，______不含有x。

23.设M（x）:

x是人，D（s）:

x是要死的，则命题“所有的人都是要死的”可符号化为（x）______,其中量词（x）的辖域是______。

24.若H1∧H2∧…∧Hn是______，则称H1,H2,…Hn是相容的，若H1∧H2∧…∧Hn是______，则称H1,H2,…Hn是不相容的。

25.判断一个语句是否为命题，首先要看它是否为，然后再看它是否具有唯一的。

三、计算题（共30分）

26.（4分）设有向图G=（V,E）如下图所示，试用邻接矩阵方法求长度为2的路的总数和回路总数。

27.（5）设A={a,b},P（A）是A的幂集，是对称差运算，可以验证<

P（A），>

是群。

设n是正整数，求（{a}-1{b}{a}）n{a}-n{b}n{a}n

28.（6分）设A={1,2,3,4,5},A上偏序关系

R={〈1，2〉，〈3，2〉，〈4，1〉，〈4，2〉，〈4，3〉，〈3，5〉，〈4，5〉}∪IA;

（1）作出偏序关系R的哈斯图

（2）令B={1,2,3,5}，求B的最大，最小元，极大、极小元，上界，下确界，下界，下确界。

29.（6分）求┐（P→Q）（P→┐Q）的主合取范式并给出所有使命题为真的赋值。

30.（5分）设带权无向图G如下，求G的最小生成树T及T的权总和，要求写出解的过程。

31.（4分）求公式┐（（x）F（x,y）→（y）G（x,y））∨（x）H（x）的前束范式。

四、证明题（共20分）

32.（6分）设T是非平凡的无向树，T中度数最大的顶点有2个，它们的度数为k（k≥2）,证明T中至少有2k-2片树叶。

33.（8分）设A是非空集合，F是所有从A到A的双射函数的集合，是函数复合运算。

证明：

〈F,〉是群。

34.（6分）在个体域D={a1,a2,…，an}中证明等价式：

（x）（A（x）→B（x））（x）A（x）→（x）B（x）

五、应用题（共15分）

35.（9分）如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C++语言。

只要他学过DELPHI语言或者C++语言，那么他就会编程序。

因此如果他是计算机系本科生，那么他就会编程序。

请用命题逻辑推理方法，证明该推理的有效结论。

36.（6分）一次学术会议的理事会共有20个人参加，他们之间有的相互认识但有的相互不认识。

但对任意两个人，他们各自认识的人的数目之和不小于20。

问能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人?

根据是什么?

参考答案

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

1.B2.D3.A4.A5.D

6.D7.D8.C9.D10.B

11.A12.A13.C14.B15.C

二、填空题

16.01

17.10

18.单位元1

19.x∩yx∪y

20.入射满射

21.［x］R=［y］R

22.A（x）B（y）

23.（M（x）→D（x））M（x）→D（x）

24.可满足式永假式（或矛盾式）

25.陈述句真值

三、计算题

26.M=

M2=

G中长度为2的路总数为18，长度为2的回路总数为6。

27.当n是偶数时，x∈P（A）,xn=

当n是奇数时，x∈P（A）,xn=x

于是：

当n是偶数，（｛a｝-1｛b｝｛a｝）n｛a｝-n｛b｝n｛a｝n

=（｛a｝-1）n｛b｝n｛a｝n=

当n是奇数时，

（｛a｝-1｛b｝｛a｝）n｛a｝-n｛b｝n｛a｝n

=｛a｝-1｛b｝｛a｝（｛a｝-1）n｛b｝n｛a｝n

=｛a｝-1｛b｝｛a｝｛a｝-1｛b｝｛a｝=

28.

（1）偏序关系R的哈斯图为

（2）B的最大元：

无，最小元：

无；

极大元：

2，5，极小元：

1，3

下界：

4，下确界4；

上界：

无，上确界：

无

29.原式（┐（P→Q）→（P→┐Q））∧（（P→┐Q）→┐（P→Q））

（（P→Q）∨（P→┐Q））∧（┐（P→┐Q）∨┐（P→Q））

（┐P∨Q∨┐P∨┐Q）∧（┐（┐P∨┐Q）∨（P∧┐Q））

（┐（P∧┐Q）∨（P∧┐Q））

（P∧Q）∨（P∧┐Q）

P∧（Q∨┐Q）

P∨（Q∧┐Q）

（P∨Q）∧（P∨┐Q）

命题为真的赋值是P=1,Q=0和P=1,Q=1

30.令e1=（v1,v3）,e2=（v4,v6）

e3=（v2,v5）,e4=（v3,v6）

e5=（v2,v3）,e6=（v1,v2）

e7=（v1,v4）,e8=（v4,v3）

e9=（v3,v5）,e10=（v5,v6）

令ai为ei上的权，则

a1<

a2<

a3<

a4<

a5=a6=a7=a8<

a9=a10

取a1的e1∈T,a2的e2∈T,a3的e3∈T,a4的e4∈T,a5的e5∈T,即，

T的总权和=1+2+3+4+5=15

31.原式┐（x1F（x1,y）→y1G（x,y1））∨x2H（x2）（换名）

┐x1y1（F（x1,y）→G（x,y1））∨x2H（x2）

x1y1┐（F（x1,y1）→G（x,y1））∨x2H（x2）

x1y1x2（┐（F（x1,y1）→G（x,y1））∨H（x2）

四、证明题

32.设T中有x片树叶，y个分支点。

于是T中有x+y个顶点，有x+y-1条边，由握手定理知T中所有顶点的度数之的

=2（x+y-1）。

又树叶的度为1，任一分支点的度大于等于2

且度最大的顶点必是分支点，于是

≥x·

1+2（y-2）+k+k=x+2y+2K-4

从而2（x+y-1）≥x+2y+2k-4

x≥2k-2

33.从定义出发证明：

由于集合A是非空的，故显然从A到A的双射函数总是存在的，如A上恒等函数，因此F非空

（1）f,g∈F,因为f和g都是A到A的双射函数，故fg也是A到A的双射函数，从而集合F关于运算是封闭的。

（2）f,g,h∈F,由函数复合运算的结合律有f（gh）=（fg）h故运算是可结合的。

（3）A上的恒等函数IA也是A到A的双射函数即IA∈F,且f∈F有IAf=fIA=f,故IA是〈F，〉中的幺元

（4）f∈F,因为f是双射函数，故其逆函数是存在的，也是A到A的双射函数，且有ff-1=f-1f=IA,因此f-1是f的逆元

由此上知〈F，〉是群

34.证明（x）（A（x）→B（x））x（┐A（x）∨B（x））

（┐A（a1）∨B（a1））∨（┐A（a2）∨B（a2））∨…∨（┐A（an）∨B（an）））

（┐A（a1）∨A（a2）∨…∨┐A（an）∨（B（a1）∨B（a2）∨…∨（B（an））

┐（A（a1）∧A（a2）∧…∧A（an））∨（┐B（a1）∨B（a2）∨…∨（B（an））

┐（x）A（x）∨（x）B（x）（x）A（x）→（x）B（x）

五、应用题

35.令p：

他是计算机系本科生

q：

他是计算机系研究生

r：

他学过DELPHI语言

s:

他学过C++语言

t:

他会编程序

前提：

（p∨q）→（r∧s）,（r∨s）→t

结论：

p→t

证①pP（附加前提）

②p∨qT①I

③（p∨q）→（r∧s）P（前提引入）

④r∧sT②③I

⑤rT④I

⑥r∨sT⑤I

⑦（r∨s）→tP（前提引入）

⑧tT⑤⑥I

36.可以把这20个人排在圆桌旁，使得任一人认识其旁边的两个人。

根据：

构造无向简单图G=<

V,E>

其中V={v1,v2,…，V20}是以20个人为顶点的集合，E中的边是若任两个人vi和vj相互认识则在vi与vj之间连一条边。

Vi∈V,d（vi）是与vi相互认识的人的数目，由题意知vi,vj∈V有d（vi）+d（vj）20,于是G中存在汉密尔顿回路。

设C=Vi1Vi2…Vi20Vi1是G中一条汉密尔顿回路，按这条回路的顺序按其排座位即符合要求。

第7页共7页