Loading [MathJax]/jax/element/mml/optable/GeneralPunctuation.js

离散数学笔记(7)——代数系统

离散数学笔记(7)——代数系统

代数结构(代数系统)

函数

定义

对于集合 XYf 是从 XY 的关系,如果 xX,都存在唯一 yY,使得 x,yf,则称 f 是从 XY函数(变换、映射),记作 f:XYXfYx,yf 可记为 y=f(x)

如果 f:XX 是函数,也称 fX 上的函数

定义域、值域和陪域(共域)

f:XY

  1. f定义域,记作 domfDf,即 Df=domf={x|xXy(yYx,yf)}=X
  2. f值域,记作 ranfRff(X),即 Rf=ranf=f(X)={y|yYx(xXx,yf)}
  3. f陪域,即 Y

函数的表示方法

枚举法、关系图、关系矩阵、谓词描述法。

XY 的函数的集合 YX

YX={f|f:XY}

YX:它是由所有的从 XY函数构成的集合。

结论:若 XY 是有限集合,且 |X|=m,|Y|=n,则 |YX|=|Y||X|=nm。从 XY 的关系 =|P(X×Y)|=2nm

规定

  1. 的函数只有 f=
  2. Y 的函数只有 f=
  3. X,则从 X 的函数不存在。

特殊函数

  1. 常值函数:函数 f:XY,如果 y0Y,使得对 xX,有 f(x)=y0,即 ranf={y0},称 f 是常值函数。
  2. 恒等函数:恒等关系 IXXX 的函数,即 IX:XX,称之为恒等函数。显然对于 xX,有 IX(x)=x

两个函数相等

设有两个函数 f:AB,g:ABf=g 当且仅当,对任何 xA,有 f(x)=g(x)

函数的类型

  1. 满射的f:XY 是函数,如果 ranf=Y,则称 f满射的
  2. 入射的f:XY 是函数,如果对于任何 x1,x2X,如果 x1x2f(x1)f(x2),则称 f入射的,也称 f单射的,也称 f一对一的
  3. 双射的f:XY 是函数,如果 f 既是满射的,又是入射的,则称 f双射的,也称 f一一对应的

特别地,:Y 是单射,: 是双射。

X 有限的情况下,f:XX 是入射的,则 f 必是满射的。

函数的复合

f:XY, g:WZ是函数,若 f(X)W,则 gf={x,z|xXzZy(yYx,yfy,zg)} 称为 gf 的左边可复合。

定理:两个函数的复合是一个函数。

43

定义:设 f:XY, g:YZ是函数,则定义 gf={x,z|xXzZy(yYx,yfy,zg)},则称 gffg 的复合函数(左复合)。

结论(gf)(x)=g(f(x))

复合函数的计算同复合关系。

性质

  1. (满足可结合性)f:XY,g:YZ,h:ZW 是函数,则 (hg)f=h(gf)

  2. f:XY,g:YZ 是两个函数,则:

    1. 如果 fg 是满射的,则 gf 也是满射的。
    2. 如果 fg 是入射的,则 gf 也是入射的。
    3. 如果 fg 是双射的,则 gf 也是双射的。

    44

  3. f:XY,g:YZ 是两个函数,则:

    1. 如果 gf 是满射的,则 g 是满射的。
    2. 如果 gf 是入射的,则 f 是入射的。
    3. 如果 gf 是双射的,则 f 是入射的且 g 是满射的。
  4. f:XY 是函数,则 fIX=fIYf=f

逆函数

定理 1:若 fXY 的双射,则 fcYX 的函数。

45

定义:设 fXY 的双射函数,则称 fc:YXf 的逆函数,并记为 f1

定理 2f1YX 的双射函数。

46

性质

  1. fXY 的双射函数,则 (f1)1=f

  2. fXY 的双射函数,则 f1f=IXff1=IY

    47

  3. f:XY,g:YX 是两个函数,如果 gf=IXfg=IY,则 g=f1

    48

    49

  4. f:XY,g:YX 是两个双射函数,则 (gf)1=f1g1

代数结构(系统)的概念

n 元运算

X,Y 是集合,f:XnY 是个映射,则称 fX 上的一个 n 元运算。

主要讨论二元运算,一般用 xy=z 表示 f(x,y)=z

