离散数学总复习.ppt
《离散数学总复习.ppt》由会员分享,可在线阅读,更多相关《离散数学总复习.ppt(82页珍藏版)》请在课桌文档上搜索。
1、离 散 数 学,期 末 总 复 习,复 习 时 注 意准确掌握每个概念灵活应用所学定理注意解题思路清晰证明问题时,先用反向思维(从结论入手)分析问题,再按正向思维写出证明过程.,全书知识网络:,总 复 习 要 求,复习重点第一章 命题逻辑1.联结词的定义(含义及真值表定义).2.会命题符号化.3.永真式的证明.4.永真蕴涵式的证明,记住并能熟练应用常用公式.5.等价公式的证明,记住并能熟练应用常用公式.6.会写命题公式的范式,*能应用范式解决问题.7.熟练掌握命题逻辑三种推理方法.,第二章 谓词逻辑1.准确掌握有关概念.2.会命题符号化.(如P60题(2)3.掌握常用的等价公式和永真蕴涵式.包
2、括:带量词的公式在论域内展开式,量词否定,量词辖域扩充,量词分配公式.4.会用等价公式求谓词公式的真值.(如P66题(3)5.会写前束范式6.熟练掌握谓词逻辑推理.第三章 集合论初步1.幂集,全集,空集.2.集合的五种运算及相关性质(特别是差集,对称差.)3.应用包含排斥原理.,第四章 二元关系1.关系的概念,表示方法.2.二元关系的 性质的定义,熟练掌握性质的判断及证明.3.掌握关系的复合,求逆及闭包运算(计算方法及有关性质)4.掌握等价关系的判断,证明,求等价类和商集.5.掌握相容关系定义,简化图和简化矩阵,相容类,最大相容类,完全覆盖.6.偏序关系的判断,会画Hasse图,会求一个子集的
3、极小(大)元,最小(大)元,上界与下界,最小上界及最大下界.,第六章 代数系统1.掌握运算的定义.2.熟练掌握二元运算的性质的判断及证明.3.掌握代数系统的同构定义,会证明.了解同构性质的保持.4.了解半群,独异点,环和域的概念.5.熟练掌握群,子群,交换群(会证明),了解循环群.6,子群的陪集,Lagrange定理及其推论,(会应用).第七章 格与布尔代数1.掌握格的定义,了解格的性质.2.会判断格,分配格,有补格和布尔格,3.重点掌握两个元素的布尔代数的性质(10个).4.会写两个元素的布尔表达式的范式.(实质是第一章的主析取和主合取范式).,第八章 图论1.掌握图的基本概念.(特别注意相
4、似的概念)2.熟练掌握图中关于结点度数的定理.(会应用)3.无向图的连通性的判定,连通分支及连通分支数的概念.4.有向图的可达性,强连通,单侧连通和弱连通的判定.求强 分图,单侧分图和弱分图.5.会求图的矩阵.6.会判定欧拉图和汉密尔顿图.7.会判定平面图,掌握欧拉公式.8.了解对偶图.9.掌握树的基本定义,v和e间的关系式.会画生成树,会求最小生成树.根树的概念,完全m叉树的公式,会画最优树,会设计前缀码.,总 复 习,复习重点第一章 命题逻辑1.联结词的定义(含义及真值表定义).2.会命题符号化.3.永真式的证明.4.永真蕴涵式的证明,记住并能熟练应用常用公式.5.等价公式的证明,记住并能
5、熟练应用常用公式.6.会写命题公式的范式,能应用范式解决问题.7.熟练掌握命题逻辑三种推理方法.,第一章 命题逻辑1.联结词定义了六个逻辑联结词,分别是:(1)否定“”(2)合取“”(3)析取“”(4)异或“”(5)蕴涵“”(6)等价“”要熟练掌握这五个联结词在自然语言中所表示的含义以及它们的真值表的定义。:否定 表示“不”:合取 表示“不但,而且.”“并且”:析取 表示“或者可兼取的或”:异或 表示“或者不可兼取的或”:蕴涵 表示“如果,则.”:等价 表示“当且仅当”“充分且必要”可以将这六个联结词看成六种“运算”。,联结词的定义(包括真值表和含义).特别要注意:“或者”的二义性,即要区分给
6、定的“或”是“可兼取的或”还是“不可兼取的或”。“”的用法,它既表示“充分条件”也表示“必要条件”,即要弄清哪个作为前件,哪个作为后件.,P Q PQ PQ PQ PQ P Q,F F F F T T F,F T F T T F T,T F F T F F T,T T T T T T F,2.会命题符号化.例如 P:我有时间.Q:我上街.R:我在家.表示P是Q的充分条件:如果p,则Q.只要P,就Q.PQ 表示P是Q的必要条件:仅当P,才Q.只有P,才Q.QP 如果P,则Q;否则R.(PQ)(PR)3.永真式的证明.方法1.列真值表.(R(QR)(PQ)P 方法2.用公式的等价变换,化简成T.例
7、如证明(R(QR)(PQ)P是永真式.证:上式(R(QR)(PQ)P(PQPQ)(R(QR)(PQ)P(公式的否定公式)(R(QR)(PQ)P)(结合律)(RQ)(RR)(PP)(QP)(分配律)(RQ)(QP)RQQP T(互补,同一律),4.永真蕴涵式的证明,记住常用的公式.永真蕴涵式:AB是永真式,则称A永真蕴涵B.(AB)方法1.列真值表.方法2.假设前件真,推出后件真.(即直接推理)方法3.假设后件假,推出前件假.(即反证法)例证明(P(QR)(PQ)(PR)是永真蕴涵式.证:假设后件(PQ)(PR)假,则PQ为T,PR为F,于是P为T,R为F,进而又得Q为T.所以QR为F,所以前件
8、P(QR)为F.所以(P(QR)(PQ)(PR)为永真式.对于给定一个题,究竟是用哪种方法,原则上哪种都可以.但是哪个方法简单,要根据具体题而定.,5.等价公式的证明,记住常用的公式.方法1.列真值表.方法2.用公式的等价变换.例如:证明 P(QR)(PQ)R P(QR)P(QR)(PQ)R(PQ)R(PQ)R注意:不论是证明永真蕴涵式,还是证明等价公式以及后边的求公式的范式,命题逻辑推理,都应用43页的公式。必须记忆一些常用的公式 如:P43表中的永真蕴涵式:I1,I3,I9,I10,I11,I12,I13,等 价 公 式:E1 E16,E18,E19,E20,E21,6.命题公式的范式1)
9、析取范式:A1A2.An(n1)Ai(i=1,2.n)是合取式.2)合取范式:A1A2.An(n1)Ai(i=1,2.n)是析取式.3)析取范式与合取范式的写法.4)小项及小项的性质.m3 m2 m1 m0 P Q PQ PQ PQ PQ 00 F F F F F T 01 F T F F T F 10 T F F T F F 11 T T T F F F,6)大项及其性质.M0 M1 M2 M3 P Q PQ PQ PQ PQ 00 F F F T T T 01 F T T F T T 10 T F T T F T 11 T T T T T F7)主析取范式:A1A2.An(n1)Ai(i=
10、1,2.n)小项.8)主合取范式:A1A2.An(n1)Ai(i=1,2.n)大项.,9).会写主析取范式和主合取范式.求下面命题公式的范式:A(P,Q,R)(PQ)R方法1.列真值表.主析取范式A(P,Q,R)(PQ)R(PQR)(PQR)(PQR)(PQR)(PQR)主合取范式A(P,Q,R)(PQ)R(PQR)(PQR)(PQR),方法2.用公式的等价变换.主析取范式;A(P,Q,R)(PQ)R(PQ)R(PQ)R(PQ(RR)(PP)(QQ)R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)主合取范式:A(P,Q,R)(P
11、Q)R(PQ)R(PQ)R(PR)(QR)(P(QQ)R)(PP)QR)(PQR)(PQR)(PQR),已知A(P,Q,R)的主析取范式中含有如下小项:m0,m3,m4,m5,m7求它的主合取范式.解:A(P,Q,R)的主合取范式中含有大项:M1,M2,M6A(P,Q,R)(PQR)(PQR)(PQR)范式的应用 如P39习题(7),(8):安排工作(排课表),判断比赛名次,携带工具箱,7.会用三种推理方法,进行逻辑推理.会用三个推理规则:P,T,CP例如:证明(AB)C)D(CD)AB1.直接推理:D P CD P C T I10 Q,(PQ)P(AB)C P(AB)T I12 Q,PQ P
12、 AB T E8(PQ)PQ,(AB)C)D(CD)AB2.条件论证:适用于结论是蕴涵式.AB ABA P(附加前提)(AB)C P A(BC)T E19 BC T I11D PCD PC T I10 B T I12 AB CP,(AB)C)D(CD)AB3.反证法:(AB)P(假设前提)AB T E9(AB)C P C T I11 D PCD PC T I10CC T I9,第二章 谓词逻辑1.准确掌握有关概念.2.会命题符号化.(如P60题(2)3.掌握常用的等价公式和永真蕴涵式.包括:带量词的公式在论域内展开式,量词否定,量词辖域扩充,量词分配公式.4.会用等价公式求谓词公式的真值.(如
13、P66题(3)5.会写前束范式6.熟练掌握谓词逻辑推理.,第二章 谓词逻辑1.准确掌握有关概念.客体:客体变元,谓词,量词,量词后的指导变元,量词的辖域,约束变元与自由变元,论域,全总个体域,谓词公式(WFF),命题函数,前束范式,2.会命题符号化.(如P60题(2)命题的符号表达式与论域有关。当论域扩大时,需要添加用来表示客体特性的谓词,称此谓词为特性谓词。特性谓词往往就是给定命题中量词后边的那个名词。如“所有自然数.”、“有些大学生.”。如何添加特性谓词,这是个十分重要的问题,这与前边的量词有关。如果前边是全称量词,特性谓词后边是蕴含联结词“”;如果前边是存在量词,特性谓词后边是合取联结词
14、“”。另外有些命题里有的客体在句中没有明确的量词,而在写它的符号表达式时,必须把隐含的量词明确的写出来.,例如金子闪光,但闪光的不一定都是金子.设:G(x):x是金子.F(x):x闪光.x(G(x)F(x)x(F(x)G(x)x(G(x)F(x)x(F(x)G(x)没有大学生不懂外语.S(x):x是大学生.F(x):x外语.K(x,y):x懂得y.x(S(x)y(F(y)K(x,y)x(S(x)y(F(y)K(x,y)有些液体可以溶解所有固体.F(x):x是液体.S(x):x是固体.D(x,y):x可溶解y.x(F(x)y(S(y)D(x,y)每个大学生都爱好一些文体活动。S(x):x是大学生
15、,L(x,y):x爱好y,C(x):x是文娱活动,P(x):x是体育活动.)x(S(x)y(C(y)P(y)L(x,y),3.掌握常用的等价公式和永真蕴涵式.包括:带量词的公式在论域内展开式,量词否定,量词辖域扩充,量词分配公式.设论域为a1,a2,.,an,则 1).xA(x)A(a1)A(a2).A(an)2).xB(x)B(a1)B(a2).B(an)1).xA(x)xA(x)2).xA(x)xA(x)1).xA(x)Bx(A(x)B)2).xA(x)Bx(A(x)B)3).xA(x)Bx(A(x)B)4).xA(x)Bx(x)B)5).BxA(x)x(BA(x),6).BxA(x)x(
16、BA(x)7).xA(x)Bx(A(x)B)8).xA(x)Bx(A(x)B)1).x(A(x)B(x)xA(x)xB(x)2).x(A(x)B(x)xA(x)xB(x)3).x(A(x)B(x)xA(x)xB(x)4).xA(x)xB(x)x(A(x)B(x)4.会用等价公式求谓词公式的真值.(如P66题(3)例设论域为1,2,A(x,y):x+y=xy,求xyA(x,y)的真值.xyA(x,y)xyA(x,y)yA(1,y)yA(2,y)(A(1,1)A(1,2)(A(2,1)A(2,2)(TT)(TF)T,*5.将下面谓词公式写成前束范式(xF(x,y)yG(y)xH(x,y)(xF(x
17、,y)yG(y)xH(x,y)(去)xF(x,y)yG(y)xH(x,y)(摩根)xF(x,y)yG(y)xH(x,y)(量词否定)xF(x,z)yG(y)tH(t,z)(变元换名)xyt(F(x,z)G(y)H(t,z)(辖域扩充),6.熟练掌握谓词逻辑推理.1).注意使用ES、US、EG、UG的限制条件,特别是ES,UG2).对于同一个客体变元,既有带也有带的前提,去量词时,应先去后去,这样才可以特指同一个客体 c.3).去量词时,该量词必须是公式的最左边的量词,且此量词的前边无任何符号,它的辖域作用到公式末尾。下面的作法是错误的:正确作法:xP(x)xQ(x)P xP(x)xQ(x)P
18、P(c)xQ(x)US xP(x)xQ(x)T E或xP(x)Q(c)ES xP(x)xQ(x)T E实际上x的辖域扩充后 x(P(x)Q(x)T E 量词改成为x P(c)Q(c)ES P(c)Q(c)TE,下面的作法是错误的:正确作法:xP(x)P xP(x)P P(c)US xP(x)T E实际上中量词不是 P(c)ES x而是x xyP(x,y)P xyP(x,y)PxP(x,c)ES yP(c,y)US令P(x,y):y是x的生母,显然是个假命题4).添加量词时,也要加在公式的最左边,(即新加的量词前也无任何符号!)且其辖域作用到公式的末尾。例如下面作法是错误的:xP(x)Q(c)P
19、 xP(x)yQ(y)EG,例如.证明下面推理的有效性.证明:x(A(x)D(x)P A(a)D(a)ES A(a)T I D(a)T I x(A(x)(B(x)C(x)P A(a)(B(a)C(a)US B(a)C(a)T I x(A(x)(C(x)D(x)P A(a)(C(a)D(a)US C(a)D(a)T I C(a)T I B(a)T I A(a)B(a)T I x(A(x)B(x)EG,第三章 集合论初步1.幂集,全集,空集.2.集合的五种运算及相关性质(特别是差集,对称差.)3.应用包含排斥原理.,第三章 集合论初步基本概念:集合与元素,子集与真子集,空集,全集,幂集,并集,交集
20、,相对补集(差集),绝对补集(补集),1空集,全集,幂集 空集:无元素的集合.x是矛盾式.(空集是唯一的)全集E:包含所讨论所有集合的集合.(全集不唯一)xE是永真式 幂 集:由A的所有子集构成的集合.P(A)=X|XA|P(A)|=2|A|2.掌握集合的五种运算及相关性质.AB=x|xAxB xAB xAxB AB=x|xAxB xAB xAxB A-B=x|xAx B xA-B xAxB A=E-A=x|xExA=x|xA xAxA A-B=A BAB=(A-B)(B-A)=x|(xAxB)(xBxA)AB=(AB)-(AB),例1.已知全集E=,AE,计算:a)P()P()=()b)P(
21、A)P(A)=()c)P(E)-P()=()解:a)因为任何集合A,都有 A A=所以 P()P()=b)因为A A,即P(A)P(A)所以 P(A)P(A)=c)P(E)=,=P()=P()=,P(E)-P()=,-,=,例2.令全集E为信息学院的学生的集合,C表示计算机专 业学生的集合,M表示学习了离散数学的学生的集合,D表示学习了数据结构课学生的集合,F表示一年级的学生的集合.用集合的关系式表达下面句子.“学习了离散数学和数据结构课的学生,一定是计算机专业的非一年级的学生”.解.(MD)(CF)例4.在什么条件下,下面命题为真?a)(A-B)(A-C)=A解.(A-B)(A-C)=(AB
22、)(AC)=A(BC)=A(BC)=A-(BC)=A 所以满足此式的充要条件是:ABC=b)(A-B)(A-C)=解.(A-B)(A-C)=A-(BC)=充要条件是:A BCc)(A-B)(A-C)=解.(A-B)(A-C)=(AB)(AC)=A(BC)=A(BC)=A-(BC)=充要条件是:A BCd)(A-B)(A-C)=解.因为 当且仅当A=B,才有AB=所以满足此式的充要条件是:A-B=A-C,*有14位学生参加考试,9位同学数学得了优;5位同学物理得了优;4位同学化学得了优;其中物理和数学都得优的同学有4人;数学和化学都得优的同学有3人;物理和化学都得优的同学有3人;三门都得优的同学
23、有2人;问没有得到优的有多少人?恰有两门得优的同学有多少人?解.令A、B、C分别表示数学、物理、化学得优同学集合.全集为E.于是有|E|=14|A|=9|B|=5|C|=4|AB|=4|AC|=3|BC|=3|ABC|=2|ABC|=|A|+|B|+|C|-|AB|-|BC|-|BC|+|ABC|=9+5+4-4-3-3+2=10 于是得到优的人数是10人.没有得到优的人数是:14-10=4 人恰有两门得优的人数:(|AB|-|ABC|)+(|BC|-|ABC|)+(|BC|-|ABC|)=4-2+3-2+3-2=4,第四章 二元关系1.关系的概念,表示方法.2.二元关系的 性质的定义,熟练掌
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 复习
链接地址:https://www.desk33.com/p-233571.html