第2篇 集合论之二元关系

《第2篇 集合论之二元关系》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2篇集合论主讲人：任长安计算机与信息科学系2009.07引言集合论是现代数学的重要组成部分，在科学和技术的诸多领域里都得了到广泛的应用。在计算机科学中，集合论是不可缺少的数学工具，在程序设计、形式语言、自动机、人工智能、数据库等许多领域都有着重要的作用。集合论产生于16世纪末。当时，只是由于微积分学的需要，人们只对数集进行了研究。1872一1883年间，康托尔（GaorgeCantor1845一1918年，德国数学家）对任意元素的集合进行了系统的研究，提出了关于基数、序数和良序集等理论，奠定了集合论的基础，从

2、而建立起了集合论。引言集合论是一门研究数学基础的学科，它试图从一个比“数”更简单的概念——集合（sets）出发，定义数及其运算，进而发展到整个数学。在这一点上它取得了极大的成功。我们介绍集合论则不仅因为此，而且因为计算机科学及应用的研究，也和集合论理论有着极密切的关系。集合不仅可用来表示数及其运算，更可以用于非数值信息的表示和处理。像数据的删节、插入、排序，数据间关系的描述，数据的组织和查询都很难用传统的数值计算来处理，但却可以用集合运算来实现。本篇介绍集合论的基础知识，主要内容包括集合及其运算、性质、序偶、关

3、系、映射、函数等。主要内容1集合2二元关系3函数第4章二元关系在日常生活中，“关系”的含义是我们所熟知的，如人与人之间有父子、师生关系；两数之间有小于关系。集合论为刻划这种联系提供了一种数学模型—关系，它仍然是一个集合，以具有那种联系的对象组合为成员。在离散数学中，“关系”被抽象为一个基本概念，在通常情况下，“关系”是至少由两个集合在给定条件下产生的新集合，它提供了一种描述事物间多值依赖的工具，为计算机科学提供了一种很好的数学模型。本章给出了关系的几种等价定义和常用性质、二元关系的运算，研究了计算机科学中具有重

4、要应用的关系闭包运算、等价关系、相容关系和偏序关系。第4章二元关系主要内容：4.1有序对与笛卡尔积4.2二元关系及其表示4.3二元关系的性质4.4二元关系的运算4.5特殊关系及其性质4.1有序对与笛卡尔积1、有序对和多元序组由两个元素x和y按一定的次序排成的二元组，称为一个有序对，表示成，x是第一元素，y是第二元素。有序对满足：1)x≠y≠2)(x=u)(y=v)=n元序组定义为：满足：4.1有序对与笛卡尔积2笛卡尔乘积设A、B为任意集合，以A中元素为第一

5、元素、B中元素为第二元素构成的有序对组成的集合称为A和B的卡氏积，记为AB，即：AB={

6、xAyB}一些性质：1)不满足交换律和结合律：ABBA(A,B,AB)(AB)CA(BC)(A,B,C)4.1有序对与笛卡尔积2)满足分配律：A(BC)=(AB)(AC)A(BC)=(AB)(AC)(BC)A=(BA)(CA)(BC)A=(BA)(CA)3)A=，A=4)基数满足：card(AB)=card(A)

7、card(B)5）n阶卡氏积定义为：4.1有序对与笛卡尔积定理设A,B,C为任意三个集合，C≠Φ，则（1）AB的充要条件是A×CB×C；（2）AB的充要条件是C×AC×B。定理设A,B,C,D为四个非空集合，则A×BC×D,当且仅当AC,BD4.2二元关系及其表示在日常生活中，“关系”的含义是我们所熟知的，如人与人之间有父子、兄弟、师生关系；两数之间有大于、等于、小于关系。集合论为刻划这种联系提供了一种数学模型——关系，它仍然是一个集合，以具有那种联系的对象组合为其成员。在离散数学中，“关系”被

8、抽象为一个基本概念，在通常情况下，“关系”是至少由两个集合在给定条件下产生的新集合，它提供了一种描述事物间多值依赖的工具，为计算机科学提供了一种很好的数学模型。4.2二元关系及其表示1、二元关系的定义集合A、B的笛卡尔积A×B的任意一个子集称为A到B的一个二元关系；如果A=B则称为A上的一个二元关系。由于我们仅讨论二元关系，故二元关系可简称为关系，一个关系常用R表示。1）集合A到集合B的关系R是一个集合，RA×B，称R的所有有序对的第一元素组成的集合R的定义域(domain)，即：domR={x

9、y(

10、y>R)}；4.2二元关系及其表示R的所有有序对的第二元素组成的集合R的值域(range)，即：ranR={y

11、x(R)}R的所有有序对的两个元素组成的集合R的域，即：fldR=domRranR称A为R的前域，B为R的陪域。显然，domRA，ranRB。2）对于aA，bB，若R，则称a,b满足关系R，也可记为aRb；若R，则称a,b不满