离散数学

f · · ··a c 1 2 3

b

5、设函数f :A?B，若f 既是满射的，又是单射的，则称f 是双射的（或一一对应的）。

6、设f :R?R，对于任意的x1, x2?R，若x1

设R是A上的等价关系，定义一个从A到A/R的函数g:A?A/R且g(a)=[a]，它把A中的元素a映射到a的等价类[a]，称g是从A到商集A/R的自然映射。 例：

1. 设A={a, b, c}, A’={a}，则有函数?A’ :A?{0, 1}，

?A’ (a)=1, ?A’ (b)=0, ?A’ (c)=0.

2. 设A={1, 2, 3}, R={<1,2>,<2,1>}∪IA，则有函数g:A?A/R， g(1)=g(2)={1, 2}, g(3)={3}.

4.7函数的复合和反函数

设函数g :A?B, f :B?C，则复合函数 f ? g :A?C定义为： 对任意的x∈A，有(f ? g)(x) = f (g (x)).（函数的复合运算，积运算） 例： 设f :Z?Z, f(x) = 2x + 3, g:Z?Z,

g(x) = 3x + 2. 求 f ? g和g ? f.

(f ? g )(x) = f (g(x)) = f (3x + 2)

= 2(3x + 2) + 3 = 6x + 7 (g ? f )(x) = g(f (x)) = g(2x + 3)

= 3(2x + 3) + 2 = 6x + 11 [定理]：设f :A→B, g:B→C。 （1）若f, g都是满射，则g?f :A→C也是满射； （2）若f, g都是单射，则g?f :A→C也是单射； （3）若f, g都是双射，则g?f :A→C也是双射。

证明(2)：对任意x1∈A，x2∈A且x1≠x2，由于f 是单射，故有： f (x1) ≠f (x2) 记 f (x1 ) =y1， f (x2 ) =y2 . 又因为g是单射，所以， g(y1) ≠g(y2)

