离散数学复习资料李京

1离散数学复习资料h第6章集合论本章重点：集合概念，集合的运算，集合恒等式的证明，笛卡儿积.一、重点内容1.集合的概念集合与元素，具有确定的，可以区分的若干事物的全体称为集合，其中的事物叫元素.集合A中元素的个数为集合的元数A.集合的表示方法：列举法和描述法.列举集合的元素，元素不能重复出现，集合中的元素无顺序之分.集合与其元素之间存在属于“”或不属于“”关系.2.集合的关系：包含，子集，集合相等.包含(子集)，若BaAa，则B包含A(或A包含于B)，称A是B的子集，记BA，又AB，则A是B的真子集，记AB.集合相等，若AB，BA，则A＝B.注意：元素与集合,集合与子集，子集与幂集，与()，空集与所有集合等的关系.3.特殊集合：全集、空集和幂集.全集合E，在一个具体问题中，所涉及的集合都是某个集2合的子集，该集合为全集.空集，不含任何元素的集合为空集.空集是惟一的，它是任何集合的子集.集合A的幂集P(A)，有集合A的所有子集构成的集合P(A)=}{Axx.若A＝n,则P(A)=2n.一个集合的幂集就是以这个集合的所有子集（包括它本身和空集）为元素的集合.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，x,y的位置是确定的，不能随意放置.注意：有序对a，bb,a，以a,b为元素的集合{a,b}={b,a}；有序对(a,a)有意义，而集合{a,a}是单元素集合，应记作{a}.笛卡儿积，把集合A，B合成集合A×B，规定A×B＝{x,yxAyB}由于有序对x,y中x,y的位置是确定的，因此A×B的记法也是确定的，不能写成B×A.笛卡儿积也可以多个集合合成，A1×A2×…×An.笛卡儿积的运算性质.一般不能交换.二、实例例3.4设集合A＝{1,2,3,4},B={2,3,5},求BAABBABABA,,,,.解}5,4,3,2,1{BA}3,2{BA}5,4,1{}5{}4,1{)()(}5{}4,1{ABBABAABBA例3.5试证A－(B－C)＝(A－B)(AC)证明方法1对任意x，4)()()()()()()()()~()(CABACBACABAxCxAxBxAxCxBxAxCBxAxCBAx同理，有)()()(CBAxCABAx所以，A－(B－C)＝(A－B)(AC)说明：事实上，方法1的证明，完全是等值过程，可以写作)()()()()()~()(CABAxCxAxBxAxCxBxAxCBxAxCBAx方法2进行恒等推导.两个集合的差集为(B－C)=B交C的补集A－(B－C)＝)~(~CBA（分配律）摩根律)()~()()(~CABACBA=(A－B)(AC)的摩根律非(P且Q)=(非P)或(非Q)非(P或Q)=(非P)且(非Q)例3.6化简))(()))(((ABBACBA解))(()))(((ABBACBAAABAABBAABBACBA))(()))((~())~(~())~(((吸收律例3.7设集合A={a,b},B={1,2,3},C={d},求A×B×C，B×A.5解先计算A×B＝{a,1,a,2,a,3,b,1,b,2,b,3}A×B×C＝{a,1,a,2,a,3,b,1,b,2,b,3}×{d}＝{a,1,d,a,2,d,a,3,d,b,1,d,b,2,d,b,3,d}B×A＝{1,a,2,a,3,a,1,b,2,b,3,b}例3.8设集合A＝{1,2},求A×P(A).解P(A)={,{1},{2},{1,2}}A×P(A)＝{1,2}×{,{1},}{2},{1,2}={1,,2,,1,{1},2,{1},1,{2},2,{2},1,{1,2},2,{1,2}}第7、8章二元关系与函数本章重点：关系概念与其性质，等价关系和偏序关系，函数.一、重点内容1.关系的概念包括定义、关系的表示方法：集合表示、矩阵表示、图形表示.二元关系，是一个有序对集合，设集合A,B，},{ByAxyxR，记作xRy二元关系的定义域：Dom(R)A；二元关系的值域：Ran(R)B6关系的表示方法：集合表示法：关系是集合，有类似于集合的表示方法.列举法，如R＝{1,1,1,2}；描述法：如},{ByAxyxR关系矩阵：RA×B，R的矩阵njmibRaRbarrMjijiijnmijR,...,2,1,...,2,101,)(关系图：R是集合上的二元关系，若aI,bjR，由结点aI画有向弧到bj构成的图形.2.几个特殊的关系空关系；唯一是任何关系的子集的关系.全关系AAAbabaEA},,{恒等关系},{AaaaIA，MI是单位矩阵.3.关系的运算关系的集合运算，有并、交、补、差和对称差.复合关系},,,{2121RcbRbabcaRRR使，有复合关系矩阵：21RRRMMM(布尔运算)，有结合律：(RS)T＝R(ST)逆关系},,{1RyxxyR，TRRMM1，(RS)－1=S－1R－1.4.关系的性质自反性RxxAx,,；矩阵RM的主对角线元素全为1；关系图的每个结点都有自回路.7反自反性RxxAx,,；矩阵RM的主对角线元素全为0；关系图的每个结点都没有自回路.对称性若Ryx,，则Rxy,；矩阵RM是对称矩阵，即jiijrr；关系图中有向弧成对出现,方向相反.反对称性若Ryx,且Rxy,，则x=y或若yxRyx,,，则Rxy,；矩阵RM不出现对称元素.传递性若Rba,且Rcb,，则Rca,；在关系图中，有从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二元运算的并、交、补、差、逆、复合具有的性质表运算关系性质自反性反自反性对称性反对称性传递性R－1R1R28R1R2R1－R2R1R2IA由表可见，IA具有自反性，对称性、反对称性和传递性.EA具有自反性，对称性和传递性.故IA，EA是等价关系.具有反自反性、对称性、反对称性和传递性。是偏序关系.关系性质的判定，可以用定义、关系矩阵或关系图.传递性的判定，难度稍大.也常如下判定：不破坏传递性的定义，可认为具有传递性.例如可认为具有传递性，同时具有对称性和反对称性，但是不具有自反性；5.关系的闭包设R是非空集合A上的二元关系，在关系R中，添加最少的有序对，新关系用R表示，使得R具有关系的自反(对称、传递)性质，R就是R的自反(对称、传递)闭包，记作r(R)，s(R)和t(R)。闭包的求法：定理12：AIRRr)(；定理13：1)(RRRs；定理14的推论：niiRRt1)(6.等价关系和偏序关系极大(小)元、最大(小)元问题等价关系和偏序关系是具有不同性质的两个关系.9偏序关系等价关系传递性反对称性对称性自反性等价关系图的特点：每一个结点都有一个自回路；两个结点间如有有向弧线，则是双向弧线，如果从a到b，从b到c各有一条有向弧线，则从a到c一定有有向弧线。等价类，若R是等价关系，与R中的某个元素等价的元素组成的集合，就是R的一个等价类，[a]R={bbAaRb}.偏序集的哈斯图偏序集概念和偏序集的哈斯图。哈斯图的画法：(1)用空心点表示结点，自环不画；(2)若ab，则结点b画在上边，a画在下边，并画a到b的无向弧；(3)若a,b,b,c,则a,cR，此时，a到c的有向弧不画出.确定任一子集的最大(小)元，极大(小)元.极大(小)元、最大(小)元、界一个子集的极大(小)元可以有多个，而最大(小)元若有，只能惟一.且极元、最元只在该子集内；而上界与下界可在子集之外确定，最小上界是所有上界中最小者，最小上界再小也不会小于子集中的任一元素；可以与某一元素相等，最大下界也是同样.7.函数函数,设f是集合A到B的二元关系，aA,bB,且a,bf，且Dom(f)=A，f是一个函数(映射).函数是一种特殊的关系.集合A×B的任何子集都是关系，但不一定是函数.函数要求对于定义域A中每一个元素a，B中有且仅有一个元素与a对应，10而关系没有这个限制.二函数相等是指：定义域相同，对应关系相同，而且定义域内每个对应值都相同.函数的类型单射若)()(2121afafaa满射f(A)=B.即)(,,xfyAxBy使得双射单射且满射.复合函数,:,:,:CAgfCBgBAf则即))(()(xfgxgf.复合成立的条件是：)(Dom)(Rangf一般fggf，但)()(hgfhgf复合函数的性质：如果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},)(,,{1AabafBbabf，fffggf11111)(,)(二、实例例4.4试判断图4－2中关系的性质：11111232323(a)(b)(c)图4－2例4.4图解图4－2中(a)的关系在集合{1,2,3}上是对称的，因为结点1与2，1与3之间的有向弧是成对出现且方向相反.图4－2中(b)是反自反的，因为每个结点都没有自回路.它也是反对称的，因为两条边都是单向边，它又是传递的，容易求出R＝{2,1,3,1},满足RR=R.图4－2中(c)的关系自反的，反对称的、但不是传递的.因为2到1有边，1到3有边，但2到3没有边.例4.6设集合A＝{a,b,c,d},定义R＝{a,b,b,a,b,c,c,d},求r(R),s(R),t(R).解求自反闭包，R不具有自反性，由自反性的定义，只需在R上添加IA，于是r(R)=RIA={a,a,a,b,b,a