第2篇 集合论之二元关系.ppt

第2篇 集合论 主讲人：任长安 计算机与信息科学系 2009.07 引言 集合论是现代数学的重要组成部分，在科学和技术的诸多领域里都得了到广泛的应用。在计算机科学中，集合论是不可缺少的数学工具，在程序设计、形式语言、自动机、人工智能、数据库等许多领域都有着重要的作用。 集合论产生于16世纪末。当时，只是由于微积分学的需要，人们只对数集进行了研究。1872一1883年间，康托尔（Gaorge Cantor 1845一1918年，德国数学家）对任意元素的集合进行了系统的研究，提出了关于基数、序数和良序集等理论，奠定了集合论的基础，从而建立起了集合论。 引言 集合论是一门研究数学基础的学科，它试图从一个比“数”更简单的概念——集合（sets）出发，定义数及其运算，进而发展到整个数学。在这一点上它取得了极大的成功。我们介绍集合论则不仅因为此，而且因为计算机科学及应用的研究，也和集合论理论有着极密切的关系。集合不仅可用来表示数及其运算，更可以用于非数值信息的表示和处理。像数据的删节、插入、排序，数据间关系的描述，数据的组织和查询都很难用传统的数值计算来处理，但却可以用集合运算来实现。 本篇介绍集合论的基础知识，主要内容包括集合及其运算、性质、序偶、关系、映射、函数等。 主要内容 1 集合 2 二元关系 3 函数 第4章 二元关系 在日常生活中，“关系”的含义是我们所熟知的，如人与人之间有父子、师生关系；两数之间有小于关系。集合论为刻划这种联系提供了一种数学模型—关系，它仍然是一个集合，以具有那种联系的对象组合为成员。在离散数学中，“关系”被抽象为一个基本概念，在通常情况下，“关系”是至少由两个集合在给定条件下产生的新集合，它提供了一种描述事物间多值依赖的工具，为计算机科学提供了一种很好的数学模型。 本章给出了关系的几种等价定义和常用性质、二元关系的运算，研究了计算机科学中具有重要应用的关系闭包运算、等价关系、相容关系和偏序关系。 第4章 二元关系 主要内容： 4.1 有序对与笛卡尔积 4.2 二元关系及其表示 4.3 二元关系的性质 4.4 二元关系的运算 4.5 特殊关系及其性质 4.1 有序对与笛卡尔积 1、 有序对和多元序组 由两个元素x和y按一定的次序排成的二元组，称为一个有序对，表示成x, y，x是第一元素，y是第二元素。有序对满足： 1)x≠y ?x,y ≠y,x 2) (x=u) ?(y=v) ?x,y=u,v n元序组定义为： 满足： 4.1 有序对与笛卡尔积 2 笛卡尔乘积 设A、B为任意集合，以A中元素为第一元素、B中元素为第二元素构成的有序对组成的集合称为A和B的卡氏积，记为A ? B，即： A ? B = {x, y | 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) ? 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 ? D 4.2 二元关系及其表示 在日常生活中，“关系”的含义是我们所熟知的，如人与人之间有父子、兄弟、师生关系；两数之间有大于、等于、小于关系。集合论为刻划这种联系提供了一种数学模型——关系，它仍然是一个集合，以具有那种联系的对象组合为其成员。在离散数学中，“关系”被抽象为一个基本概念，在通常情况下，“关系”是至少由两个集合在给定条件下产生的新集合，它提供了一种描述事物间多值依赖的工具，为计算机科学提供了一种很好的数学模型。 4.2 二元关系及其表示 1、二元关系的定义 集合A、B的笛卡尔积A×B的任意一个子集称为A到B的一个二元关系；如果A=B则称为A上的一个二元关系。 由于我们仅讨