第一篇:同济大学考博离散数学试题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为等价关系,则必有等价类 一个图是欧拉图的充要条件是图中各点的度为偶数 证明两条件命题等价,例如:ABAB 半群中单位元e唯一 格中abcd,类似证明(ab)cb 综合题(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.。(PQ)R(PR)(QR)
证明(ab)(bc)(ab)(ac)。bc(注:为偏序关系符号),(答案参见《离散数学 理论·分析·题解》第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.2AB.{1}A
C.1AD.2 A
2.已知一棵无向树T中有8个顶点,4度、3度、2度的分支点各一个,T的树叶数为
().
A.6B.4C.3D.
53.设无向图G的邻接矩阵为
0111110011100001100111010
则G的边数为().
A.1B.7C.6D.14 4.设集合A={a},则A的幂集为().
A.{{a}}B.{a,{a}}
C.{,{a}}D.{,a}
5.下列公式中()为永真式.
A.AB ABB.AB (AB)
C.AB ABD.AB (AB)
二、填空题(每小题3分,本题共15分)
6.命题公式PP的真值是
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=
(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)邻接矩阵:
01101111(6分)1101
1110
(3)最小的生成树如图二中的粗线所示:
a 3d5
b图二1c
权为:1+1+3=5
六、证明题(本题共8分)
18.证明:设xA,因为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是整数集,定义为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∪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.陈述句 真值 三、计算题 1100101026.M= 1011001122M=21110111 121011M2ij18,ij6 M2i1i1j144 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) (换名) ┐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中所有顶点的度数之的 xy d(vi)=2(x+y-1)。 i又树叶的度为1,任一分支点的度大于等于2 且度最大的顶点必是分支点,于是 xy d(vi)≥x·1+2(y-2)+k+k=x+2y+2K-4 i1 从而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-1f=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= Vi∈V,d(vi)是与vi相互认识的人的数目,由题意知vi,vj∈V有d(vi)+d(vj)20,于是G中存在汉密尔顿回路。 设C=Vi1Vi2„Vi20Vi1是G中一条汉密尔顿回路,按这条回路的顺序按其排座位即符合要求。