当前位置：文档之家 › 离散数学第05章函数

离散数学第05章函数

  • 格式：ppt
  • 大小：627.50 KB
  • 文档页数：79

下载文档原格式

  / 79

合集下载

离散数学第五章

离散数学第五章

第五章函数Function函数在数学、应用数学等许多领域，尤其计算机科学领域有着极其重要的作用。

函数的思想、概念和应用无处不在，无时不在。

它主要是研究变量之间的关系和规律。

函数的划分有很多种。

有线性与非线性之分、连续与离散之分。

例如，x12345…y357911…5.1 函数假定A，B是两个非空集合，f : A→B，称f为A到B上的函数，对每个a∈A, 有唯一的f(a)∈B, 记做b = f(a)。

函数也叫映射mappings或变换transformations（错误）a叫做函数f的自变量argument，b被称为因变量，b=f(a)叫做函数的值value，也叫a的像。

例1. A＝{1,2,3,4}, B={a,b,c,d},，则f是一个函数。

也可以简单记为，f={(1,a), (2,a), (3,d), (4,c)}另外,g={(1,a), (1,b), (2,a), (4,c)}因为对于1来说，1∈A, 不是唯一的f(1)∈B与之相对应,f(1)=a,并且f(1)=b, 因此g就不是一个函数。

例2．f：Z→Z，f(a)=f是函数。

例3．恒等函数1A(a)=a是函数。

正如，我们在第四章里表述的，函数f : A→B，b=f(a), 是一个特殊的二元关系，我们知道，由函数f可以确定一个关系，简单地，可以表示为(a,b)∈，或 ab。

关系的特征函数为或者简记为因此，这样一来，我们以前所讨论的有关集合或关系的运算和性质对于函数来说，就可以完全适用。

例如，f：A→B, g：A→B,函数的复合设f：A→B，g：B→C，是函数，则g◦f：A→C，是函数。

g◦f（a）＝g(f(a))例4．函数的复合设f，g都是整数函数，f(a)=a+1, g(b)=2b.则g◦f (a)=2(a +1) 是整数集到偶数集的函数。

f◦g(a)=2a＋1也是整数集到奇数集的函数。

特殊函数Special Type of Functions设f是从A到B的一个函数，如果Dom(f)=A，则称f是处处有定义everywhere defined；如果 Ran(f)=B，则称f是满射；如果对于集合A中两个不同的元素a和b，有f(a)≠f(b), 则称f是单射，即a≠b f(a)≠f(b), 或f(a)=f(b) a=b；例5. A＝{1,2,3,4}, B={a,b,c,d}, f={(1,a), (2,a), (3,d), (4,c)}f是一个函数，但是f既不是单射，也不是满射。

离散数学 函数部分

离散数学 函数部分
一个十分重要的例子。
2020/3/14
计算机科学与技术学院
12
三、函数的合成运算
定义 考虑g：A→B，f：B→C是两个函数，则合成 关系f•g是从A到C的函数，记为 f•g：A→C，
称为函数g与f的合成函数。
显然，对任意x∈A，有 f•g(x)＝f(g(x))。
2020/3/14
计算机科学与技术学院
2020/3/14
计算机科学与技术学院
16
例
例1 设f：R→R,满足： 1）f＝{<x,x2>|x∈R}； 2）f＝{<x,x+1>|x∈R}。求f-1。
解 1）对任意x∈R，有f(x)＝x2与之对应，所以 f不是单射函数，即f非双射函数，因此f的逆函 数不存在。 2）因f是双射函数，所以f-1存在，且有： f-1＝{<x,x-1>|x∈R}。
计算机科学与技术学院
5
例2
设A＝{a,b}，B＝{1,2}，A×B＝{<a,1>,<a,2>,<b,1>,<b,2>}，
此时从A到B的不同的关系有24＝16个。分别如下：
R0＝Φ R1＝{<a,1>} R2＝{<a,2>} R3＝{<b,1>}；
R4＝{<b,2>}；R5＝{<a,1>,<b,1>} R6＝{<a,1>,<b,2>}
2020/3/14
计算机科学与技术学院
10
例2
设An＝{a1,a2,a3,…,an}是n个元素的有限集， Bn＝{b1b2b3…bn|bi∈{0,1}}，对An的每一个子 集S(即对任意S(An)),令

