[离散数学复习辅导之一.docVIP

离散数学复习辅导之一 第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. 笛卡儿积的运算性质. 一般不能交换. ．关系的概念 包括定义、关系的表示方法：集合表示、矩阵表示、图形表示. ? 二元关系，是一个有序对集合，设集合A，B，从集合A到B的二元关系 ， 记作xRy． 二元关系的定义域：Dom(R)； 二元关系的值域：Ran(R) ? 关系的表示方法： 集合表示法：关系是集合，有类似于集合的表示方法. 列举法，如R＝{1, 1,1, 2}；描述法：如 关系矩阵： R?A×B，R的矩阵 关系图：R是集合上的二元关系，若aI, bj?R，由结点aI画有向弧到bj构成的图形. 几个特殊的关系 空关系?；唯一是任何关系的子集的关系. 全关系 恒等关系，MI 是单位矩阵. 关系的运算 ? 关系的集合运算，有并、交、补、差和对称差. ? 复合关系 ，有 复合关系矩阵：(布尔运算)，有结合律：(R?S)?T＝R?(S?T) ? 逆关系，，(R?S)－1=S－1?R－1. 关系的性质 ? 自反性 ；矩阵的主对角线元素全为1；关系图的每个结点都有自回路. ? 反自反性 ；矩阵的主对角线元素全为0；关系图的每个结点都没有自回路. ? 对称性 若，则；矩阵是对称矩阵，即；关系图中有向弧成对出现,方向相反. ? 反对称性 若且，则x=y或若，则；矩阵不出现对称元素. ? 传递性 若且，则；在关系图中，有从a到b的弧，有从b到c的弧，则有从a到c的弧. 判断传递性较为困难. 可以证明：R是集合A上的二元关系， 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是等价关系.?具有反自反性、对称性、反对称性和传递性．?是偏序关系. 关系性质的判定，可以用定义、关系矩阵或关系图. . 关系的闭包 设R是非空集合A上的二元关系，在关系R中，添加最少的有序对，新关系用R?表示，使得R?具有关系的自反(对称、传递)性质，R?就是R的自反(对称、传递)闭包，记作r(R) ，s(R)和t(R)．闭包的求法： 定理12：自反闭包 ；定理13：对称闭包 ；定理14的推论：传递闭包 . 等价关系和偏序关系 ?等价关系和偏序关系是具有不同性质的两个关系. ?等价关系图的特点：每一个结点都有一个自回路；两个结点间如有有向弧线，则是双向弧线，如果从a到b，从b到c各有一条有向弧线，则从a到c一定有有向弧线． ?等价类，若R是等价关系，与R中的某个元素等价的元素组成的集合，就是R的一个等价类，[a]R={b?b?A?aRb}. ? ?偏序集的哈斯图 偏序集概念和偏序集的哈斯图．哈斯图的画法：(1) 用空心点表示结点，自环不画；(2) 若a?b，则结点b画在上边，a画在下边，并画a到b的无向弧；(3) 若a,b,b,c?,则a,c?R，此时，a到c的有向弧不画出. 确定任一子集的最大(小)元，极大(小)元. 极大(小)元、最大(小)元、界 一个子集的极大(小)元可以有多个，而最大(小)元若有，只能惟一. 且极元、最元只在该子集内；而上界与下界可在子集之外确定，最小上界是所有上界中最小者，最小上界再小也不会小于子集中的任一元素；可以与某一