离散总复习.ppt

1、Fundamental of Discrete Mathematics,离散数学基础（电子版）,北京交通大学 ,总 复 习,第一章 命题逻辑,数理逻辑：研究一种形式语言，其本质是将数学中的逻辑证明加以符号化，因而推动各数学分支的迅速发展。,命题：表示判断的具有确定真值的陈述句。,命题只要能判断真假，不一定已知真假 非陈述性语句不是命题 方程不是命题 悖论不是命题,联结词,否定 合取 析取： 条件 双条件：,翻译提示： 不可兼或： (P Q ) 当 P则Q(如果P，那么Q) : P Q P仅当 Q(仅当Q，则P) : P Q 除非P否则Q： P Q 只要，就有： P Q 只有，才能： Q P 定

2、义一般翻译为双条件,优先级： 高 低,1、只有你主修计算机科学或者不是新生，才能从校园内 访问因特网。2、除非你已满16周岁，否则只要你身高不足4英尺就不能乘公园滑行铁道。3、只要充分考虑一切论证，就能得到可靠见解。4、只有充分考虑一切论证，才能得到可靠见解。5、我们不能既唱歌又看书。6、如果天下雨，我出不出去看你是否同意而定。7、我唱歌，仅当你伴奏。8、或者你没有给我写信，或者信在路上丢失了。9、如果天下雨，我就在家看书，否则我就去看电影。10、只有你考试不及格或者缺考，才能参加补考。11、除非你缺考，否则只要你考试不满60分就必须参加 补考。,推理理论,P规则 T规则 证明方法： 直接证法

3、 反证法 CP规则(CP规则可以连续使用) 1、 A B C D , DE F A F 2、 PQ, QR, R S PS 3、 P (QR) ,Q P, S R P S 4、A(BC),(CD) E, F (D E) A(BF),原子命题拆成：客体 谓词 全称量词：“”，存在量词：“” 翻译注意： 特性谓词的位置：在全称量词的作用域内作条件句的前件，在存在量词的作用域内作合取项。 1、所有的人都犯错误。2、有且仅有一个偶质数。3、有些人对所有酒都感兴趣。4、所有的人都对某些酒感兴趣。5、尽管有人可恶，但并不是所有的人都可恶。6、对于任意实数，存在更大的实数。7、某些火车比所有飞机慢，但至少有

