离散数学复习资料李京.doc

1离散数学复习资料 h第 6 章 集合论 本章重点：集合概念，集合的运算，集合恒等式的证明，笛卡儿积. 一、重点内容1. 集合的概念 集合与元素，具有确定的，可以区分的若干事物的全体称为集合，其中的事物叫元素.集合 A 中元素的个数为集合的元数A.  集合的表示方法：列举法和描述法. 列举集合的元素，元素不能重复出现，集合中的元素无顺序之分. 集合与其元素之间存在属于“”或不属于“” 关系.2. 集合的关系：包含，子集，集合相等.  包含(子集) ，若 BaA，则 B 包含 A(或 A 包含于 B)，称 A 是 B 的子集，记 ，又 AB，则 A 是 B 的真子集，记AB. 集合相等，若 AB，B A，则 A＝B. 注意：元素与集合,集合与子集，子集与幂集， 与 ()，空集  与所有集合等的关系.3. 特殊集合：全集、空集和幂集. 2 全集合 E，在一个具体问题中，所涉及的集合都是某个集合的子集，该集合为全集.  空集 ，不含任何元素的集合为空集. 空集是惟一的，它是任何集合的子集.  集合 A 的幂集 P(A)，有集合 A 的所有子集构成的集合P(A)= }{x. 若A＝n, 则P(A)=2 n. 一个集合的幂集就是以这个集合的所有子集（包括它本身和空集）为元素的集合.4. 集合的运算  集合 A 和 B 的并 AB，由集合 A 和 B 的所有元素组成的集合. 集合 A 和 B 的交 AB，由集合 A 和 B 的公共元素组成的集合. 集合 A 的补集 A，属于 E 但不属于集合 A 的元素组成的集合， A. 补集总相对于一个全集 .  集合 A 与 B 的差集 A－B，由属于 A，而不属于 B 的所有元素组成的集合.. 集合 A 与 B 的对称差 AB，A B＝(A－B)( B－A)或AB＝）A B〕－（A B） 应该很好地掌握 10 条运算律(运算的性质)(教材 P71～72)，即交换律、结合律、分配律、幂等律、同一律、零律、补余律、吸收律、摩根律和双补律等. 5. 恒等式证明 3集合运算部分有三个方面的问题：其一是进行集合的运算；其二是集合运算式的化简；其三是集合恒等式的推理证明. 集合恒等式的证明方法通常有二：(1)要证明 A＝B，只需要证明 AB，又 AB；(2)通过运算律进行等式推导. 6. 有序对与笛卡儿积 有序对，就是有顺序的数组，如，x,y 的位置是确定的，不能随意放置.注意：有序对，以 a,b 为元素的集合{a,b}={b,a} ；有序对(a,a )有意义，而集合 {a,a}是单元素集合，应记作{ a}.  笛卡儿积，把集合 A，B 合成集合 A×B，规定A×B＝ {xAyB}由于有序对中 x,y 的位置是确定的，因此 A×B 的记法也是确定的，不能写成 B×A. 笛卡儿积也可以多个集合合成，A 1×A2×…×An. 笛卡儿积的运算性质. 一般不能交换.二、实例例 3.4 设集合 A＝{1,2,3,4},B ={2,3,5},求BA,,,. 解 }5,4321{ }3,2{}5,41,)()(, ABA例 3.5 试证 A－(B－C)＝(A －B) (AC)证明 方法 1 对任意 x，4)()()( )()(~)(CABCA CABxxx同理，有 )()()(xx所以，A － (B－C)＝(A －B) (AC)说明：事实上，方法 1 的证明，完全是等值过程，可以写作 )()()()(~CABxCAxBAx 方法 2 进行恒等推导. 两个集合的差集为 (B－C )=B 交 C 的补集A－ (B－C)＝ )~(BA（ 分 配 律 ）摩 根 律)()( )(C=(A－B)(AC)的摩根律非(P 且 Q)=(非 P)或(非 Q)非(P 或 Q)=(非 P)且(非 Q)例 3.6 化简 )()(ABCBA解 ()(ABA)()(~)~吸 收 律例 3.7 设集合 A={a,b},B={1,2,3},C={d},求 A×B×C，B×A. 5解 先计算 A×B＝ {,,,,,}A×B×C＝{,,,,,}×{d}＝{,d>,, d>,,d>,,d>,,d>,,d>}B×A＝{,,,,,}例 3.8 设集合 A＝{1,2},求 A×P(A). 解 P(A)={,{1},{2},{1,2}}A×P(A)＝{1,2} ×{,{1},}{2},{1,2}={,,,,,,,}第 7、8 章 二元关系与函数 本章重点：关系概念与其性质，等价关系和偏序关系，函数. 一、重点内容1. 关系的概念 包括定义、关系的表示方法：集合表示、矩阵表示、图形表示. 二元关系，是一个有序对集合，设集合 A,B，},{ByAxyR， 记作 xRy二元关系的定义域：Dom(R ) A； 二元关系的值域：Ran(R)6B 关系的表示方法：集合表示法：关系是集合，有类似于集合的表示方法. 列举法，如 R＝{,}；描述法：如},{ByAxyR关系矩阵： RA×B， R 的矩阵 njmibRarMiijnmijR ,.2101,)(关系图： R 是集合上的二元关系，若 R，由结点 aI画有向弧到 bj 构成的图形.2. 几个特殊的关系空关系 ；唯一是任何关系的子集的关系. 全关系 AbaEA},{恒等关系 I，M I 是单位矩阵. 3. 关系的运算 关系的集合运算，有并、交、补、差和对称差. 复合关系 },,,{ 2121 RcbabcaR使 ，有复合关系矩阵： 21RM(布尔运算 )，有结合律：(RS)T＝R( ST) 逆关系 },,{1yx ， TR1，(R S)－1 =S－1 R－ 1. 4. 关系的性质 自反性 RxA,；矩阵 RM的主对角线元素全为71；关系图的每个结点都有自回路. 反自反性 RxA,；矩阵 RM的主对角线元素全为0；关系图的每个结点都没有自回路. 对称性 若 yx,，则 xy,；矩阵 R是对称矩阵，即 jiijr；关系图中有向弧成对出现,方向相反. 反对称性 若 Ryx,且 xy,，则 x=y 或若yxRy,,，则 x,；矩阵 M不出现对称元素. 传递性 若 Rba,且 c,，则 ca,；在关系图中，有从 a 到 b 的弧，有从 b 到 c 的弧，则有从 a 到 c 的弧. 判断传递性较为困难.可以证明：R 是集合 A 上的二元关系，(1) (1)R 是自反的 IAR; (2)R 是反自反的IAR＝ ;(3)R 是对称的 R＝R －1 ； (4)R 是反对称的RR－1 IA；(5)R 是传递的 RRR. 关系的性质所具有的运算见表 4－1. 表 4－1 二元运算的并、交、补、差、逆、复合具有的性质表运算 关系性质自反性反自反性对称性反对称性传递性8R－1     R1R2     R1R2     R1－ R2     R1R2     IA        由表可见，I A具有自反性，对称性、反对称性和传递性.E A具有自反性，对称性和传递性.故 IA，EA是等价关系.  具有反自反性、对 称性、反对称性和传递性。

 是偏序关系.关系性质的判定，可以用定义、关系矩阵或关系图. 传递性的判定，难度稍大. 也常如下判定：不破坏传递性的定义，可 认为具有传递性. 例如  可认为具有传递性，同时具有对称性和反对称性，但是不具有自反性； 5. 关系的闭包设 R 是非空集合 A 上的二元关系，在关系 R 中，添加最少的有序对，新关系用 R表示，使得 R具有关系的自反(对称、传递) 性质， R就是 R 的自反( 对称、传递)闭包，记作 r(R) ，s( R)和 t(R)闭包的求法：定理 12： AIr；定理 13： 1)(Rs；定理 14 的推论：nit1)(96. 等价关系和偏序关系 极大(小) 元、最大(小) 元问题 等价关系和偏序关系是具有不同性质的两个关系. 偏 序 关 系等 价 关 系传 递 性反 对 称 性对 称 性自 反 性 等价关系图的特点：每一个结点都有一个自回路；两个结点间如有有向弧线，则是双向弧线，如果从 a 到 b，从 b 到 c各有一条有向弧线，则从 a 到 c 一定有有向弧线 等价类，若 R 是等价关系，与 R 中的某个元素等价的元素组成的集合，就是 R 的一个等价类，[a] R={bbAaRb}.  偏序集的哈斯图 偏序集概念和偏序集的哈斯图。

哈斯图的画法：(1) 用空心点表示结点，自环不画；(2) 若 ab，则结点 b 画在上边，a 画在下边，并画 a 到 b 的无向弧；(3) 若,,则R，此时，a 到 c 的有向弧不画出.确定任一子集的最大(小) 元，极大(小)元 .极大(小)元、最大(小)元、界 一个子集的极大(小)元可以有多个，而最大(小)元若有，只能惟一. 且极元、最元只在该子集内；而上界与下界可在子集之外确定，最小上界是所有上界中最小者，最小上界再小也不会小于子集中的任一元素；可以与某一元素相等，最大下界也是同样.7. 函数 函数, 设 f 是集合 A 到 B 的二元关系，a A,bB,且f，且 Dom(f)=A，f 是一个函数(映射). 函数是一种特殊的关系.10集合 A×B 的任何子集都是关系，但不一定是函数. 函数要求对于定义域 A 中每一个元素 a，B 中有且 仅有一个元素与 a 对应，而关系没有这个限制. 二函数相等是指：定义域相同，对应关系相同，而且定义域内每个对应值都相同.  函数的类型单射 若 )(2121affa满射 f(A)=B. 即 )(,,xfyAxy使 得双射 单射且满射.  复合函数 ,:,:,: Cgfgf 则 即 )()(xfgf. 复合成立的条件是： )(Dom)(Ran一般 fgf，但 )(hgff复合函数的性质： 如果 f,g 都是单射的，则 fg 是单射的； 如果 f,g 都是满射的，则 fg 是满射的；如果 f,g 都是双射的，则 fg 是双射的； 如果 f,g 是单射的，则 f 是单射的；如果 f,g 是满射的，则 g 是满射的；如果 f,g 是双射的，则 f 是单射的，g 是满射的.  反函数 若 f：AB 是双射，则有反函数 f－1 ：BA},)(,,{1 abbaf ， fffgf 11)(,)(二、实例11例 4.4 试判断图 4－2 中关系的性质： 1  1  12  3 2   3 2  3 (a) (b) (c) 图 4－2 例 4.4 图解 图 4－2 中(a)的关系在集合{1,2,3} 上是对称的，因为结点 1 与 2，1 与 3 之间的有向弧是成对出现且方向相反. 图 4－2 中(b) 是反自反的 ，因为每个结点都没有自回路. 它也是反对称的，因为两条边都是单向边，它又是传递的，容易求出 R＝{,},。