离散数学复习提纲(1-457章)

《离散数学复习提纲(1-457章)》由会员分享，可在线阅读，更多相关《离散数学复习提纲(1-457章)（16页珍藏版）》请在装配图网上搜索。

1、2006年12月离散数学复习提纲 16离散数学复习提纲第一章 命题逻辑1（PQ）（QR）的主合取范式和主析取范式。2试求下列公式的主析取范式：（1）；（2）（an: ）3用真值表判断下列公式是恒真？恒假？可满足？（1）（PP）Q（2）（PQ）Q（3）（PQ）（QR）（PR） (an: 解： （1） 真值表P QP PP （PP）Q0 01 0 10 11 0 01 00 0 11 10 0 0 因此公式（1）为可满足。 ) （2） 真值表P QPQ （PQ） （PQ）Q0 01 0 00 11 0 01 00 1 01 11 0 0 因此公式（2）为恒假。 （3） 真值表P Q RPQ QR

2、PR （PQ）（QR）（PR）0 0 0 1 1 1 10 0 1 1 1 1 10 1 0 1 0 1 10 1 1 1 1 1 11 0 0 0 1 0 11 0 1 0 1 1 11 1 0 1 0 0 11 1 1 1 1 1 1 因此公式（3）为恒真。4Q（PQ）蕴涵 P（an: 法1：真值表法2：若Q（PQ）为真，则 Q，PQ为真， 所以Q为假，P为假，所以P为真。 法3：若P为假，则P为真，再分二种情况： 若Q为真，则Q（PQ）为假 若Q为假，则PQ为假，则Q（PQ）为假根据 ，所以 Q（PQ）蕴涵 P。）5利用基本等价式证明下列命题公式为恒真公式。（PQ）（QR）（PR）（PQ

