《离散数学》 - 8-函数(Function).pdfVIP

《离散数学》

8-函数(Function)

杨启哲

上海师范大学信机学院计算机系

2023年11月9日

主要内容

函数的基本概念

集合基数

可计算性理论简介

2

函数的基本概念

什么是函数？

我们已经接触到各式各样的函数，比如：

•fxx21

()=+

•f(x)=sinx+cos2x

•f(x)=1

1+e−x



•f(x)=1,x∈Q



0,x∈/Q

可以看到，这些函数其实反映了x与y的某种关系，现在我们从关系的角度来给出函数的

定义。

4

函数的定义

定义1[函数].

令f是一个A到B的二元关系，若dom(f)=A并且对于任意x∈dom(f)。存在唯一的

y∈ran(f)使得(x,y)∈f，则称f是A到B的函数（映射），记作f:A→B。xfy也被

记作y=f(x)，并称y为f在x的值。

例2.

1.f1={(x1,y1),(x2,y2),(x3,y1)}是一个函数。

2.f2={(x1,y1),(x2,y2),(x3,y1),(x1,y2)}不是一个函数。

补充说明

1.上述定义对多元函数也是符合的，因为x可以理解成一个n元组。

2.如果dom(f)⊂A，则称f是A到B的部分函数(PartialFunction)。

5

函数相等

由上述可知，一个函数可以看成一个集合，因此两个函数相等可以视作两个集合相等。

定义3[函数相等].

令F,G是函数，则F=G⇔F⊆G∧G⊆F，即若F=G则我们有：

1.dom(F)=dom(G)

2.∀x∈dom(F),F(x)=G(x)

例4.

1.函数f(x)=x−1和f(x)=x2−1是不相等的。

x+1

2.函数f(x)=sin(π−2x)与函数g(x)=cos2x是相等的。

2

6

一些其他的概念

•像：令函数f:A→B，A⊆A，则f(A)={f(x)|x∈A}称为A在f下的像。

1111

•完全原像：令函数f:A→B，B⊆B，则f−1(B)={x|x∈A∧f(x)∈B}称为B在

1111