离散数学第五章 函数

离散数学第五章 函数
f -1({0})={0, 1}, f -1({1})={2, 3}, f -1(Ø)= Ø
像与逆像: 映射的“提升”
设U和V是两个集合， f : U→V 是从U到V的一个函数， ρ(U)是U的幂集，ρ(V)是V的幂集。
像与逆像将从U到V的一个映射 f : U→V “提升” 为从U的幂集 ρ(U) 到V的幂集 ρ(V) 的映射
集合 A 在函数 f 下的 像 f (A)
U
f
V
A
f(A)
集合 B 在函数 f 下的 逆像 f -1(B)
U
f
V
-1
f (B)
B
例5.1.3 设 A={a, b, c, d, e} , B={1, 2, 3, 4} , φ: A→B, φ的定义如图所示。则
φ({a, b, c})={1, 2}
例：设 U={1,2,3,4}，V={1,2,…,16}，关系 f1={ <1,1>, <2,4>, <3,9>, <4,16> }， f2={ <1,1>, <2,3>, <4,4> }， f3={ <1,1>, <1,2>, <2,15>, <3,16>, <4,1> }，
试判断哪些是函数？
解：f1 是，且 f1(a)=a2。 f2 不是，因为f2(3)=? f3 不是，因为两个f3(1)。
n×n×…×n = nm
m
映射：递归定义
例5.1.8 (1) 阶乘 n! f: N→N, f(0)=1, f(n+1)=f(n)(n+1), n∈N。
（但需要检查，是否都有射，是否没有一射多）

离散数学第五章 函数

离散数学第五章 函数
例5.10 设Z是整数集合，并且函数f: Z→Z给定成f(i)=2i+1。试求出合 成函数f3( i ) 。 解：合成函数 f3( i ) 是一个由Z到Z的函数，于是有
同有其方便之处：
对合成函数g◦f，当z=(g◦f)(x)时，必有
z=g(f(x)) g◦f与g(f(x)) 的次序是理想的。
5.2 函数的合成和合成函数的性质
定理5.1 设 f : X Y 和 g : Y Z 是两个函数。 （1）合成函数 g f 是从 X Z 的函数，并且，对于每一个 x X ，都 有 ( g f )( x) g ( f ( x)) 。
函数的基本概念和性质 函数的合成和合成函数的性质 特殊函数 反函数 特征函数 基数
不可解问题
5.1 函数的基本概念和性质
函数
定义5.1 设 A和 B是两个任意的集合，并且 f是从 A 到B 的一种关系。
如果对于每一个 x A，都存在唯一的 y B ，使得 x, y f ，则称关系 f
在本章中，首先将定义一般的函数，然后讨论特种函数，由一种特殊函数——
双射函数引出不可数集合基数的比较方法。在以后的各章中，这些概念将起着 重要作用。在开关理论、自动机理论、可计算性理论等领域中，函数都有着极 其广泛的应用。
主要内容
PART 01 PART 02 PART 03 PART 04 PART 05 PART 06 PART 07
5.1 函数的基本概念和性质
定义5.4 设A和B是任意两个集合，记：B A { f f : A B} 为从A到B的 所有函数的集合。
例5.6 设集合X={a,b,c}和集合Y={0,1}。试求出所有可能的函数f: X→Y。 解：首先求出的X×Y所有序偶，于是应有

离散数学第05章 函数