3、）（P（QR）（PQ）（PR）（an: 1、证明： （PQ）（QR）（PR） =（PQ）（QR）（PR） =（PQ）（QR）（PR）=（PQ）（QR）PR =（PQ）P ）（QR）R）=（1（QP ）（QR）1）= QPQR =（QQ） P R= 1 P R= 1 （PQ）（P（QR）（PQ）（PR） =（PQ）（P（QR）（P（QR） =（P（Q QR）（P（QR） =（P（QR）（P（QR） =1）6用形式演绎法证明：蕴涵(an: 证明： （1） 规则P （2） 规则Q （1） （3） 规则P （4） 规则Q（3） （5） 规则Q（2）（4） （6）RS 规则P （7）PS 规则Q（5）（

4、6） )7用形式演绎法证明：（蕴涵A（an: 、证明：(改()（1）A 规则D（2）AB 规则Q（1）（3） 规则P（4） 规则Q（2）（3）（5）D 规则Q（4）（6） 规则Q（5）（7） 规则P （8）E 规则Q（6）（7）（9） 规则Q（1）（8）8（PQ），QR，R 蕴涵 P（an: （1）QR（2）R（3）Q（4）（PQ）（5）PQ（6）P）9某案涉及甲、乙、丙、丁四个，根据已有线索，已知：（1） 若甲、乙均未作案，则丙、丁也均未作案；（2） 若丙、丁均未作案，则甲、乙也均未作案；（3） 若甲与乙同时作案，则丙与丁有一人且只有一人作案；（4） 若乙与丙同时作案，则甲与丁同时作案或同未

5、作案。办案人员由此得出结论：甲是作案者。这个结论是否正确？为什么？（an: 解：对问题中的四个简单命题用P1，P2，P3，P4分别表示甲，乙，丙，丁作案，则办案人员的推理如下：前提：1) P1P2P3P42) P3P4P1P23) P1P2(P3P4)(P3P4)4) P3P4(P1P2)(P1P2)结论：P1。(P1P2P3P4) (P3P4P1P2) ( P1P2(P3P4)(P3P4) ( P3P4(P1P2)(P1P2) P1不是永真式，比如：P1取假，P2取真，P3取假，P4取真时，上式为假所以P1不是前提的有效结论，所以甲是作案者的结论是错误的)课后习题：p8：1，5p19：7p2

6、3：6，7，8p39：4p47：4，5第二章 谓词逻辑1设个体域D=1，2，5，F（x）：x2，G（x,y）：xy, 消去（x）(F(x)（y）G(y,x) 中的量词，并讨论其真值。2所有的主持人都很有风度。李明是个学生并且是个节目主持人。因此有些学生是很有风度。请用谓词逻辑中的推理理论证明上述推理。（个体域：所有人的集合）3设数，小于，将“不存在最小的数。”符号化。 （an: ）4利用一阶逻辑的基本等价式，证明：（x）（y）（F（x）G（y）=（$x）F（x）（y）G（y）(an: xy（F（x）G（y）=x（F（x）y G（y） = x（F（x）y G（y） = x（F（x）y G（y）

7、= $xF（x）y G（y）= $xF（x）yG（y）)5（x）（F(x) A(x)），（x）（A(x)B(x)，（$x） B(x)蕴涵 （$x） F(x)（an: （1）$x B(x)（2）B(c)（3）x（A(x)B(x)）（4）A(c)B(c)（5）A(c)（6）x（F(x) A(x)）（7）F(c) A(c)（8）F(c)（9）$x F(x)）6符号化下列命题并推证其结论：没有不守信用的人是可以信赖的，有些可以信赖的人是受过教育的人，因此，有些受过教育的人是可守信用的。（个体域：所有人的集合）（an:令M(x)：x是守信用的；J(x)：x是受过教育的；D(x)：x是可以信赖的前提：$x

8、（M(x)D(x)），（$x D(x) J(x)）有效结论：$x（J(x) M(x)）证明：1）（$x D(x)J(x)）前提2）$x D(x)J(y)代替规则3）$x D(x)合取4）D(c)EI规则5）J(y)合取6）zJ(z)UG规则7）J(c)UI规则8）$x（M(x) D(x)）前提规则9） x（M(x) D(x)） 等价10） x（M(x) D(x)）等价11）M(c) D(c)UI规则12）M(c)等价13）M(c) J(c)合取14）$x（J(x) M(x)）EG规则)7在一阶逻辑中，构造下面的证明：前提：，F(a) 结论:（an: 1)x(F(x)G(x)2) F(a)G(a

9、)3) F(a)4)G(a)5) $G(x)8设解释I为：（1） 定义域D=-2，3，6；（2） F（x）：x3；G（x）：x5。在解释I下求公式($x)（F（x）G（x）的真值。（an: ( $x)（F（x）G（x） =（F（-2）G（-2）（F（3）G（3）（F（6）G（6） =（10）（10）（01） = 1）9不存在能表示成分数的无理数。有理数都能表示成分数。因此，有理数都不是无理数。（an: F(x)：x为无理数，G(x)：x为有理数，H(x)：x能表示成分数）10 设个体域为集合a, b, c, 试消去下列公式中的量词。(1) （x） P(x)（x）Q(x)(2) （x）（ P(x

10、) Q(x)）课后习题：p59：1，2p62：3，6p65：2，3p72：1，4p75：1p79：2，3第三章 集合论1设A，是偏序集，A=1，2，3，4，5，6，8，是整除关系，请画出A，的哈斯图。写出A中的极大元，极小元和最大元，最小元。2设A=1，2，3，求A上所有等价关系。3设全集有下列子集 A= B= C= 求1） 2） 3）（an:）4设集合，试求： 1）AB 2） 3）（an: ）5一个年级170人中，120名学生学英语，80名学生学德语，60名学生学日语，50名学生既学英语又学德语，25名学生既学英语又学日语，30名学生既学德语又学日语，还有10名学生同时学习三种语言。试问：有

11、多少名学生这三种语言都没有学习？（an: 解：设E为全集，A为学英语学生的集合，B为学德语学生的集合，C为学日语学生的集合。由公式， |ABC|=|A|+|B|+|C|-|AB|-|BC|-|AC|+|ABC| 可得：|ABC|=120+80+60-50-30-25+10 =165 所以，这三种语言都没有学习的学生为 170-165=5人。）6A=a，b，c，d，R1，R2是A上的关系，其中R1=（a，a），（a，b），（b，a），（b，b），（c，c），（c，d），（d，c），（d，d），R2=（a，b），（b，a），（a，c），（c，a），（b，c），（c，b），（a，a），（b，b），（

