第一篇：《离散数学》期末复习
《离散数学》期末复习
内容：第一章~第七章 题型：
一、选择题（20%，每题2分）二．填空题（20%，每题2分）
三、计算题（20%，每题5分）
四、证明题（20%，每题5分）
五、判断题（20%，每题2分）
第1章 数学语言与证明方法
1.1 常用的数学符号
1.计算常用的数学符号式子 1.2 集合及其表示法
1.用列举法和描述法表示集合
2.判断元素与集合的关系(属于和不属于)3.判断集合之间的包含与相等关系，空集(E)，全集()4.计算集合的幂集
5.求集合的运算：并、交、相对补、对称差、绝对补
6.用文氏图表示集合的运算 7.证明集合包含或相等
方法一： 根据定义, 通过逻辑等值演算证明
方法二： 利用已知集合等式或包含式, 通过集合演算证明
1.3 证明方法概述
1、用如下各式方法对命题进行证明。 直接证明法：AB为真
间接证明法：“AB为真” “ ¬B ¬A为真” 归谬法(反证法)： A¬B0为真
穷举法： A1B, A2B,…, AkB 均为真
构造证明法：在A为真的条件下, 构造出具有这种性质的客体B 空证明法：“A恒为假” “AB为真” 平凡证明法：“B恒为真” “AB为真” 数学归纳法： 第2章 命题逻辑
2.1 命题逻辑基本概念
1、判断句子是否为命题、将命题符号化、求命题的真值（0或1）。
命题的定义和联结词(¬, , , , )
2、判断命题公式的类型
赋值或解释.成真赋值,成假赋值；重言式(永真式)、矛盾式(永假式)、可满足式:。2.2 命题逻辑等值演算
1、用真值表判断两个命题公式是否等值
2、用等值演算证明两个命题公式是否等值
3、证明联结词集合是否为联结词完备集 2.3 范式
1、求命题公式的析取范式与合取范式
2、求命题公式的主析取范式与主合取范式（两种主范式的转换）
3、应用主析取范式分析和解决实际问题 2.4 命题逻辑推理理论
1、用直接法、附加前提、归谬法、归结证明法等推理规则证明推理有效 第3章 一阶逻辑
3.1 一阶逻辑基本概念
1、用谓词公式符号命题（正确使用量词）
2、求谓词公式的真值、判断谓词公式的类型 3.2 一阶逻辑等值演算
1、证明谓词公式的等值式
2、求谓词公式的前束范式 第4章 关系
4.1 关系的定义及其表示
1、计算有序对、笛卡儿积
2、计算给定关系的集合
3、用关系图和关系矩阵表示关系 4.2 关系的运算
1、计算关系的定义域、关系的值域
2、计算关系的逆关系、复合关系和幂关系
3、证明关系运算满足的式子 4.3 关系的性质
1、判断关系是否为自反、反自反、对称、反对称、传递的2、判断关系运算与性质的关系
3、计算关系自反闭包、对称闭包和传递闭包 4.4 等价关系与偏序关系
1、判断关系是否为等价关系
2、计算等价关系的等价类和商集
3、计算集合的划分
4、判断关系是否为偏序关系
5、画出偏序集的哈期图
6、求偏序集的最大元、最小元、极小元、极大元、上界、下界、上确界、下确界
7、求偏序集的拓扑排序 第5章 函数
1.判断关系是否为函数 2.求函数的像和完全原像
3.判断函数是否为满射、单射、双射 4.构建集合之间的双射函数 5.求复合函数
6.判断函数的满射、单射、双射的性质与函数复合运算之间的关系 7.判断函数的反函数是否存在，若存在求反函数 第6章 图
1.指出无向图的阶数、边数、各顶点的度数、最大度、最小度
2.指出有向图的阶数、边数、各顶点的出度和入度、最大出度、最大入度、最小出度最小入出度
3.根据握手定理顶点数、边数等
4.指出图的平行边、环、弧立点、悬挂顶点和悬挂边 5.判断给定的度数列能否构成无向图
6.判断图是否为简单图、完全图、正则图、圈图、轮图、方体图 7.求给定图的补图、生成子图、导出子图 8.判断两个图是否同构 6.2 图的连通性
1.求图中给定顶点通路、回路的距离
2.计算无向图的连通度、点割集、割点、边割集、割边 3.判断有向图的类型：强连通图、单向连通图、弱连通图 6.3 图的矩阵表示
1.计算无向图的关联矩阵 2.计算有向无环图的关联矩阵 3.计算有向图的邻接矩阵 4.计算有向图的可达矩阵
5.计算图的给定长度的通路数、回路数 6.4 几种特殊的图
1、判断无向图是否为二部图、欧拉图、哈密顿图 第7章 树及其应用 7.1 无向树
1.判断一个无向图是否为树
2.计算无向树的树叶、树枝、顶点数、顶点度数之间的关系 3.给定无向树的度数列，画出非同构的无向树 4.求生成树对应的基本回路系统和基本割集系统 5.求最小生成树 7.2 根树及其应用
1.判断一个有向图是否为根树
2.求根树的树根、树叶、内点、树高 3.求最优树
4.判断一个符号串集合是否为前缀码 5.求最佳前缀码
6.用三种方法遍历根树
第二篇：离散数学期末复习试题及答案(二)
第二章 二元关系
1.设A={1,2,3,4},A上二元关系
R={(a,b)|a=b+2}，S={(x,y)|y=x+1 or y=
x2} 求RS,SR,SRS,S2,S
3,SRc。
RS={(3,2),(4,3),(4,1)} SR={(2,1),(3,2)} SRS={(2,2),(3,3),(3,1)} S2={(1,1),(1,3),(2,2),(2,4),(3,2),(4,1),(4,3)} S3={(1,2),(1,4),(2,1),(2,2),(2,3),(3,1),(3,3),(4,2),(4,4)} SRc={(1,4),(2,3),(4,4)}
2．A={a,b,c,d,e,f,g,h}，给定A上关系R的 关系图如下：
图3－14 求最小正整数ｍ，ｎ，ｍ＜ｎ，使Ｒm＝Ｒn。
Ｒ1＝Ｒ16
这是因为R15是8个顶点以及8个自回路，相 当于左图的点各走了5圈，左图的点各走了3圈，R16就成了原来的R．
３．证明：
(1)(InA)IA(a,a)I2nA,aA,(a,a)IA,...,(a,a)IA, (b,b)InA,bA,(b,b)IA.(2)IARRIAR(a,b)R,a,bA,(a,a)IA,(b,b)IA,(a,b)IAR,(a,b)RIA,即RI
AR,RRIA;(a,b)IAR,若(a,b)R,则(a,b)IAR,矛盾,得IARR;同理,RIAR.事实上，当|A|有限时，R与IA复合，相当于矩阵与 单位矩阵相乘，不会变化。
(3)(RIn2nA)IARR...Rn1(RIA)IAR;设(RIk2A)IARR...Rk
(RIk1(I2A)...RkARR)(RIA)(RR2...Rk1)(I2ARR...Rk)IR2...RkRk1AR
４．判断下列等式是否成立（Ｒ,Ｒ1,Ｒ2均是Ａ到Ｂ的 二元关系）
(1)(Rccc1R2)R1R2对,(a,b)(Rc1R2)(b,a)R1R2(b,a)R
1or(b,a)R2(a,b)Rc1or(a,b)Rc2(a,b)Rcc1R2
(2)(Rcc1R2)R1Rc2对(a,b)(Rc1R2)(b,a)R1R2(b,a)R
1and(b,a)R2(a,b)Rcc1and(a,b)R2(a,b)Rcc1R2
(3)(R1R2)R1R2对cccc(a,b)(R1R2)(R1R2)c(b,a)R1R2(b,a)R1,(b,a)R2
(a,b)Rc1,(a,b)Rc2(a,b)Rcccc1R2R1R2(4)(AB)cAB否,例:A{1,2},B{3,4},AB{(1,3),(2,3),(1,4),(2,4)}
(AB)c{(3,1),(3,2),(4,1),(4,2)}(5)c否,c
与的定义域,值域对换了一下.(6)(R)c(Rc)对,(a,b)(R)c(b,a)R(b,a)R(a,b)Rc(a,b)Rc(7)(Rcc1R2)R2Rc1否,R2的定义域不一定与R1的值域相同(8)如果Rcc1R2,则R1R2对,(a,b)Rc1,(b,a)R1R2,(a,b)Rc2.(9)如果R1Rcc2,则R1R2对,(a,b)Rc1,(b,a)R1R2,(a,b)Rc2，R1R2,(c,d)R2,(c,d)R1,(d,c)Rc2,而(d,c)Rc1..
(10)R1R2R2R1否,R
2的定义域不一定与R1的值域相同.5.设R1,R2是集合A上的二元关系，如果R2R1，其中r,s,t分别是自反闭包，对称闭包，传递闭包的 记号。试证明:(1)r(R2)r(R1)R2R1,IAIA, R2IAR1IA
(2)s(R2)s(R1)R2Rcc1,R2R1
Rcc2R2R1R1
(3)t(R2)t(R1)R222R1(R2)1(R1)1(即R2R2R1R1)(a,b)R(a,b)(R2R1(R1)1b)R22)1(a,2,cA,(a,c),(c,b)R2R1,(a,b)R21,(a,b)(R1)1(a,b)t(R2),k,使(a,b)(R2)k(R1)kt(R1).6.设R1,R2,R3,R4分别是A到B，B到C，B到C，Ｃ到D的二元关系，证明
(1)R1(R2R3)R1R2R1R3(x,y)R1(R2R3)z,(x,z)R1,(z,y)R2or(z,y)R3z,(x,z)R1,(z,y)R2or(x,z)R
1,(z,y)R3(x,y)R1R2or(x,y)R1R3(x,y)R1R2R1R3
(2)R1(R2R3)R1R2R1R3(x,y)R1(R2R3)z,(x,z)R1,(z,y)R2and(z,y)R3z,(x,z)R
1,(z,y)R2and(x,z)R1,(z,y)R3(x,y)R1R2and(x,y)R1R3(x,y)R1R2R1R3(3)(4)类(1)(2)证明。
7.设R是A上的二元关系，证明对任意自然数m,n，(1)RmRnRmn(2)(Rm)nRmn
由归
(1)1)n1,Rm1RmR2)假定RmRnRmn{(a,b)|cA,(a,c)Rm,(c,b)Rn}n1RmR{(a,b)|cA,(a,c)Rm,(c,b)Rn1}其中,Rn1{(c,b)|dA,(c,d)Rn,(d,b)R}RmRn1{(a,b)|c,dA,(a,c)Rm,(c,d)Rn,(d,b)R}{(a,b)|dA,(a,d)Rmn,(d,b)R}RmnRR(mn)1Rm(n1)
(2)1)n1,RmRm2)假定(Rm)nRmn(Rm)n1(Rm)nRmRmnRm
由(1)RmnmRm(n1)8.设R是A上的二元关系，｜A｜＝n，证明存在 自然数s,t，使RsRt,且0st2n2，其中定义
R0{(a,a)|aA}。
0(ai,aj)R证:R(rij)nn,rij1(ai,aj)R至多有2n2个不同的Rk(kN)出现,
0k2n2,由鸽洞原理,(2n21)个Rk中必存在s,t,0st2n2,RsRt.9.R1，R2是Ａ上的二元关系，判别下列命题正确与否
(1)如果R1，R2自反，则R1R2也自反。
对,aA,(a,a)R1,(a,a)R2,(a,a)R
1R2
(2)如果R1，R2反自反，则R1R2也反自反。
否,若(a,b)R1,(b,a)R2,(a,a)R1R2
(3)如果R1，R2对称，则R1R2也对称。
否,例:A{1,2,3},R1{(1,2),(2,1)},R2{(2,3),(3,2)},(1,2)R
1,(2,3)R2,(1,3)R1R2,而(3,1)R1R2
(4)如果R1，R2反对称，则R1R2也反对称。
否,例:A{1,2,3},R1{(1,2),(3,2)},R2{(2,3),(2,1)},(1,2)R,3)R，1,(22,(1,3)R1R2(3,2)R1,(2,1)R2,(3,1)R1R2
(5)如果R1，R2传递，则R1R2也传递。
否,例:A{1,2,3,4},R1{(1,1),(2,3)},R2{(1,2),(3,3)},(1,1)R1,(1,2)R2,(1,2)R1R2，(2,3)R1,(3,3)R2,(2,3)R1R2,但(1,3)R1R2
10.设A={a,b,c}，以下分别给出一个P(A)上的二元 关系，确定它们哪些是自反的，反自反的，对称的，反对称的，传递的。
P(A)={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}（１）ｘ是ｙ的一个真子集
R1{(x,y)|xy,x,yP(A)}
反自反，不对称，反对称，传递（２）ｘ与ｙ不相交
R2{(x,y)|xy,x,yP(A)}
不自反，也不反自反()，对称，不传递（３）xyA
R3{(x,y)|xyA,x,yP(A)}
不自反，也不反自反{a,b,c}{a,b,c}A，对称，不传递。
11.设R是A上二元关系，证明R是传递的当且仅当
R2R。
任(a,b)∈R2,C,(a,c)(c,b)∈R ,由R传递(a,b)∈R , 即R2 R;若(a,b)∈R,(b,c)∈R , 即(a,c)∈R2 R , 所以R传递。
12.R是A上反对称的二元关系，问t(R)总是反对称 的吗？
010111否, 例： R001,t(R)111
100111
13．设R是A上的一个自反关系，证明当且仅当(a,b)和(a,c)属于R推出(b,c)属于R时，R是一个等价 关系。
若(a,b)∈R，又自反(a,a)∈R, 推出(b,a)∈R, 所以对称；
若(a,b)(b,c)∈R , 由对称(b,a)(b,c)∈R , 推出(a,c)∈R ,所以传递。若R等价,(a,b)(a,c)∈R , 由对称性(b,a)(a,c)∈R , 由传递性 ,(b,c)∈R。
14.设R是A上的一个对称和传递的关系，证明如果对A中的每个a，在A中存在b，使得(a,b)∈R，则R是一个等价关系。 aA,bA,(a,b)R,由对称性,(b,a)R,又由传递性,(a,a)R.15.设R是A上的一个传递和自反的关系，设T是 A上的一个二元关系，使得当且仅当(a,b)和(b,a)同时 属于R时，(a,b)∈T，证明T是一个等价关系。 a(a,a)∈R,(a,a)∈R =>(a,a)∈T 若(a,a)∈T,(a,b)(b,a)∈R , 即(b,a)(a,b)∈R
=>(b,a)∈T 若(a,b)(b,c)∈T,(a,b)(b,a)(b,c)(c,b)∈R
=>(a,c)∈R,(c,a)∈R
=>(a,c)∈T
16.设R是A上一个二元关系，设
S={(a,b)｜对某个C，(a,c)∈R且(c,b)∈R｝
证明如果R是等价关系，则Ｓ也是等价关系。
a,(a,a)∈R,(a,a)∈R
=>(a,a)∈S 若(a,b)∈S , 存在c,(a,c)(c,b)∈R 由R对称,(b,c)(c,a)∈R , 所以(b,a)∈S 若(a,b)(b,c)∈S
存在d,e
(a,d)(d,b)(b,e)(e,c)∈R
由R传递(a,b)(b,c)∈R 所以(a,c)∈S
17.设R是A上的二元关系，对所有的xi,xj,xk∈A，如果xiRxj∧xjRxkxkRxi，则称R为循环关系，试证明当且仅当R是等价关系时，R才是自反的和循环的。（其中aRb表示(a,b)∈Ｒ）。
R等价, 当然自反，如果xiRxj且xjRxk则由传递性，xiRxk, 由对称性xkRxi，R是自反, 循环的；
若(a,b)∈R, 由R自反 a,(a,a)∈R, 又(a,b)∈R, 由循环(b,a)∈R，对称，若(a,b)(b,c)∈R，由循环(c,a)∈R, 由对称(a,c)∈R，传递。
18．设R1，R2是A上二元关系，证明(1)r(R1R2)r(R1)r(R2)(2)s(R1R2)s(R1)s(R2)(3)t(R1R2)t(R1)t(R2)(1)r(R1R2)(R1R2)IAR1IAR2R1(IAIA)R2(R1IA)(IAR2)(R1IA)(R2IA)r(R1)r(R2)(2)s(Rc1R2)(R1R2)(R1R2)Rcc1R2R1R2
(Rcc1R1)(R2R2)s(R1)s(R2)(3)(R1R2)2{(a,b)|c,(a,c)R1orR2,(c,b)R1orR2}R221R2R1R2R2R1 29 R2221R2(R1R2)用归纳法可证RnRnn12(R1R2)
n,可得t(R1)t(R2)t(R1R2)
19.设A={a,b,c,d},A上二元关系
R={(a,b),(b,a),(b,c),(c,d)}
（１）用矩阵算法和作图法求r(R),s(R),t(R)。（２）用Warshall算法求t(R)。
110001001111 r(R)=1110101011110011 s(R)= 0101 t(R)=0001000100100000
010010011101010i10110i211100001100010001
0000j20000j1,20000i3111111111111110i311111i41111j20001000100010000j20000j1,2,30000
20.讨论正实数集上二元关系Ｒ的几何意义。（１）Ｒ是自反的（２）Ｒ是对称的（３）Ｒ是传递的
（提示：以第一象限的点讨论）
(1)第一象限角平分线
(2)关于对角平分线对称的点对集合
(3)若有P1(x1,y1)、P2(x2,y2), 若x2=y1，必有第三个点P3(x1,y2)
第三篇：离散数学期末复习试题及答案(一)
离散数学习题参考答案
第一章 集合
１．分别用穷举法，描述法写出下列集合（１）偶数集合
（２）36的正因子集合（３）自然数中3的倍数（４）大于１的正奇数
(1)E={，-6，-4，-2，0，2，4，6，}
={2 i | i I }
(2)D= { 1, 2, 3, 4, 6, } = {x>o | x|36 }
(3)N3= { 3, 6, 9, ```} = { 3n | nN }
(4)Ad= {3, 5, 7, 9, ```} = { 2n+1 | nN }
２．确定下列结论正确与否（１）φφ
×（２）φ｛φ｝√（３）φφ√（４）φ｛φ｝√（５）φ｛ａ｝×（６）φ｛ａ｝√
（７）｛ａ，ｂ｝｛ａ，ｂ，ｃ，｛ａ，ｂ，ｃ｝｝×（８）｛ａ，ｂ｝｛ａ，ｂ，ｃ，｛ａ，ｂ，ｃ｝｝√（９）｛ａ，ｂ｝｛ａ，ｂ，｛｛ａ，ｂ｝｝｝×（１０）｛ａ，ｂ｝｛ａ，ｂ，｛｛ａ，ｂ｝｝｝√
３．写出下列集合的幂集（１）｛｛ａ｝｝
{φ, {{ a }}}
(2)φ
{φ}（３）｛φ，｛φ｝｝
{φ, {φ}, {{φ}}, {φ,{φ}} }（４）｛φ，ａ，｛ａ，ｂ｝｝
{φ, {a}, {{a,b }}, {φ}, {φ, a }, {φ, {a,b }}，{a, {a b }}, {φ,a,{ a, b }} }（５）Ｐ（Ｐ（φ））
{φ, {φ}, {{φ}}, {φ,{φ}} }
４．对任意集合Ａ，Ｂ，Ｃ，确定下列结论的正确与否（１）若ＡＢ，且ＢＣ，则ＡＣ√（２）若ＡＢ，且ＢＣ，则ＡＣ×（３）若ＡＢ，且ＢＣ，则ＡＣ×（４）若ＡＢ，且ＢＣ，则ＡＣ ×
５．对任意集合Ａ，Ｂ，Ｃ，证明
(1)A(BC)(AB)(AC)左差A(BC)差A(BC)D.MA(BC)
分配(AB)(AC)右(2)A(BC)(AB)(AC)1)左差A(BC)(1)的结论(AB)(AC)差(AB)(AC)右
2)左差A(BC)D.MA(BC)分配(AB)(AC)差(AB)(AC)右(3)A(BC)(AB)(AC)左差A(BC)D.MA(BC)幂等(AA)(BC)
结合,交换(AB)(AC)右(4)(AB)BAB 左差(AB)B对称差((AB)B)((AB)B)
分配,结合((AB)(BB))(A(B)B))
互补((AB)U)(A)
零一
(AB)(AB)右(5)(AB)CA(BC)左差(AB)C结合A(BC)
D.MA(BC)差A(BC)(6)(AB)C(AC)B左差(AB)C结合A(BC)交换A(CB)结合(AC)B
差(AC)B右(7)(AB)C(AC)(BC)右(5)A(C(BC))差A(C(BC))分配A((CB)(CC))互补A((CB)U)
零一A(CB)交换A(BC)(5)(AB)C左
６．问在什么条件下，集合Ａ，Ｂ，Ｃ满足下列等式
(1)A(BC)(AB)C左(AB)(AC)右若要右左,须CA(BC)，CA时等式成立
(2)ABA左右是显然的,AABAB,AB，AB时等式成立
(3)ABBABB,BB,B,代入原式得A，AB时等式成立
(4)ABBAABBA,只能AB,AB, BA,BA,AB时等式成立
(5)ABAB,若B,bB，当bA,bABA矛盾;当bA,bABA矛盾
(6)ABAB右左是显然的,ABAB,AAB,ABBAB,BAABAB时等式成立
(7)(AB)(AC)A左(AB)(AC)A(BC)A(BC)A(BC)A
ABC时等式成立
(8)(AB)(AC)左(AB)(AC)A(BC)A(BC)A(BC)
A(BC),AB,AC时等式成立
(9)(AB)(AC)左(AB)(AC)A(BC)A(BC)A(BC)
A(BC)时等式成立
(10)(AB)(AC)((AB)(AC))((AB)(AC))(AB)(AC)(AB)(AC)
由(6)知,(AB)(AC),ABAC,ABAC时等式成立
(11)A(BA)BA(BA)(AB)(AA)(AB)U(AB)B
AB时等式成立
７．设Ａ＝｛ａ，ｂ，｛ａ，ｂ｝，｝，求下列各式（１）φ∩｛φ｝=φ（２）｛φ｝∩｛φ｝={φ} （３）｛φ，｛φ｝｝－φ={φ,{φ}}（４）｛φ，｛φ｝｝－｛φ｝= {{φ}}（５）｛φ，｛φ｝｝－｛｛φ｝｝={φ}（６）Ａ－｛ａ，ｂ｝={{a,b}, φ}（７）Ａ－φ = A（８）Ａ－｛φ｝={a,b,{a,b}}（９）φ－Ａ=φ（１０）｛φ｝－Ａ=φ
８．在下列条件下，一定有Ｂ＝Ｃ吗？（１）ABAC
否，例：A={1，2，3}，B={4}，C={3,4}, ABAC{1,2,3,4},而BC。
（２）ABAC
否，例：A={1，2，3}，B={2，3}，C={2，3，4} ABAC{2,3},而BC。
（３）ABAC
对,若BC,不妨,aB,aC,若aA,aAB,aAB,aAB,aAC,aAC,aAC;若aA,aAB,aAB,aAB,aAC,aAC,aAC矛盾（４）ABAC且ABAC
bB,若bA,bABAC,bC,若bA,bABAC,bC，BC,同理,CB,BC
9.(1)(AB)(BC)AB
证:a左,a(BC),aB,aB;a(AB),而aB,aA,aAB
(2)若A(BC)且B(AC),则B。
若B,aB(AC)(AC),aA(BC),aC,aB即aB,矛盾
10．化简
((ABC)(AB))((A(BC))A)(AB)A(AB)A
(AA)(BA)(BA)BA11.设A={2，3，4}，B={1，2}，C={4，5，6}，求（１）AB{1, 3, 4} （２）ABC{1,3,5,6}（３）(AB)(BC){2,3,5,6}
12.设A={1，2，3，4}，B={1，2，5}，求
(1)P(A)P(B){φ,{1},{2},{1,2}}
(2)P(A)P(B)
{φ,{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}, {1,2,3,},{1,2,4,},{1,3,4,},{2,3,4},{1,2,3,4,},{5},{1,5}, {2,5},{1,2} }
(3)P(A)P(B)
{ {3},{4},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4}，{2,3,4},{1,2,3,4} }
(4)P(A)P(B)
{{3},{4},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4}, {2,3,4},{1,2,3,4},{5},{1,5},{2,5},{1,2,5} }
第四篇：离散数学期末试题
离散数学考试试题（A卷及答案）
一、（10分）求(PQ)(P∧(Q∨R))的主析取范式 解：(PQ)(P∧(Q∨R))((P∨Q))∨(P∧Q∧R))
(P∨Q)∨(P∧Q∧R))
(P∨Q∨P)∧(P∨Q∨Q)∧(P∨Q∨R)(P∨Q)∧(P∨Q∨R)
(P∨Q∨(R∧R))∧(P∨Q∨R)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)M0∧M1
m2∨m3∨m4∨m5∨m6∨m7
二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。乙说：王教授不是上海人，是苏州人。丙说：王教授既不是上海人，也不是杭州人。
王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？
解 设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有： 甲：P∧Q 乙：Q∧P 丙：Q∧R
王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有Q∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为：
((P∧Q)∧((Q∧R)∨(Q∧R)))∨((Q∧P)∧(Q∧R))(P∧Q∧Q∧R)∨(P∧Q∧Q∧R)∨(Q∧P∧Q∧R)(P∧Q∧R)∨(P∧Q∧R)P∧Q∧R T 因此，王教授是上海人。
三、（10分）证明tsr(R)是包含R的且具有自反性、对称性和传递性的最小关系。
证明 设R是非空集合A上的二元关系，则tsr(R)是包含R的且具有自反性、对称性和传递性的关系。
若R是包含R的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r(R)R。则 ''sr(R)s(R)＝R，进而有tsr(R)t(R)＝R。
综上可知，tsr(R)是包含R的且具有自反性、对称性和传递性的最小关系。
四、（15分）集合A＝{a，b，c，d，e}上的二元关系R为R＝{
(2)判断R是不是偏序关系，为什么？ 解(1)R的关系矩阵为： ''''10M(R)000111111010101
00110001(2)由关系矩阵可知，对角线上所有元素全为1，故R是自反的；rij＋rji≤1，故R是反对称的；可计算对应的关系矩阵为：
10M(R2)000由以上矩阵可知R是传递的。
111111010101M(R)
00110001
五、（10分）设A、B、C和D为任意集合，证明(A－B)×C＝(A×C)－(B×C)。证明：因为
(x∈A∧xB)∧y∈C
(x∈A∧y∈C∧xB)∨(x∈A∧y∈C∧yC)(x∈A∧y∈C)∧(xB∨yC)(x∈A∧y∈C)∧(x∈B∧y∈C)
六、（10分）设f：AB，g：BC，h：CA，证明：如果hgf＝IA，fhg＝IB，gfh＝IC，则f、g、h均为双射，并求出f、g和h。
解 因IA恒等函数，由hgf＝IA可得f是单射，h是满射；因IB恒等函数，由fhg＝IB可得g是单射，f是满射；因IC恒等函数，由gfh＝IC可得h是单射，g是满射。从而f、g、h均为双射。
由hgf＝IA，得f＝hg；由fhg＝IB，得g＝fh；由gfh＝IC，得h＝gf。－
1－1
－1－1－1
－1
七、（15分）设
证明 因G有限，不妨设G＝{a1，a2，…，an}。由a*x＝a*yx＝y得，若x≠y，则a*x≠a*y。于是可证，对任意的a∈G，有aG＝G。又因为运算*满足交换律，所以aG＝G＝Ga。令e∈G使得a*e＝a。对任意的b∈G，令c*a＝b，则b*e＝(c*a)*e＝c*(a*e)＝c*a＝b，再由运算*满足交换律得e*b＝b，所以e是关于运算*的幺元。对任意a∈G，由aG＝G可知，存在b∈G使得a*b＝e，再由运算*满足交换律得b*a＝e，所以b是a的逆元。由a的任意性知，G中每个元素都存在逆元。故G是一群。
八、（20分）（1）证明在n个结点的连通图G中，至少有n－1条边。
证明 不妨设G是无向连通图（若G为有向图，可略去边的方向讨论对应的无向图）。
设G中结点为v1、v2、…、vn。由连通性，必存在与v1相邻的结点，不妨设它为v2（否则可重新编号），连接v1和v2，得边e1，还是由连通性，在v3、v4、…、vn中必存在与v1或v2相邻的结点，不妨设为v3，将其连接得边e2，续行此法，vn必与v1、v2、…、vn1中的某个结点相邻，得新边en1，由此可见G中至少有n－1条边。
2（2）给定简单无向图G＝
2证明 若n≥Cm。1＋2，则2n≥m－3m＋6（1）
2若存在两个不相邻结点u、v使得d(u)＋d(v)＜m，则有2n＝
wVd(w)＜m＋(m－2)(m－3)＋m＝m－
23m＋6，与（1）矛盾。所以，对于G中任意两个不相邻结点u、v都有d(u)＋d(v)≥m。由定理10.26可知，G是哈密尔顿图。离散数考试试题（B卷及答案）
一、（10分）使用将命题公式化为主范式的方法，证明(PQ)(P∧Q)(QP)∧(P∨Q)。证明：因为(PQ)(P∧Q)(P∨Q)∨(P∧Q)
(P∧Q)∨(P∧Q)(QP)∧(P∨Q)(Q∨P)∧(P∨Q)(P∧Q)∨(Q∧Q)∨(P∧P)∨(P∧Q)(P∧Q)∨P
(P∧Q)∨(P∧(Q∨Q))(P∧Q)∨(P∧Q)∨(P∧Q)(P∧Q)∨(P∧Q)所以，(PQ)(P∧Q)(QP)∧(P∨Q)。
二、（10分）证明下述推理： 如果A努力工作，那么B或C感到愉快；如果B愉快，那么A不努力工作；如果D愉快那么C不愉快。所以，如果A努力工作，则D不愉快。
解 设A：A努力工作；B、C、D分别表示B、C、D愉快；则推理化形式为： AB∨C，BA，DCAD
(1)A 附加前提(2)AB∨C P(3)B∨C T(1)(2)，I(4)BA P(5)AB
T(4)，E(6)B T(1)(5)，I(7)C T(3)(6)，I(8)DC P(9)D T(7)(8)，I(10)AD CP
三、（10分）证明xy(P(x)Q(y))(xP(x)yQ(y))。xy(P(x)Q(y))xy(P(x)∨Q(y))x(P(x)∨yQ(y))xP(x)∨yQ(y)xP(x)∨yQ(y)(xP(x)yQ(y))
四、（10分）设A＝{，1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B)B。解 P(A)＝{，{}，{1}，{{1}}，{，1}，{，{1}}，{1，{1}}，{，1，{1}}} P(B)－{0}＝{，{0}，{{0}}，{0，{0}}－{0}＝{，{0}，{{0}}，{0，{0}} P(B)B＝{，{0}，{{0}}，{0，{0}}{0，{0}}＝{，0，{{0}}，{0，{0}}
五、（15分）设X＝{1，2，3，4}，R是X上的二元关系，R＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>}(1)画出R的关系图。(2)写出R的关系矩阵。
(3)说明R是否是自反、反自反、对称、传递的。解(1)R的关系图如图所示：(2)R的关系矩阵为：
10M(R)11反自反的；由于矩阵不对称，R不是对称的；
经过计算可得
1011101100 00(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的；由于对角线上存在非0元，R不是10M(R2)111011101100M(R)，所以R是传递的。00
六、（15分）设函数f：R×RR×R，f定义为：f(
(4)求复合函数ff和ff。
证明(1)对任意的x，y，x1，y1∈R，若f(
(2)对任意的
1uwuwuwuwuw，y＝，则f(
－1(4)ff(
xyxyxy(xy)，>＝
444
55ff(
七、（15分）给定群
证明 对G中任意元a和b。
因为a*b＝(a*b)，所以a*a*b*b＝a*(a*b)*b，即得a*b＝(b*a)。同理，由a*b＝(a*b)可得，a*b＝(b*a)。由a*b＝(a*b)可得，a*b＝(b*a)。
于是(a*b)*(b*a)＝(b*a)＝a*b，即b*a＝a*b。同理可得，(a*b)*(b*a)＝(b*a)＝a*b，即b*a＝a*b。
由于(a*b)*b＝a*b＝b*a＝b*(b*a)＝b*(a*b)＝(b*a)*b，故a*b＝b*a。
八、（15分）（1）证明在n个结点的连通图G中，至少有n－1条边。
证明 不妨设G是无向连通图（若G为有向图，可略去边的方向讨论对应的无向图）。
设G中结点为v1、v2、…、vn。由连通性，必存在与v1相邻的结点，不妨设它为v2（否则可重新编号），连接v1和v2，得边e1，还是由连通性，在v3、v4、…、vn中必存在与v1或v2相邻的结点，不妨设为v3，将其连接得边e2，续行此法，vn必与v1、v2、…、vn1中的某个结点相邻，得新边en1，由此可见G中至少有n－1条边。
（2）试给出|V|＝n，|E|＝(n－1)(n－2)的简单无向图G＝
12344
333334
34333
4333
133
113
122244 6
第五篇：离散数学复习重点
离散数学复习重点：
1、集合的运算以及运算律；
2、关系的三种表示方法，以及他们之间的转化；
3、常见关系的定义；
4、哈斯图的画法，以及最大最小元、极大极小元、上下界，上下确界的求法；
5、单射、满射以及双射的证明（尤其是在代数系统中）；
6、代数系统的概念以及代数系统的常用性质，能够证明具体的代数系统的运算律，找出单
位元，零元、以及逆元等；
7、环和格只要记住不同的环和格满足的运算律就好；
8、各种图和树的概念及相关的结论，比如：欧拉图的充要条件，哈密顿图的充分条件、必
要条件、充要条件等；
9、图的矩阵计算；
10、会画一些简单的树；
11、五种联结词的真值表；
12、一些要求记住的命题公式；
13、命题公式的证明；
14、命题公式的析取范式，合取范式，主析取范式和主合取范式的求法。
题型：填空题、证明题和解答题。
友情提醒：
1、周三下午一点半到三点半在逸夫楼519答疑。
2、概念、定理和公式请务必记住，可能会出填空题；
3、考试内容不会超出我们的重点；
请大家好好复习，争取一次性通过。
点击咨询 