离散数学第05章 函数
定理5.3.1 设f:AB和g:BC是函数，通 过复合运算o，可以得到新的从A到C的函数， 记为gof，即对任意aA，有(gof)(x)=g(f(x))。
注意，函数是一种关系，今用斜体“o”表 示函数复合运算，记为gof，这是“左复合”， 它与关系的“右复合”fog次序正好相反，为区 分它们在同一公式中的出现，用粗体符号表示 关系复合fog，故有gof=fog。
BA={f|f:AB}
设 |A|=m ， |B|=n ， 则 |BA|=nm 。 这 是 因 为 对 每个自变元，它的函数值都有n种取法，故总共 有nm种从A到B的函数。
上面介绍一元函数，下面给出多元函数的 定义。
n 定义5.1.5 设A1,A2,···,An和B为集合，若f:
AiB 为 函 数 ， 则 称 f 为 n 元 函 数 。 在
定理5.4.4 （Zermelo）设A和B是任意两个 集合，则下述情况恰有一个成立：
① |A|<|B| ② |B|<|A| ③ |A|=|B|
定理5.4.5 （Cantor-Schroder-Bernstein） 设A和B是任意两个集合，若|A|≤|B|和|B|≤|A|， 则|A|=|B|。
本定理对证明两集合具有相同基数提供了 有效的方法。若能够构造一单射函数f:AB， 则有|A|≤|B|；又能构造另一个单射函数g:BC， 以证明|B|≤|A|。于是根据本定理即可得出|A|=|B|。 特别要注意，f和g不必是满射。因为通常构造 这样两个单射函数比构造一个双射函数要容易 许多。
该定义说明了，B中的每个元素b是且仅是 A中某个元素a的像。因此，若A和B是有穷集合， 存在双射函数f:AB，则|A|=|B|。
定义5.2.4 设f:AB是函数，若存在bB， 使 对 任 意 aA 有 f(a)=b ， 即 f(A)={b} ， 则 称 f:AB为常值函数。

离散数学第5章_函数

离散数学第5章_函数

