离散数学第6章陈瑜.ppt

计算机科学与工程学院 陈瑜 Email：chenyu.inbox@ * 主要内容 1.函数的基本概念 2.单射 、满射、双射 3.复合函数和逆函数 4.集合的基数 5.有限集、无限集 6.可数集和不可数集 第六章 函数 函数是数学和计算机科学中使用得最广泛的概念之一。 实际上本书自始自终都在使用函数的概念来说明问题，只是到了本章我们才明确地从集合论的角度给函数一个定义，并着重研究在离散对象集合上定义的函数的三种重要形式、运算及性质，并以此作为工具来讨论集合的基数、有限集和无限集等问题。 第六章 函数 函数是一种特殊的二元关系,我们可以把函数看作输入输出关系;它把一个集合(输入集合)的元素变成另一个集合(输出集合)的元素。 在高等数学中，函数的概念是从变量的角度提出来，而且是在实数集合上讨论，这种函数一般是连续或间断连续的函数。 这里，将连续函数的概念推广到对离散量的讨论。前面所讨论的有关集合或关系的运算和性质，对于函数完全适用。 第六章 函数 函数是一种特殊的二元关系,我们可以把函数看作输入输出关系;它把一个集合(输入集合)的元素变成另一个集合(输出集合)的元素。 在高等数学中，函数的概念是从变量的角度提出来，而且是在实数集合上讨论，这种函数一般是连续或间断连续的函数。 这里，将连续函数的概念推广到对离散量的讨论。前面所讨论的有关集合或关系的运算和性质，对于函数完全适用。 第六章 函数 函数是一种特殊的二元关系,我们可以把函数看作输入输出关系;它把一个集合(输入集合)的元素变成另一个集合(输出集合)的元素。 在高等数学中，函数的概念是从变量的角度提出来，而且是在实数集合上讨论，这种函数一般是连续或间断连续的函数。 这里，将连续函数的概念推广到对离散量的讨论。前面所讨论的有关集合或关系的运算和性质，对于函数完全适用。 第六章 函数 任何程序在计算机中的实现,都包含种种这样或那样的变换。如编译程序把一个源程序变换成机器语言的指令集合—目标程序。或者说,计算机中的程序可以把一定范围内的任一组数据变换成另一组数据。 函数是许多数学工具的基础,计算机科学中大量用到函数,如数据结构,程序语言的设计与实现,开关理论,自动机理论,代数结构,可计算性理论,计算复杂化,程序正确性证明等。 第六章 函数 任何程序在计算机中的实现,都包含种种这样或那样的变换。如编译程序把一个源程序变换成机器语言的指令集合—目标程序。或者说,计算机中的程序可以把一定范围内的任一组数据变换成另一组数据。 函数是许多数学工具的基础,计算机科学中大量用到函数,如数据结构,程序语言的设计与实现,开关理论,自动机理论,代数结构,可计算性理论,计算复杂化,程序正确性证明等。 §6.1 一般集合的函数概念 §6.1 一般集合的函数概念 §6.1 一般集合的函数概念 函数与关系的差别 函数与关系的差别 函数与关系的差别 函数与关系的差别 例6.1 例6.1 例6.1 例6.1 定义6.2 设f和g是从集合X到Y的两个函数，如果对?x?X ,都有f(x)=g(x), 则称f与g相等，记为 f=g。 从二元关系的角度看，两个函数相等当且仅当它们是同一个关系。 定义6.2 设f和g是从集合X到Y的两个函数，如果对?x?X ,都有f(x)=g(x), 则称f与g相等，记为 f=g。 从二元关系的角度看，两个函数相等当且仅当它们是同一个关系。 习题 P85 1, 2（2）（3） §6.2 单射 、满射和双射 §6.2 单射 、满射和双射 §6.2 单射 、满射和双射 习题 P86 8，9 §6.3函数的复合与逆函数 §6.3函数的复合与逆函数 函数的复合运算 函数的复合运算 函数的复合运算 函数的复合运算 函数的复合运算 置 换 置 换 置 换 例6.5： 集合A={1,2,3}上的置换共有6个: 循 环 循 环 例6.6： 设 例6.6： 设 例6.6： 设 循环的积 一个置换可能由一个单一的循环表示出来，也可能由多个循环连接在一起表示，称之为循环的积（置换的复合）。 当两个循环没有公共元素时，它们的积仍是原来的两个循环；当两个循环有公共元素时，它们的积按照复合的意义变成了新的循环的积。 例如： 循环的积 一个置换可能由一个单一的循环表示出来，也可能由多个循环连接在一起表示，称之为循环的积（置换的复合）。 当两个循环没有公共元素时，它们的积仍是原来的两个循环；当两个循环有公共元素时，它们的积按照复合的意义变成了新的循环的积。 例如： 证明：（续） 证明：（续） 逆函数 逆函数 逆函数 逆函数 定理6.2 函数f存在逆函数当且仅当f是双射。 证明： f为从X到Y的双射，根据定义，对每个y?Y,有且仅