12、c，c）。（1） 写出R1和R2的关系矩阵，并画出R1和R2的关系图；（2） 判断它们是否为等价关系，是等价关系的求A中各元素的等价类。（an:） R1为等价关系等价类M1=a,b，M2=c,dR2不为等价关系 7集合，R是集合A上的关系，求，并分别画出它们的关系图。（an: 它们的关系图：）8设集合，R为A上的整除关系，（1）画出偏序集（A， R）的哈斯图；（2）写出集合A中的最大元、最小元、极大元、极小元；（3）写出A的子集的上界、下界、最小上界、最大下界。（an: （1）半序集（A，R）的哈斯图如下所示： 248 124 6 2 3 （2）集合A中的最大元是24，无最小元，极大元是24，

13、极小元是2与3。（3）集合B的上界是12与24，无下界，最小上界是12，无最大下界。）9设集合，试画出偏序集的哈斯图，并写出A的最大元，最小元，极大元和极小元。（an: （A，）的哈斯图为： e b c d a a为A的极小元，也是最小元； e为A的极大元，也是最大元。 ）11设R是集合A上的二元关系，证明：R是传递的，当且仅当t（R）=R。（an: 证明： 若R是传递的，又有R R，对于任何包含R的传递关系 ，都有 ，所以R满足传递闭包定义中 的全部条件，即 t（R）=R。反之，若 t(R)=R，由传递闭包含定义中的条件1可得R是传递的。 ）12设集合上的关系 则R在A上构成的等价类是？（a

14、n: ）13设集合A=，为A上的二元关系， 则是？（an: （1，1），（1，2），（1，3），（2，1），（2，2），（2，3），（3，1），（3，2），（3，3）14设R是一个二元关系，设S=|存在某个C，使R且R，证明R是一个等价关系，则S也是一个等价关系。（an: 1、证明：（1）R是自反，若有xA就有x，xRx，xSS是自反的。（2）因有a，bS且存在c，使a，cR且c，bR R是对称的c，aR，b，cRb，aSS是对称的（3）设a，b，b，cS则存在d,e使a，d，d，b，b，e，e，cRR是传递的a，b，b，cRa，cS 即S是传递的因此得证S是等价关系。）课后习题：p85：5，

15、6p95：3，4p99：4，5p104：2，4p109：2，5，7p113：4，6p119：1，6，8p127：2，7p130：1，2，4p135：2，3，4，p139：3，5p145：1，3，6第四章 函数1设映射都是双射，求证p151：1，3，4，6p156：2，3，4离散数学复习提纲（代数系统）1（1） 相等关系显然是所有代数结构上的同余关系. 同余关系是相等关系的推广。（2） 同余关系也是模k相等关系（数论中也称模k同余关系）的推广。可证模k相等关系是如上定义的关于整数加、乘运算的同余关系。 设整数x,y,u,v满足xy（mod k）, uv（mod k）,那么x y = nk,u v

16、 = mk(n,m为整数),于是 (x+u) (y+v) = (n+m)k故x+u = y+v（mod k）。 为证 xuyv（mod k），将 x = y+nk与u = v+mk两边分别相乘,于是有 xu yv = ymk+vnk+nmk2 xu yv = (ym+vn+nmk)k 由于ym+vn+nmk 为整数，xuyv（mod k）得证。模k相等关系关于减运算和一元减运算（添负号运算）也是同余关系，请读者自行验证。2设为群,G中元素a的阶为k,那么,an = e当且仅当k整除n .证 先证充分性 设 ak e，k整除n，那么n = kr（r为整数），因为ak e，所以an = akr =

17、 (ak )r = e r = e 。 再证必要性 设 an e，n = mk r，其中m为n除以 k的商，r为余数，因此0 rk 。于是eanamk+ramk*arar因此,由k的最小性得r = 0，k整除n 3有限群G的每个元素都有有限阶,且其阶数不超过群G的阶数 | G | .证 设a为G的任一元素,考虑 e = a0 ,a1 ,a2 , ,aG这 | G |+1个G中元素.由于G中只有 | G |个元素,因此它们中至少有两个是同一元素,不妨设 ar = as (0 r s | G | )于是as-r = e,因此a有有限阶,且其阶数至多是s-r,不超过群G的阶数| G | .4设为群，