第5章 函数
证明 f和ρf的图示如图5 ― 2所示。 1) 任取a∈A， 有f(a)＝f(a)， 所以 (a， a)∈ρf， 故ρf自反； 任取a， b∈A， 若(a， b)∈ρf， 则f(a)＝f(b)， 所以 f(b)＝f(a)， 即(b 任取a， b， c∈A， 若(a， b)∈ρf， (b， c)∈ρf， 则f(a)＝f(b)， f(b)＝f(c) ， 所以 f(a)＝f(c)， 即(a， c)∈ρf； 故ρf传递。 综上ρf是A上的等价关系。
第5章 函数
任取b∈Rf， 由Rf的定义， 有a∈A， 使f(a)＝b， 即有［a］∈A/ρf， 使得 g(［a］)＝f(a)＝b。 所以 g是满射。 综上g是双射。 定义 5.1 ― 5 恒等关系IA＝｛(a， a)|a∈A｝是A 到A的双射， 它称为A上的恒等函数。 定义 5.1 ― 6 若函数f： A→B， 对一切a∈A， 都 有f(a)＝b， b∈B， 则f称为常函数。
第5章 函数
定义 5.1 ― 2 设有函数f： A→B， g： C→D， 若 有A＝C、 B＝D且对所有的x∈A， 有f(x)＝g(x)， 则称 函数f和g相等， 记为f＝g。 定义 5.1 ― 3 集合A到集合B的所有函数的集合记 为BA， 即 BA＝｛f|f： A→B｝
第5章 函数
定理 5.1 ― 1 当A和B是有限集合时,有 |BA|＝|B||A| 证明 设|A|＝m， |B|＝n（m， n∈Ｎ）； 又设A＝｛a1， a2， …， am｝。 因为 Df＝A，所以 f＝｛(a1， f(a1))， (a2， f(a2))， …， (am ， f(am))｝。 而每个f(ai)（i∈Ｎm）都有n种可能， {n·n·…·n } ＝n +m个 m个即 |BA|＝|B||A|

离散数学_函数


因此f(A∪ 因此 ∪B)=f(A)∪f(B)。 ∪ 。
）、（3）的证明请读者完成。注意，（ ，（2）、 （2）、（ ）的证明请读者完成。注意，（ ）、 ）、（ （3）中的包含符号不能用等号代替。我们举例说 ）中的包含符号不能用等号代替。 明。
函数（ 第五章 函数（Functions） ）
【例3】 设X={a,b,c,d}，Y={1,2,3,4,5}，f : 】 ， ， X→Y,如图 如图4.1.3所示。那么， 所示。 如图 所示 那么， f ({a})={2}, f ({b})={2}, f ({a})∩f({b})={2} f ({a})-f({b})= ∅
函数（ 第五章 函数（Functions） ）
证明 （1）对任一 ∈Y ）对任一y∈ y∈f(A∪B)⇔ x(x∈A∪B∧y=f(x)) ∈ ∪ ∈ ∪ ∧ ∃ ∈ ∧ ∨ ∈ ∧ ⇔ ∃ x((x∈A∧y=f(x))∨(x∈B∧y=f(x))) ∈ ∧ ∨ ∈ ∧ ⇔ ∃ x(x∈A∧y=f(x))∨x(x∈B∧y=f(x)) ∈ ∨ ∈ ⇔ y∈f(A)∨y∈f(B) ∈ ∪ ⇔ y∈f(A)∪f(B)
⊆ ），且对每一 系 （f X×Y），且对每一 ∈X，都有唯一的 × ），且对每一x∈ ，
y∈Y，使〈x,y〉∈f，称 f 为X到Y的函数 ∈ ， 〉 ， 到 的函数 （functions），记为 f：X→Y。当 ），记为 ： ）， 。
X=X1×X2×…×Xn时，称f为n元函数。函数也 元函数。 × 为 元函数 称映射（ 称映射（mapping）。 ）。
函数（ 第五章 函数（Functions） ）
换言之，函数是特殊的关系， 换言之，函数是特殊的关系，它满足 （1）函数的定义域是 ，而不能是 的某个真子集 ）函数的定义域是X，而不能是X的某个真子集 (即dom(f )=X)。 即 。 （2）若〈x,y〉∈f，〈x,y′〉∈f，则y＝y′（单值 ） 〉 ， 〉 ， ＝ （ 性）。

《离散数学》 第五章 函数

（1）函数的基本概念 （2）单射、满射和双射函数 （3）函数的复合运算 （4）函数的逆运算 （5）置换
主要内容
5.1 函数的概念 5.2 函数的性质 5.3 复合函数与逆函数
5.1 函数的概念
定义5.1.1 设和Y是任意两个集合，f是一个从X到Y的二元关系， 如果f满足：对于每一个x∈X，都有唯一的y∈Y，使得<x， y>∈f，则称关系f为X到Y的函数，记作： f：X → Y 或 X Y 当<x，y>∈f时，通常记为y＝f(x)，这f时 称x为函数的自变量 （或原象），y为x在f下的函数值（或映像）。集合X称为f的 定义域，由所有映像组成的集合称为函数的值域，记作f(X) 。
5.1 函数的概念
例5.1.1 判断下列关系中哪个能构成函数。 （1）集合X＝{a，b，c，d}，Y＝{1，2，3，4，5，6}，f1，f2， f3分别是X到Y的二元关系，其中 f1＝{<a，2>，<b，5>，<c，1>，<d，4>} f2＝{<a，2>，<b，6>，<d，4>} f3＝{<a，3>，<b，1>，<c，5>，<d，2>，<d，4>}
解 （1）f1不是从X到Y的函数，因为dom f1＝{1，2，3}≠X； f2是从X到Y的函数，但f2（3）＝ f2（5）＝c，ran f2＝{a，b，c， e}≠Y，因此f2既非单射也非满射； f3是从X到Y的双射函数。
5.2 函数的性质
例5.2.1 确定如下关系是否是函数，若是函数，是否是单射、满射、 双射。
（3）设f：X → X，对于任意的x1，x2∈X，如果x1＜ x2，则有f（x1）≤f（x2），就称f为单调递增；如果x1＜x2， 则有f（x1）＜f（x2），就称f为严格单调递增的。类似地 也可以定义单调递减和严格单调递减的函数。它们统称为 单调函数。

离散数学_5函数


可见这里所说的函数与以前的数学中函数有区别。 可见这里所说的函数与以前的数学中函数有区别。 这里所说的函数与以前的数学中函数有区别 2.自变元与函数值 像源与映像 ：f:X→Y, 如果 自变元与函数值(像源与映像 自变元与函数值 像源与映像) → 如果<x,y>∈f, ∈ 是自变元(像源 的映像) 称x是自变元 像源 ，称 y是x 的函数值 的映像 。 是自变元 像源)， 是 的函数值(x的映像 <x,y>∈f y=f(x) f:x→y ∈ →
例 f:X→Y, g:Y→Z → → X = {1,2,3} Y={1,2,3,4} Z={1,2,3,4,5} f = {<1,2>,<2,4>,<3,1>} g = { <1,3>,<2,5>,<3,2>,<4,1> } g f = { <1,3>,<2,5>,<3,2>,<4,1> } {<1,2>,<2,4>,<3,1>} <3,3> } = { <1,5> , <2,1>， 用有向图复合: 用有向图复合: f X → 1。 2。 3。 g Y → Z 。 。 1 1 。 2 。 。 2 3 。 。 4 3 。 。 5
源程序
编译 目标代码
硬币
自动售货机
商品
具有分析、使用函数的能力在很多领域都是十分重要的。 具有分析、使用函数的能力在很多领域都是十分重要的。 本章主要介绍函数的概念、函数的复合、逆函数， 本章主要介绍函数的概念、函数的复合、逆函数，以 及在集合的基数中的应用。 及在集合的基数中的应用。
5-1 函数的基本概念

《离散数学》函数


A
B
C
y=f(x)
z =g( y ) =( g◦f )( x )
x
29
函数的复合
例
– f ： → ，f (x) = x+1， – g ： → ，g(x) = 2x+1, – h ： → ，h(x) = x2+1, g ◦ f (x)=g(f(x)) =2f(x)+1 =2(x+1)+1=2x+3 f ◦ g(x)=f(g(x)) =g(x)+1 =2x+1+1=2x+2 h ◦ g ◦ f (x)=h(g(f(x))) = (2x+3)2+1
20
函数的性质
练习 – f： + → + ， – f(1) = 1，f(n) = n–1 (n>1)
– 单射? – 满射? – 双射?
21
函数的性质
对于有限集合上的函数，有如 下主要结果：
定理 假设 A 和 B 是两个有限集合
且满足 |A| = |B|，则函数 f : AB 是单射当且仅当 f 是满射。
第五章 函数
《离散数学及应用》
第五章 函数
§5.1 函数的定义 §5.2 函数的性质 §5.3 函数的复合 §5.4 逆函数 §5.5 计算机科学中的常用函数 *§5.6 双射函数及集合的势
2
函数
A 和 B 为非空集合 设 f 为 A 到 B 的二元关系, 若对于任意 xDom( f ) 都存在唯一的 yRan( f ) 使得 (x, y)f 成立，则称 f 为函数 (function)。 函 数 也 称 作 映 射 （ mapping ） 或 变 换 （transformation）
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
证：a. 先证 f : X→Y是入射 它是一个满射
若 f 是入射，则X = f(X)(一对一映射源的个数=象的个数)。因 为 f(X) = Y (由定理条件 X=Y，象的个数=Y的元素个数)和 f(X)Y 。又因为Y是有限集合，故 f(X) =Y。 f: X→Y是满射， b. 再证 f : X→Y是一个满射 它是入射 若 f 是满射（f(X) =Y），则 X = Y = f(X)。又因为X是有限 集合，源的个数=象的个数，所以 f: X→Y是入射。
对应的元素共有2种取法， am对应的元素共有1种取法。
故 f：A→B 的不同双射共有m(m-1)(m-2)…2·1=m! (个)

三、常用函数
定义5.1.6 (1) 设 f：AB，如果存在cB使得对所有的 xA都有
f(x)=c，则称 f：AB是常函数。 (2) 称A上的恒等关系IA为A上的恒等函数，对所有的 xA都有 IA(x)=x。 (3) 设<A，≼>，<B，≼>为偏序集，f：AB，如果对任意的x1， x2A，x1≺x2，就有 f(x1)≼f(x2)，则称 f 为单调递增的；如果对 任意的x1，x2A，x1≺x2，就有 f(x1)≺f(x2)，则称 f 为严格单调 递增的。 (4) 设A为集合，对于任意的A’A，A’的特征函数 A‘：A{0,1} 定义为 A' (a)=1，aA' A' (a)=0，aA-A' (5) 设R是A上的等价关系，令 g：AA/R，g(a)=[a]，aA 称 g 是从A到商集A/R的自然映射。
(a) 证 f -1 是一个满射
∵
xX，y 有 <x,y>f， <y,x>f -1,
因此，仅当 f 是双射函数时，它的逆函数 f c
存在。 f c 记为 f -1。
逆函数存在的条件 定理5.2.1 设 f: XY是一个双射函数，那么 f -1
为Y到X的双射函数，即有 f -1 : YX 。
证：
① 证 f -1 是一个函数（需要证存在性和唯一性）
② 证 f -1 也是双射的（ f -1 : YX 的双射）
Y中元素若有原象 则原象唯一
例：函数f：{a,b}→{2,4,6}为 f(a)=2, f(b)=6，则这个
函数是入射，但不是满射。
定义5.1.7 如果 f 既是X到Y的单射，又是X到Y的满射，
则称 f 为X到Y的双射函数（bejection）。双射函数也称
一一对应。
Y中的每一元 素都有原象且 原象唯一
3、函数集合
从函数的定义可以知道，X Y的子集并不能都成为X 到Y的函数。
例：设X={a,b,c}，Y={0,1}，
XY={<a,0>,<b,0>,<c,0>,<a,1>,<b,1>,<c,1>} XY有26个可能的子集，但其中只有23个子集定义为 从X到Y的函数。
f0={<a,0>,<b,0>,<c,0>}
注：此定理不适用于无限集合上的映射。
例：设A和B是有穷集合，有多少不同入射函数和多
少不同的双射函数?
解：设|A|=m，|B|=n，要使映射 f：A→B 为入射，必须有
|A|≤|B|，即m≤n。在B中任意选出m个元素的任一全排列，就 能形成的一个不同的入射，故的不同入射共有：
(个)
要使映射 f：A→B 为双射，必须 |A|=|B|。 设A={a1,a2,…,am}，B={b1,b2,…,bm}，则对a1对应的元 素共有m种取法， a2对应的元素共有m-1种取法，…… am-1
能够成为函数。
2、函数相等
因为函数是序偶的集合，故两个函数相等可用集合 相等的概念予以定义。
定义5.1.2 设函数 f: A→B，g: C→D，如果A=C，
B=D，且对所有xA和xC，都有f(x)=g(x)，则称 函数f等于函数g, 记为 f=g。 如果AC，B＝D，且对每一xA，f(x)＝g(x) 。则 称 函数f包含于函数g，记为fg。
对yY，设 x1和 x2X，使得 <y, x1> f -1∧ <y, x2> f -1 成立， 即有 <x1 , y > f ∧ <x2 , y> f ∵ f 是单射的，得 x1= x2
yY，! xX与之对应，故 f -1 是函数。
f -1 是YX的函数。
② 证 f -1 也是双射的（ f -1 :YX 的双射）
f(a)=1，f(b)=1，f(c)=3，f(d)=2 则 f 是满射的。
定义5.1.6 从X到Y的映射中，X中没有两个元素有相
同的象，则称这个映射为入射（或一对一映射）。
设 f：X→Y，如果对任意x1，x2X , x1x2 蕴涵
f(x1) f(x2)。则称 f 为X到Y的单射函数(injection)， 单射函数也称一对一的函数或入射函数。
那么，在什么情况下 f 的逆 f c 是函数呢？
设 f：AB，则 f c：BA是函数：
Dom f c =B，即ran f = B f 是满射； 单值性：<y,x1>f c <y,x2>f c x1 = x2 即有： <x1,y >f <x2,y>f x1= x2
f 是单射。
即Y的每一个元素是X中一个或多个元素的象点， 则称这个映射为满射（或到上映射）。
设 f：XY ，如果对任意 yY，均有 xX，使 y=f(x)， 即ran f=Y，则称 f为X到Y的满射函数(surjection)。
Y中的每一元 素都有原象
例：A={a,b,c,d}，B={1,2,3}，如果 f：AB为
3、函数集合
设X和Y都为有限集，分别有m个和n个不同元素，
由于从X到Y任意一个函数的定义域是X，在这些函数
中每一个恰有m个序偶。另外任何元素x X，可以有Y
的n个元素中任何一个作为它的象，故共有nm个不同的
函数。 在上例中n=2，m=3，故应有23个不同的函数。今后 我们用符号YX表示从X到Y的所有函数的集合，甚至当 X和Y是无限集时，也用这个符号。
第五章 函数
本章主要从关系的角度讲授函数的基本概念
和函数的运算。
要求掌握函数的基本概念，能够判断给定函
数的类型（满射、入射、双射），能够对于 给定的函数进行运算。
函数是一个基本的数学概念，在通常的函数定 义中，y= f(x) 是在实数集合上讨论，我们这里 把函数概念予以推广，把函数看作是一种特殊 的关系。 例如：
二、函数的性质 三、常用函数

一、函数的定义
1、定义
定义5.1.1 设X，Y为任何两个集合，如果 f 为X到Y
的关系（fXY），且对每一 xX，都有唯一的 yY，使 <x , y>f 。则称 f 是X到Y的函数 （functions），记为 f：XY，
当X=X1…Xn时，称 f 为n元函数。函数也称映射 （mapping）或变换(transformation）。 若<x , y>f ，则x称为自变量，y称为在f作用下x的象， <x , y>f 记作y=f(x)。dom f=X
计算机中把输入、输出间的关系看成是一种 函数； 在开关理论、自动机理论和可计算性理论等 领域中，函数是有着极其广泛的应用。
第五章 函数
5.1 函数的概念 5.2 逆函数和复合函数 5.3 置换 (补充)
5.4 基数的概念
5.5 可数集与不可数集 5.6 基数的比较
5.1 函数的概念
一、函数的定义
5.2 逆函数和复合函数
一、逆函数
对任意给定函数，它的逆不一定是函数，只是一个 二元关系。
例：f ={<x1,y1>,<x2,y2>,< x3,y2 >}，
f c ={<y1,x1>,<y2,x2>, <y2,x3>}
显然，f c 不是函数。
∵ y2∈dom f c 有x2和x3两个值与之对应，
f c 不是函数。
f2={<a,0>,<b,1>,<c,0>} f4={<a,1>,<b,0>,<c,0>} f6={<a,1>,<b,1>,<c,0>}
f1={<a,0>,<b,0>,<c,1>}
f3={<a,0>,<b,1>,<c,1>} f5={<a,1>,<b,0>,<c,1>} f7={<a,1>,<b,1>,<c,1>}
证：① 证 f -1 是一个函数
设 f={ <x, y> | xX∧ yY∧ f(x)=y } f -1={ <y, x> | <x, y> f } ∵ f 是函数， f -1是关系。 又∵ f 双射，即 dom f = X, ran f = Y 有
dom f -1 = ran f = Y，ran f -1 = dom f = X
说明： 若|A|＝m，|B|＝n，且m,n>0，则|BA|＝nm。 当A或B至少有一个集合是空集时： A＝且B＝，则BA＝＝{}。 A＝且B≠，则BA＝B＝{}。 A≠且B＝，则BA＝A＝。

二、函数的性质
定义5.1.5 对于 f：XY的映射中，如果ran f=Y，
由定义可知，两个函数 f 和 g 相等, 一定满足 下面两个条件：
（1）dom f＝dom g
（2）x∈dom f＝dom g，都有 f(x)＝g(x) 例：函数 f(x)＝(x21)/(x+1)，g(x)＝x1不相等，