离散数学函数

离散数学函数第1页，课件共15页，创作于2023年2月§5.1函数的定义和性质高等数学课程中详细研究了函数的概念和性质，但这些函数概念一般不好直接应用地计算机科学。如数据结构，开关理论，自动机等。计算机科学要求推广以往的函数概念。第2页，课件共15页，创作于2023年2月函数：设F为二元关系，如F1={<x1,y1>,<x2,y1>,<x3,y2>}是函数F2={<x1,y1>,<x1,y2>,<x2,y1>,<x3,y2>}不是函数若对任意的xdomF都存在唯一的yranF，使得xFy成立，则F为函数，y是F在x的函数值。第3页，课件共15页，创作于2023年2月从A到B的函数：设A、B是集合，如果函数f满足以下条件(1)domf=A(2)ranf

B则称f是从A到B的函数，记作：f：A

B集A'

在

f

下的象：设f：A

B，A'

A，则f[A']是A'在f下的象。则f(A')={f(x)|x

A'}=

f[A']，

第4页，课件共15页，创作于2023年2月设函数f：A

B(1)若ranf=B，则说f具有满射性；(2)若对于任何x1,x2

A，x1

x2都有f(x1)f(x2)，则说f具有单射性；(3)若f既具有满射性，又具有单射性，则说f具有双射性。函数的性质第5页，课件共15页，创作于2023年2月例5.1判断以下函数的单射、满射和双射性。(1)f：R

R

R

R，R为实数集f(<x,y>)=<x+y,x

y

解：(1)先说f是单射的。这要证明对任取<x,y>，<u,v>

R

R。反证，如果<x+y,x

y>=<u+v,uv>，则，x+y

=u+v且x

y=u

v。<x,y>

<u,v>时,<x+y,x

y><u+v,u

v>；第6页，课件共15页，创作于2023年2月解关于x,y的方程组知：x=u且y=v，故<x,y>=<u,v>与已知矛盾。再说f是满射的。这只要让对任意的(u,v)

R

R，可以找到<x,y>

R

R,使得f(<x,y>)=<u,v>就可以了。由f的定义有x+y=u和x

y=v综上所述，f是双射的。第7页，课件共15页，创作于2023年2月(2)f：N

N

N，N为自然数集(0N)f(<x,y>)=|x2

y2|解：

f不是单射，因为f(<2,2>)=f(<1,1>)=0；f不是满射，因为找不到自然数x和y满足|x2

y2|=2，所以2ranf

第8页，课件共15页，创作于2023年2月特征函数：设A为集合，XA'(a)=1a

A'0a

A

A'如A={a,b,c}，A'={a}，则XA'(a)=1，XA'(b)=XA'(c)=0对于任意的A'

A，A'的特征函数XA'：A{0，1}定义为：第9页，课件共15页，创作于2023年2月自然映射：设R是A上的等价关系，如：A={1,2,3}，R={<1,2>,<2,1>}∪IA则有g(1)=g(2)={1,2}，g(3)={3}称g为从A到A/R的自然映射。定义一个从A到A/R的函数g：A

A/R且g(a)=[a]，它把A中的元素a映到a的等价类[a]。第10页，课件共15页，创作于2023年2月§5.2函数的运算由定义可知：只有当f：A

B是双射函数时，它才有逆函数.函数的逆：关系f是从A到B的一个函数，如果f的逆关系f1也是一个函数(B到A的)，这个函数称之为f的逆函数，记作f1：B

A。第11页，课件共15页，创作于2023年2月函数的合成：设f：

A

B和g：B

C都是函数，则合成关系g

f={<a,c>|a

A

c

C

b(b

B

<a,b>f

<b,c>g)}称为f与g的合成函数：g

f：A

C第12页，课件共15页，创作于2023年2月例5.2设函数f：R

R,f(x)=3x+2,求f2,f3,f4解：∵

f2=f

f

∴f2(x)=f(f(x))=f(3x+2)∵f3=f

f2

∴f3(x)=f(f2(x))∵f4=f

f3

∴f4(x)=f(f3(x))=3(3x+2)+2=9x+8

=3f2(x)+2=3(9x+8)+2=27x+26

=3f3(x)+2=3(27x+26)+2=81x+80

第13页，课件共15页，创作于2023年2月合成运算的性质(1)若f:A

B,g:B

C都是满射，则g

f也是满射；(2)若f:A

B,g:

B

C都是单射，则g

f也是单射；(3)若f:A

B,g:B

C都是