离散定义定理整理

巡山小妖精
881次浏览
2021年01月29日 14:38
最佳经验
本文由作者推荐

描写动物的作文400字-感性的意思

2021年1月29日发(作者:芡实的作用与功效)

代数运算
================================= =========
代数运算定义:
设
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=…< br>,*n>
到
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=*1,
…
,
*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,
·
>
是
·
>
的子独异点。定义



半群同态


和
h(a*b) = h(a) . h(b)


独异点同态
(
单位元映射到单位元
)
半群性质

定理
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=A
,o>

C=A
,o,I
A
>
D=<

*,o>

D=<

*,o,
ε
>





独异点

E=

E=

A
的子独异点

F=<

+,o>

D
的子半群

A
,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=,E>,
其中
:
①

结点集合
V
≠

;

②

边集合
E
是
V&V
的多重子集。

有向图:
是一个二元组

G=,E>,
其中
:
①

结点集合
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=,E>
为图,
则

deg(
v
)

2< br>|
E
|
v

V
推论
11.1.1
任何图中,
度数为奇数的顶点数必为偶数。
定
理
11.1.2
有
向
图
G=,E>
中
,


描写动物的作文400字-感性的意思


描写动物的作文400字-感性的意思


描写动物的作文400字-感性的意思


描写动物的作文400字-感性的意思


描写动物的作文400字-感性的意思


描写动物的作文400字-感性的意思


描写动物的作文400字-感性的意思


描写动物的作文400字-感性的意思