离散数学关系的概念、性质及运算.ppt

主要内容： 关系的概念 关系的性质 关系的合成 集合与图论 * 第6节 关系的概念、性质及合成 定义1 设A,B是两个集合。A?B的任一子集R称为从A到B的一个二元关系。 如果A=B，则称R为A上的一个二元关系。 1 关系的概念 如果(a, b)? R，则称a与b符合关系R，并记为 aRb; 如果(a, b)? R，则称a与b不符合关系R，并记为aRb。 定义2 设R?A?B，集合 {x? x? A且?y ?B使得(x, y) ?R} 称为R的定义域，并记为dom(R)。 例如：设A={1,2,3,4}，B={a,b,c,d,e}， {(1,a),(2,b),(2,c),(3,c)}是一个二元关系。 {1,2,3}是定义域，{a,b,c}是值域 一般情况下：A ? dom(R); B ? ran(R)。 集合 {y? y ?B且?x ?A使得(x, y) ?R} 称为R的值域，并记为ran(R)。 dom(R)?A; ran(R)?B。 定义域与值域 例如: A={1,2}，B={a,b,c}。 映射是特殊的二元关系。 令f:A?B，f(1)=a，f(2)=b，则 映射f就对应着A?B的子集{(1,a)，(2,b)} 关系与映射 问题1：映射与二元关系有什么联系？ （前提：映射和二元关系都是从A到B的） 定义1’ 设A,B是两个集合，一个从A?B到{是,否}的映射R，称为从A到B的一个二元关系，或A与B间的一个二元关系。 ?(a, b)?A?B，如果(a, b)在R下的象为“是”，则a与b符合关系R，记为aRb； 若A=B，则称R为A上的二元关系。 如果(a, b)在R下的象为“否”，则说a与b没有或不符合关系R，并记为aRb。 关系与映射 定义1’’ 一个从A到B的多值部分映射R称为从A到B的一个二元关系。 关系与映射 设A,B是两个集合，一个从A到2B 的映射R称为 从A到B的一个多值部分映射。 如果a?A，R(a)= ?，则称R在a无定义； 而如果R(a)? ?，则?b?R(a)，b称 a在R下的一 个象或值 。 例如：设A={1,2}，B={a,b,c}， A?B={(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)}。 A?B有6个元素， 从而有26个子集， 因此从A到B就有26个关系。 答案：2mn 问题2：A到B的关系的个数 设|A|=m，|B|=n，则A到B上有多少个二元关系？ 关系的个数 集合{(a, a)? a ?A}称为A上的恒等关系或相等关 系，并记为IA。 空集?也是A?B的一个子集。 空集?叫做A到B的空关系。 A?B是A?B的一个子集，按定义A?B也是从A 到B的一个二元关系。 A?B叫做A到B的全关系。 四个特殊二元关系 设R是A到B的二元关系，集合 {(y, x)? (x, y) ?R} 称为R的逆关系，简称R的逆，记为R-1。 显然：R-1是B到A的二元关系。 例1：整除关系 例2：整数集Z上的模n同余关系 设Z为整数集，Z上的整除关系记为?。?m, n ?Z, m?n 当且仅当 m能除尽n。 设n为任一给定的自然数。对任意两个整数m, k，如果m和k被n除，所得余数相等，则称m与k为模n同余，并记为：m ? k (mod n) 当n=3时，2?5(mod 3)，5?7(mod 3)。 关系实例 例3：设X是一个集合，集合的包含于“?”是2X上的二元关系。 定义3 设A1,A2,...,An是n个集合，一个 A1?A2?...?An的子集R称为A1,A2,...,An间的n元关系。 每个Ai称为R的一个域。 例4： 设 1、A为某单位职工“姓名”的集合； 2、B为“性别”之集合，B={男，女}； 3、C为职工年龄集合 C={1,2,...,100}; 4、D表示“文化程度”； D={小学,初中,高中,大学,硕士,博士}； 5、E是“婚否”集合，E={是，否}； 6、F表示月工资，F=[0,200