同济大学考博离散数学试题2007年试题

时间:2019-05-15 09:31:50下载本文作者:会员上传
简介:写写帮文库小编为你整理了多篇相关的《同济大学考博离散数学试题2007年试题》,但愿对你工作学习有帮助,当然你在写写帮文库还可以找到更多《同济大学考博离散数学试题2007年试题》。

第一篇:同济大学考博离散数学试题2007年试题

同济大学考博离散数学试题2007年试题(330)

一、写出定义(15分)(1)格;(2)置换;(3)图。

二、证明下列命题(50分)

1.不记得

2.等价式证明题。

3.下列合取范式是否为可满足的:

E=(X1∨¯X2)∧(¯X1∨X2)∧¯X3(答案:可满足解为(1,1,0)或(0,0,0),可能用真值表法求解比较好)

4.不记得

5.证明图的边数与图的度数的关系,即图的度数为2n,n为边数。(答案见《离散数学》第274页定义7-1.2证明)

三、综合题(35分,第1题15分,第2题20分)

1. 不记得

2.找一种9个a,9个b,9个c的圆形排列,使由字母{a,b,c}组成的长度为3的27个字的每个字仅出现一次。

(答案参见《离散数学 理论·分析·题解》第387页7—

第二篇:同济大学考博离散数学试题2008年试题(最终版)

同济大学考博离散数学试题2008年试题(330)

一、名词解释并说明其作用(15分)

1.格2.关系3.代数系统

二、证明下列命题(50分)

1.2.

3.4.

5.三、1.

2.3.

数。R为等价关系,则必有等价类 一个图是欧拉图的充要条件是图中各点的度为偶数 证明两条件命题等价,例如:ABAB 半群中单位元e唯一 格中abcd,类似证明(ab)cb 综合题(35分)给定两个图,说明其同构 画a,b,c,d的幂集对应的哈斯图 设计一个有限状态机M,接收a、b字符,a的个数为偶数,b的个数为3的倍

第三篇:同济大学考博离散数学试题2006年试题

同济大学考博离散数学试题2006年试题(330)

一、二、给出下列定义,简要叙述其作用。(15分)(1)关系;(2)合取范式;(3)格 证明下列命题(50分)

n1.集合A的幂集P中元素个数为2。

(答案参见《离散数学 理论·分析·题解》第148页3—66)

2.一有向图G=(V,E),其基本回路长度不大于|V|,V是结点集。

(答案可借鉴《离散数学》第280页定理7-2.1证明,此时有结点vj=vk,j=k)

3.代数系统S,,运算“”若存在单位元素,则必惟一。

(答案参见《离散数学》p181定理5-2.1证明,零元证明参见《离散数学 理论·分析·题解》p268 5—6)

4.。(PQ)R(PR)(QR)

5.设是格,任意a,b,cA,且满足a

证明(ab)(bc)(ab)(ac)。bc(注:为偏序关系符号),(答案参见《离散数学 理论·分析·题解》第326页6—10)

三、综合题(35分,第1题15分,第2题20分)

1. 有集合3,5,15,1,2,3,6,12,3,9,27,54,其上面的偏序关系为整除,画出集合的偏序关系图,并指出哪个是全序关系。(答案参见《离散数学 理论·分析·题解》第184页3—136)

2. 有一农村集市平时每天开放,遇雨天则三天开放一次,用有限状态机实现该模型。离散

1. 函数、映射和关系的定义及其它们间的不同。

2. 根据所给出的条件构造一个自动机,并转换成另一种自动机形式。

3. 证明谓词关系式两边等价。

4. 有关群、子群的相关证明。

5. 证明某偏序关系是否是格。

6. 有关左陪集和右陪集的一个证明。

第四篇:离散数学试题

中央电大离散数学试题

一、单项选择题(每小题3分,本题共15分)

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

A.2AB.{1}A

C.1AD.2  A

2.已知一棵无向树T中有8个顶点,4度、3度、2度的分支点各一个,T的树叶数为

().

A.6B.4C.3D.

53.设无向图G的邻接矩阵为

0111110011100001100111010

则G的边数为().

A.1B.7C.6D.14 4.设集合A={a},则A的幂集为().

A.{{a}}B.{a,{a}}

C.{,{a}}D.{,a}

5.下列公式中()为永真式.

A.AB  ABB.AB  (AB)

C.AB  ABD.AB  (AB)

二、填空题(每小题3分,本题共15分)

6.命题公式PP的真值是

7.若无向树T有5个结点,则T的边数为.

8.设正则m叉树的树叶数为t,分支数为i,则(m-1)i

9.设集合A={1,2}上的关系R={<1, 1>,<1, 2>},则在R中仅需加一个元素,就可使新得到的关系为对称的.

10.(x)(A(x)→B(x,z)∨C(y))中的自由变元有.

三、逻辑公式翻译(每小题6分,本题共12分)

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

12.将语句“他去操场锻炼,仅当他有时间.”翻译成命题公式.

四、判断说明题(每小题7分,本题共14分)

判断下列各题正误,并说明理由.

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

14.设G是一个有4个结点10条边的连通图,则G为平面图.

五.计算题(每小题12分,本题共36分)

15.试求出(P∨Q)→(R∨Q)的析取范式.

16.设A={{1}, 1, 2},B={ 1, {2}},试计算

(1)(A∩B)(2)(A∪B)(3)A (A∩B).

17.图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权最小的生成树及其权值.

六、证明题(本题共8分)

18.试证明:若R与S是集合A上的自反关系,则R∩S也是集合A上的自反关系.

中央电大2010年7月离散数学

试题解答

(供参考)

一、单项选择题(每小题3分,本题共15分)

1.B2.D3.B4.C5.B

二、填空题(每小题3分,本题共15分)

6.假(或F,或0)

7.48.t-

19. <2, 1>

10.z,y

三、逻辑公式翻译(每小题6分,本题共12分)

11.设P:今天上课,(2分)则命题公式为:P.(6分)

12.设 P:他去操场锻炼,Q:他有时间,(2分)则命题公式为:P Q.(6分)

四、判断说明题(每小题7分,本题共14分)

13.错误.(3分)因为A中元素2没有B中元素与之对应,故f不是A到B的函数.(7分)

14.错误.(3分)不满足“设G是一个有v个结点e条边的连通简单平面图,若v≥3,则e≤3v-6.”(7分)

五.计算题(每小题12分,本题共36分)

15.(P∨Q)→(R∨Q) ┐(P∨Q)∨(R∨Q)(4分)

(┐P∧┐Q)∨(R∨Q)(8分)

(┐P∧┐Q)∨R∨Q(析取范式)(12分)

16.(1)(A∩B)={1}(4分)

(2)(A∪B)={1, 2, {1}, {2}}(8分)

(3)A(A∩B)={{1}, 1, 2}(12分)

17.(1)G的图形表示如图一所示:ad1

5b c(3分)图一

(2)邻接矩阵:

01101111(6分)1101

1110

(3)最小的生成树如图二中的粗线所示:

a 3d5

b图二1c

权为:1+1+3=5

六、证明题(本题共8分)

18.证明:设xA,因为R自反,所以x R x,即< x, x>R;

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

10分)12分)(4分)(6分)(8分)((

第五篇:离散数学试题+答案

www.xiexiebang.com 专注于收集各类历年试卷和答案

一、单项选择题(本大题共15小题,每小题1分,共15分)在每小题列出的四个选项中只有一个选项是符合题目要求的,请将正确选项前的字母填在题后的括号内。1.一个连通的无向图G,如果它的所有结点的度数都是偶数,那么它具有一条()A.汉密尔顿回路

B.欧拉回路 C.汉密尔顿通路

D.初级回路

2.设G是连通简单平面图,G中有11个顶点5个面,则G中的边是()A.10

B.12

C.16

D.14 3.在布尔代数L中,表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是()A.b∧(a∨c)B.(a∧b)∨(a’∧b)C.(a∨b)∧(a∨b∨c)∧(b∨c)D.(b∨c)∧(a∨c)4.设i是虚数,·是复数乘法运算,则G=<{1,-1,i,-i},·>是群,下列是G的子群是()A.<{1},·>

B.〈{-1},·〉

C.〈{i},·〉

D.〈{-i},·〉

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是整数集,定义为xxy=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∪IA

B.R

C.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

www.xiexiebang.com 专注于收集各类历年试卷和答案

D.(x)(y)(A(x,y)→A(f(x,a),a))12.设B是不含变元x的公式,谓词公式(x)(A(x)→B)等价于()A.(x)A(x)→B

B.(x)A(x)→B C.A(x)→B

D.(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∨Q

B.P∧┐Q

C.P→┐Q

D.P∨┐Q 15.以下命题公式中,为永假式的是()A.p→(p∨q∨r)

B.(p→┐p)→┐p C.┐(q→q)∧p

D.┐(q∨┐p)→(p∧┐p)

二、填空题(每空1分,共20分)16.在一棵根树中,仅有一个结点的入度为______,称为树根,其余结点的入度均为______。17.A={1,2,3,4}上二元关系R={〈2,4〉,〈3,3〉,〈4,2〉},R的关系矩阵MR中m24=______,m34=______。18.设〈s,*〉是群,则那么s中除______外,不可能有别的幂等元;若〈s,*〉有零元,则|s|=______。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的幂集,是对称差运算,可以验证

是群。设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;

www.xiexiebang.com 专注于收集各类历年试卷和答案

(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.B

2.D

3.A

4.A

5.D

6.D

7.D

8.C

9.D

10.B

11.A

12.A

13.C

14.B

15.C

二、填空题 16.0 17.1

0 18.单位元

19.x∩y

x∪y 20.入射

满射

21.[x]R=[y]R

 22.A(x)

B(y)23.(M(x)→D(x))

M(x)→D(x)

www.xiexiebang.com 专注于收集各类历年试卷和答案

24.可满足式

永假式(或矛盾式)25.陈述句

真值

三、计算题

1100101026.M=

1011001122M=21110111

121011M2ij18,ij6 M2i1i1j144

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

www.xiexiebang.com 专注于收集各类历年试卷和答案

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

取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)

(换名)

┐x1y1(F(x1,y)→G(x,y1))∨x2H(x2)

x1y1┐(F(x1,y1)→G(x,y1))∨x2H(x2)

x1y1x2(┐(F(x1,y1)→G(x,y1))∨H(x2)

四、证明题

32.设T中有x片树叶,y个分支点。于是T中有x+y个顶点,有x+y-1 条边,由握手定理知T中所有顶点的度数之的

xy

d(vi)=2(x+y-1)。

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

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

xy

d(vi)≥x·1+2(y-2)+k+k=x+2y+2K-4 i1

从而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的双射函数,故fg也是A到A的双射函数,从而集合F关于运算是封闭的。

(2)f,g,h∈F,由函数复合运算的结合律有f(gh)=(fg)h故运算是可结合的。

(3)A上的恒等函数IA也是A到A的双射函数即IA∈F,且f∈F有IAf=fIA=f,故IA是〈F,〉中的幺元

(4)f∈F,因为f是双射函数,故其逆函数是存在的,也是A到A的双射函数,且有ff-1=f-1f=IA,因此f-1是f的逆元

由此上知〈F,〉是群

34.证明(x)(A(x)→B(x)) x(┐A(x)∨B(x))

www.xiexiebang.com 专注于收集各类历年试卷和答案

(┐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

证①p

P(附加前提)

②p∨q

T①I

③(p∨q)→(r∧s)

P(前提引入)

④r∧s

T②③I

⑤r

T④I

⑥r∨s

T⑤I

⑦(r∨s)→t

P(前提引入)

⑧t

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

根据:构造无向简单图G=,其中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中一条汉密尔顿回路,按这条回路的顺序按其排座位即符合要求。

下载同济大学考博离散数学试题2007年试题word格式文档
下载同济大学考博离散数学试题2007年试题.doc
将本文档下载到自己电脑,方便修改和收藏,请勿使用迅雷等下载。
点此处下载文档

文档为doc格式


声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:645879355@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。

相关范文推荐

    08离散数学试题

    离散数学试题 一、 填空(共36分) 1、命题公式PQ的真值为假,当且仅当。 2、设F(x):x是整数,G(x):x是自然数,则命题“并不是每个整数都是自然数”符号化为。 3、设10阶平面图G有5个......

    离散数学试题与答案

    《离散数学》试题及答案一、选择题:本题共5小题,每小题3分,共15分,在每小题给出的四个选项中,只有一项是符合题目要求的。1. 命题公式(PQ)Q为 ()(A) 矛盾式 (B) 可满足式(C) 重言......

    离散数学试题A卷(合集5篇)

    离散数学试题A卷一、单项选择题(本大题共10小题,每小题2分,共20分)1.下列命题公式中不是重言式的是 .A.p→(q→r)C.p→(p→p) B.p→(q→p) D.(p→(q→r))(q→(p→r))2.设个体域是整数集......

    考博试题大全

    中国科学院2007年生态环境研究中心硕士入学考试试题-----土壤学试题 中国科学院2007年生态环境研究中心硕士入学考试试题-----土壤学试题 07年中科院生态环境研究中心土壤......

    全国2008年4月自考离散数学试题

    全国2008年4月自考离散数学试题 课程代码:02324 一、单项选择题(本大题共15小题,每小题1分,共15分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在......

    北京大学1997年研究生入学考试离散数学试题

    北京大学1997年研究生入学考试 离散数学试题(共50分)1 (7分) 在一阶逻辑自然推理系统F中,构造下面推理的证明。个体域是人的集合。 “每位科学家都是勤奋的,每个勤奋又身体......

    2009年4月离散数学试题(附答案)

    全国2009年4月自学考试离散数学试题(附答案) 课程代码:02324 一、单项选择题(本大题共15小题,每小题1分,共15分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填......

    离散数学试题及解答(5篇范文)

    离散数学 2^m*n一、 选择题(2*10) 1.令P:今天下雨了,Q:我没带伞,则命题“虽然今天下雨了,但是我没带伞”可符号化为( (A)P→Q (C)P∧Q )。 (B)P∨Q (D)P∧Q 2.下列命题公式为永真蕴含式的是( )。......