离散数学第4.1-4.3-陈瑜.ppt

计算机科学与工程学院 陈瑜 Email：chenyu.inbox@ * 第4章的主要内容 1.学习关系的数学定义、表示方法、性质及运算； 2.掌握两类在实践中非常重要的二元关系：等价关系、偏序关系； 本节课主要内容 1.关系的定义 2.关系的表示 3.关系的性质 第四章 二元关系 万事万物之间总可以根据需要确定相应的关系。从数学的角度看，这类联系就是某个集合中元素之间的关系。 在第三章我们讨论了集合及其元素，本章讨论集合中元素之间的关系。关系是表征事物的结构及其内在的联系。 研究事物结构,主要是研究关系。关系的概念应用广泛,在计算机科学中起着重要的作用,如数据结构,数据库,数字逻辑,情报检索,算法分析,编译,人工智能等领域它都是很重要的数学工具。 第四章 二元关系 万事万物之间总可以根据需要确定相应的关系。从数学的角度看，这类联系就是某个集合中元素之间的关系。 在第三章我们讨论了集合及其元素，本章讨论集合中元素之间的关系。关系是表征事物的结构及其内在的联系。 研究事物结构,主要是研究关系。关系的概念应用广泛,在计算机科学中起着重要的作用,如数据结构,数据库,数字逻辑,情报检索,算法分析,编译,人工智能等领域它都是很重要的数学工具。 第四章 二元关系 万事万物之间总可以根据需要确定相应的关系。从数学的角度看，这类联系就是某个集合中元素之间的关系。 在第三章我们讨论了集合及其元素，本章讨论集合中元素之间的关系。关系是表征事物的结构及其内在的联系。 研究事物结构,主要是研究关系。关系的概念应用广泛,在计算机科学中起着重要的作用,如数据结构,数据库,数字逻辑,情报检索,算法分析,编译,人工智能等领域它都是很重要的数学工具。 §4．1 二元关系及其表示 关系是一个基本的概念,通俗地说,所谓关系,是指对象之间的相互联系,它表征事物的结构。如自然界中的“引力关系”,人与人之间的“父子关系”,“上下级关系“,”同志关系”,“同学关系”,对象间的“位置关系”,两个数间的“大于”,“等于”,“整除关系”,两个变量之间的“函数关系”,计算机部件间的“联结关系”,程序间的“调用关系”,… §4．1 二元关系及其表示 为表达元素之间的关系，可用英文字母R表示所定义的关系。 如： 1）当元素x关于元素y具有指定的关系R时，则 表示成：xRy； 2）当x关于y不具有指定的关系R时，则表示成：xRy 此外，还可以用另外的形式来表达关系。如可以用笛卡尔序偶（x，y）来表达xRy的意义。 下面的定义就将这两种表示法联系了起来。 §4．1 二元关系及其表示 为表达元素之间的关系，可用英文字母R表示所定义的关系。 如： 1）当元素x关于元素y具有指定的关系R时，则 表示成：xRy； 2）当x关于y不具有指定的关系R时，则表示成：xRy 此外，还可以用另外的形式来表达关系。如可以用笛卡尔序偶（x，y）来表达xRy的意义。 下面的定义就将这两种表示法联系了起来。 §4．1 二元关系及其表示 为表达元素之间的关系，可用英文字母R表示所定义的关系。 如： 1）当元素x关于元素y具有指定的关系R时，则 表示成：xRy； 2）当x关于y不具有指定的关系R时，则表示成：xRy 此外，还可以用另外的形式来表达关系。如可以用笛卡尔序偶（x，y）来表达xRy的意义。 下面的定义就将这两种表示法联系了起来。 关系的表示法 关系的表示法 2.关系图法（有向图表示法） 2.关系图法（有向图表示法） 2.关系图法（有向图表示法） 例6： 例6： 例6： 例6： 3.关系矩阵表示法 3.关系矩阵表示法 例7： 例7： §4.2 关系的性质 §4.2 关系的性质 例8： 例8： 例8：(续1) 例8：(续1) 例8：(续2) 例8：(续2) 结论 结论 结论 对称性与反对称性 对称性与反对称性 例9： 例9： 例9： 例9： 例9：(续1) 例9：(续1) 例9：(续1) 例9：(续1) 结论 结论 结论 传递性 传递性 例10: ★ 结论 结论 §4.3 关系的运算 例11： 例11： 关系的复合运算 复合关系的矩阵表示 例12： 例12： 例12（续）： 例12（续）： 例12（续）： 关系的幂 关系的逆运算 关系的逆运算 例4.13 例4.13 例4.13 例4.13(续) 证明（续） 习题 P65 3 P66 10(2)(4)、11 定义4.5设R是一个从集合A到集合B的二元关 系，S是从集合B到集合C的二元关系(也可 简单地描述为R：A→B，S：B→C)，则R与 S的复合关系（合成关系）R?S是从A到C的关系， 并且： R?S＝{(x,z)|(x∈A)∧(z∈C)∧