4、一架飞机比所有火车快。 8、并非所有的人都喜欢喝酒。,第二章 谓词逻辑,量化断言与命题的关系,假设个体域D=a1, a2，an (x) (P(x) P(a1) P(a2) P(an) ( x)(P(x) P(a1) P(a2) P(an),谓词演算的推理理论,消去、添加量词规则 全称指定 US 全称推广 UG 存在指定 ES 存在推广 EG,在谓词推理中，必须注意的两点：,不能在量词的作用域内使用等价式和蕴含式 在同一证明中，若既要使用存在指定，又要使用全称指定，则先用存在指定，后用全称指定。,谓词推理理论,P规则、T规则、 US、UG、ES、EG 证明方法：直接证法 反证法 CP规则 1、(

5、x)(P(x) Q(x) (x)P(x) (x)Q(x) 2、( x)A(x) (x)B(x) (x)(A(x) B(x) 3、(x)P(x) (x)(P(x)Q(x) R(x), (x)P(x),(x)Q(x) (x)(y)(R(x) R(y) 4、(x) (A(x)B(x) (x)A(x)(x)B(x) 5、 ( x)(F(x) S(x) (y)(M(y) W(y), (y)(M(y) W(y) (x)(F(x) S(x) 6、(x)(F(x)H(x), (x)(G(x)H(x) (x)(G(x) F(x),第三章 集合与关系,定理 集合A和B相等的充分必要条件是这两个集合互为子集。 集合

6、的运算 、 、(相对补)、 (绝对补)、 (对称差) 运算的性质 序偶与笛卡儿积 1、若C ， 则 AB ACBC 2、设A,B为两个集合，若AB ，则 (AB)(AB)(AA)(BB) 3、证明 P(A)P(B)=P(AB) 4、设A和B是论域E的子集， B=A AB=EAB= ,关系性质的证明方法：,要证明R在X上自反 假设xX ，证出 R 要证明R在X上对称 对x,y X,设R ，证出 R 要证明R在X上传递 对x,y,zX,设R R ，证出 R 要证明R在X上反自反 假设xX，证出 R ） 要证明R在X上反对称 对x,yX，设RR ，证出 xy,关系的性质 自反、对称、传递、反自反、反

7、对称,关系的的运算：, 、 、(相对补)、 (绝对补)、 (对称差) 关系的复合、关系的逆、关系的闭包运算,集合的划分与覆盖,等价关系与等价类及其性质,序关系：,偏序关系、哈斯图、极大元、极小元、最大元、最小元、上界、下界、上确界、下确界,划分可以确定一个等价关系 覆盖可以确定一个相容关系,1、设R是集合X上的一个自反关系。则R是对称和传递的，当且仅当RR，有在R之中。 2、若关系R和S在集合X上是等价的，证明RS也是等价的。 3、如果关系R在集合X上是等价的，证明Rc也是等价的。 4、设R是集合A上的等价关系，则对于所有a,b A ，或者aR=bR或者aR bR= 。 5、设集合A有一个划分

8、S=S1,S2,Sm，试由此划分确定一 个等价关系。 6、设S是X上的二元关系，S是传递的当且仅当S S S。 7、设R是X上的二元关系，则: a）R是对称的，当且仅当R=Rc b）R是反对称的，当且仅当R R c Ix,第四章 函数,函数的概念 入射、满射、双射 逆函数(当f 是双射函数时逆函数才有意义。) 复合函数(注意写法与关系的复合不同。) 求gof时，若ranf 不包含于 domg，则gof为空 1、令gof是一个复合函数，则 (1)若g 和f 是满射的,则 gof 是满射的； (2)若g 和f 是入射的,则 gof 是入射的； (3)若g 和f 是双射的,则 gof 是双射的。 2

9、、令gof是复合函数，则 (1)若gof 是满射的,则g是满射的； (2)若gof 是入射的,则f是入射的； (3)若gof 是双射的,则g是满射的，f是入射的。,第五章 代数系统,运算的性质(封闭性、交换性、结合性、分配律、吸收律、等幂律) 特殊元素(幺元、零元、逆元) 广群、半群、独异点、群和子群 阿贝尔群和循环群,设是一个半群，如果S是一个有限集，则必有 对于bS , b*bS，记b2=b*b b2*b=b*b2S，记b3=b2*b=b*b2 由于S是有限集，所以必存在 ji，使得bi=bj ,证明方法举例：,证明a是b的逆元? a * b= b * a =e例如：(a * b)-1=b

10、-1 * a-1,群中满足消去律 群中不可能有零元。 任何一个循环群必定是阿贝尔群。 群中的幺元 e 必定也是其子群中的幺元。 子群的判定定理：当是有限集： *在上封闭 当是无限集： a，bS， 有a*b-1S 任何质数阶的群必定是循环群。,陪集与拉格朗日定理 设是群 的一个子群，aG，则集合aH称为由a所确定的H在G中的左陪集，记为aH。 拉格朗日定理。,1、设是一个半群，如果S是一个有限集，则必有aS，使得a*a=a。 2、设是一个群，B是G的非空子集，如果B是一 个有限集，那末只要运算*在B上封闭，必定是的子群。 3、设是群，S是G的非空子集，如果对于S中的任意元素a和b有a*b-1S，

11、则是的子群。 4、设是有限的可交换独异点，且对任意的a,b,cS，等式 a*b=a*c 蕴含着 b = c，证明是阿贝尔群。 5、设是一个群，是阿贝尔群的充要条件 是对任意的a,bG，有(a*b)*(a*b)=(a*a)*(b*b),6、设是群的子群， A=x|xG , x*H*x-1=H，证明是的一个子群。 7、设是群的子群， aH和bH是H在G中的任意两个左陪集，证明：或者aH=bH，或者aHbH=。 8、若是半群，e是左幺元且对每一个xA，存在x1A使得x1 * x = e。 a)证明：对于任意的a，b，cA，如果a*ba*c，则bc。 b)通过证明e是中的幺元，证明是群。 9、证明：循

12、环群的同态象必定是循环群。,每个图中结点度数的总和等于边数的两倍。 deg(v)= 2|E| 在任何有向图中，所有结点的出度之和等于所有结点的入度之和。 无向图的连通性：连通性是结点集合上的一种等价关系。 点割集、边割集 有向图的可达性：强连通=单侧连通弱连通 强分图、单侧分图、弱分图 在有向图G=中，它的每一个结点位于且只位于一个强分图中。,第七章 图论,欧拉图与汉密尔顿图,给定无孤立结点图G ，若存在一条回路，经过图中的每边一次且仅一次，该回路为欧拉回路。具有欧拉回路的图，称为欧拉图。 无向图G具有一条欧拉回路当且仅当G是连通的，且所有结点度数全为偶数。 给定图G，若存在一条回路，经过图中

13、每个结点恰好一次，这条回路称为汉密尔顿回路。具有哈密尔顿回路的图，称为汉密尔顿图。,平面图,一个有限平面图，面的次数之和等于其边数的两倍。 设有一个连通的平面图G，共有v个结点e条边和r个面，则欧拉公式vr成立。 设是一个有个结点条边的连通简单平面图， 若v3，则v。,树与生成树,一个连通且无回路的无向图称为树。 一个无回路的无向图称作森林 任一树中，有e=v-1。 任一棵树中至少有两片树叶。 连通图至少有一颗生成树。,以下关于树的定义是等价的：,最小生成树的生成算法：,避回路法 破圈法,无回路的连通图。 无回路且e=v-1，其中e是边数，v是结点数。 连通且e=v-1。 无回路，但增加一条新边，得到一个且仅有一个回路。 连通，但删去任一边后便不连通。 每一对结点之间有一条且仅有一条路。,1、证明在任何有向完全图中，所有结点入度的平方之和等于所有结点出度的平方之和。 2、一个连通无向图G中结点v为割点的充分必要条件是存在两结点u,w，使得u和w之间每一条路都经过v。 3、设G是11个或更多结点的图，证明G或 是非平面图。 4、证明在有向图G中，它的每一个结点位于且仅位于一个强分图中。,5、一个连通无向图G中结点v是割点的充分必要条件是存在两个结点u和w，使得结点u和w的每一条路都通过v。 6、任一棵树中至少有两片树叶。 7、当且仅当连通图的每