离散数学复习辅导之一

1离散数学复习辅导之一第1章关系与函数一、主要内容1．有序对与笛卡儿积有序对，就是有顺序的数组，如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.笛卡儿积的运算性质.一般不能交换.2．关系的概念包括定义、关系的表示方法：集合表示、矩阵表示、图形表示.二元关系，是一个有序对集合，设集合A，B，从集合A到B的二元关系},{ByAxyxR，记作xRy．二元关系的定义域：Dom(R)A；二元关系的值域：Ran(R)B关系的表示方法：集合表示法：关系是集合，有类似于集合的表示方法.列举法，如R＝{1,1,1,2}；描述法：如},{ByAxyxR关系矩阵：RA×B，R的矩阵njmibRaRbarrMjijiijnmijR,...,2,1,...,2,101,)(关系图：R是集合上的二元关系，若aI,bjR，由结点aI画有向弧到bj构成的图形.3．几个特殊的关系空关系；唯一是任何关系的子集的关系.全关系AAAbabaEA},,{恒等关系},{AaaaIA，MI是单位矩阵.4．关系的运算关系的集合运算，有并、交、补、差和对称差.复合关系},,,{2121RcbRbabcaRRR使，有复合关系矩阵：21RRRMMM(布尔运算)，有结合律：(RS)T＝R(ST)逆关系},,{1RyxxyR，TRRMM1，(RS)－1=S－1R－1.5．关系的性质自反性RxxAx,,；矩阵RM的主对角线元素全为1；关系图的每个结点都有自回路.反自反性RxxAx,,；矩阵RM的主对角线元素全为0；关系图的每个结点都没有自回路.对称性若Ryx,，则Rxy,；矩阵RM是对称矩阵，即jiijrr；关系图中有向弧成对出现,方向相反.2反对称性若Ryx,且Rxy,，则x=y或若yxRyx,,，则Rxy,；矩阵RM不出现对称元素.传递性若Rba,且Rcb,，则Rca,；在关系图中，有从a到b的弧，有从b到c的弧，则有从a到c的弧.判断传递性较为困难.可以证明：R是集合A上的二元关系，(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R1R2R1－R2R1R2IA由表可见，IA具有自反性，对称性、反对称性和传递性.EA具有自反性，对称性和传递性.故IA，EA是等价关系.具有反自反性、对称性、反对称性和传递性．是偏序关系.关系性质的判定，可以用定义、关系矩阵或关系图.6.关系的闭包设R是非空集合A上的二元关系，在关系R中，添加最少的有序对，新关系用R表示，使得R具有关系的自反(对称、传递)性质，R就是R的自反(对称、传递)闭包，记作r(R)，s(R)和t(R)．闭包的求法：定理12：自反闭包AIRRr)(；定理13：对称闭包1)(RRRs；定理14的推论：传递闭包niiRRt1)(7.等价关系、相容关系和偏序关系等价关系、相容关系和偏序关系是具有不同性质的两个关系.？性自反性性相容系等价系性偏序系反性等价关系图的特点：每一个结点都有一个自回路；两个结点间如有有向弧线，则是双向弧线，如果从a到b，从b到c各有一条有向弧线，则从a到c一定有有向弧线．等价类，若R是等价关系，与R中的某个元素等价的元素组成的集合，就是R的一个等价类，[a]R={bbAaRb}.相容类，设B是A的子集，如果在B中的任意两个元素都是相关的，则称为由相容关系R产生的相容类．3偏序集的哈斯图偏序集概念和偏序集的哈斯图．哈斯图的画法：(1)用空心点表示结点，自环不画；(2)若ab，则结点b画在上边，a画在下边，并画a到b的无向弧；(3)若a,b,b,c,则a,cR，此时，a到c的有向弧不画出.确定任一子集的最大(小)元，极大(小)元.极大(小)元、最大(小)元、界一个子集的极大(小)元可以有多个，而最大(小)元若有，只能惟一.且极元、最元只在该子集内；而上界与下界可在子集之外确定，最小上界是所有上界中最小者，最小上界再小也不会小于子集中的任一元素；可以与某一元素相等，最大下界也是同样.8.函数函数,设f是集合A到B的二元关系，aA,bB,且a,bf，且Dom(f)=A，f是一个函数(映射).函数是一种特殊的关系.集合A×B的任何子集都是关系，但不一定是函数.函数要求对于定义域A中每一个元素a，B中有且仅有一个元素与a对应，而关系没有这个限制.二函数相等是指：定义域相同，对应关系相同，而且定义域内每个对应值都相同.函数的类型单射若)()(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)(,)(二、实例例1设给定集合A＝{a,b}，写出P(A)和P(A)上的包含关系的集合表达式．解}},{},{},{,{)(babaAP}},{},{,},{},{,},{,,}{,,}{,{babbaababa例2设A＝{1,2,3},用列举法给出A上的恒等关系IA，全关系EA，A上的小于关系},,{yxAyxyxLA及其逆关系和关系矩阵.解}3,3,2,2,1,1{AIAAIE},2,3,1,3,3,2,1,2,3,1,2,1{}3,2,3,1,2,1{AL,LA的逆关系}2,3,1,3,1,2{1AL000100110ALM0110010001ALM.有TLLAAMM1例3设集合A={a,b,c}，A上的二元关系4R＝{a,a,a,b,b,c,c,b}，S={a,c,b,c,c,c}求RS，并用关系矩阵验证．解RS＝{a,a,a,b,b,c,c,b}{a,c,b,c,c,c}＝{a,c,b,c,c,c}100100100,010100011SRMM,100100100100100100010100011SRM，从矩阵也可得RS＝{a,c,b,c,c,c}例4设R和S是集合A＝{1,2,3}上的二元关系，R＝{1,1,1,2,2,3,3,1,3,3}S={1,2,1,3,2,1,3,3}求RS和S2以及M2S．解RS={1,1,1,2,2,3,3,1,3,3}{1,2,1,3,2,1,3,3}=}3,3,2,3,3,2,1,1,3,1,2,1{S2=SS={1,2,1,3,2,1,3,3}{1,2,1,3,2,1,3,3}=}3,3,3,2,2,2,3,1,1,1{100110101SSM例5设R是实数集，R上的二元关系S为S＝{x,yx,yRx=y}试问二元关系S具有哪些性质？简单说明理由．解12.S具有自反性，显然x,xS；S具有对称性，x,yS，有x=y，则y,xS；S具有反对称性，x,y,y,xS，有x=y；S具有传递性，x,y,y,zS,因为x=y=z，故x,zS．例6设集合A1,2,3,4,A上的二元关系R1,2,3,2,2,3,3,4（1）求出R2，R3的集合表达式；（2）画出R2的关系图．解(1)R2={1,3,2,2,3,3,2,4}R3={1,2,1,4,3,2,3,4,2,3}(2)R2的关系图如例6图例7设集合A＝{a,b,c,d,e}，定义A上的二元关系AIdeedabbaR},,,,,,,{1},,,,,,,,,,,{2edddccbbabbaR判断R1，R2是否为等价关系？分析判断等价关系，就是验证是否具有自反性、对称性和传递性.解写出R1的关系矩阵，1243例6图R2的关系图511000110000010000011000111RM由关系矩阵可知，R1具有自反性和对称性.由关系图(例7图)可知它具有传递性，故R1是等价关系.R2不是等价关系，因为)),((),(22ReeRaa或，故R不具有自反性.注意：自反性，对称性和传递性之一不具备，就是破坏了等价关系的定义.事实上22,,,RdeRed但，故R2不具有对称性；2,Rab，2,Raa但，R2也不具有传递性.对例7的R1进行分类：元素a，因为bbabbaaa,,,,,,,均属于R1，所以a生成的等价类},{][1baaR或记作1][Rb.元素c，因为1,Rcc，所以c生成的等价类}{][1ccR;类似地，d生成的等价类},{][1eddR＝1][Re.例8设集合A＝{0，1，2，3，4，5，6}上的偏序关系R如下：R＝{0,1,0,20,3,0,4,0,5,0,6,2,5,3,5，4,6}IA做偏序集A,R的哈斯图，并求B={0,2,3}的极大元、极小元、最大元和最小元，B的上界和最小上界，下界和最大下界．解A＝{0,1,2,3,4,5,6},B={0，2，3}，哈斯图如例8图所示．B的极大元：2，3,B的极小元：0B的最大元：无B的最小元：0B的上界为5，最小上界也是5；B的下界和最大下界均为0．若C＝{0,3}，那么C的上界为5，3，最小上界为3．若D＝{4,6}，那么D的上界和最小上界为6，下界为0，4，最大下界为4．再强碉一下，子集B的极大(小)、最大(小)元，一定是B的元素；而B的界可以不是B的元素，只要是所讨论的集合A的元素即可．例9已知如图，集合A上的关系，请回答下列问题：111111222222333333444444fgh例9图求：(1)f,g,