离散数学-第八章函数讲述

证 先证明FG是函数.
因为F, G是关系, 所以FG也是关系. 若对某个x∈dom(FG)有 xF Gy1和 xFGy2, 则
<x, y1>∈FG∧<x, y2>∈FG
t1(<x,t1>∈F∧<t1,y1>∈G)∧t2(<x,t2>∈F∧<t2,y2>∈G)
t1t2(t1=t2∧<t1,y1>∈G∧<t2,y2>∈G) （F为函数）
.
函数的定义
设A, B为集合, 如果 f 为函数, domf=A, ranfB,
则称 f 为从A到B的函数, 记作 f：A→B.
.
函数的定义
在<x,y> f 中,
定义域
domf A
例：d设omXf ={张A 三、李四、王五}， Y ={值法域国、(函美数国像、的俄集罗合斯)、英国} f ={<r张an三f ,美B国, ><李四,俄罗斯>
.
函数的复合
定理 设f:A→B, g:B→C (1) 如果 f:A→B, g:B→C满射, 则 fg:A→C也满射 (2) 如果 f:A→B, g:B→C单射, 则 fg:A→C也单射 (3) 如果 f:A→B, g:B→C双射, 则 fg:A→C也双射 定理 设 f:AB, 则 f = f IB = IAf
4.2 逆函数和复合函数
❖复合函数 ❖反函数
关系与逆关系: < y,x >R-1 <x,y>R 函数与反函数。 可能出现的问题： 定义域 (dom(f -1) A) 函数值 (一对多)
.
函数的复合
设F, G是函数, 则FG也是函数, 且满足 (1) dom(FG)={x|x∈domF∧F(x)∈domG} (2) x∈dom(FG)有FG(x)=G(F(x))

2019/12/13
11
计算机科学学院 刘芳
8.2 函数的性质
解 (1) f : R→R, f(x)= x2+2x1
在x=1取得极大值0. 既不是单射也不是满射的.
(2) f : Z+→R, f(x)=lnx
单调上升, 是单射的. 但不满射, ranf={ln1, ln2, …}.
(3) f : R→Z, f(x)= x
8.1 函数的定义
例3：
设A ＝ {1, 2, 3}, B ＝ {a, b}，则A到B共有多少个不
同的函数？分别列出来。
解：
f0={<1,a>,<2,a>,<3,a>} , f2={<1,a>,<2,b>,<3,a>} , f4={<1,b>,<2,a>,<3,a>},
f6={<1,b>,<2,b>,<3,a>} ,
BA＝{f | f : A→B}
思考：设|A|=m,|B|=n,则|BA|=？
2019/12/13
7
计算机科学学院 刘芳
8.1 函数的定义
解：
设：A={x1, x2, …,xm}, B={y1, y2, …,yn}, 则集合A到B的函数f形如：
f＝{<x1,□>， {<x2,□>，…… {<xm,□>} 对于每个□所在的 位置都可用B中的任何一个
2019/12/13
19
计算机科学学院 刘芳
8.4 函数的复合和反函数
定理8.1
设f, g是函数, 则f∘g也是函数, 且满足

例8.5 对于以下各题给定的A,B和f，判断是否构成函 数f：A→B。如果是，说明 f：A→B是否为单射，满 射，双射的，并根据要求进行计算。 (1) A={1,2,3,4,5}, B={6,7,8,9,10}, f={<1,8>,<3,9>,<4,10>,<2,6>,<5,9>} 能构成函数f：A→B，但f：A→B既不是单射也不是 满射的。 (2) A,B同（1），f={<1,7>,<2,6>,<4,5>,<1,9>,<5,10>}
令f：A→B，使得f()=f0，f({1})=f1，f({2})=f2，f({3})=f3， f({1,2})=f4，f({1,3})=f5，f({2,3})=f6，f({1,2,3})=f7
(2) A=[0,1]，B=[1/4,1/2]
令f：[0,1]→[1/4,1/2]，f(x)=(x+1)/4. (3) A=Z，B=N 将Z中元素以下列顺序排列并与N中元素对应：
例8.1 设 F1={<x1,y1>,<x2,y2>,<x3,y2>} F2={<x1,y1>,<x1,y2>} 判断它们是否为函数。 解：F1是函数，F2不是函数。
因为对应于x1存在y1和y2满足x1F2y1和x1F2y2， 与函数定义矛盾。
F 是函数（映射） 对于x1，x2∈A， 如果x1=x2 ，一定有f(x1)＝f(x2)。即， 如果对于x1，x2∈A有f(x1) ≠f(x2)，则一定有x1≠x2
函数是集合，可以用集合相等来定义函数的相等
定义8.2 设F，G为函数，则 F=G F G∧G F 由以上定义可知，如果两个函数F和G相等，一 定满足下面两个条件： 1．domF=domG 2． x∈domF=domG都有F(x)=G(x)

西南科技大学
6
计算机科学与技术学院
Discrete Mathematics 为方便起见，在无向图中往往用字母ei表示 边。例如，在上图中，用e1表示边(v2,v2)，e2 表示边(v1,v2)等。 对于一个确定的图，我们不关心顶点的位置， 边的长短与形状，因此，所画出的图的图形可 能不唯一。 定义 一个有向图G是一个二元组<V,E>，即 G=<V,E>，其中
西南科技大学
4
计算机科学与技术学院
Discrete Mathematics 定义 一个无向图G是一个二元组<V,E>，即 G=<V,E>，其中
(1). V是一个非空的集合，称为G的顶点集， V中元素称为顶点或结点；
(2). E是无序积 的一个多重子集 (元素可重复 出现的集合为多重集)，称E为G的边集，E中元 素称为无向边或简称边。 在一个图G=<V,E>中，为了表示V和E分别 为G的顶点集和边集，常将V记成V(G)，而将E 记成E(G)。
由于2m，
为偶数，所以
也为偶数。
可是,vV1时，d(v)为奇数，偶数个奇数之和才能 为偶数，所以|V1|为偶数。结论得证。
西南科技大学
17
计算机科学与技术学院
Discrete Mathematics 对有向图来说，还有下面的定理： 定理 设G=<V,E>为有向图， V={v1,v2,…,vn} ， |E|=m，则
(5).设E´ E且E´ ≠Φ ，以E´为边集，以E´中边
关联的顶点的全体为顶点集的G的子图，则称G´是由 边集E´导出的G的子图。
西南科技大学
26
计算机科学与技术学院
Discrete Mathematics 例如，在下图中，(2)，(3)均为(1)的子图；(3)是 生成子图；(2)是顶点子集{v1,v2}的导出子图，也