内容发布更新时间 : 2024/11/15 11:43:11星期一 下面是文章的全部内容请认真阅读。
离散数学复习辅导之一
第1章 关系与函数
一、主要内容
1．有序对与笛卡儿积
有序对，就是有顺序的数组，如
注意：有序对
? 笛卡儿积，把集合A，B合成集合A×B，规定
A×B＝{
由于有序对
包括定义、关系的表示方法：集合表示、矩阵表示、图形表示.
? 二元关系，是一个有序对集合，设集合A，B，从集合A到B的二元关系
R?{?x,y?x?A?y?B}， 记作xRy．
二元关系的定义域：Dom(R)?A； 二元关系的值域：Ran(R)?B
? 关系的表示方法：
集合表示法：关系是集合，有类似于集合的表示方法.
列举法，如R＝{<1, 1>,<1, 2>}；描述法：如R?{?x,y?x?A?y?B}
??1 关系矩阵： R?A×B，R的矩阵MR?(rij)m?n,rij????0aiRbj?i?1,2...,m,??? ?aiR?bj?j?1,2,...,n??关系图：R是集合上的二元关系，若
3．几个特殊的关系
空关系?；唯一是任何关系的子集的关系. 全关系EA?{?a,b?a,b?A}?A?A
恒等关系IA?{?a,a?a?A}，MI 是单位矩阵. 4．关系的运算
? 关系的集合运算，有并、交、补、差和对称差.
? 复合关系 R?R1?R2?{?a,c??b使?a,b??R1??b,c??R2}，有 复合关系矩阵：MR?MR1?MR2(布尔运算)，有结合律：(R?S)?T＝R?(S?T) ? 逆关系R?1－－－T，(R?S)1=S1?R1. ?{?y,x??x,y??R}，MR?1?MR5．关系的性质
? 自反性 ?x?A,?x,x??R；矩阵MR的主对角线元素全为1；关系图的每个结点都有自回路.
? 反自反性 ?x?A,?x,x??R；矩阵MR的主对角线元素全为0；关系图的每个结点都没有自回路.
? 对称性 若?x,y??R，则?y,x??R；矩阵MR是对称矩阵，即rij?rji；关系图中有向弧成对出现,方向相反.
? 反对称性 若?x,y??R且?y,x??R，则x=y或若?x,y??R,x?y，则
?y,x??R；矩阵MR不出现对称元素.
? 传递性 若?a,b??R且?b,c??R，则?a,c??R；在关系图中，有从a到b的弧，有从b到c的弧，则有从a到c的弧. 判断传递性较为困难.
可以证明：R是集合A上的二元关系，
(1) R是自反的?IA?R; (2) R是反自反的?IA?R＝?;
－－
(3) R是对称的 ?R＝R1； (4) R是反对称的?R?R1?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：自反闭包 r(R)?R?IA；
定理13：对称闭包 s(R)?R?R； 定理14的推论：传递闭包 t(R)?
?1n?Ri?1i
7. 等价关系、相容关系和偏序关系
?等价关系、相容关系和偏序关系是具有不同性质的两个关系.
?性？ 自反性??性?????反性????相容系???等价系 性???偏序系 ?等价关系图的特点：每一个结点都有一个自回路；两个结点间如有有向弧线，则是双向弧线，如果从a到b，从b到c各有一条有向弧线，则从a到c一定有有向弧线． ?等价类，若R是等价关系，与R中的某个元素等价的元素组成的集合，就是R的一个等价类，[a]R={b?b?A?aRb}.
?相容类，设B是A的子集，如果在B中的任意两个元素都是相关的，则称为由相容关系R产生的相容类．
?偏序集的哈斯图 偏序集概念和偏序集的哈斯图．哈斯图的画法： (1) 用空心点表示结点，自环不画；
(2) 若a?b，则结点b画在上边，a画在下边，并画a到b的无向弧； (3) 若
极大(小)元、最大(小)元、界 一个子集的极大(小)元可以有多个，而最大(小)元若有，只能惟一. 且极元、最元只在该子集内；而上界与下界可在子集之外确定，最小上界是所有上界中最小者，最小上界再小也不会小于子集中的任一元素；可以与某一元素相等，最大下界也是同样. 8. 函数 ?函数, 设f是集合A到B的二元关系，?a?A,?b?B,且
集合A×B的任何子集都是关系，但不一定是函数. 函数要求对于定义域A中每一个元素a，B中有且仅有一个元素与a对应，而关系没有这个限制. 二函数相等是指：定义域相同，对应关系相同，而且定义域内每个对应值都相同.
?函数的类型
单射 若a1?a2?f(a1)?f(a2)
满射 f(A)=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?A
f?1?{?b,a?b?B,f(a)?b,a?A}，(f?g)?1?g?1?f?1,(f?1)?1?f 二、实例
例1 设给定集合A＝{a,b}，写出P(A)和P(A)上的包含关系?的集合表达式． 解 P(A)?{?,{a},{b},{a,b}}
??{??,{a}?,??,{b}?,??,{a,b}?,?{a},{a,b}?,?{b},{a,b}?}
例2 设A＝{1,2,3},用列举法给出A上的恒等关系IA，全关系EA，A上的小于关系 LA?{?x,y?x,y?A?x?y} 及其逆关系和关系矩阵.
解 IA?{?1,1?,?2,2?,?3,3?}
EA?{?1,2?,?1,3?,?2,1?,?2,3?,?3,1?,?3,2?,}?IA
1 LA?{?1,2?,?1,3?,?2,3?}, LA的逆关系L?A?{?2,1?,?3,1?,?3,2?}
?011??000?????T MLA??001? ML?1??100?. 有 MLA?ML?1 AA?000??110????? 例3 设集合A={a, b, c}，A上的二元关系