离散定义定理整理
余年寄山水
601次浏览
2021年01月29日 14:38
最佳经验
本文由作者推荐
描写动物的作文400字-感性的意思
代数运算
================================= =========
代数运算定义：
设
A
为非空集合，
n
I+,f:An
→
A
称为
A
上的
n
元运 算，
n
称为运算的阶。
封闭性：
设
o< br>是
A
上的
n
元运算，
S
A
且S
，如果
a1,
…
,an
S ,
均有
o(a1,
…
,an)
S,
则称
S
关于运算
o
是封闭的。
定理
7.1.1:
设
o
是
A
上的
n
元运算，
C
是
< br>(A)
的非空子集，
若
S
C,S
关于运 算
o
是封闭的，则∩
C
关于运算
o
也是封闭的。
单
位
元
：
设
*
是
A
上
的
二
元
运
算
，
0+a=a
a+0=a
型的。
保持运算：
设
*
和
*
’
分别是集合
S,S
’
上的
n
元运算 ，函数
h:S
→
S
’,
如果
a1,
…< br>,an
S,
都有：
h(*(a1,
…
,an))= *
’
(h(a1),
…
,h(an)),
则称
h
关 于
*
和
*
’
保持运算。
同态和同构：
设
A=
,*n>
和
A
’
=
,*
’
1,
…
,*
’
n>
是同型的代数系统，
函数
h:S
→
S
’
，
如果
i
N(1
≤
i
≤
n),h
关于*i
和
*
’
i
都保持运算，则称
h
为从
A
到
A
’
的
同态映射
，并称
A
和
A
’
同态
。特别地
①
若
h
单射，则称
h
为单一同态映射，称
A
和
A
’
单一< br>0+a=a+0=a
①
若
el
A,
使得
a
A,
有
el*a=a,
则称
el
为关于
*
的
左
单位元
.
②
②
若
er
A,
使得
a
A,
有
a*er=a,
则称
er
为关于
*
的
右单位元
.
③
若
e
A,
使得
a
A,
有
e*a=a*e=a,
则称
e
为关于
*
的
单位元
.
定理
7.1.4
：
设
*
是
A
上的二元运算，
el和
er
分别是关于
*
的左右
单位元，则
el=er
，且它是关于
*
的唯一单位元。
零元：
设
*
是
A
上的二元运算，
①
若
zl
A,
使得
a
A,
有
zl*a=zl,
则称
zl
为关于
*
的左
零元
.
②
若
zr
A,
使得
a
A,
有
a*zr=zr,
则称
zr
为关于
*
的
右零元
.
③
若
z
A,
使得
a
A,
有
z*a=a*z=z,
则称
z
为关于
*
的零元
.
定理
7.1. 5
：
若关于
*
的左右零元都存在，则他们相等，是唯
一零元。
逆元：
设
*
是
A
上的二元运算，
e
是 关于
*
的单位元，
a
A
①
若
al
A,
使得
al*a=e,
则称
al
为
a
关于
*
的左逆元
.
②
若
ar
A,
使得
a*ar=e,
则称
ar
为
a
关于
*
的右逆元
.
③
若
a
’
A,
使得
a
’
*a=a*a
’
=e,
则称
a
’
为
a
关于
*
的逆
元
.
定理
7.1.6
：
设
*
是
A
上 的可结合的二元运算，
e
是关于
*
的
单位元，
al,ar< br>分别为
a
关于
*
的左右逆元，
则
al=ar
且它是
a
关于
*
的唯一逆元。
幂等元：
设
*
是
A
上二元运算，
a
A
，若
a*a =a,
则称
a
是关于
*
的幂等元。
可约元：设
*
是
A
上二元运算，
a
A
，
①
x,y
A,a*x=a*y
x=y,
则称
a
关于
*
左可约；
②
x,y
A,x*a=y*a
x=y,
则称< br>a
关于
*
右可约；
③
若
a关于
*
既左可约又右可约，则称
a
关于
*
可约；
④
若
a
A
都是可约的，则称
*
满足消去律。
定理
7.1.7
：
设
*
为
A
上的可结合的二元运算，
a
A
，若
a
关
于
*
可逆，则
a
关于
*
可约。
分析例
4
的运算表，如何识别运算的性质及特殊元？
封闭型
iff
运算表中的每个元素均属于
A;
可交换性
iff
运算表关于主对角线对称；
单位元
iff
该元素对应行与表头行相同，对应列与表头
列相同；
零元
iff
零元素对应的行和列全部元素都等于零元；
幂等元
iff
主对角线上元素与该行（列）的表头元素相
同。
代数系统同态与同构
=================================
代数系统：
设
S
为非空集合，
*1,*2,
…
,* n
为
S
上的代数运算，
称
,*n>
为一个代数系统
/
代数结构，< br>S
为该代数系统的定
义域。
有限代数系统：
若
S< br>是有限集，其中
|S|
称为该系统的阶。
同类型：
设
A=
,*n>
和
A
’
=
,*
’
1,*
’
2,
…
,*
’
n>
是两
个代数系统
,
如果
i
N(1
≤
i
≤
n),*i
和
*
’
i
是同阶运算
,
则称
A
和
A
’
是同
同态
；
②
若
h满射，
则称
h
为满同态映射，
称
A
和
A
’
满同态
，
用
A~A
’
表示；
③
若
h
双射，则称
h
为同构映射，称
A
和
A
’
同构
，用
A
A
’
表示；
④
若
A=A
’
，则称
h
为
自同态
；
⑤
若
A=A
’
且
h
双射，则称
h
为
自同构
；
定理
7.2.1
：
>
定则：
h:R
→
R+, h(x)=ex (x
R)
h
是
R
到
R+
的函数，∵
x
R,
都有
R+
中唯一的元素
ex
与
之对 应；
h
双射，
∵
y
< br>R+
，有
lny
R,
使
h(lny)=elny= y
∴
h
满射
又∵
x1 ,x2
R
，当
x1
≠
x2
时
,
e
x
1
e
x
2
∴
h
单射
（
3
）
h
关于
+
和
保持运算，∵
x1,x2
R
，
h
(
x< br>1
x
2
)
e
x
1
< br>x
2
e
x
1
e
x
2< br>=h(x1)
h(x2)
定理
7.2.1
设
f< br>为从
A=
,*n>
到
A
’
=
,*
’
1,
…
,*
’
n>
的
同态映射，
g
为从
A
’
=
,*< br>’
1,
…
,*
’
n>
到
A
’’=
,*
’’
1,
…
,*
’’
n>
的同
态映射，则
gof
是从
A
到
A
’ ’
的同态映射。
定理
7.2.2
设
f
为从A=
,*n>
到
A
’
=
,*
’
1,
…
,*
’
n>
的
同构 映射，则
f-1
是从
A
’
到
A
的同构映射。
代数系统间的同构关系具有自反、对称和传递性。
对任意的代数系统
A
，
A
A;
对任意的代数系统
A
和
A
’,
若
A
A
’,
则
A
’
A;
对任意的代数系统
A
、
A
’
和
A
’’,
若
A
A
’
且
A
’
A
’’,
则
A
A
’’;
定理
7.2.3
设
h
是从
A=
到
A
’
=
,*
’
1 ,
…
,*
’
n>
的
同态映射，则
h(A)=
1,
…
,*
’
n>
是
A
’
的子代数，称为
A
关于
h
的同态象。
定理
7.2.4
设
h
是
A=
, +>
到
A
’
=
,
,
< br>>
的满同态
,
,+
是
二元运算
,
则
①
若
是可交换的，则
也是可交换的；
②
若
是可结合的，则
也是可结合的；
③
若
关于
+
可分配，则
关 于
也是可分配的；
④
若
e
是关于< br>
的单位元，则
h(e)
是关于
的单位元；
⑤
若
z
是关于
的零元，则
h(z)< br>是关于
的零元；
⑥
若
a
< br>S
关于
可逆，则
h(a)
关于
也可逆， 且
h(a)-1=h(a-1)
；
同余关系：
A=
,*n>
为代数系统，
R
是
S
上的等价关
系
，
①
对于运算
*i,
如 果
a1,b1,a2,b2,
…
,ani,bni
S
(
其中：
j
(
ni
a
11< br>,...,
a
m
1
为
*i
的
阶
）< br>
akRbk,k=1,
…
,ni
*i(a1,
…
,ani)R*i(b1,
…
,bni),
称
R
关
于
*i
具有
置换性质
；
②
若
R
关于
*i(1
≤
i
≤
n),
具有置换 性质，则称
R
为
A
上
的
同余关系
。
与同态映射间的联系
定理
7.3.1
设
h
是从
A=
,*n>
到
A
’
=
,*
’
1,
…
,*
’
n>
的
同态映射，定义由
h
诱导的
S
上的二元关系
Rh
：
x,y
S,xRhy iff
h(x)=h(y),
则
Rh
是
A
上的同余关系。
商代数和积代数
============================== =======
商代数
：
设
R
为代数系统
A=< S,*1,
…
,*n>
上的同余关系，
称
A/R=
…
,
*n>
为
A
关
于
R
的
商
代
数
。
其
中
：
*i([a
1
]
R
,
…
,[a
ni
]
R
)=[*i(a
1
,
…
,a
ni
)]
R
同余关系是代数系统的定义域中的等价关系，
并且在代数系
统的运算的作用下，能够保持关系。
定理
7.4.1:
设
R
为代数系统
A=
,*n>
上的同余关系，
则
·
>
是群。
定理
8.2.2
设
·
>
为半群。
若
a
，
b
G
,
方程
a
·
x=b和
y
·
a=b
在
G
中都有解，则
·
>
是群。
性质：
设
·
>
为群。则
a
，
b
G
,
方程（
a
·
b
）
-1 =b-1
·
a-1
定义函
f :S
→
S/R,
a
S,f(a)=[a]R,
则
f
是从
A
到商代数
A/R
的满同
态映射，称为 自然同态。
定理
7.4.2:
设
h
为
A=
,*n>
到
A
’
=
, *
’
1,
…
, *
’
n>
的
同
态
映
射
，
R
为
A
上
由
h
诱
导
的
同
余
关
系
(R
定
义
为
:
x,y
S,xRy
iff
h(x)= h(y))
，
f
是从
A
到
A/R
的自然同态
(
a
S,
f(a)=[a]R),
则存在从A/R
到
h(A)
的同构映射
g,
使
gof=h
。
推论：
设
h
为
A=
,*n>
到
A
’
=
,
*
’
1,
*
’
n>
的满同态
映射，R
为
A
上由
h
诱导的同余关系，则
A/R
A
’
。
*
分析
>
到
m>
同态映射
h:I
→
Nm
h(i)=i mod m
R=?,f=?,g=?
定理
7.4.1
设
h
为
A=
,*n>
到
A
’
=
’
1,
…
,*
’
n>
同态
映射，
R
为
A
上由
h
诱导的同余关系
(
x,y
S,xRy iff h(x)=h(y))
，
f
是A
到
A/R
的自然同态
(
a
S, f(a)=[a]R),
则存在
A/R
到
h(A)
的
同构 映射
g,
使
gof=h
。
积
代
数
：
设
Ai=
,*in>(i=1,
…
,m)
为
同
型
代
数
系
统
,A1 ,
…
,Am
的积代数
m
m
A
i
1
,...,*
n
,
i
1
S
i
,*
i
1
其中：< br>
j
(
j
1
,...,
n
)定义为
(
设
*
j
的阶为
n
j
)
：
a
11
,...,
a
m
1
,...,
a
1
n
j
,...,
a
m
n
j
S
1
...
S
m
,
积代数性质
:
定理
7.4.3:
设
Ai=
(i=1,< br>…
,m)
为同型代数系统
,*i
和
+i
为
二
元
运
算
,A1,
…
,Am
的
积
代
数
m
m
A
i
S
i
,
*
,
,
则
i
1
i
1
①
如果
*i(i=1,
…
,m)
可交换，则
*
也可交换；
②
如果
*i(i=1,
…
,m)
可结合，则*
也可结合；
③
如果
*i
关于
+ i(i=1,
…
,m)
可分配，则
*
关于
+
也可分 配；
④
如果
ei
是关于
*i(i=1,
…
,m)
的单位元
,
则
,em>是
关于
*
的单位元；
⑤
如果
zi
是关于
*i(i=1,
…
,m)
的零元，
则
,zm>
是关
于
*
的零元；
⑥
如果
ai
Si
关于
*i(i=1,
…
,m)
有逆元
ai-1
，
则
,am>
关于
*
有逆元
,am-1 >
。
半群和群
===================== =====================
定理
8.1.1
设
,e>
为可交换独异点，
T
为
S
中所有幂等元< br>的集合，则〈
T,
·
>
是
>
的子独异点。定义
半群同态
和
独异点同态
(
单位元映射到单位元
)
半群性质
定理
8.1.2
半群
*>
与
o>
同态。
定理
8.1.3
任意 独异点都同构于某一变换独异点。即
必与
的某个子独异点同构。
群：
设
·
>
为独异点，如果
a
G
,a
都可逆，则称
·
>
为
群。
阿贝尔群：
若 群
·
>
中的二元运算·
是可交换的，
则称< br>
·
>
为可交换群，也称阿贝尔群。
定理
8.2.1
设
·
>
为半群。若
①
有左单位元，即
el
A,
使得
a
G
,
有
el
·
a=a
②
每个元素有左逆元，
即
a
G
al
G
,
使得
al
·
a=el ,
a
，
b
G
,
方程
a
·
x= b
和
y
·
a=b
在
G
中有唯
一解
;
·
>
中消去律成立。
元素的阶：
设
·
>
为群，
a
G
。若
n
I+,an
≠
e,
则称
a
的阶是无限的，否则
an
=
e的最小正整数
n
为
a
的阶。
A
的
阶也称为a
的周期，常用
|a|
表示。
分析下列系统：
A=
A=
可交换独异点
B=<
(A),
> B=<
(A),
,
>
C=
,o>
C=
,o,I
A
>
D=<
*,o>
D=<
*,o,
ε
>
独异点
E=
E=
A
的子独异点
F=<
+,o>
D
的子半群
,o,I
A
>
的子独异点称为变换独异点。
环：
设〈
R,+,
·
>
是代数系统，若
(1)
+>
是可交换群，
(2)
>
是半群，
(3)
·关于
+
可分配，则称〈
R,+,
·>
为环，称
+
为加法、
·为
乘法。
域：
设〈
R,+,
·
>
是代数系统，若
(1)
是可交换群，
(2)
>
是可交换群，
(3)
·关于
+
可分配，则称〈
R,+,
·
>
为域，称
+
为加法、
·为
乘法。
格：
< br>定义
1
：
设
>
是偏序集，若
a,b
L,{a,b}
在
L
中
都有最大下和 最小上界，则称
>
为格。
定义
2
：
若
>
是代数系统，
*
和⊕是二元运算且
满足交换律、
结合律和吸收律
(a*(a
b)=a,a
(a*b)=a)
，
则称
>
是格。
图
=================== ============================
无序积：
设
A,B
是任意集合
,{(a,b)|a
A
b
B}
称为
A
和
B
的
无序积
,
记作
A&B
无向图：
是一个二元组
G=
其中
:
①
结点集合
V
≠
；
②
边集合
E
是
V&V
的多重子集。
有向图：
是一个二元组
G=
其中
:
①
结点集合
V
≠
；
②
边集合
E
是
V
V
的多重子集。
无向图顶点的度数：
deg(v)=
与
v
关联的边数。< br>(
自回路计算
2
次
)
有向图顶点的度数：
出度：
deg+(v)=
以
v
为起始点的边数。
入度：
deg-(v)=
以
v
为终点的边数。
度：
deg(v)=deg+(v)+deg-(v)
度数和边数的联系
定理
11.1.1
设
G=
为图，
则
deg(
v
)
2< br>|
E
|
v
V
推论
11.1.1
任何图中，
度数为奇数的顶点数必为偶数。
定
理
11.1.2
有
向
图
G=
中
，