从而，g(f (x1) ≠ g(f (x2)，即 g?f (x1) ≠ g?f (x2).

对于双射函数f :A?B，称f -1:B?A是

f 的反函数。

对于任意x∈A, y∈B，若f (x)=y，则 f -1(y)=x.

[定理]： 设f :A?B是双射的，则f -1是函数，且是从B到A的双射函数。 对任何双射函数f :A?B和它的反函数f -1 :B?A，它们的复合函数都是恒等函数，且满足f -1? f = IA , f ? f –1= IB .

图中定义了函数f , g和h.

· ··

f 1 2 3 4 1 · ··5

· ··2 3 4

1 2 3 4 g 设V1=，V2=，其中，?和?’是二元运算，△和△’是一元运算，k1?S1，k2?S2是代数常数，如果映射?: S1→S2满足以下条件： ?x, y?S1，都有：

?(x ? y)= ?(x) ?’ ?(y)， ?(△x)= △’?(x)，

?(k1)=k2.

则称?是V1到V2的同态映射，简称同态。 例1：设V1=，V2=，其中+为普通加法， ?为模n加法，即?x, y?Zn，有x ? y=(x+y) mod n，这里Zn={0, 1, …, n-1}。令?: Z→Zn，?(x)=(x) mod n， 则?是V1到V2的同态。 ∵?x, y?Z，有：

?(x+y)=(x+y) mod n=(x) mod n ? (y) mod n =?(x) ? ?(y). 例2：

设V1=，V2=，其中R为实数集合，+和·为普通加法和乘法。令?: R→R，?(x)=ex，则?是V1到V2的同态。 ∵?x, y?R，有：

?(x+y) = ex+y = ex · ey = ?(x) · ?(y).

例3：

设V1=，V2=，其中+和· 分别表示普通加法和乘法，-x表示求x的相反数，x -1表示求x的倒数。令

?: R→R+ ，?(x)=ex，则?是V1到V2的同态。

∵?x, y?R，有：

?(x+y)= ex+y = ex · ey = ?(x) · ?(y), ?(-x)= e-x = (ex)-1= (?(x))-1. 例4：

设V1=，V2=，其中+为普通加法， ?为模n加法，令

?: Z→Zn，?(x)=(x) mod n，则?是V1到V2的同态。

∵?x, y?Z，有：

?(x+y) = (x+y) mod n

= (x) mod n ? (y) mod n = ?(x) ? ?(y), ?(0) = 0 mod n = 0.

6

· · 1 2 3 4

(1) 求f , g和h的象。

(2) 求g ? f , f ?h和g ? g .

(3) 指出f, g, h中哪些函数是单射的，哪些函数是满射的。

(4) f, g, h种哪些函数存在反函数，给出其反函数的表达式。

解：(1) 令A={1,2,3,4}，则f, g, h都是从A到A的函数，

f(A)={1, 2, 4}, g(A)={1, 2, 3, 4}=A, h(A)={1, 3}.

(2) g?f :A?A, g?f (1)=4, g?f (2)=2, g?f (3)=2, g?f (4)=3.

f ?h:A?A, f ?h(1)=2, f ?h(2)=1, f ?h(3)=2, f ?h(4)=1.

g ?g:A?A, g ?g(1)=4, g ?g(2)=3, g ?g(3)=2, g ?g(4)=1.

(3) 只有g是单射的，满射的。

(4) 只有g有反函数g-1 :A?A, g-1(1)=3, g-1(2)=1,

g-1(3)=4, g-1(4)=2.

5.3 代数系统的同态与同构

· · · ·h 1 ·· · ·· · ··2 3 4

设?是V1=到V2=的同态，则称是V1在?下的同态象。

设?是V1=到V2=的同态，如果?是满射的，则称?为V1到V2的满同态，记作V1 V2 。如果?是单射的，则称?为V1到V2的单同态，如果?是双射的，则称?为V1到V2的同构，记作 V1 V2 。

自同态：V到V自身的同态； 零同态：所有元素映射到幺元； 自同构：双射的自同态； 单自同态：单射的自同态。 定理：

设V1, V2为代数系统，?和*为V1上的二元运算，?’和*’为V2上的二元运算，如果?: V1→V2是从Vl到V2的满同态，则：

(1) 若?是可交换的（可结合的，幂等的），则?’也是可交换的（可结合的，幂等的）。 (2) 若?对*是可分配的，则?’对*’也是可分配的；若?对*是可吸收的，则?’对*’也是可吸收的。

(3) 若e为?运算的幺元，则?(e)为?’运算的幺元。

(4) 若?为?运算的零元，则?(?)为?’运算的零元。

(5) 设u?V1，若u-1是u关于?运算的逆元，则?(u-1)是?(u)的逆元，即?(u)-1= ?(u-1)。

6.1群

设V=是代数系统，?为二元运算，如果?是可结合的，则称V为半群。 如： (1) , , , , 都是半群，其中+表示普通加法。 (2) 是半群，其中·表示矩阵乘法。 可交换半群：半群V中的二元运算可交换。 含幺半群（独异点）：半群V中的二元运算含有幺元。

子半群：半群的子代数。

子独异点：独异点的子代数。

积半群：若V1, V2是半群，则V1?V2是积半群。

积独异点：若V1, V2是独异点，则V1?V2是积独异点。

(1) , , , , 都是可交换半群。 (2) 不是可交换半群，因为矩阵乘法不适合交换律。

(1)中除了外都是独异点，其中普通加法的幺元是0。 (2) 是独异点，矩阵乘法的幺元是n阶单位矩阵E。

, 都是的子半群，且 也是的子独异点，但不是的子独异点，因为幺元0?Z，但0?Z+。

设V1=, V2=为半群，?: S1→S2，且?x, y?S1，有： ?(x ? y)= ?(x) * ?(y)，

则称?为半群V1到V2的同态。

设V1=, V2=为独异点，

?: S1→S2，且?x, y?S1，有：

?(x ? y)= ?(x) * ?(y)， ?(e1)= e2， 则称?为独异点V1到V2的同态。

设是代数系统，?为二元运算。如果?是可结合的，存在幺元e?G，并且对G中的任意元素x都有x-1?G，则称G为群。 如，

(1) , , 都是群，而 , 不是群，因为中的元素都没有逆元，而在中只有0有逆元0。 (2) 不是群，因为不是所有的实矩阵都有逆矩阵。 设G={a, b, c, e}，·为G上的二元运算，由下表给出，不难证明G是一个群。

7