离散数学：第9讲 函数.ppt

*
函数
内容提要
函数(映射)定义
象,原象
单射,满射,双射,计数问题
常数函数,恒等函数,特征函数,单调函数,自然映射
复合,逆函数
*
函数(function)
函数: F是函数  F是单值的二元关系
F单值: xdomF, y,zranF,
xFy  xFz  y=z
函数亦称映射(mapping)
F(x)=y  <x,y>F  xFy
是函数,称为空函数
常用F,G,H,…,f,g,h,…表示函数.
x
y
z
非单值
单值
*
偏函数(partial function)
偏函数: domFA
A到B的偏函数: domFA且ranFB
偏函数记作 F:AB, 称A为F的前域,
A到B的全体偏函数记为AB
AB = { F | F:AB }
*
例1
例1: 设 A={a,b}, B={1,2}, 求AB.
解: |A|=2,|B|=2,|AB|=4,|P(AB)|=24=16.
f0=, f1={<a,1>}, f2={<a,2>},
f3={<b,1>}, f4={<b,2>},
f5={<a,1>,<b,1>}, f6={<a,1>,<b,2>},
f7={<a,2>,<b,1>},f8={<a,2>,<b,2>}.
AB = {f0 ,f1 ,f2 ,f3 ,f4 ,f 5,f6 ,f7 ,f8}. #
非函数: {<a,1>,<a,2>}, {<b,1>,<b,2>},
{<a,1>,<a,2>,<b,1>},…
*
全函数(total function)
全函数: domF=A
全函数记作 F:AB
A到B的全体全函数记为BA或AB
BA = AB = { F | F:AB }
*
关于BA的说明
BA={ F | F:AB }={ F | F是A到B全函数 }
|BA| = |B||A|.
当A=时, BA={}
当A且B=时, BA=AB=,
但AB={}.
*
真偏函数(proper partial function)
真偏函数: domFA,
真偏函数记作F:AB,
A到B的全体真偏函数记为AB
AB = { F | F:AB }
*
例1(续)
例1(续): 设 A={a,b}, B={1,2}, 求AB.
解: f0=, f1={<a,1>}, f2={<a,2>},
f3={<b,1>}, f4={<b,2>},
f5={<a,1>,<b,1>}, f6={<a,1>,<b,2>},
f7={<a,2>,<b,1>},f8={<a,2>,<b,2>}.
AB={f0 , f1 , f2 , f3 , f4}. #
*
三者关系
AB = AB  AB
偏函数AB domFA
全函数AB domF=A
真偏函数AB domFA
说明: FAB  FdomFB
FAB  FdomFB
*
函数(function)定义
：X和Y是两个集合，f是X到Y的关系，如果对于任意x∈X，有唯一的y∈Y使得<x,y>∈f，称关系f为函数，记作：f：X→Y或X Y。称x为原象,y为象。
;
f=A;