离散数学复习之一第1章 关系与函数一、主要内容 1．有序对与笛卡儿积h 有序对，就是有顺序的数组，如，x, y 的位置是确定的，不能随意放置.注意：有序对¹，以a, b为元素的集合{a, b}={b, a}；有序对(a, a)有意义，而集合{a, a}是单元素集合，应记作{a}. h 笛卡儿积，把集合A，B合成集合A×B，规定A×B＝{½xÎAÙyÎB}由于有序对中x, y的位置是确定的，因此A×B的记法也是确定的，不能写成B×A. 笛卡儿积也可以多个集合合成，A1×A2×…×An. 笛卡儿积的运算性质. 一般不能交换.2．关系的概念 包括定义、关系的表示方法：集合表示、矩阵表示、图形表示.h 二元关系，是一个有序对集合，设集合A，B，从集合A到B的二元关系，记作xRy．二元关系的定义域：Dom(R)； 二元关系的值域：Ran(R)h 关系的表示方法： 集合表示法：关系是集合，有类似于集合的表示方法. 列举法，如R＝{<1, 1>,<1, 2>}；描述法：如 关系矩阵： RÍA×B，R的矩阵关系图：R是集合上的二元关系，若ÎR，由结点aI画有向弧到bj构成的图形.3．几个特殊的关系空关系Æ；唯一是任何关系的子集的关系. 全关系恒等关系，MI 是单位矩阵. 4．关系的运算h 关系的集合运算，有并、交、补、差和对称差.h 复合关系 ，有 复合关系矩阵：(布尔运算)，有结合律：(R·S)·T＝R·(S·T) h 逆关系，，(R·S)－1=S－1·R－1. 5．关系的性质h 自反性 ；矩阵的主对角线元素全为1；关系图的每个结点都有自回路.h 反自反性 ；矩阵的主对角线元素全为0；关系图的每个结点都没有自回路.h 对称性 若，则；矩阵是对称矩阵，即；关系图中有向弧成对出现,方向相反.h 反对称性 若且，则x=y或若，则；矩阵不出现对称元素.h 传递性 若且，则；在关系图中，有从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：自反闭包 ；定理13：对称闭包 ；定理14的推论：传递闭包 7. 等价关系、相容关系和偏序关系 h等价关系、相容关系和偏序关系是具有不同性质的两个关系. ？ h等价关系图的特点：每一个结点都有一个自回路；两个结点间如有有向弧线，则是双向弧线，如果从a到b，从b到c各有一条有向弧线，则从a到c一定有有向弧线． h等价类，若R是等价关系，与R中的某个元素等价的元素组成的集合，就是R的一个等价类，[a]R={b½bÎAÙaRb}. h相容类，设B是A的子集，如果在B中的任意两个元素都是相关的，则称为由相容关系R产生的相容类． h偏序集的哈斯图 偏序集概念和偏序集的哈斯图．哈斯图的画法：(1) 用空心点表示结点，自环不画；(2) 若a£b，则结点b画在上边，a画在下边，并画a到b的无向弧；(3) 若,Î,则ÎR，此时，a到c的有向弧不画出.确定任一子集的最大(小)元，极大(小)元. 极大(小)元、最大(小)元、界 一个子集的极大(小)元可以有多个，而最大(小)元若有，只能惟一. 且极元、最元只在该子集内；而上界与下界可在子集之外确定，最小上界是所有上界中最小者，最小上界再小也不会小于子集中的任一元素；可以与某一元素相等，最大下界也是同样. 8. 函数 h函数, 设f是集合A到B的二元关系，"aÎA,$bÎB,且Îf，且Dom(f)=A，f是一个函数(映射). 函数是一种特殊的关系.集合A×B的任何子集都是关系，但不一定是函数. 函数要求对于定义域A中每一个元素a，B中有且仅有一个元素与a对应，而关系没有这个限制. 二函数相等是指：定义域相同，对应关系相同，而且定义域内每个对应值都相同. h函数的类型单射 若满射 f(A)=B. 即双射 单射且满射. h复合函数 若即. 复合成立的条件是：一般，但h复合函数的性质： 如果f,g都是单射的，则f·g是单射的； 如果f,g都是满射的，则f·g是满射的；如果f,g都是双射的，则f·g是双射的； 如果f,g是单射的，则f是单射的；如果f,g是满射的，则g是满射的；如果f·,g是双射的，则f是单射的，g是满射的. h反函数 若f：A®B是双射，则有反函数f－1：B®A ，二、实例例1 设给定集合A＝{a,b}，写出P(A)和P(A)上的包含关系Ì的集合表达式． 解 例2 设A＝{1,2,3},用列举法给出A上的恒等关系IA，全关系EA，A上的小于关系 及其逆关系和关系矩阵. 解 , LA的逆关系 . 有 例3 设集合A={a, b, c}，A上的二元关系R＝{,,,}，S={,,}求R·S，并用关系矩阵验证． 解 R·S＝{,,,}·{,,}＝{,,},，从矩阵也可得R·S＝{,,} 例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以及M．解 R·S= {<1,1>,<1,2>,<2,3>,<3,1>,<3,3>}·{<1,2>,<1,3>,<2,1>,<3,3>} = S2=S·S={<1,2>,<1,3>,<2,1>,<3,3>}·{<1,2>,<1,3>,<2,1>,<3,3>} = 例5 设R是实数集，R上的二元关系S为 S＝{½x,yÎRÙx=y}试问二元关系S具有哪些性质？简单说明理由． 解 12. S具有自反性，显然ÎS； S具有对称性，"ÎS，有x=y，则ÎS； S具有反对称性，",ÎS，有x=y； S具有传递性，",ÎS,因为x=y=z，故ÎS． 例6 设集合A={1,2,3,4},A上的二元关系R={<1,2>,<3,2>,<2,3>,<3,4>} 1 · ·2 4 · ·3 例6图 R2的关系图（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上的二元关系 判断R1，R2是否为等价关系？ 分析 判断等价关系，就是验证是否具有自反性、对称性和传递性. 解 写出R1的关系矩阵， a ¡ b ¡ ¡ ec ¡ ¡ d例7图 由关系矩阵可知，R1具有自反性和对称性. 由关系图(例7图)可知它具有传递性，故R1是等价关系. R2不是等价关系，因为，故R不具有自反性. 注意：自反性，对称性和传递性之一不具备，就是破坏了等价关系的定义. 事实上，故R2不具有对称性；，，R2也不具有传递性. 对例7的R1进行分类：元素a，因为均属于R1，所以a生成的等价类或记作. 元素c，因为，所以c生成的等价类; 类似地， d生成的等价类＝.例8 设集合A＝{0，1，2，3，4，5，6}上的偏序关系R如下： R＝{<0,1>,<0,2><0,3>,<0,4>,<0,5>,<0,6>,<2,5>,<3,5>，<4,6>}ÈIA 6· 5· ·4 3· 2· ·1 0· 例8图做偏序集的哈斯图，并求B={0,2,3}的极大元、极小元、最大元和最小元，B的上界和最小上界，下界和最大下界． 解 A＝{0,1,2,3,4,5,6}, B={0，2，3}，哈斯图如例8图所示． B的极大元：2，3, B的极小元：0 B的最大元：无 B的最小元：0 B的上界为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 · · 1 1 · · 1 1 · · 1 2 · · 2 2 · · 2 2 · · 2 。
