当前位置:文档之家› 离散数学集合论部分常考××题

离散数学集合论部分常考××题

离散数学常考题型梳理第2章关系与函数一、题型分析本章主要介绍关系的概念及运算、关系的性质与闭包运算、等价关系、相容关系和偏序关系三个重要关系、函数以及函数相关知识等内容。

常涉及到的题型主要包括:2-1关系的概念理解以及关系的并、交、补、差以及复合和逆关系等运算2-2关系自反和反自反、对称和反对称等性质的概念理解与判定;自反、对称和传递闭包运算。

2-3等价关系2-4偏序关系和哈斯图2-5 函数的概念和性质因此,在本章学习过程中希望大家要清楚地知道:1.有序对和笛卡尔积(1)有序对:所谓有序对就是指一个有顺序的数组,如< x , y >,x , y的位置是确定的,且< a , b >< b , a >。

(2)笛卡尔积:把集合A,B合成集合A×B,规定:{,|}⨯=<>∈∈且A B x y x A y B由于有序对< x , y >中x,y 的位置是确定的,因此A×B 的记法也是确定的,不能写成B×A 。

笛卡儿积的运算一般不满足交换律。

2.二元关系的概念和表示、几种特殊的关系和关系的运算(1)二元关系的概念:二元关系是一个有序对集合,设集合A,B ,从集合A 到B的二元关系R∈x∈<y=且>},x{B|yA记作xRy。

二元关系的定义域:ARam⊆R)(。

)RDom⊆(;二元关系的值域:B 二元关系R 是一个有序对组成的集合.因此,一个二元关系是一个集合,可以用集合形式表示;反过来说,一个集合未必是一个二元关系,仅当集合是由有序对元素组成的,才能当做二元关系。

常用关系的表示法包括了集合表示法、列举法、描述法、关系矩阵法和关系图法。

关系矩阵和关系图是有限集合上的二元关系的表示方法。

(2)特殊的关系:空关系、全关系和恒等关系 空关系(记作):是任何关系的子集全关系(记作E A ):A A A b a b a E A ⨯≡∈><=},|,{恒等全系(记作I A ):}|,{A a a a I A ∈><=(3)关系的集合运算、复合运算和逆运算:关系的集合运算与普通集合运算基本相同,主要为并运算、交运算、补运算、差运算和对称差运算。

关系复合运算,描述为1212{,|,,}R R R a c b a b R b c R =∙=<><>∈<>∈存在使且复合关系满足结合律:)()(T S R T S R ∙∙=∙∙关系的逆运算,描述为},|,{1R x y y x R >∈<><=-逆关系满足:111)(---∙=∙R S S R二元关系 R 的逆关系可以用关系矩阵和关系图表示.并且逆关系的关系矩阵就是关系R 的关系矩阵的转置,而逆关系的关系图就是把关系 R 的关系图中的有向弧的方向改变。

3.关系的性质:自反性、反自反性、对称性、反对称性、传递性(1)自反性:对任意R x x A x >∈<∈∀,,有,则关系R 是自反的。

自反关系的矩阵R M 主对角线元素全为1;自反关系图的每个结点都有自回路。

(2)反自反性:对R x x A x >∉<∈∀.,有,则关系R 是反自反的。

反自反关系矩阵R M 主对角线元素全为0;关系图的每个结点都没有自回路。

(3)对称性:对R x y R y x >∈<>∈<∀,,,有,则关系R 是对称的。

对称关系的矩阵R M 是对称矩阵,即ji ij r r =;关系图中有向弧成对出现,方向相反.(4)反对称性:对,,x y R y x R ∀<>∈<>∈,若,必有x y =,则关系R 是反对称的;或者R x y R y x >∉<>∈<∀,,,必有,则关系R 是反对称的.反对称关系的矩阵R M 不出现对称元素,关系图中任意两个顶点之间或者没有有向弧,或者仅有一条有向弧.(5)传递性:对,,,a b R b c R a c R ∀<>∈∃<>∈<>∈,若,使得,则关系R 是传递的.在传递关系的关系图中,若有从a 到b 的弧,且有从b 到c 的弧,则必有从a 到c 的弧。

4.关系的自反闭包、传递闭包和对称闭包求解方法 (1)求解关系的自反闭包集合法:把所有的A a ∈构成的有序对< a , a > 添加到A 上的关系R 中,就能够获得R 的自反闭包r (R )。

即:A I R R r ⋃=)(,其中,I A 是A 上的恒等关系。

矩阵法:若R 的关系矩阵M R ,通过公式E M M R r +=,就能够求出R 的自反闭包r (R ) 的关系矩阵M r ,其中E 是单位矩阵。

图像法:在R 的关系图上没有自回路的结点处都添上自回路,就得到了R 的自反闭包r (R ) 的关系图。

(2)求解关系的对称闭包集合法:若R 上的任意关系a , b ,若R a b >∉<,,则把b , a 添加到关系R 中,就能够获得R 的对称闭包s (R )。

即:1)(-⋃=R R R s 。

矩阵法:若R 的关系矩阵为M R ,利用公式T R R s M M M +=,就能够得出R 的对称闭包s (R )的关系矩阵M s ,其中R T RM M 是的转置矩阵. 图像法:把R 的关系图图上所有单向弧都画为双向弧,就能得到R 的对称闭包s (R )的关系图.(3)求解关系的传递闭包集合法:先求出R 2,…,R n ,再求它们的并n R R R R ⋃⋃⋃⋃...21,就能够获得R 的传递闭包t (R )。

即:231()ni t R R R R ==⋃⋃⋃⋅⋅⋅。

矩阵法:若已知R 的关系矩阵M R ,通过公式n R R R t M M M M +++=...2,便能求出R 的传递闭包t (R )的关系矩阵M t 。

图像法:若已知R 的关系图,从关系图的每个结点a i (i =1,2,…,n )出发,找出所有2步,3步,…,n 步长的路径,设路径的终点为k j j j a a a ,...,,21,从a I 依次用有向弧连接到k j j j a a a ,...,,21,当检查完所有结点后,就画出了R 的传递闭包t (R )的关系图。

5.等价关系等价关系概念:设R 是非空集合A 上的二元关系,如果R 是自反的、对称的和传递的,则称R 是A 上的等价关系。

设R 是一个等价关系,若<a , b >∈R ,则称a 等价于b ,记作a ~b 。

6.偏序关系和哈斯图(1)偏序关系设R 是非空集合A 上的二元关系,如果R 是自反的、反对称的和传递的,则称R 是A 上的偏序关系或者简称序关系。

偏序关系记作≤。

<a , b >∈≤,则称a 小于等于b ,记作a ≤ b 。

(2)哈斯图作图规则:i .去掉每个结点的自回路,用空心点表示集合的元素;ii .对于集合任意元素a 和b ,若a ≤b ,则将a 画在b 的下方;iii .对于集合任意元素a 和b ,若a <b ,且不存在c 使a <c <b ,则在a 和b 之间划一条弧。

(3)最小元、极小元、最大元和极大元,上界和下界一个子集的极大(小)元可以有多个,而最大(小)元若有,只能惟一;且极元、最元只在该子集内;而上界与下界可在子集之外确定,最小上界是所有上界中最小者,最小上界再小也不会小于子集中的任一元素;可以与某一元素相等,最大下界也是同样。

7.函数的概念与性质(1)函数的概念设 f 是集合 A 到 B 的二元关系,若任意 a ∈A ,存在 b ∈B ,且< a , b >∈ f ,Dom ( f ) = A ,则 f 是一个函数(映射).函数是一种特殊的关系。

注意:集合 A ×B 的任何子集都是关系,但不一定是函数。

函数要求对于定义域 A 中每一个元素 a ,B 中有且仅有一个元素与 a 对应,而一般的关系没有这个限制。

(2)单射、满射和双射的判断单射:若)()(2121a f a f a a ≠⇒≠;满射:f (A) = B ,即对任意 y ∈B ,存在 x ∈A ,使得 y = f (x ) ;双射:单射且满射。

(3)函数的复合若C B g B A f →→:,:,则C A g f →∙:,即))(())((x f g x f g =∙。

复合成立的条件是:二、常考知识点分析常考知识点1:关系的概念与性质(历年考核次数:4次,本课程共考过6次;重要程度:★★★★)(2010年1月试卷第7题)如果R 是非空集合A 上的等价关系,a ∈A ,b ∈A ,则可推知R 中至少包含 等元素[解题过程]:由等价关系的概念,知道R 具备了自反性、对称性和传递性。

根据已知A 上的元素a 和b ,根据自反的概念,知道R 中必须包含<a, a>和<b, b>,由对称和传递概念,得知{<a, a>,<b, b>}也具备对称性和传递性,因此对应A 上的关系R 至少应该包含元素<a, a>,<a, b>正确答案:<a, a>,<b, b>易错点:同学们对本题目中要求的最小等价关系没有理解清楚,容易将答案写为{<a, a>,<a, b>,<b, a>,<b, b>},仔细观察可以看出,该关系去掉<a, b>和<b, a>之后,仍然为等价关系。

提示:先加入自反关系,然后再根据等价关系加入必要的对称和传递所需的元素。

(2009年7月试卷第2题)集合A ={1, 2, 3, 4, 5, 6, 7, 8}上的关系R ={<x ,y >|x +y =10且x , y ∈A },则R 的性质为( ).A .自反的B .对称的C .传递且对称的D .反自反且传递的[解题过程]:首先,可以写出关系R 的有限集合表示,即 {<2,8>,<8,2>,<3,7>,<7,3>,<4,6>,<6,4>,<5,5>}容易看出,<1,1>∉ R ,因此R 不是自反的。

<5,5>∈R 因此,R 不是反自反的。

又因为<2,8>∈R ,且<8,2>∈R ,而<2,2>∉ R ,因此,R 不具备传递性。

因此,答案选择B 。

易错点:同学们对关系的自反性、对称性、传递性和反自反性没有理解清楚,往往是能够写出R 的有限集合表示却不能用相关概念进行判别。

相关主题