2022年系统分析师复习资料.docx

精选学习资料 - - - - - - - - - 学习必备 欢迎下载系统分析员考试复习数学运算机数学基础 1 第三单元辅导 . 1五种性质的定义 . 1欧拉图 . 26哈密顿图 . 26平面图 . 27运算机数学基础 1 第三单元辅导五种性质的定义我们已经看到,在一个很小的集合上就可以定义许多个不同的关系；但是真正有实际意义的只是其中很少的一部分,它们一般都是有着某些性质的关系；设 R 是集合 A 上的关系, R 的性质主要有以下五种：称性 和传递性 ；1 自反性集合 A 上的关系 R,我们说它是自反的,就是自反性 、反自反性 、对称性 、反对为真；也就是说,假如命题“ 对于A 中的任意元素x,都在 R 中” 为真,就R 是自反的；2 反自反性集合 A 上的关系 R,我们说它是反自反的,就是为真；也就是说,如果命题“ 对于A 中的任意元素x,都不在 R 中” 为真,就R 是反自反的；3 对称性集合 A 上的关系 R,我们说它是对称的,就是为真；也就是说,如果命题“ 对于A 中的任意元素x 和 y,如就必有” 为真,就 R 是对称的；4 反对称性集合 A 上的关系 R,我们说它是反对称的,就是且为真；也就是说,假如命题“ 对于A 中的任意元素x 和 y,如就必有”为真,就 R 是反对称的；名师归纳总结 - - - - - - -第 1 页,共 27 页精选学习资料 - - - - - - - - - 由于学习必备欢迎下载,所以,假如等值于对于 A 中的任意两个不相同的元素x 和 y,和不同时在 R 中,就 R 是反对称的；5 传递性集合 A 上的关系 R,我们说它是传递的,就是且为真；也就是说,假如命题“ 对于A 中的任意元素x、y 和 z,如,就必有” 为真,就R 是传递的；4.1 所示；它们的定义及其在关系矩阵、关系图中的特点如表表 4.1 除有以上定义外,仍可以通过集合间的关系来描述关系的五种性质；名师归纳总结 1. 任何集合 A 上的自反关系R 肯定包含了A 上的恒等关系,即；第 2 页,共 27 页2. A 上的反自反关系R 肯定与不交,即；假如且,那么 R 既不是自反的,也不是反自反的；3. A 上的对称关系R 肯定满意等式；4. 反对称关系R 就满意等式；由此可以知道,假如R 既是对称的,又是反对称的,就；- - - - - - -精选学习资料 - - - - - - - - - 学习必备欢迎下载；5. 关于传递关系 R,它满意的条件是本单元重点 ：关系概念与其性质,等价关系和偏序关系,函数. 图的概念,握手定理,通路、回路以及图的矩阵表示 .一、重点内容1. 关系的概念包括定义、关系的表示方法：集合表示、矩阵表示、图形表示B . 二元关系,是一个有序对集合,设集合A,B,Rx,yxAy,记作 xRy 二元关系的定义域：Dom RA ； 二元关系的值域：RanRB关系的表示方法：集合表示法：关系是集合,有类似于集合的表示方法. jB 列举法,如R<1,1>,<1,2> ；描述法：如Rx,yxAy关系矩阵：RA× B,R 的矩阵MRrijmn,rij1aiRbjji,12.,m ,0aiR b,12 ,.,n关系图：R 是集合上的二元关系,如<aI,bj>R,由结点 aI画有向弧到bj 构成的图形 . 2. 几个特别的关系空关系；唯独是任何关系的子集的关系 . 全关系 EA a , b a , b A A A恒等关系 I A a , a a A ,M I 是单位矩阵 . 3. 关系的运算关系的集合运算,有并、交、补、差和对称差 . 复合关系 R R 1 R 2 a , c b 使 a , b R 1 b , c R 2 ,有复合关系矩阵：M R M R 1 M R 2 布尔运算 ,有结合律： R S TR S T 1 T逆关系 R y , x x , y R ,M R 1 M R,R S1=S1 R1. 4. 关系的性质名师归纳总结 自反性xA,x ,xR；矩阵MR的主对角线元素全为1；关系图的每个结点都第 3 页,共 27 页- - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载有自回路 . 反自反性xA,x,xR；矩阵MR的主对角线元素全为0；关系图的每个结点都没有自回路 . 对称性 如 x, y R,就 y, x R；矩阵 M R 是对称矩阵,即 r ij r ji；关系图中有向弧成对显现 ,方向相反 . 反对称性 如 x, y R 且 y, x R,就 x=y 或如 x , y R , x y, 就y, x R；矩阵 M R 不显现对称元素 . 传递性 如 a, b R 且 b, c R,就 a, c R；在关系图中, 有从 a 到 b 的弧,有从 b 到 c 的弧,就有从 a 到 c 的弧 . 判定传递性较为困难 . 可以证明： R 是集合 A 上的二元关系,1 1 R 是自反的 IA R; 2R 是反自反的 IA R; 3R 是对称的 RR 1；4R 是反对称的 R R1IA；5R 是传递的 R R R. 关系的性质所具有的运算见表 41. 表 4 1 二元运算的并、交、补、差、逆、复合具有的性质表运算关系性自反性反自反性对称性反对称性传递性质R1 名师归纳总结 R1R2 第 4 页,共 27 页R1R2 - - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载R1R2 R1 R2 IA 由表可见, IA具有自反性,对称性、反对称性和传递性.EA 具有自反性,对称性和传递性.故 IA,EA 是等价关系 . 具有反自反性、对称性、反对称性和传递性；是偏序关系 . 关系性质的判定,可以用定义、关系矩阵或关系图 .传递性的判定,难度稍大 . 也常如下判定：不破坏传递性的定义,可认为具有传递性 . 例如 可认为具有传递性,同时具有对称性和反对称性,但是不具有自反性；5. 关系的闭包设 R 是非空集合 A 上的二元关系,在关系 R 中,添加最少的有序对,新关系用 R 表示,使得 R 具有关系的自反 对称、 传递 性质, R就是 R 的自反 对称、传递 闭包,记作 rR ,sR和 tR；闭包的求法 ：定理 12：rR RIA；定理 13：s R RR1；定理 14 的推论：tR in1i R6. 等价关系和偏序关系极大 小元、最大 小元问题名师归纳总结 等价关系和偏序关系是具有不同性质的两个关系. 第 5 页,共 27 页自反性对称性传递性等价关系反对称性偏序关系等价关系图的特点：每一个结点都有一个自回路；两个结点间如有有向弧线,就是双向弧线,假如从a 到 b,从 b 到 c 各有一条有向弧线,就从a 到 c 肯定有有向弧线；等价类 ,如 R 是等价关系,与R 中的某个元素等价的元素组成的集合,就是R 的一个等价类, a R= b bA 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,且 Domf=A, f 是一个函数 映射 . 函数是一种特别的关系 .集合 A×B 的任何子集都是关系,但不肯定是函数 . 函数要求对于定义域 A 中每一个元素a,B 中有且仅有一个元素与 a 对应,而关系没有这个限制 . 二函数相等是指：定义域相同,对应关系相同,而且定义域内每个对应值都相同 . 函数的类型单射 如 a 1 a 2 f a 1 f a 2 满射 fA= B. 即 y B , x A , 使得 y f x 双射 单射且满射 . 复合函数 f : A B , g : B C , 就 f g : A C , 即 f g x g f x . 复合成立的条件是：Ran f Dom g 一般 f g g f,但 f g h f g h 复合函数的性质：假如 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 是双射,就有反函数 f1：B Af 1 b , a b B , f a b , a A , f g 1 g 1 f 1 , f 1 1 f二、实例名师归纳总结 例 4.1 设集合 A a,b, R是 PA上的包含关系,写出xR 的表达式和关系矩阵. 第 6 页,共 27 页解 用描述法表示；Rx ,yx ,yP A y 用列举法表示：由于PA ,a ,b ,A ,所以- - - - - - -精选学习资料 - - - - - - - - - R,a ,b 学习必备A欢迎下载a,a, a , A , b , b , b , A , A , A a b 1 1 1 1 A0 1 0 1M R0 0 1 1 图 41 关系矩阵：0 0 0 1,关系图如图 41 例 4.2 设 A1,2,3, 用列举法给出 A 上的恒等关系 I A,全关系 EA,A 上的小于关系L A x , y x , y A x y 及其逆关系和关系矩阵 . 解 I A 1 1, , 2 , 2 , 3 3, E A ,1 2 , ,1 3 , 2 1, , ,2 3 , 1,3 , ,3 2 , I AL A ,1 2 , 3,1 , 2 3, , LA的逆关系 L A 1 ,2 1 , 1,3 , ,3 2 0 1 1 0 0 0M L A 00 00 10 M L A1 11 01 00 . 有 M L A M L TA1例 4.3 设集合 A2,3,4, B=4,6,7, C=8,9,12,14 . R1是由 A 到 B 的二元关系, R2是由 B到 C 的二元关系,定义如下：名师归纳总结 R 1a ,ba 是素数且a 整除b ,R 2b ,cb 整除c 6 , 12,7 14第 7 页,共 27 页求复合关系R 1R 2,并用关系矩阵表示. R 28,4,4 , 12,解R 1,24,2 6,6,3,因此R 1R 2<2,8>,<2,12>,<3,12> 489121446721101010MR 13010MR 260010700014000- - - - - - -精选学习资料 - - - - - - - - - 学习必备欢迎下载891214MRMR 1MR 21101010布尔运算 21010010001030010000000140000例 4.4 试判定图 42 中关系的性质：1 1 1 2 3 2 3 2 3 a b c 图 42 例 4.4 图解 图 42 中a的关系在集合 1,2,3 上是对称的,由于结点 1 与 2, 1 与 3 之间的有向弧是成对显现且方向相反 .图 42 中b是反自反的,由于每个结点都没有自回路. 它也是反对称的,由于两条边都是单向边,它又是传递的,简洁求出R<2,1>,<3,1>, 满意 R R=R. 图 42 中c的关系自反的,反对称的、但不是传递的 但 2 到 3 没有边 . . 由于 2 到 1 有边, 1 到 3 有边,例 4.5 设集合 A1,2,3,4,5, R 是 A 上的关系,定义为 R <1,2>,<1,3>,<1,4>,<1,5>,<2,3>,<2,4>,<2,5>,<3,4>,<3,5>,<4,5> I A 试判定 R 是名师归纳总结 1 A 上的自反关系；2 A 上的对称关系；第 8 页,共 27 页3 A 上的反对称关系；4 A 上的传递关系 . 1解 写出关系矩阵MR,作关系图,如图43. 5 111112 01111MR001113 4 0001100001, 图 43 1 1 由于xA,x ,x R或 M R的主对角线元素皆为1,或关系图中每个结点都有自回路,故 R 是自反关系 . 2 由于2,1 R ,而 1,2R或 M R不是对称矩阵,或关系图中每对结点都没有成对出- - - - - - -精选学习资料 - - - - - - - - - 现的方向相反的弧学习必备欢迎下载,故 R 不是对称关系 . 3 由于 3,1 R , 且 1 3 , 就 1,3 R 或 M R中当 i j 时 , mij =0, 就 mji=1,或关系图中每对结点没有成对的有向弧 ,故 R 是反对称关系 . 4 因 为 不 难 验 证 a , b , c A , a , b R , b , c R , 有 a , c R 或 关 系 图 中a , b , c A , a 到 b 有有向弧 , b 到 c 有有向弧 , a 到 c 就有有向弧 , 故 R 是传递关系 . 例 4.6 设集合 Aa,b,c,d, 定义 R < a,b>,< b,a>,< b,c>,< c,d>, 求 rR,sR,tR. 解 求自反闭包, R 不具有自反性,由自反性的定义,只需在R 上添加 IA,于是rR=R IA=< a,a>,<a,b>,< b,a>,< b,b>,< b,c>,< c,c>,< c,d>,<d,d> 其中下画线者为添加元素 . 1sR= R R =R < c,b>,<d,c>= < a,b>,< b,a>,< b,c>,<c,b>,< c,d>,<d,c> 2 3 4tR= R R R R =R < a,a>,<b,b>,<a,c>,<b,d>,<a,d> =< a,a>, <a,b>,< a,c>,<a,d>,< b,a>,< b,b>,< b,c>,< b,d>,<c,d> 例 4.7 设集合 Aa,b,c,d,e ,定义 A 上的二元关系R 1a ,bb,b ,a,d,e,e ,dcIAd,d,d,eR 2a ,b ,a,b ,b,c,判定 R1,R2 是否为等价关系？分析 判定等价关系,就是验证是否具有自反性、对称性和传递性 . a解 写出 R1的关系矩阵,000bcde1111000MR 1001000110000011图 44 由关系矩阵可知,R1具有自反性和对称性. 由关系图 图 44可知它具有传递性,故R1是等价关系 . 名师归纳总结 R2不是等价关系,由于a,aR 2或e ,eR 2,故 R 不具有自反性 . 第 9 页,共 27 页- - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载留意：自反性,对称性和传递性之一不具备,就是破坏了等价关系的定义 . 事实上d,eR 2,但e ,dR 2,故 R2 不具有对称性；; ,b,aR2,但a ,aR 2,R2 也不具有传递性. b ,b均属于 R1,所以 a对例 4.7 的 R1进行分类：元素a,由于a ,a,a ,b,b ,a生成的等价类aR 1a ,b 或记作bR 1. 元素 c,由于c ,cR 1,所以 c 生成的等价类c R 1c类似地,d 生成的等价类dR 1d,e eR 1. 例 4.8 设集合 A18 的正整数因子 , 为整除关系,说明 分析 偏序关系只需验证自反性、反对称性和传递性 .解 集合 A1,2,3,6,9,18 ,整除关系为<A, >是偏序关系 . I A <1,2>,<1,3>,<1,6>,<1,9>,<1,18>,<2,6>,<2,18>,<3,6>,<3,9>,<3,18> ,<6,18> ,<9,18> 简洁验证 IA,故 有自反性；a,b , a b, 就b,a, 有反对称性；x,y,z A, <x,y> 且<y,z> ,就<x,z>,具有传递性 . 所以 <A, >是偏序关系 . 画<A, >的关系图和哈斯图如图 45a和b：关系图与哈斯图不是一回事 18 18 1 9 6 9 2 6 2 3 3 1 a 的关系图 b 的哈斯图图 4 5 名师归纳总结 - - - - - - -第 10 页,共 27 页精选学习资料 - - - - - - - - - <A, >的最大元是18,极大元是学习必备欢迎下载1. 18,最小元、微小元均为如子集 B1 2,3,6 ,就 B1最大元和极大元都是 上确界为 6,下确界为 1. 6,无微小元 . 上界为 6,18; 下界为 1,如子集 B2 3,6,9, 就 B2无最大元,极大元为6,9,最小元和微小元都是3, 上界为 18,下界为 3,1,上确界为18,下确界为3. 如子集 B3=1,2,3, 就极大元 2,3, 无最大元 .微小元和最小元均为 而不能是 9. 下界和下确界为 1. 1. 上界 18,6, 上确界是 6,例 4.9确定以下各题的f 是否为从 A 到 B 的函数,并对其中的函数,f：AB 指出它是单射,满射或双射？假如不是,请说明理由. 2,6,5 9,; 1A,12 ,3 4,5, ,B,67 ,89 , 10 ,f8,1,9,3,4 , 102 A,B 同1, f=<1,8>,<3,10>,<2,6>,<4,9> 3 A,B 同1, f=<1,7>,<2,6>,<4,5>,<1,9>,<5,10> 名师归纳总结 4 A,B 为实数集,fx x2x; 5 A,B 同4,fxx3; 第 11 页,共 27 页6 A,B 同4 ,fx x; 7 A,B 同4,fx1; x8 A,B 为正整数集,fx x1; 9 A,B 同8,fx 11x1; xx110 A,B 为正实数集,fxx2x1. 解1 f 是从 A 到 B 函数, 但不是单射, 由于 f3=f5=9 ；也不是满射, 由于 7Ranf. 2 f 不是从 A 到 B 函数,由于Domf=1,2,3,4A. 3 f 不是从 A 到 B 函数,由于1 Dom f, f1=7 和 9. 4 f 是从 A 到 B 函数,但不是单射,由于f0=f1=0 ；也不是满射,由于该函数的最小值是 1/4,所以 Ranf是1/,4,不是整个实数集. 5 f 是从 A 到 B 的双射函数,由于fx3是严格单调,且f:fR R. 66 f 不是从 A 到 B 函数,由于由于负实数没有定义. 77 f 不是从 A 到 B 函数,由于0 没有对应值 . 88 f 是从 A 到 B 函数,且 f 是单射,由于易验证n 1,n2N,n 1n 2n 11n 21- - - - - - -精选学习资料 - - - - - - - - - 但 f 不是满射,由于1 Ranf. 学习必备欢迎下载9 f 是从 A 到 B 函数,且 f 是满射,由于,且f,1,0Domf 是 ,1,Ranf是0,但不是单射,由于f1= f2=1 . 110f 是从 A 到 B 函数,但 f 不是单射,如x>0, fx=fx. 当 x=1 时 ,f1=1/2 是极大值, Ranf是0,1/2 ,不是整个正实数集,故f 不是满射 . 1 例 4.10图 46 中,定义了函数f,g,h1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 f gh 图 46 求： 1 f,g,h 的像 ; 2 f g, h f, g g; 3 指出 f,g,h 中哪些是单射,满射和双射4 f,g,h 中哪些函数存在反函数,给出其反函数的表达式 . 解 1 fA=1,2,4, gA=A, hA=1,3 2 f g=<1,4>,<2,2>,<3,2>,<4,3> g g=<1,4>,<2,3,>,<3,2>,<4,1> h f=<1,2>,<2,1>,<3,2>,<4,1> 3 只有 g 是单射,又是满射,即为双射 . 4 只有 g 有反函数 g 1：A A,且满意 , g1<1,3>,<2,1>,<3,4>,<4,2> 例 4.11 单项挑选题1.设集合 A1,2 ,B= a,b,c, C= c,d, 就 A× B C A< c,1>,<2,c> B <1, c>,<2,c> C< c,1>,<c,2> D<1, c>,<c,2> 答案 ：B 解答 ：B C c , A B C ,1 c , 2 , c ,故挑选 B. 2. 设 A0, a, B=1, a,3, 就 A B 的恒等关系是 A <0,0><1,1>,<3,3>,< a,a> B <0,0>,<1,1>,<3,3> C <1,1>,< a,a>,<3,3> D <0,1>,<1, a>,< a,3>,<3,0> 名师归纳总结 - - - - - - -第 12 页,共 27 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载答案 ：A 解答 ：由于 A B0,1,3, a, 故 AB 的恒等关系IAB<0,0>,<1,1>,<, a,a>,<3,3>, 应当选择A . 3. 设集合 A a,b,c, A 上的二元关系 R< a,a>,<b,b> 不具备关系 性质 . A 传递性 B 反对称性 C 对称性 D 自反性答案 ：D 解答 ：只有每个结点都有自回路,才具有自反性,R 缺少 <c,c>. 故应选 D . a24. 设集合3Aa1,a2,a3,a4,Bb 1,b2,b 3,是从 A 到 B 的函数,a1b2,b2,a,b 1,a4,b3,就是 A 双射B 满射但不是单射C 单射但不是满射D 非单射也非满射答案 ：B 解答 ：由于A=B,故是满射,但是a1= a2=b2,故不是单射 . 所以应选 B. 例 12 填空题1. 设 R1,R2是集合 A 1,2,3,4 上的二元关系 ,其中就 R1 R2R1<1,1>,<1,2>,<2,4>, R2=<1,4>,<2,3>,<2,4>,<3,2>, 答案 ：<1,4>,<1,3> 解答 ：由合成的定义：1R 11R 24 ,141,R 1d2R 23 ,1 3,2R 14R2d,R 1R 23,1,143. 设Aa,b ,c,d,R 1,R 2是 A 上的二元关系,R 1a ,a,b ,b,b ,c,d ,dR 2a ,a,b ,b,b ,c,c ,b,就 R2 是 R1 的闭包答案 ：对称解答 ：在 R1的基础上添加 <c,b>,此时关系矩阵是对称矩阵,故 三、练习题 1. 设 A1,2,3,4, R 是 A 上的二元关系,其关系矩阵为R2是 R1 的对称闭包名师归纳总结 - - - - - - -第 13 页,共 27 页精选学习资料 - - - - - - - - - 1001学习必备欢迎下载试求MR10002 Dom R和 RanR；. 000110001 R 的关系表达式；3 R R 中有多少个有序对4 R1 的关系图中有多少条自回路2. 设集合 A 1,2,3,4, A 上的二元关系求R1<1,1>,<1,3>,<1,4>,<2,4>,<3,3>,<4,4> R2<1,2>,<1,3>,<2,3>,<4,4> R3<1,1>,<2,2>,<3,3>,<4,4> R 1R2,R2R 3;R 1,R 1R3,R 1R 23. 设集合Aa,b ,c ,d,判定以下关系,哪些是自反的,对称的,反对称的,传递的？R 1a ,a,b ,a,R 2a ,a,b ,c,d,a,R 3c ,d,R 4a,a,b ,