18、a为G中任一元素，那么a与a-1具有相同的阶证 只要证 a具有阶n当且仅当a-1具有阶n 。由于逆元是相互的，即(a-1)-1a，同此只需证：当a具有阶n时，a-1 也具有阶n 。 设a的阶是n，a-1的阶是m 。由于(a-1)n(an)-1e -1 e 故mn 。又因为a m(a-1)m)-1 e -1 e 故nm 。因此，nm 。5设为群，那么为子群的充分必要条件是 （l）G的么元eH （2）若a，bH ，则a*bH （3）若aH，则a-1H 证 先证必要性 设H为子群那么（2）是显然的（因H为子代数）为证（l）,设的么元为e,那么e* e= e。由于在G中只有e是等幂元,故e = e ,

19、 eH得证 .为证（3）设中任一元素a的H中逆元为b,那么a*b = b*a = e,由逆元的唯一性,b就是a在G中的逆元,即b = a-1H. 充分性是明显的.事实上只要条件（2），（3）便可使为子群,因为H不空时条件（2）（3）蕴涵条件（l）.因此，可用（2）,（3）来判别非空子集H是否构成G的子群。 显然,对任何群G , 及均为其子群,它们被称为平凡子群,其它子群则称为非平凡子群或真子群6 （1）为循环群，1或（l）为其生成元 . （2）令 A =2i | iI，那么(为数乘 )是循环群 ，2是生成元 （3）为循环群，1，2，3，4都可以是生成元7循环群的子群都是循环群 证 设为g生成的

20、循环群，为其子群当然，H中元素均可表示为gr形 （1）若He,显然H为循环群 （2）若He，那么H中有gi(i0)由于H为子群，H中必还有g-i .因此，不失一般性，可设i为正整数，并且它是H中元素的最小正整数指数现证H为gi生成的循环群 设gj为H中任一元素令jmi+r，其中m为i除j的商，r为剩余，0ri于是 gj = gmi+rgmi*gr gr= g-mi*gj由于gj, g-miH，（因gmiH），故grH，根据i的最小性，r 0，从而 gj = gmi = (gi)m， H为循环群8（1）有循环子群： ， ， ，, （2）有循环子群： ， ， , 9有限群举例(四阶以内)课后习题：

21、p178：1，2p184：1，2，3p190：1，3，5，6p196：1，2，3，4，5p200：1，2，3，5p208：2，3，5，7，8p221：1，2，4，6，8，10，11离散数学复习提纲（图论）1. 判别图61的两幅图是否可以一笔画出？v4h hv5 Eh h F hAv2h h v3 Bh h C hv1 h D（a） (b) 图61解 在图61(a) 中， deg(v1)=deg(v2)=deg(v3)3有两个以上的结点的度为3. 故在(a)中不存在欧拉通路，不能一笔画出. 在图61(b) 中，deg(A)=2, deg(B) =deg(C)= deg(D)=4，deg(E) =

22、deg(F)=3只有两个奇数度的结点，所以存在欧拉通路，可以一笔画出. 一条欧拉通路，如EDBEFCABCDF.2 画出具有下列条件的有5个结点的无向图.(1) 不是哈密顿图，也不是欧拉图；(2) 有哈密顿回路，没有欧拉回路；(3) 没有哈密顿回路，有欧拉回路；(4) 是哈密顿图，也是欧拉图. 解 作图如图63(不唯一). h h h h h h h h h h h h h h h h h h h h(1) (2) (3) (4)在图(1)中，可以走遍5个点，但不是回路，无哈密顿回路，故不是哈密顿图。无论指定怎样的方向，可以走遍所有边，但不是回路，不能构成欧拉路。在图(2)中，容易找出走遍5个

23、点的回路，即有哈密顿回路，故是哈密顿图。但是构成回路，要么出现重复边，要么漏掉边，即不存在欧拉回路，因此不是欧拉图。在图(3)中，不重复地走遍5个点是不可能的，故不是哈密顿图。如指定右边垂直边方向向上，就可以画出一个走遍所有的边，又不重复的回路，所以有欧拉回路，故是哈欧拉图。在图(4)中 ，满足要求的条件是显然的。3在下列图中各有几个面，写出每个面的边界和次数。 解：（a）图中共有5个面。 第1个面，边界为abea，次数为3；第2个面，边界为bdeb，次数为3；第3个面，边界为abca，次数为3；第4个面，边界为adea，次数为3；第5个面，边界为acbda，次数为4。 （b）图中共有两个面，