二元运算的运算表

可用一个表来表示二元运算的运算规律。

50

代数系统的概念

  1. 代数系统的定义X 是非空集合,f1,f2,,fm 分别是 Xk1,k2,,km 元运算,ki 为整数,称集合 X 和运算 f1,f2,,fm 所构成的系统为一个代数系统 U(或一个代数结构),简称一个代数,记作 U=X,f1,f2,,fm(m1)
  2. 有限代数系统U=X,f1,f2,,fm 是一个代数系统,如果 X 是个有限集合,则称 U 是个有限代数系统
  3. 同类型代数系统:给定两个代数系统,U=X,f1,f2,,fm,V=Y,g1,g2,,gm,若对应的运算 figi 的元数相同,则称 UV同类型代数系统

封闭性

X 上的二元运算,如果对任何 x,yX,有 xyX,则称二元运算 X 上是封闭的。

交换性

X 上的二元运算,如果对任何 x,yX,有 xy=yx,则称 可交换的。

从运算表看交换性:是个以主对角线为对称的表。

等幂元、等幂性

X 上的二元运算,如果存在 aX,使得 aa=a,则称 a等幂元,如果对任何 xX,都有 xx=x,则称 等幂性

从运算表看等幂元、等幂性:主对角线的元素与上表头(或左表头)元素相同。

单位元(幺元、恒等元)

X 上的二元运算,如果存在 eLX,使得对任何 xX,有 eLx=x,则称 eL 是相对 左单位元。如果存在 eRX,使得对任何 xX,有 xeR=x,则称 eR 是相对 右单位元。如果 eL=eR=e,对任何 xX,有 ex=xe=x,称 e 是相对 单位元

从运算表中找左单位元 eLeL 所在行的各元素均与上表头元素相同。

从运算表中找右单位元 eReR 所在列的各元素均与左表头元素相同。

定理 1:设 X 上的二元运算,如果有左单位元 eLX,也有右单位元 eRX,则 eL=eR=e,且单位元 e 是惟一的。

51

零元

X 上的二元运算,如果存在 θLX,使得对任何 xX,有 θLx=θL,则称 θL 是相对 左零元。如果存在 θRX,使得对任何 xX,有 xθR=θR,则称 θR 是相对 右零元。如果 θL=θR=θ,对任何 xX,有 θx=xθ=θ,称 θ 是相对 零元

从运算表找左零元 θLθL 所在行的各元素均与左表头元素相同。

从运算表找右零元 θRθR 所在列的各元素均与上表头元素相同。

定理 2:设 X 上的二元运算,如果有左零元 θLX,也有右零元 θRX,则 θL=θR=θ,且零元 θ 是惟一的。

定理 3A, 是代数系统,且集合 A 中元素个数大于 1,如果该代数系统中存在单位元 e 和零元 θ,则 eθ

可结合性

X 上的二元运算,如果对任何 x,y,zX,有 (xy)z=x(yz),则称 可结合的

是可结合的运算,则相同元素 x 运算一般可以写成乘幂的形式:xx=x2,xxn1=xn

定理:设 A 是非空集合,A 上的二元运算且满足结合律,则对任意的正整数 mn ,有 xmxn=xm+n,(xm)n=xmn

逆元

X 上有单位元 e 的二元运算,xX,如果存在 x1LX,使得 x1Lx=e,则称 x1Lx 相对 左逆元。如果存在 x1RX,使得 xx1R=e,则称 x1Rx 相对 右逆元。如果 x1L=x1R=x1,使得 x1x=xx1=e,称 x1x 相对 逆元,并称 x 可逆。也称 x1x 互为逆元。

从运算表找左逆元 x1L:在 x 列向下找到单位元 e 后,再向左到左表头元素即是 x1L

从运算表找右逆元 x1R:在 x 行向右找到单位元 e 后,再向上到上表头元素即是 x1R

定理 1:设 X 上有单位元 e 且可结合的二元运算,如果 xXx 的左、右逆元都存在,则 x 的左、右逆元必相等,且 x 的逆元是唯一的。

52

定理 2:设 X 上有单位元 e 且可结合的二元运算,如果 xX,都存在左逆元,则 x 的左逆元也是它的右逆元。

53

 

点赞 0

No Comments

Add your comment