2024年4月25日发(作者：宋心诺)
严禁用于商业用途?前言??本文收集了1997、1998年和2001年到2007年和2009年南京大学
研究生入学考试科目《离
散数学》的试卷以及相应试卷答案。2008年试题未找到1997年到2007年试题给出本人所
做
的答案因为离散数学难度大很多答案问过原来教我们离散数学的老师老师也只能给出
部
分答案所以不能保证全部答案的正确性2009年试题答案未与同学核对同样不能确保
答
案正确性故不在此给出。部分答案有更优解需要同学们自己开发。?
?南京大学从2005年开始把《离散数学》作为复试科目满分为80分与《编译原理》同
为笔试项目总分150分。主要考试部分为数理逻辑、集合论、代数结构和图论。推荐复习
时
候以南大课件为主课件在网上可以查到有宋方敏和陈道旭两种版本。通过真题发现很
多
题目都是课件上证明题的原题而且考试重点与课件也吻合。?
?离散数学特点就是难度大上手容易深入难。代数系统和图论两章难度非常大所以复习
好离散数学要有一定的耐心和钻研精神。?
相信天下无难事只怕有心人。祝愿所有有志考南大CS的同学金榜提名。?
?
?
?????????????????冷城?
??????????????????2009年7月?
?
?
?
?
?
?
???1?/?30?
?严禁用于商业用途?1996年?一试证?a.自然数集为无限集中势最小者。?
b.不存在最大的势。?
?
二任给无向图G其联结矩阵为A=[aij]即若存在边(vi,vj)则aij=1否则aij=0试
定义矩阵运
算并给出关于A的矩阵的表达式B=E(A)使得矩阵B=[bij]满足对于G中的任意两结点
vi,vj若其间存在通路则bij=1否则bij=0。?
?
三任给无向图G?对G中的边赋予方向得图G’试证存在G满足对任意两点v1,v2
G’
不论从哪点为始终端均有有向通路到达另一点的充分条件是原图G连通且不存在割边。?
?
四试分别用永真推理过程和假设推理过程证明?
???(?α→?(?β?→?γ?)?)?→?(?(?α?∧?β?)?→?γ?)?
?
五试给出下式的析合范式和合析范式?
???(?p?→?q?)?→?(?p?→?r?)?
?
六试用谓词演算公式来描述一个代数系统(A,*)为一个群。?
?
七任给一个集合SS到自身的一一对应的映射成为S上的置换试证S上置换的全体
关于
置换的复合运算构成群。?
?
???2?/?30?
?严禁用于商业用途?1996年答案?一证明?
a.?无限集A将A中元素按照某种次序任意规则排序以0,1,2,„„,n来表示A中
某
元素排列的位置所自集合A的单射NA。?以存在然数集N到得证。
元素αA设BA
α
则A到B有单射关系”=”αAAB。?b.?无限集A
AB比A势更大的集合。因为对任一集合均有比其更大的势的集合。得证。?
?
二B?=?E(?An?)其中An?=??A??n?=?1时?运算定义为两矩阵相乘?
??????An?–?1A?n?>?1时?E为An运算收敛后若元素不为0则将其置为1?
?
三证明?
?1.?对于G中任一条边先证其必在一个圈中?
设存在边ee不在一个圈中e的两个断点记为uv。若去掉边eu,?v不在一个圈
中?????
uv间无通路即P(?G?–?e?)?>?P(G)。e为桥与题设矛盾。得证。?
2.?再证不存在桥的连通图G赋予边以方向后G’为强连通图。?
设不存在这样的圈则存在对两个顶点u,?v没有经过它们的圈。G是连通的u到v
有
通路设通路上的点为u,?v1,?v2,?„„,?vnv对于与u,?v相关联边必有圈v1,?v2
间必有圈
则可将两圈合并得到必有u到v2的圈同理可得u到v3的圈以此类推可得到u到v的
圈与假设不成立。必存在将所有顶点连接的圈将其以逆时针赋予方向后得经过每
个点至少一次的回路G为强连通图。?
得证。?
?
四证明?
?永真推理
α ?
α
β γ
β
γ ?
??? β
α β
γ
???????????? α
???????????? 1?
?假设推理?
????前提引入???α
β γ
????结论???
α β
γ?
????结论
否定引入? α
γ ?
???? ??
α
β γ
α β
γ
? α
β γ
β
γ
α βγ ?
????α β γ α β γ ?
???? 0?
?
五p?→?r?)?(?q?)?→?(?p?→??
? p p q r ?
? p r ? p q
????qp? p r
?? q p r??3?/?30?
? pp
? p q r?
?
?????严禁用于商业用途???????m0 m1 m2 ?m3 m4 m5
m7??
六群的(1(A(2)、*为二元运算(3)、存在关于*的单位元?定义)、,?*?)是代数系统
(4)、aAa–?1A。?
?P(?x,?y?)x与y构成代数系统??H(?x,?y?)x∈y?
?F(?x?)x是二元运算????I(?x,?y?)x是y的逆?
?系R(?x,?y?)x是关y的单位元。?
?P
A,
F
e R
e,
a Ha,A b I
b,a
H b,A ?
?
七证明?
?【置换群问题答案略】?
?
?
???4?/?30?
?严禁用于商业用途?1997年?一R1、R2分别是集合S、T上的关系定义S
T上的关系R3
t1R2t2。?证明?(1)若R1、R2为等价关系则R3为等价关系。?????(2)若R1、R2为偏序
则R3也是偏序。?
?
二证明S是无限集当且仅当存在S的真子集S’满足S与S’等势。?
?
三图G=(VG,EG)R1是定点集VG上的相邻关系即对任意u,v∈VGuR1v当且仅当u,v
∈EG。
R2是VG上的可达关系即uR2v当且仅当在G中存在vu‐通路。???证明R2是R1的传递闭
包。?
?
四(1)T是树e是T中任意一条边证明T’=T‐{e}是连通分支数为2的森林。?
?(2)图G=(VG,EG)|VG|=n|EG|=mG连通且恰好含一个回路的充分必要条件是下列三项
中
的任意两项成立。?
??(i)G连通(ii)G恰好含一个回路(iii)m=n。?
?
五(1)若G是奇数阶有限群证明对任意a∈G方程x2=a有解。?
??(2)若在有限群G中对任意ax2=a有唯一解则|G|必为奇数。?
?
六Zm、Zn分别是m、n阶剩余加群。定义代数系统(ZmZn,*)对任意x1,x2∈Zmy1,y2
∈Zn
(x1,y1)*(x2,y2)=(x1+mx2,y1+ny2)。?
证明若m、n互质ZmZn是循环群生成元为(1,1)。?
证明1封闭性?
???????????????2可结合性?
???????????????3幺元?0,?0?
???????????????4逆元??显然对于任意a,bZ∈m×Zn,?有a‐1,?b‐1?
????????????????综上所述对于任意的m、nZm×Zn,?*都是群。?????????????????
显然若m与n互质?Zm×Zn是循环群生成元为(1,1)。?
?
七试讨论在一给定公理系统的公理系统集合中添加或删除元素对系统的性质可能产生什
么
影响。提示在添加元素的情况下要考虑所加公式在原系统中是否可证。?
?
八给下列命题?
??(1)参加展览的人中每个N大学的男生都背K牌书包。?
(2)参观展览的人中每个背K牌书宝的都是来自N大学的男生。?
(3)每个背K牌书包的N大学男生都参观了该展览。?
写出相关的谓词逻辑表达式证明(1)(2)不能推出(3)。?
?
?
???5?/?30?
?严禁用于商业用途?1997年答案?一证明?
1.?① R1与R2都是等价关系 S1∈S? t1∈T有S1R1S1与t1R1t1。
R3?
??②?对于?S1R1S2必有S2R1S1同样1R2t2必t2R2t1?
? ?t有。
???R3??SRS2? t1R2t2 ?S2R1S1? t2R2t1?
??R3?
???R足对称性。?111满
???③ ?R?S2,?t2> ?R?S3,?t3>?3? < <
???(?S1R1S2?t1R2t2?) (?S2R1S3?t2R2t3?)?3?3? ?
???(?S1R1S2? S2R1S3?) ?(?t1R2t2? t2R2t3?)??
????1R1S3? ?t1R2t2?
S
???? ?R3??
????R3满足传递性。?
?2.?自反性与传递性1。?同
?证明反对称性 S1,1>??
?>?R
????(?S1R1S2?)?(?t1R2t2?)?S1S2??t1t2?
????(?SR1S1?)? (?t2R2t1?)?S1S2?t1t2?
?
???? ?R3?
R3也是偏序关系。?二证明?
1.?充分性S??S将S中去掉一个元素x并将S→S的映射从元素x开始指向原来的下
一个元素。是无限集S到S’仍然存在双射 SSSS。?S是无限集
S’也
2.?必要性SSSS?若S不是无限集则S’中必比S中少元素则不可能
有S’→S
的单射这与SS矛盾S必是无限集。?
三证明?????????????
?1.?对于任意,,,?R’有u到v通路?
????v到通路则u到r必有通路的。?r有,R是传递
?2.? E到v必有通路,?R u,va则uR。?
?u与v必是n条边关联的通路1,2„„?3.?对,即有
,、
?,R对于包含R的传递关系R’’必有,R R
。?
四证明?
1.?树中每条边都是桥去掉一条边后连通分支数加1T’?=?T?–?{e}为连通分支
数为2的
森林。??
2.?(i)(ii)成立则结果显然成立。?
??(i)(iii)成立则对于G中的某一生成树n?=?m?+?1n?=?m对于这个生成树
任加一
条边根据树的性质可得生成的图仅含一个回路得证。?
??(ii)(iii)成立G中恰含一条回路则去掉回路一条边得G中无回路此时
n?=?m?+?1。
对于G各个连通分量均有vi?=?ei?+?1
v?=?v1?+?v2?+?„?+?vn’?=?e1?+?e2?+?„?+?en?+?n’?=?e?+?n’。
nm1n1。G中只有一个连通分量即G是连通的。?
五1.?证明?
?????因为G的阶为奇数?
??????????故无偶数因子??6?/?30?
?严禁用于商业用途???????????所以任意一个元素a的阶也是奇数不妨设
为2k+1。即有?
??????????????????a2k+1=e幺元???????????而且????aj≠e. 因此方程
x2=a有解如下 x= ak+1 事实上
ak+1)2=a2k+1a=ea=a?
?2.?证明?
??????????a有唯一解有e ° e?=?e。xx2?=?
???aG且ae有a?°?a‐1?=?e且aa‐1。?
???a与a‐1成对出现。?
????????????非e元素有偶数个元素数为奇即|G|必为奇数。?
六?证明?
?1.?代数系统中*是二元运算关系x1,?x2,?x3Zmy1,?y2,?y3
Zn。?
?*??*??=??=??*?
(?*?)
足合律。??*??=???*??=?存
在幺元。?1满结
?Zm ?Zn是群。?2.?设?=?t证
明?x?+?1,?y?>?=?t2(t,?t1,?t2为整数)。?
<1?>t1?x,??+?1?>?=
一次同方定理?gcd(n,?m)?|?1α使 nαm (α为整数)。?根据余程
?t?=?t?+?nα?t?+?nα?=?。?1同理可得
,ZmZn均有?=?t存在即ZZ=?>是
生成元。?
??>mα?=??mn八设?F(x)x参观了展览。??(1)?M?七【略】?
xFxNxxKx
??N(x)x来自N大学。??(2)?M?xFxKxNxx
??M(x)x是男生。???(3)?xKxNxMxFx?
??K(x牌书包。)x背k???
?前提xFxKxNxMx?xFxNx
MxKx
?结论?xKxNxMxFx
??Nx??前提引入?xFxMxKx??
??NxKx???①?xFxMx
??Kxx??前提引入?xFxNMx??
??NxFxKx
x
M
x
???②?
?FNM与②交??
KxN
x
M
x
①
?
x
K
x
N
x
M
x
x
x
xxxxKxxFx
F
N
xM
K
x
F
x
?
N
x
M
x
N
x
M
x
?
?
x
xK
x
? x
x
x
F
FK
?
?K??xF
x
x
xKxNxMxFx
?xKNx xF
K
x
xxMFx?
?FKKMxFx? x
x
x
xNx
? xKxNxMxFx不一定为真?
??上述结论不一定成立。?
???7?/?30?
?严禁用于商业用途?1998年?一(1)在下演算中哪列谓词公式些变元可以
换名?
???(a)xFxGx??(b)zyAzByCx,y?
??(2)写出命题演算公式(?p?→?q?)?∧?(?(q∧r)?→(p∧r)?)的析合、合析范式。?
?
二利用谓词演算描述下列推理的过程?
???前提(i)所有的狗都不吃鱼。(ii)没有一个猫不吃鱼。?
???结论没有一只狗是猫。?
?
三设N是正整数集定义关系RNN如下对任意的x,y∈NxRy当且仅当存在z
∈N
使得xz=y。(即x|y).?
(1)证明R是偏序。?
(2)偏序集
(3)描述偏序集
足
(4)描述偏序集
满足对B中任意元素x,y若xy则xRy和yRx均部成立。?
?
四人给一个有限的正整数序列序列中元素各不相等。?
(1)证明以不同元素结尾的最大递增或最大递减子序列长度不会相等。例如在序列2
15876421中以6结尾的最大递增子序列是26最大递减子序
列是15
876。而以4结尾的最大递增子序列是24最大递减子序列是158
764。?
?(2)利用鸽巢原理证明在由n2+1个不同的正整数构成的序列中至少有一个递增或递减
子
序列的长度大于n。?
?
五若干足球队参加比赛每队之间赛一场没有平局而且对任意三个队A、B和C若A
胜B且B胜C则必有C胜A。试建立一个描述此问题的图模型并讨论满足上述条件的
参赛队伍的个数是否有上限若有是多少?
?
六简单连通图G恰好含2KK是不小于1的整数个奇次顶点。证明G可以分为K各边
互
不相交的简单通路。?
?
七代数系统Sa,b,c,d,,中的运算均满足交换率证明结合S上所有保
持?
ab
cd的值不变的一一对应的映射置换构成对称群S4即S上所有置换的
集合与映射符合运算所构成的群的子群。?
?
八代数系统S满足以下4条公理?
??(i)封闭性???(ii)对任意的a,b∈S,a(bc)=(ba)c?
(iii)有单位元???(iv)每个元素都有逆元素。?
证明S是可交换群。?
?
???8?/?30?
?严禁用于商业用途?1998年答案?一1.?a.?x,?y)中xy不在zy辖
域内可换元。?G(x)中x不在x辖域内可换名。b.?G(
?q
p 2.??
p q
r r
?
? q r
r
?
pq
p
?qp p q
? q r p q
???M4?5?M7?
M
??m0? m1? m2? m3? m6?
二F(x)x是狗?
?G(x)x是猫?
?R(x)x吃鱼。?
?前提xx G
x
R
x
? F
x
R
x
?结论x
r ?
r qr p ?p
?x F
G
x
(1) F
R??????前提引入?x x
x
?
(2) xR F
x
x
?
(3)
???????前提引入?xG
x
R
x
(4) R
x G
x
x
?
(5) FR x??(2)(4)合并?
x
x
x
x G
R
x
(6)
G
x
R
x
?x
xR
x
(7)
?x F
x
G
x
(8) x?
F
x
F
G
x
(9) x
F
x
G???????
x
?得证
三1.?证明自反性x N有x|所以xRx,。R满足自反律。?
x成立
????反对称性x立,yN且xy有x|y成立则y|x必不成?
。RR‐1IA。R满足?
即,,反对称性。
????传递性, ,则x|yy|z则x|z即,
?
????????????????????????R满足传递性。?
?2.?有极小元与最小元1无极大元和最大元。?
?3.?B是集合{?2k?|?k?≥?0}。?
?4.?B是素数。?
四【答案略】?
五【颜色填充问题答案略】?
六对k用数学归纳法证明?
?1.?k?=?1图G是一个只含俩个节点u和v的连通图所以图G存在一条欧拉通路E(P1)
且E(G)?=?E(P1)?=?(?u,?v?)。??2.?归纳假设k?≤?i?(?i≥1?)时结论成立即G中存在
各边不重复的i条简单路P1P2„Pi使得???E(G)?=?E(P1)??E(P2)? „
E(Pi)??3.?k?=?i?+?1时任选两个奇节点不妨设为v1和u1。??因为图G是连通的所以
为v1和u1间必存在一条简单路径边部重复的路径P不妨设为为v1?v2„?vpu1。从G
中删去路径P节点v2?„vp?奇数的奇偶性不变而v1和u1变为偶度数结点。?
?设图G删去路径P后变为G’如果G’中某节点v’的度数为0则再删去v’显然G’
的奇?9?/?30?
?严禁用于商业用途?度数结点变为2i个。?
?在G’的任意连通分支中对于只含有偶度数结点的连通分支OnOn是欧拉图所以On
存在欧拉回路。??因为图G是连通的所以On中必存在一个节点v0在v1和u1间的简单路
径P上。??把这个欧拉回路v0加入路径P得P’。同理可以采用这种方法消除致函偶度数
结点的连通分支。?
对于含有奇度数结点的连通分支Wm根据握手定理则一定包含偶数个奇度数结点。?
不妨设连通分支Wm中含有2x?(?m?=?2x?)个奇度数结点并且xm≤i在根据归纳假设2
Wm中存在各边不重复的x(m)条简单路P1P2„使得?
Px(m)
?????E(Wm)?=?E(P1)??E(P2)? „ E(P?x(m))?
综上所述G中存在各边不重复的条简单2„Pk使得?
k路P1P
??????E(G)?=?E(P1)??E(P2)? „ E(P?k)?
七【置换群、对称群问题答案略】?
八证明?
?推出S是群只需证明交换群。?由(i)(ii)(iii)可
? a,b ,c S?a(bc)?=?(ab)c。?
??a(bc)?=?(ba)c?
??(ab)c?=?(ba)c?
?律?群满足消去
?a,b S有ab?=?ba?
??S为Abel群。?
???10?/?30?
?严禁用于商业用途?2001年?一设(H,*)*j|h,j∈H}?是群(G,*)的子群对
于a∈G令HaH={h*a
?证明
a,bG
HaHHbHHaHHbH?
?
二设P、演?Q为一元谓词在一阶谓词算中证明
a) 成立?xPxQxxPxxQx
b) xPxxQxxPxQx不成立?
?
三问题考试日程安排问题。?
每个学生选若干课。要求安排能保证每个学生不会有两门或两门以上所选课程考试时间重
叠。假设每门课的考试时间一样长以一门考试为单位时间段。求所需的最短时间段数。?
?
???11?/?30?
?严禁用于商业用途?2001年答案?一证明?
G若a?=?b对于hij?H在代数系统内有hajHaH。?
a,b
ab?
bjHbH?hajh
HaH?HbH
HaH?同理可证HbH
HHbH?aH
H?b与题设矛盾。?若ab对于h,j若h*a*j?=?h*b*j则更具消去率a?=
hH hajHbH?aj hbjhaj Ha
HhbjHaH?同理hbjHb
?HaHHbH
a,bG
HaHHbHHaHHbH?
二证明?
?P
a)?xx
Q
x
xPxxQx?
?xPQxPx?
?x? xPx
?Qx? xPxx
?Px xPxQ
?? xPxP
x
xQx
?PPP
x
xQx? xx
?P xQx
x
xQx?
?x xQxP
x
xx xQx
Qx xPxxQ
PxxQx
x xQx?
x QxP
x Qx
xQx?
? xQxxP
x
xQx?
? ?1????原命题成立?
x?//从一开始使用归谬法更简单?b?xP
x
xQ
x
xP
?
Px
xP
xx
xQ
x?
xQ
使用归谬法?
?
?P
x
Q
x
?
?x
x
xP
x
Qx??
xPxxQx xP
xPxxQx x
xx? xPx
Q
xxPxQx?
xQxxPxQ
xxPxQx?
xQxxPxQx
xQxx
xQxQ
xQx
Qx?
PxQx
xPx
xQ
Qx
xP
?
?xQ
x
xP
x
? xQx
? P
x
? x
? 0??????????原命题未必成立?
三【颜色填充问题答案略】?
???12?/?30?
?严禁用于商业用途?2002年?一H为无限循环群G为任意阶循环群证明
存在从H到G的满同态。?
?
二设α,β,γ为命题演算中任意命题 和分别表示否定和蕴含联结词仅仅用一下
公理A1
A2A3和规律R1R2R3证明αα。?
公理?α
β
:
β
:α
α?A1:α A2α
αβ
α A3
ββ
规则?R1:αβαβ R2:αβ γα
γβ
R3:αββγαγ?
?
三设G为无向简单图e为G的边数v为G的点数证明若ev23v6/2
则G含
有Hamilton回路。?
?
?
???13?/?30?
?严禁用于商业用途?2002年答案?一证明
1.?若G为无限群则
G
Z而
H
Z
G
H
ZHG的
漫射。?
2.?若G为有限群|a|?=?n则
G
Z而
H
存在到Z的满射HG的
满射。?
得证。?
二证明?
① α?????????????公理A1?αα
②?αα???????公理A3?α
③?ααα??公理A3?α??
④?αα???规则R3?αα
?
????
α
⑤?αα??规则R3?α?????
⑥?αααα???公理A2?α
⑦?αα?????????规则R1⑤成立?
三证明?
? e
?
? e
?
?v62evv?
v3
? v3?
?和设为d?2e即为G的每个顶点度数之
? v3v6dvv?
?点v1v2度数为d1d2?
任取两个不相邻的顶
?dddd?对于剩下v?–?2个顶点其内部
?而与vv相关联边上的度ddd?
??即不与v1v2相关联边上的度度数最大为?
v2
v3v5v6
?12dv5v62dd?
?5v62dd?
v3v6v?d? 2v2d
? vdd?
?根据定理G为阶n大于3的无向图人两个不相邻顶点均有ddn则G中存在哈密
尔
顿图。?
?得证。?
?
?
?
???14?/?30?
?严禁用于商业用途?2003年?一证明?∪?A∪B?=?∪A?∪(∪B)。?
?
二设N为全体自然数的集合证明若SN×N且对于S的任何两个元素(x1,y1)和(x2,y2)
既无??
x1≤x2∧y1≤y2?又无?(x2≤x1∧y2≤y1),则S有穷.??
?
三设G为简单连通图证明G为一条非回路的基本通路G中有两点的度为1且其余点的
度
为2.??
?
四设
G证明
这里H为G的正规子群是指(a∈G)(aH=Ha)。?
?
五在命题演算中证明??
??????(α→β)→(γ→β)→((γ∨τ)→((τ→β)→α))本题有误?
?
???15?/?30?
?严禁用于商业用途?2003年答案?一证
?AB则aA或a
明?
集合a且aB?
?x一个集合aAB使得xa? xAB则必有
??若???则aA?xA?
??B?若aB????则x
?? xAB?
??B? ABA
??aA或aB使得xa?xAB必存在某集合
?? xaAB?
?? x?AB
??有A
B
AB?
??A
B
AB?
二证明?
设元素,若S中存在x,y且xx若yy
y若yy亦
然xx?则对于S中其他元素可分为两类?①且则y
x,yx
??????????①x,y且x?
??,,y,yN?
xx,xNy
?? y0,x0 ????????可证y0,x0不成立?
??????????
???对于①有则①为有穷集合 0y
对于则②为有穷集合。 ②有0x
S为①②,?????????????? S为有穷。?
三证明?
xx
?
y则有
?开始节点度数为d1有n个节点最后一个节点度数为dn。?
设
??G是一个初级通路?边数e?=?n?–?1?
??d1?+?d2?+?„?+?di?+?„2=??(?*?)?
?+?dn?=?(?n?–?1?)?2n?–?2?
?对于G中各节点d1则?+?d?+?„?d+?„?+12n2?
?d1则d1?+?d2?+?„?+?d+?„?+?d12
n2
12n2与(?*?)矛盾?
d1d2?
?d1?+i??dn 12
n2
2?若1或d
? 1?i?ndd
??则d1?+?d2?+?„?+?di?+?„?+?dn12
n3
212n2与(?*?)矛盾?若d2?
? d2?
??G中有两点度数为1其余点度数为2。?
四证明?
?
|
H
|
|
G
|
?G:
2
|
G
|
2024年4月25日发(作者：宋心诺)
严禁用于商业用途?前言??本文收集了1997、1998年和2001年到2007年和2009年南京大学
研究生入学考试科目《离
散数学》的试卷以及相应试卷答案。2008年试题未找到1997年到2007年试题给出本人所
做
的答案因为离散数学难度大很多答案问过原来教我们离散数学的老师老师也只能给出
部
分答案所以不能保证全部答案的正确性2009年试题答案未与同学核对同样不能确保
答
案正确性故不在此给出。部分答案有更优解需要同学们自己开发。?
?南京大学从2005年开始把《离散数学》作为复试科目满分为80分与《编译原理》同
为笔试项目总分150分。主要考试部分为数理逻辑、集合论、代数结构和图论。推荐复习
时
候以南大课件为主课件在网上可以查到有宋方敏和陈道旭两种版本。通过真题发现很
多
题目都是课件上证明题的原题而且考试重点与课件也吻合。?
?离散数学特点就是难度大上手容易深入难。代数系统和图论两章难度非常大所以复习
好离散数学要有一定的耐心和钻研精神。?
相信天下无难事只怕有心人。祝愿所有有志考南大CS的同学金榜提名。?
?
?
?????????????????冷城?
??????????????????2009年7月?
?
?
?
?
?
?
???1?/?30?
?严禁用于商业用途?1996年?一试证?a.自然数集为无限集中势最小者。?
b.不存在最大的势。?
?
二任给无向图G其联结矩阵为A=[aij]即若存在边(vi,vj)则aij=1否则aij=0试
定义矩阵运
算并给出关于A的矩阵的表达式B=E(A)使得矩阵B=[bij]满足对于G中的任意两结点
vi,vj若其间存在通路则bij=1否则bij=0。?
?
三任给无向图G?对G中的边赋予方向得图G’试证存在G满足对任意两点v1,v2
G’
不论从哪点为始终端均有有向通路到达另一点的充分条件是原图G连通且不存在割边。?
?
四试分别用永真推理过程和假设推理过程证明?
???(?α→?(?β?→?γ?)?)?→?(?(?α?∧?β?)?→?γ?)?
?
五试给出下式的析合范式和合析范式?
???(?p?→?q?)?→?(?p?→?r?)?
?
六试用谓词演算公式来描述一个代数系统(A,*)为一个群。?
?
七任给一个集合SS到自身的一一对应的映射成为S上的置换试证S上置换的全体
关于
置换的复合运算构成群。?
?
???2?/?30?
?严禁用于商业用途?1996年答案?一证明?
a.?无限集A将A中元素按照某种次序任意规则排序以0,1,2,„„,n来表示A中
某
元素排列的位置所自集合A的单射NA。?以存在然数集N到得证。
元素αA设BA
α
则A到B有单射关系”=”αAAB。?b.?无限集A
AB比A势更大的集合。因为对任一集合均有比其更大的势的集合。得证。?
?
二B?=?E(?An?)其中An?=??A??n?=?1时?运算定义为两矩阵相乘?
??????An?–?1A?n?>?1时?E为An运算收敛后若元素不为0则将其置为1?
?
三证明?
?1.?对于G中任一条边先证其必在一个圈中?
设存在边ee不在一个圈中e的两个断点记为uv。若去掉边eu,?v不在一个圈
中?????
uv间无通路即P(?G?–?e?)?>?P(G)。e为桥与题设矛盾。得证。?
2.?再证不存在桥的连通图G赋予边以方向后G’为强连通图。?
设不存在这样的圈则存在对两个顶点u,?v没有经过它们的圈。G是连通的u到v
有
通路设通路上的点为u,?v1,?v2,?„„,?vnv对于与u,?v相关联边必有圈v1,?v2
间必有圈
则可将两圈合并得到必有u到v2的圈同理可得u到v3的圈以此类推可得到u到v的
圈与假设不成立。必存在将所有顶点连接的圈将其以逆时针赋予方向后得经过每
个点至少一次的回路G为强连通图。?
得证。?
?
四证明?
?永真推理
α ?
α
β γ
β
γ ?
??? β
α β
γ
???????????? α
???????????? 1?
?假设推理?
????前提引入???α
β γ
????结论???
α β
γ?
????结论
否定引入? α
γ ?
???? ??
α
β γ
α β
γ
? α
β γ
β
γ
α βγ ?
????α β γ α β γ ?
???? 0?
?
五p?→?r?)?(?q?)?→?(?p?→??
? p p q r ?
? p r ? p q
????qp? p r
?? q p r??3?/?30?
? pp
? p q r?
?
?????严禁用于商业用途???????m0 m1 m2 ?m3 m4 m5
m7??
六群的(1(A(2)、*为二元运算(3)、存在关于*的单位元?定义)、,?*?)是代数系统
(4)、aAa–?1A。?
?P(?x,?y?)x与y构成代数系统??H(?x,?y?)x∈y?
?F(?x?)x是二元运算????I(?x,?y?)x是y的逆?
?系R(?x,?y?)x是关y的单位元。?
?P
A,
F
e R
e,
a Ha,A b I
b,a
H b,A ?
?
七证明?
?【置换群问题答案略】?
?
?
???4?/?30?
?严禁用于商业用途?1997年?一R1、R2分别是集合S、T上的关系定义S
T上的关系R3
t1R2t2。?证明?(1)若R1、R2为等价关系则R3为等价关系。?????(2)若R1、R2为偏序
则R3也是偏序。?
?
二证明S是无限集当且仅当存在S的真子集S’满足S与S’等势。?
?
三图G=(VG,EG)R1是定点集VG上的相邻关系即对任意u,v∈VGuR1v当且仅当u,v
∈EG。
R2是VG上的可达关系即uR2v当且仅当在G中存在vu‐通路。???证明R2是R1的传递闭
包。?
?
四(1)T是树e是T中任意一条边证明T’=T‐{e}是连通分支数为2的森林。?
?(2)图G=(VG,EG)|VG|=n|EG|=mG连通且恰好含一个回路的充分必要条件是下列三项
中
的任意两项成立。?
??(i)G连通(ii)G恰好含一个回路(iii)m=n。?
?
五(1)若G是奇数阶有限群证明对任意a∈G方程x2=a有解。?
??(2)若在有限群G中对任意ax2=a有唯一解则|G|必为奇数。?
?
六Zm、Zn分别是m、n阶剩余加群。定义代数系统(ZmZn,*)对任意x1,x2∈Zmy1,y2
∈Zn
(x1,y1)*(x2,y2)=(x1+mx2,y1+ny2)。?
证明若m、n互质ZmZn是循环群生成元为(1,1)。?
证明1封闭性?
???????????????2可结合性?
???????????????3幺元?0,?0?
???????????????4逆元??显然对于任意a,bZ∈m×Zn,?有a‐1,?b‐1?
????????????????综上所述对于任意的m、nZm×Zn,?*都是群。?????????????????
显然若m与n互质?Zm×Zn是循环群生成元为(1,1)。?
?
七试讨论在一给定公理系统的公理系统集合中添加或删除元素对系统的性质可能产生什
么
影响。提示在添加元素的情况下要考虑所加公式在原系统中是否可证。?
?
八给下列命题?
??(1)参加展览的人中每个N大学的男生都背K牌书包。?
(2)参观展览的人中每个背K牌书宝的都是来自N大学的男生。?
(3)每个背K牌书包的N大学男生都参观了该展览。?
写出相关的谓词逻辑表达式证明(1)(2)不能推出(3)。?
?
?
???5?/?30?
?严禁用于商业用途?1997年答案?一证明?
1.?① R1与R2都是等价关系 S1∈S? t1∈T有S1R1S1与t1R1t1。
R3?
??②?对于?S1R1S2必有S2R1S1同样1R2t2必t2R2t1?
? ?t有。
???R3??SRS2? t1R2t2 ?S2R1S1? t2R2t1?
??R3?
???R足对称性。?111满
???③ ?R?S2,?t2> ?R?S3,?t3>?3? < <
???(?S1R1S2?t1R2t2?) (?S2R1S3?t2R2t3?)?3?3? ?
???(?S1R1S2? S2R1S3?) ?(?t1R2t2? t2R2t3?)??
????1R1S3? ?t1R2t2?
S
???? ?R3??
????R3满足传递性。?
?2.?自反性与传递性1。?同
?证明反对称性 S1,1>??
?>?R
????(?S1R1S2?)?(?t1R2t2?)?S1S2??t1t2?
????(?SR1S1?)? (?t2R2t1?)?S1S2?t1t2?
?
???? ?R3?
R3也是偏序关系。?二证明?
1.?充分性S??S将S中去掉一个元素x并将S→S的映射从元素x开始指向原来的下
一个元素。是无限集S到S’仍然存在双射 SSSS。?S是无限集
S’也
2.?必要性SSSS?若S不是无限集则S’中必比S中少元素则不可能
有S’→S
的单射这与SS矛盾S必是无限集。?
三证明?????????????
?1.?对于任意,,,?R’有u到v通路?
????v到通路则u到r必有通路的。?r有,R是传递
?2.? E到v必有通路,?R u,va则uR。?
?u与v必是n条边关联的通路1,2„„?3.?对,即有
,、
?,R对于包含R的传递关系R’’必有,R R
。?
四证明?
1.?树中每条边都是桥去掉一条边后连通分支数加1T’?=?T?–?{e}为连通分支
数为2的
森林。??
2.?(i)(ii)成立则结果显然成立。?
??(i)(iii)成立则对于G中的某一生成树n?=?m?+?1n?=?m对于这个生成树
任加一
条边根据树的性质可得生成的图仅含一个回路得证。?
??(ii)(iii)成立G中恰含一条回路则去掉回路一条边得G中无回路此时
n?=?m?+?1。
对于G各个连通分量均有vi?=?ei?+?1
v?=?v1?+?v2?+?„?+?vn’?=?e1?+?e2?+?„?+?en?+?n’?=?e?+?n’。
nm1n1。G中只有一个连通分量即G是连通的。?
五1.?证明?
?????因为G的阶为奇数?
??????????故无偶数因子??6?/?30?
?严禁用于商业用途???????????所以任意一个元素a的阶也是奇数不妨设
为2k+1。即有?
??????????????????a2k+1=e幺元???????????而且????aj≠e. 因此方程
x2=a有解如下 x= ak+1 事实上
ak+1)2=a2k+1a=ea=a?
?2.?证明?
??????????a有唯一解有e ° e?=?e。xx2?=?
???aG且ae有a?°?a‐1?=?e且aa‐1。?
???a与a‐1成对出现。?
????????????非e元素有偶数个元素数为奇即|G|必为奇数。?
六?证明?
?1.?代数系统中*是二元运算关系x1,?x2,?x3Zmy1,?y2,?y3
Zn。?
?*??*??=??=??*?
(?*?)
足合律。??*??=???*??=?存
在幺元。?1满结
?Zm ?Zn是群。?2.?设?=?t证
明?x?+?1,?y?>?=?t2(t,?t1,?t2为整数)。?
<1?>t1?x,??+?1?>?=
一次同方定理?gcd(n,?m)?|?1α使 nαm (α为整数)。?根据余程
?t?=?t?+?nα?t?+?nα?=?。?1同理可得
,ZmZn均有?=?t存在即ZZ=?>是
生成元。?
??>mα?=??mn八设?F(x)x参观了展览。??(1)?M?七【略】?
xFxNxxKx
??N(x)x来自N大学。??(2)?M?xFxKxNxx
??M(x)x是男生。???(3)?xKxNxMxFx?
??K(x牌书包。)x背k???
?前提xFxKxNxMx?xFxNx
MxKx
?结论?xKxNxMxFx
??Nx??前提引入?xFxMxKx??
??NxKx???①?xFxMx
??Kxx??前提引入?xFxNMx??
??NxFxKx
x
M
x
???②?
?FNM与②交??
KxN
x
M
x
①
?
x
K
x
N
x
M
x
x
x
xxxxKxxFx
F
N
xM
K
x
F
x
?
N
x
M
x
N
x
M
x
?
?
x
xK
x
? x
x
x
F
FK
?
?K??xF
x
x
xKxNxMxFx
?xKNx xF
K
x
xxMFx?
?FKKMxFx? x
x
x
xNx
? xKxNxMxFx不一定为真?
??上述结论不一定成立。?
???7?/?30?
?严禁用于商业用途?1998年?一(1)在下演算中哪列谓词公式些变元可以
换名?
???(a)xFxGx??(b)zyAzByCx,y?
??(2)写出命题演算公式(?p?→?q?)?∧?(?(q∧r)?→(p∧r)?)的析合、合析范式。?
?
二利用谓词演算描述下列推理的过程?
???前提(i)所有的狗都不吃鱼。(ii)没有一个猫不吃鱼。?
???结论没有一只狗是猫。?
?
三设N是正整数集定义关系RNN如下对任意的x,y∈NxRy当且仅当存在z
∈N
使得xz=y。(即x|y).?
(1)证明R是偏序。?
(2)偏序集
(3)描述偏序集
足
(4)描述偏序集
满足对B中任意元素x,y若xy则xRy和yRx均部成立。?
?
四人给一个有限的正整数序列序列中元素各不相等。?
(1)证明以不同元素结尾的最大递增或最大递减子序列长度不会相等。例如在序列2
15876421中以6结尾的最大递增子序列是26最大递减子序
列是15
876。而以4结尾的最大递增子序列是24最大递减子序列是158
764。?
?(2)利用鸽巢原理证明在由n2+1个不同的正整数构成的序列中至少有一个递增或递减
子
序列的长度大于n。?
?
五若干足球队参加比赛每队之间赛一场没有平局而且对任意三个队A、B和C若A
胜B且B胜C则必有C胜A。试建立一个描述此问题的图模型并讨论满足上述条件的
参赛队伍的个数是否有上限若有是多少?
?
六简单连通图G恰好含2KK是不小于1的整数个奇次顶点。证明G可以分为K各边
互
不相交的简单通路。?
?
七代数系统Sa,b,c,d,,中的运算均满足交换率证明结合S上所有保
持?
ab
cd的值不变的一一对应的映射置换构成对称群S4即S上所有置换的
集合与映射符合运算所构成的群的子群。?
?
八代数系统S满足以下4条公理?
??(i)封闭性???(ii)对任意的a,b∈S,a(bc)=(ba)c?
(iii)有单位元???(iv)每个元素都有逆元素。?
证明S是可交换群。?
?
???8?/?30?
?严禁用于商业用途?1998年答案?一1.?a.?x,?y)中xy不在zy辖
域内可换元。?G(x)中x不在x辖域内可换名。b.?G(
?q
p 2.??
p q
r r
?
? q r
r
?
pq
p
?qp p q
? q r p q
???M4?5?M7?
M
??m0? m1? m2? m3? m6?
二F(x)x是狗?
?G(x)x是猫?
?R(x)x吃鱼。?
?前提xx G
x
R
x
? F
x
R
x
?结论x
r ?
r qr p ?p
?x F
G
x
(1) F
R??????前提引入?x x
x
?
(2) xR F
x
x
?
(3)
???????前提引入?xG
x
R
x
(4) R
x G
x
x
?
(5) FR x??(2)(4)合并?
x
x
x
x G
R
x
(6)
G
x
R
x
?x
xR
x
(7)
?x F
x
G
x
(8) x?
F
x
F
G
x
(9) x
F
x
G???????
x
?得证
三1.?证明自反性x N有x|所以xRx,。R满足自反律。?
x成立
????反对称性x立,yN且xy有x|y成立则y|x必不成?
。RR‐1IA。R满足?
即,,反对称性。
????传递性, ,则x|yy|z则x|z即,
?
????????????????????????R满足传递性。?
?2.?有极小元与最小元1无极大元和最大元。?
?3.?B是集合{?2k?|?k?≥?0}。?
?4.?B是素数。?
四【答案略】?
五【颜色填充问题答案略】?
六对k用数学归纳法证明?
?1.?k?=?1图G是一个只含俩个节点u和v的连通图所以图G存在一条欧拉通路E(P1)
且E(G)?=?E(P1)?=?(?u,?v?)。??2.?归纳假设k?≤?i?(?i≥1?)时结论成立即G中存在
各边不重复的i条简单路P1P2„Pi使得???E(G)?=?E(P1)??E(P2)? „
E(Pi)??3.?k?=?i?+?1时任选两个奇节点不妨设为v1和u1。??因为图G是连通的所以
为v1和u1间必存在一条简单路径边部重复的路径P不妨设为为v1?v2„?vpu1。从G
中删去路径P节点v2?„vp?奇数的奇偶性不变而v1和u1变为偶度数结点。?
?设图G删去路径P后变为G’如果G’中某节点v’的度数为0则再删去v’显然G’
的奇?9?/?30?
?严禁用于商业用途?度数结点变为2i个。?
?在G’的任意连通分支中对于只含有偶度数结点的连通分支OnOn是欧拉图所以On
存在欧拉回路。??因为图G是连通的所以On中必存在一个节点v0在v1和u1间的简单路
径P上。??把这个欧拉回路v0加入路径P得P’。同理可以采用这种方法消除致函偶度数
结点的连通分支。?
对于含有奇度数结点的连通分支Wm根据握手定理则一定包含偶数个奇度数结点。?
不妨设连通分支Wm中含有2x?(?m?=?2x?)个奇度数结点并且xm≤i在根据归纳假设2
Wm中存在各边不重复的x(m)条简单路P1P2„使得?
Px(m)
?????E(Wm)?=?E(P1)??E(P2)? „ E(P?x(m))?
综上所述G中存在各边不重复的条简单2„Pk使得?
k路P1P
??????E(G)?=?E(P1)??E(P2)? „ E(P?k)?
七【置换群、对称群问题答案略】?
八证明?
?推出S是群只需证明交换群。?由(i)(ii)(iii)可
? a,b ,c S?a(bc)?=?(ab)c。?
??a(bc)?=?(ba)c?
??(ab)c?=?(ba)c?
?律?群满足消去
?a,b S有ab?=?ba?
??S为Abel群。?
???10?/?30?
?严禁用于商业用途?2001年?一设(H,*)*j|h,j∈H}?是群(G,*)的子群对
于a∈G令HaH={h*a
?证明
a,bG
HaHHbHHaHHbH?
?
二设P、演?Q为一元谓词在一阶谓词算中证明
a) 成立?xPxQxxPxxQx
b) xPxxQxxPxQx不成立?
?
三问题考试日程安排问题。?
每个学生选若干课。要求安排能保证每个学生不会有两门或两门以上所选课程考试时间重
叠。假设每门课的考试时间一样长以一门考试为单位时间段。求所需的最短时间段数。?
?
???11?/?30?
?严禁用于商业用途?2001年答案?一证明?
G若a?=?b对于hij?H在代数系统内有hajHaH。?
a,b
ab?
bjHbH?hajh
HaH?HbH
HaH?同理可证HbH
HHbH?aH
H?b与题设矛盾。?若ab对于h,j若h*a*j?=?h*b*j则更具消去率a?=
hH hajHbH?aj hbjhaj Ha
HhbjHaH?同理hbjHb
?HaHHbH
a,bG
HaHHbHHaHHbH?
二证明?
?P
a)?xx
Q
x
xPxxQx?
?xPQxPx?
?x? xPx
?Qx? xPxx
?Px xPxQ
?? xPxP
x
xQx
?PPP
x
xQx? xx
?P xQx
x
xQx?
?x xQxP
x
xx xQx
Qx xPxxQ
PxxQx
x xQx?
x QxP
x Qx
xQx?
? xQxxP
x
xQx?
? ?1????原命题成立?
x?//从一开始使用归谬法更简单?b?xP
x
xQ
x
xP
?
Px
xP
xx
xQ
x?
xQ
使用归谬法?
?
?P
x
Q
x
?
?x
x
xP
x
Qx??
xPxxQx xP
xPxxQx x
xx? xPx
Q
xxPxQx?
xQxxPxQ
xxPxQx?
xQxxPxQx
xQxx
xQxQ
xQx
Qx?
PxQx
xPx
xQ
Qx
xP
?
?xQ
x
xP
x
? xQx
? P
x
? x
? 0??????????原命题未必成立?
三【颜色填充问题答案略】?
???12?/?30?
?严禁用于商业用途?2002年?一H为无限循环群G为任意阶循环群证明
存在从H到G的满同态。?
?
二设α,β,γ为命题演算中任意命题 和分别表示否定和蕴含联结词仅仅用一下
公理A1
A2A3和规律R1R2R3证明αα。?
公理?α
β
:
β
:α
α?A1:α A2α
αβ
α A3
ββ
规则?R1:αβαβ R2:αβ γα
γβ
R3:αββγαγ?
?
三设G为无向简单图e为G的边数v为G的点数证明若ev23v6/2
则G含
有Hamilton回路。?
?
?
???13?/?30?
?严禁用于商业用途?2002年答案?一证明
1.?若G为无限群则
G
Z而
H
Z
G
H
ZHG的
漫射。?
2.?若G为有限群|a|?=?n则
G
Z而
H
存在到Z的满射HG的
满射。?
得证。?
二证明?
① α?????????????公理A1?αα
②?αα???????公理A3?α
③?ααα??公理A3?α??
④?αα???规则R3?αα
?
????
α
⑤?αα??规则R3?α?????
⑥?αααα???公理A2?α
⑦?αα?????????规则R1⑤成立?
三证明?
? e
?
? e
?
?v62evv?
v3
? v3?
?和设为d?2e即为G的每个顶点度数之
? v3v6dvv?
?点v1v2度数为d1d2?
任取两个不相邻的顶
?dddd?对于剩下v?–?2个顶点其内部
?而与vv相关联边上的度ddd?
??即不与v1v2相关联边上的度度数最大为?
v2
v3v5v6
?12dv5v62dd?
?5v62dd?
v3v6v?d? 2v2d
? vdd?
?根据定理G为阶n大于3的无向图人两个不相邻顶点均有ddn则G中存在哈密
尔
顿图。?
?得证。?
?
?
?
???14?/?30?
?严禁用于商业用途?2003年?一证明?∪?A∪B?=?∪A?∪(∪B)。?
?
二设N为全体自然数的集合证明若SN×N且对于S的任何两个元素(x1,y1)和(x2,y2)
既无??
x1≤x2∧y1≤y2?又无?(x2≤x1∧y2≤y1),则S有穷.??
?
三设G为简单连通图证明G为一条非回路的基本通路G中有两点的度为1且其余点的
度
为2.??
?
四设
G证明
这里H为G的正规子群是指(a∈G)(aH=Ha)。?
?
五在命题演算中证明??
??????(α→β)→(γ→β)→((γ∨τ)→((τ→β)→α))本题有误?
?
???15?/?30?
?严禁用于商业用途?2003年答案?一证
?AB则aA或a
明?
集合a且aB?
?x一个集合aAB使得xa? xAB则必有
??若???则aA?xA?
??B?若aB????则x
?? xAB?
??B? ABA
??aA或aB使得xa?xAB必存在某集合
?? xaAB?
?? x?AB
??有A
B
AB?
??A
B
AB?
二证明?
设元素,若S中存在x,y且xx若yy
y若yy亦
然xx?则对于S中其他元素可分为两类?①且则y
x,yx
??????????①x,y且x?
??,,y,yN?
xx,xNy
?? y0,x0 ????????可证y0,x0不成立?
??????????
???对于①有则①为有穷集合 0y
对于则②为有穷集合。 ②有0x
S为①②,?????????????? S为有穷。?
三证明?
xx
?
y则有
?开始节点度数为d1有n个节点最后一个节点度数为dn。?
设
??G是一个初级通路?边数e?=?n?–?1?
??d1?+?d2?+?„?+?di?+?„2=??(?*?)?
?+?dn?=?(?n?–?1?)?2n?–?2?
?对于G中各节点d1则?+?d?+?„?d+?„?+12n2?
?d1则d1?+?d2?+?„?+?d+?„?+?d12
n2
12n2与(?*?)矛盾?
d1d2?
?d1?+i??dn 12
n2
2?若1或d
? 1?i?ndd
??则d1?+?d2?+?„?+?di?+?„?+?dn12
n3
212n2与(?*?)矛盾?若d2?
? d2?
??G中有两点度数为1其余点度数为2。?
四证明?
?
|
H
|
|
G
|
?G:
2
|
G
|