信息安全原理与数学基础(六)

基本信息

授课教师：zbs

Lecture 13 代数系统

代数系统

代数结构

抽象代数

运算

$S^n$到$S$的一个函数

用$*$表示二元运算$*(x,y)=x*y$
用$\Delta$表示一元运算

运算的性质

• 普遍性
• 单值性
• 封闭性

二元运算的一般性质

• 结合律
• 交换律
• $*$运算对于$\#$运算满足分配律

代数结构

载体，运算，公理

幺元

幺元 e：$\forall x(x*e=e*x=x)$

• 左幺元 $e^\prime*x=x$
• 右幺元 $x*e^{\prime}=x$
• 幺元是唯一的，如果不存在幺元，那么左右幺元可能不一样，也可能是多个

零元

零元 o：$\forall x(x*o=o*x=o)$

• 左零元 $o^\prime*x=o$
• 右零元 $x*o^{\prime}=o$
• 零元是唯一的，如果不存在零元，那么左右零元可能不一样，也可能是多个

对于二元运算，零元和幺元的存在性是无关的

逆元

存在幺元 e，$x*y=e$，x 为 y 的左逆，y 为 x 的右逆

• 如果 $x*y=y*x$ 则 x，y 互为逆元
• x 的逆元 $x^{-1}$

逆元的性质

• 多于 1 个元素的载体集上，零元没有逆元
• 满足结合律的代数结构，逆元上唯一的

可约元素

$\forall x,y\in S,a\in S:$

• $a*x=a*y\to x=y$
• $x*a=y*a\to x=y$

则 a 是可约的

可约的性质

• 满足结合律的代数结构中，有逆元的元素是可约的

两个代数结构

同构

如果两个代数结构

• 存在双射 $h:S\to S^\prime$
• $h(x*y)=h(x)\circ h(y)$

同类型

如果两个代数结构

• $|S|=|S^\prime|，并且运算元数相同$

同态映射 homomorphism

$\forall a,b\in S,\exists h:S\to S^\prime,h(\Delta(a))=\Delta^\prime h(a),h(a\#b)=h(a)\#h(b)$

• h 单射：单一同态映射
• h 满射：满同态映射
• h 双射：同构映射

同余

$a\sim b\to\Delta a\sim\Delta b$
$a\sim b,c\sim d\to a*c\sim b*d$

保持了等价类的性质，同余类 $[x]_\sim$

代数结构的类型

出卷想到就要考咯

• 半群：满足结合律的代数结构
• 独异点：含有幺元的半群
• 群：每个元素都有逆元，没有零元的独异点
• 交换群 / 阿贝尔群：满足交换律的群

环

<R, +, *>

• <R, +> 是阿贝尔群
• <R, *> 是半群
• * 对 + 可以分配

域

<F, +, *>

• <F, +, *> 是环
• <F - {o}, *> 是阿贝尔群

自然语言

通识课，启动

人工语言