
离散数学笔记(7)——代数系统
代数结构(代数系统)
函数
定义
对于集合 X 与 Y,f 是从 X 到 Y 的关系,如果 x∈X,都存在唯一 y∈Y,使得 ⟨x,y⟩∈f,则称 f 是从 X 到 Y 的函数(变换、映射),记作 f:X→Y 或 Xf⟶Y,⟨x,y⟩∈f 可记为 y=f(x)。
如果 f:X→X 是函数,也称 f 是 X 上的函数。
定义域、值域和陪域(共域)
设 f:X→Y:
- f 的定义域,记作 domf 或 Df,即 Df=domf={x|x∈X∧∃y(y∈Y∧⟨x,y⟩∈f)}=X。
- f 的值域,记作 ranf 或 Rf 或 f(X),即 Rf=ranf=f(X)={y|y∈Y∧∃x(x∈X∧⟨x,y⟩∈f)}。
- f 的陪域,即 Y。
函数的表示方法
枚举法、关系图、关系矩阵、谓词描述法。
从 X 到 Y 的函数的集合 YX
YX={f|f:X→Y}
YX:它是由所有的从 X 到 Y 的函数构成的集合。
结论:若 X、Y 是有限集合,且 |X|=m,|Y|=n,则 |YX|=|Y||X|=nm。从 X 到 Y 的关系 =|P(X×Y)|=2nm。
规定:
- 从 ∅ 到 ∅ 的函数只有 f=∅。
- 从 ∅ 到 Y 的函数只有 f=∅。
- 若 X≠∅,则从 X 到 ∅ 的函数不存在。
特殊函数
- 常值函数:函数 f:X→Y,如果 ∃y0∈Y,使得对 ∀x∈X,有 f(x)=y0,即 ranf={y0},称 f 是常值函数。
- 恒等函数:恒等关系 IX 是 X 到 X 的函数,即 IX:X→X,称之为恒等函数。显然对于 ∀x∈X,有 IX(x)=x。
两个函数相等
设有两个函数 f:A→B,g:A→B,f=g 当且仅当,对任何 x∈A,有 f(x)=g(x)。
函数的类型
- 满射的:f:X→Y 是函数,如果 ranf=Y,则称 f 是满射的。
- 入射的:f:X→Y 是函数,如果对于任何 x1,x2∈X,如果 x1≠x2 有 f(x1)≠f(x2),则称 f 是入射的,也称 f 是单射的,也称 f 是一对一的。
- 双射的:f:X→Y 是函数,如果 f 既是满射的,又是入射的,则称 f 是双射的,也称 f 是一一对应的。
特别地,∅:∅→Y 是单射,∅:∅→∅ 是双射。
在 X 有限的情况下,f:X→X 是入射的,则 f 必是满射的。
函数的复合
设 f:X→Y, g:W→Z是函数,若 f(X)⊆W,则 g∘f={⟨x,z⟩|x∈X∧z∈Z∧∃y(y∈Y∧⟨x,y⟩∈f∧⟨y,z⟩∈g)} 称为 g 在 f 的左边可复合。
定理:两个函数的复合是一个函数。
定义:设 f:X→Y, g:Y→Z是函数,则定义 g∘f={⟨x,z⟩|x∈X∧z∈Z∧∃y(y∈Y∧⟨x,y⟩∈f∧⟨y,z⟩∈g)},则称 g∘f 为 f 与 g 的复合函数(左复合)。
结论:(g∘f)(x)=g(f(x))
复合函数的计算同复合关系。
性质:
- (满足可结合性)f:X→Y,g:Y→Z,h:Z→W 是函数,则 (h∘g)∘f=h∘(g∘f)。
f:X→Y,g:Y→Z 是两个函数,则:
- 如果 f 和 g 是满射的,则 g∘f 也是满射的。
- 如果 f 和 g 是入射的,则 g∘f 也是入射的。
- 如果 f 和 g 是双射的,则 g∘f 也是双射的。
f:X→Y,g:Y→Z 是两个函数,则:
- 如果 g∘f 是满射的,则 g 是满射的。
- 如果 g∘f 是入射的,则 f 是入射的。
- 如果 g∘f 是双射的,则 f 是入射的且 g 是满射的。
- f:X→Y 是函数,则 f∘IX=f 且 IY∘f=f。
逆函数
定理 1:若 f 是 X→Y 的双射,则 fc 是 Y→X 的函数。
定义:设 f 是 X→Y 的双射函数,则称 fc:Y→X 为 f 的逆函数,并记为 f−1。
定理 2:f−1 是 Y→X 的双射函数。
性质:
- 设 f 是 X→Y 的双射函数,则 (f−1)−1=f。
设 f 是 X→Y 的双射函数,则 f−1∘f=IX 且 f∘f−1=IY。
令 f:X→Y,g:Y→X 是两个函数,如果 g∘f=IX 且 f∘g=IY,则 g=f−1。
令 f:X→Y,g:Y→X 是两个双射函数,则 (g∘f)−1=f−1∘g−1。
代数结构(系统)的概念
n 元运算
设 X,Y 是集合,f:Xn→Y 是个映射,则称 f 是 X 上的一个 n 元运算。
主要讨论二元运算,一般用 x⋆y=z 表示 f(⟨x,y⟩)=z。
二元运算的运算表
可用一个表来表示二元运算的运算规律。
代数系统的概念
- 代数系统的定义:X 是非空集合,f1,f2,⋯,fm 分别是 X 上 k1,k2,⋯,km 元运算,ki 为整数,称集合 X 和运算 f1,f2,⋯,fm 所构成的系统为一个代数系统 U(或一个代数结构),简称一个代数,记作 U=⟨X,f1,f2,⋯,fm⟩(m≥1)。
- 有限代数系统:U=⟨X,f1,f2,⋯,fm⟩ 是一个代数系统,如果 X 是个有限集合,则称 U 是个有限代数系统。
- 同类型代数系统:给定两个代数系统,U=⟨X,f1,f2,⋯,fm⟩,V=⟨Y,g1,g2,⋯,gm⟩,若对应的运算 fi 和 gi 的元数相同,则称 U 与 V 是同类型代数系统。
封闭性
设 ⋆ 是 X 上的二元运算,如果对任何 x,y∈X,有 x⋆y∈X,则称二元运算 ⋆ 在 X 上是封闭的。
交换性
设 ⋆ 是 X 上的二元运算,如果对任何 x,y∈X,有 x⋆y=y⋆x,则称 ⋆ 是可交换的。
从运算表看交换性:是个以主对角线为对称的表。
等幂元、等幂性
设 ⋆ 是 X 上的二元运算,如果存在 a∈X,使得 a⋆a=a,则称 a 是等幂元,如果对任何 x∈X,都有 x⋆x=x,则称 ⋆ 有等幂性。
从运算表看等幂元、等幂性:主对角线的元素与上表头(或左表头)元素相同。
单位元(幺元、恒等元)
设 ⋆ 是 X 上的二元运算,如果存在 eL∈X,使得对任何 x∈X,有 eL⋆x=x,则称 eL 是相对 ⋆ 的左单位元。如果存在 eR∈X,使得对任何 x∈X,有 x⋆eR=x,则称 eR 是相对 ⋆ 的右单位元。如果 eL=eR=e,对任何 x∈X,有 e⋆x=x⋆e=x,称 e 是相对 ⋆ 的单位元。
从运算表中找左单位元 eL:eL 所在行的各元素均与上表头元素相同。
从运算表中找右单位元 eR:eR 所在列的各元素均与左表头元素相同。
定理 1:设 ⋆ 是 X 上的二元运算,如果有左单位元 eL∈X,也有右单位元 eR∈X,则 eL=eR=e,且单位元 e 是惟一的。
零元
设 ⋆ 是 X 上的二元运算,如果存在 θL∈X,使得对任何 x∈X,有 θL⋆x=θL,则称 θL 是相对 ⋆ 的左零元。如果存在 θR∈X,使得对任何 x∈X,有 x⋆θR=θR,则称 θR 是相对 ⋆ 的右零元。如果 θL=θR=θ,对任何 x∈X,有 θ⋆x=x⋆θ=θ,称 θ 是相对 ⋆ 的零元。
从运算表找左零元 θL:θL 所在行的各元素均与左表头元素相同。
从运算表找右零元 θR:θR 所在列的各元素均与上表头元素相同。
定理 2:设 ⋆ 是 X 上的二元运算,如果有左零元 θL∈X,也有右零元 θR∈X,则 θL=θR=θ,且零元 θ 是惟一的。
定理 3:⟨A,⋆⟩ 是代数系统,且集合 A 中元素个数大于 1,如果该代数系统中存在单位元 e 和零元 θ,则 e≠θ。
可结合性
设 ⋆ 是 X 上的二元运算,如果对任何 x,y,z∈X,有 (x⋆y)⋆z=x⋆(y⋆z),则称 ⋆ 是可结合的。
⋆ 是可结合的运算,则相同元素 x 的 ⋆ 运算一般可以写成乘幂的形式:x⋆x=x2,x⋆xn–1=xn。
定理:设 A 是非空集合,⋆ 是 A 上的二元运算且满足结合律,则对任意的正整数 m 和 n ,有 xm⋆xn=xm+n,(xm)n=xmn。
逆元
设 ⋆ 是 X 上有单位元 e 的二元运算,x∈X,如果存在 x−1L∈X,使得 x−1L⋆x=e,则称 x−1L 是 x 相对 ⋆ 的左逆元。如果存在 x−1R∈X,使得 x⋆x−1R=e,则称 x−1R 是 x 相对 ⋆ 的右逆元。如果 x−1L=x−1R=x−1,使得 x−1⋆x=x⋆x−1=e,称 x−1 是 x 相对 ⋆ 的逆元,并称 x 可逆。也称 x−1 与 x 互为逆元。
从运算表找左逆元 x−1L:在 x 列向下找到单位元 e 后,再向左到左表头元素即是 x−1L。
从运算表找右逆元 x−1R:在 x 行向右找到单位元 e 后,再向上到上表头元素即是 x−1R。
定理 1:设 ⋆ 是 X 上有单位元 e 且可结合的二元运算,如果 x∈X,x 的左、右逆元都存在,则 x 的左、右逆元必相等,且 x 的逆元是唯一的。
定理 2:设 ⋆ 是 X 上有单位元 e 且可结合的二元运算,如果 ∀x∈X,都存在左逆元,则 x 的左逆元也是它的右逆元。
No Comments