24、第1个面，边界为 gfcdefg，次数为6；第2个面，边界为 abcdefcba，次数为8。4在具有n个结点的完全图Kn中，需要删去多少条边才能得到树？ 解 n个结点的完全图共有条边，而n个结点的树共有n1条边. 因此需要删去条边后方可得到树. 5设G是图，无回路，但若外加任意一条边于G后，就形成一回路. 试证明G必为树. 证明 由树的定义可知，只需证G连通即可. 任取不相邻两点u,v, 由题设，加上边就形成一回路，于是去掉边,从u到v仍有路u,v，即u,v连通，由u,v的任意性可知，G是连通的，故G必是树.6如图65是有6个结点a,b,c,d,e,f的带权无向图，各边的权如图所示. 试求其最

25、小生成树. b 23 1 15c 25 a 4 f 28 9 16 3 d 15 e 图65解 构造连通无圈的图，即最小生成树， 用克鲁斯克尔算法： b 23 1 c a 4 f 9 3 d e 图66第一步： 取ab1；第二步： 取af=4；第三步： 取fe=3；第四步： 取ad=9；第五步： 取bc=23.如图66。权为1+4+3+9+23=307试画出一棵带权1，2，2，3，4，5，5，6，7，8，10的最优二叉树。 解：最优二叉树如下：9试证明下图中两个无向图是不同构的。10一个简单无向图同构于它的补图，称为自补图，证明其结点必是4k或者4k+1.11非平凡的树至少有两个叶子。12证明

26、: 在任何n (n2)个顶点的简单图G中，至少有两个顶点具有相同的度。证 如果G有两个孤立顶点，那么它们便是具有相同的度的两个顶点。如果G恰有一个孤立顶点，那么我们可对有n 1 个顶点但没有孤立顶点的G（它由G删除孤立顶点后得到）作下列讨论。不妨设G没有孤立顶点，那么G 的n个顶点的度数应是：1，2，3，n1 这n1种可能之一，因此必定有两个顶点具有相同的度。13n个城市间有m条相互连接的直达公路。证明：当时，人们便能通过这些公路在任何两个城市间旅行。证 用n个顶点表示n个城市，顶点间的边表示直达公路，据题意需证这n个城市的公路网络所构成的图G是连通的。反设G不连通，那么可设G由两个不相关的子

27、图（没有任何边关联分别在两个子图中的顶点）G1，G2组成，分别有n1，n2个顶点，从而，n = n1+n2，n1 1，n2 1。 由于各子图的边数不超过 ，因此G的边数m满足： 与已知矛盾，故图G是连通的。14有7人a，b，c，d，e，f，g分别精通下列语言，问他们7人是否可以自由交谈（必要时借助他人作翻译）。 a 精通英语。 b 精通汉语和英语。 c 精通英语、俄语和意大利语。 d 精通日语和英语。 e 精通德语和意大利语。 f 精通法语、日语和俄语。g 精通法语和德语。 ab d c e g f解 下图中7个顶点表示7个人，关联两个顶点的边表示两个人同时精通某一种语言：由于该图是连通的，因

28、此他们7人是可以自由交谈（必要时借助他人作翻译）。15证明：恰有两个奇数度顶点u,v的无向图G是连通的,当且仅当在G上添加边（u，v）后所得的图G*是连通的。证 必要性是显然的。设G*是恰有两个奇数度顶点u,v的无向图G添加边（u，v）后所得，且是连通的,那么图G*是一个欧拉图（每一个顶点都是偶数度的连通图），因此G*中删除边（u，v）后所得的图G仍是连通的。判别图8.31中各图是否为哈密顿图，若不是，请说明理由，并回答它是否有哈密顿通路。图8.31 解（a），(b) 是为哈密顿图。(c) 不是哈密顿图，也没有哈密顿通路。在图(c)中增加顶点k ，并对其顶点做二着色，构成图(d)（如下）。图(d) 不是哈密顿图，也没有哈密顿通路。因为图中白色顶点比黑色顶点多两个。故(c) 不是哈密顿图，课后习题:p279: 1，2，3，5p287: 3，4，5，7，8p300: 1，2，3，4p311: 1，2，3，6p317: 1，2，4p321: 1，3，5p327: 1，2，6p337: 1，3，6，8