离散数学讲义第三章(2)

离散数学课件word2003

例1: 设A={a.b.c} B={1,2} f: A→B g: B→C gf: A→C 例2: f: 2A →Z g: Z→R

C={4,5}

f={(a,1),(b,1)(c,2)} g={( 1,4),(2,4)} 则 gf={(a,4),(b,4)(c,4)}是A到C的复合函数 . 是 到 的复合函数 A是有限集合 且f(s)=#s 是有限集合, 是有限集合 # g(z)=(z-5)/2 则gf: 2A →R 是2A 到R 复合

函数; 任意s∈ 函数 任意 ∈A , 有gf(s) =g(f(s))=g(#s)= (#s -5)/2 # # 函数g.f均为 均为A到 的函数 的函数. 例3: A={1.2.3} 函数 均为 到A的函数 f={(1,2)(2,3)(3,1)} g={(1,2)(2,1)(3,3)} 则 g f={(1,1)(2,3)(3,2)} fg={(1,3)(2,2)(3,1)}≠gf

离散数学课件word2003

二. 复合函数的性质 1) . 若f: A→B 2). 若f: A→B 则 f IA= Ibf=f g: B→C 同关系的性质类似. 同关系的性质类似

h: C→D 则

(hg)f=h(gf) 有结合律 (定理 有结合律. 定理 定理3.1) 3). 若fi: Ai →A i+1 (i=1,2,3, ……, n) fnf n-1 ……f1: A1 →A n+1

4). 若 f: A→A 则 fn: A→A 例4: 设f: I→I f(i) =2i+1 求f 3 解 : f 3(i)=f( f 2(i))=2 f 2(i)+1=2[2f(i)+1]+1= 2[2[2i+1]+1] +1 =8i+7 则

离散数学课件word2003

三.幂等函数 幂等函数 定义2: 若f: A→A ;且f 2=f, 则称f是幂等函数 显然幂等函数有 定义 且 则称 是幂等函数.显然幂等函数有 是幂等函数 f n=f . 任意S 其中p是素数 例5: f: 2N→2N 任意 ∈ 2N f (S)={n| n ∈S∩p}其中 是素数 其中 是幂等函数. 集. 则f是幂等函数 是幂等函数 因为任意S∈ 2N 因为任意 记S中的素数的集合为 P, 则 中的素数的集合为S 中的素数的集合为 所以

f 2(S) = f (f(S)) = f(SP)= SP= f(S) f 2=f 练习: 练习 是幂等函数. 即f 是幂等函数

f(x)=[x]是否为 到Z上的内射 满射 是否为R到 上的内射 满射. 上的内射.满射 是否为 [x]是取整函数 是取整函数. 是取整函数

离散数学课件word2003

复合函数的内射.满射 双射. 四.复合函数的内射 满射 双射 复合函数的内射 满射.双射 定理3.2 设f: A→B 定理 g: B→C 则

1).若f . g 均为内射 则gf为内射 若 均为内射,则 为内射 为内射. 2).若f . g 均为满射 则gf为满射 若 均为满射,则 为满射 为满射. 3).若f . g 均为双射 则gf为双射 若 均为双射,则 为双射 为双射. 证明: 1).任意 i.aj∈A ai≠aj 由f . g 均为内射 f (ai)≠ f (aj ) 任意a 均为内射, 证明 任意 g(f (ai))≠ g(f (aj )) 即( gf )(ai) ≠ ( gf )(aj ) 所以g f为内射 所以 为内射. 为内射 2).任意 ∈C 由f . g 均为满射 所以存在 b∈B,使 任意c∈ 均为满射, 任意 ∈ 使 g(b)=C, 对此 ∈B存在 ∈A 使f(a)=b,即g(f(a))=C, 对此b∈ 存在 存在a∈ 即 ( gf )(a) =C, 所以 为满射 所以gf为满射 为满射. 3).由1).2) gf为内射 gf为满射 所以 为双射 证毕 由 为内射; 为满射.所以 为双射. 为内射 为满射 所以gf为双射 证毕.

离散数学课件word2003

定理3.2的逆不全成立 即部分可逆 定理 的逆不全成立,即部分可逆 是下面的 的逆不全成立 即部分可逆,是下面的 定理3.3 设f: A→B 定理 g: B→C 则

1).若g f 为内射 则f为内射 若 为内射,则 为内射 为内射. 2).若g f 为满射 则g为满射 若 为满射,则 为满射 为满射. 3).若gf 为双射 则g为满射 f为内射 若 为双射,则 为满射 为内射 为满射; 为内射. 证明: 1).反证法 f非内射 即存在a 反证法:设 非内射,即存在 证明: 1).反证法:设f非内射,即存在ai.aj∈A ai≠aj 使 f(ai)=f(aj )=b 以, 设g(b)=c,则gf(ai)=gf(aj )=g(b)=c,与g f 为内射相矛盾 所 则 与 为内射相矛盾.所 b1 g a1 b2 f c1 f为内射 a2 为内射. 为内射 b3 c2a3 b4 c3

离散数学课件word2003

2). 反证法 设g不是满射 则存在 0∈C,使 任意 ∈B, g(b)≠c0. 反证法:设 不是满射 则存在c 不是满射.则存在 使 任意b∈ 但对此c 由于gf是满射 存在a∈ 是满射, 但对此 0∈C, 由于 是满射 存在 ∈A 使 (gf)(a ) = g(f(a)) =c0, 而f (a) ∈ Rf 矛盾,所以 为满射. 所以g为满射 与g(b) ≠

c0矛盾 所以 为满射b1 a1 a2 a3

Dg B

gc1 c2 b4 c3

f

b2 b3

3).是1).2)的综合 是 的综合. 的综合 推论:若f: A→B 推论 若 g: B→C h: C→D 当gf与hg均为双射时 与 均为双射时, 均为双射时

h .g . f均为 双射 均为 双射.