离散数学第5章

10
5.2 代数系统


定义5.12 设S是个非空集合，fi是S上 的ni元运算，其中i=1，2，…，k。 由S及f1，f2，…，fm组成的系统，称为 代数系统，简称代数。 记作<S，f1，f2，…，fk>。
11
子代数


定义5.13 设V=<S，f1，f2，…，fk> 是代数系统，非空集合BS， 如果B对运算f1，f2，…，fk都是封闭的， 且B与S含有相同的特异元， 则称<B，f1，f2，…，fk>是V的子代数系 统，简称子代数。 记为<B，f1，…><S，f1，…>。
25
循环群

定义6.6 在群G中如果存在aG 使得 G={ak|kZ}，则称G为循环群，记作 G=< a >，称a为G的生成元。
26
6.2 环与域


定义6.8 设<R，+，•>是代数系统， R 为集合，+和•都是二元运算，如果 ①<R，+>是Abel群， ②<R，•>是半群， ③ •对于+是可分配的， 则称<R，+，•>是环。 交换环、含幺环
12
积代数


定义 设<S，⊙>与<T，○>是同类型的，而 <S×T，>成为新的代数结构，其中S×T是 集合S和集合T的笛卡儿积，且定义如下： <s1，t1><s2，t2>=<s1⊙s2，t1○t2>， 其中s1，s2∈S，t1，t2∈T。 则称<S×T，>为代数结构<S，⊙>和<T， ○>的积代数， <S，⊙>和<T，○>为<S×T， >的因子代 数。
21
￮ e

e e
￮ e a
e e a
a a e
￮ e a b d d e a b c
e e a b
a a b e
b b e a
一阶群
￮ e a b c d e e a b c d a a b c d e
二阶群
b b c d e a c c d e a b

三阶群

五阶群
22

四阶群
e e a b c a a b c e b b c e a c c e a b ￮ e a b c e e a b c a a e c b b b c e a c c b a e e
定理5.2 设为S上的二元运算，θl和θr 分别为运算的左零元和右零元，则 θl=θr=θ，且θ为S上关于运算的唯一的 零元。
7

逆元


定义5.10 设为S上的二元运算， eS 为运算的幺元。对于xS，若存在元 素yl S(或yr S)使得 yl x = e ，则称yl是x的左逆元； x yr = e ，则称yr是x的右逆元。 若yS既是x的左逆元，又是x的右逆元， 则称y是x的逆元。
27
域



左零因子、右零因子、无零因子环 定义6.9 若环<R，+，•>是交换、含幺 和无零因子的，则称R为整环。 若环<R，+，•>至少含有2个元素且是含 幺和无零因子的，并且aR（a0）有 a-1R，则称R为除环。 若环<R，+，•>既是整环，又是除环， 则称R是域。
28
6.3 格与布尔代数
30
分配格

定义6.11
设<L,∧,∨>是格，对任意的
a,b,cL，有
① a∧(b∨c)=(a∧b)∨(a∧c)
② a∨(b∧c)=(a∨b)∧(a∨c)

则称<L,≤ >为分配格。
31
有界格

定义6.12 格。
设<L,∧,∨>是格，若L中有
最大元和最小元，则称<L,∧,∨>为有界

一般把格中最大元记为1，最小元记为0。 有界格记为<L,∧,∨，0，1>。
第5章 代数系统的一般性质


5.1 二元运算及其性质 5.2 代数系统及其子代数和积代数 5.3 代数系统的同态与同构
1
5.1 二元运算及其性质

定义5.1 设S是个非空集合且函数 f : Sn →S，则称f为一个n元运算。 其中n是自然数，称为运算的元数或阶。 当n=1时，称f为一元运算， 当n=2时，称f为二元运算。
① (a’)’=a ②(a∨b)’=a’∧b’， (a∧b)’=a’∨b’
34




定义5.17 设是V1 =<S1,￮>到V2=<S2,> 的同态， 如果是满射，则称是V1到V2的满同态； 如果是单射，则称是V1到V2的单同态； 如果是双射，则称是V1到V2的同构。 如果V1=V2，则称是V1的自同态。 如果V1=V2且是同构，则称是V1的自 同构。
15
32
有补格

定义6.13 设<L,∧,∨，0，1>是有界格， 对任意aL，若存在bL,使得a∧b=0， a∨b=1，则称b为a的补元。
若有界格L中每个元素都有补元，则称L 为有补格。

33
布尔代数

定义6.14 如果格L是有补分配格，则 称L为布尔格，也称为布尔代数。 定理6.8 设<L,∧,∨，’，0，1>是布尔 代数，则对a,bL,有：
第6章 几个典型的代数系统


6.1 半群与群 6.2 环与域 6.3 格与布尔代数
16
6.1 半群与群



定义6.1 设V= <S，￮> 是代数系统， ￮是二元运算。如果￮是可结合的，则称 V为半群。 如果半群V= <S，￮> 中￮是可交换的，则 称V为可交换半群。 如果半群V= <S，￮> 中的二元运算含有 幺元e，则称V为含幺半群，或独异点。
8

定理5.3
设为S上可结合的二元运算，
e为运算的幺元。 对于xS，如果存在
左逆元yl和右逆元yr，则有yl=yr=y，且y
是x唯一的逆元。
9

定义5.11 设为S上的二元运算，如果 对x,y,zS，都有 (1)若x y = x z且x不是零元，则y = z， (2)若y x = z x且x不是零元，则y = z， 则称运算满足消去律。

幺元


定义5.8 设为S上的二元运算，如果 存在元素el(er) S，使得对xS，都有 el x = x，则称el是S中关于运算的一 个左幺元； x er= x，则称er是S中关于运算的一个 右幺元。 若eS关于既是左幺元，又是右幺元， 则称e是S上关于运算的幺元。
5

定义6.10 设<L,≤ >是一个偏序集，若 对任意x,yL，都存在最小上界lub{x,y} 和最大下界 glb{x,y}，则称<L,≤ >为格。
最小上界 lub{x,y}：x∨y 最大下界 glb{x,y}：x∧y


29

定理6.7 设<L,≤>是格，则对a,b,cL， 有 ① a∨b=b∨a, a∧b=b∧a。（交换律） ② a∨(b∨c)=(a∨b)∨c， a∧(b∧c)=(a∧b)∧c 。 （结合律） ③ a∨a=a, a∧a=a。 （幂等律） ④a∨(a∧b)=a，a∧(a∨b)=a.（吸收律）
零元


定义5.9 设为S上的二元运算，若存 在元素θl(θr) S，使得对xS，都有 θl x =θl ，则称θl是S上关于运算的左 零元； x θr =θr，则称θr是S上关于运算的右 零元。 若θS关于既是左零元，又是右零元， 则称θ是S上关于运算的零元。
6

定理5.1 设为S上的二元运算，el和er 分别为运算的左幺元和右幺元，则 el=er=e，且e为S上关于运算唯一的幺元。
19


定理6.3 G为群，则G中元素适合消 去律，即对a,b,cG有 （1）若ab=ac，则b=c。 （2）若ba=ca，则b=c。 定理6.4 G为有限群，则G的运算表 中的每一行（每一列）都是G中元素的 一个置换，且不同的行（或列）的置换 都不相同。
20
Abel群

定义 设G为群，若G中的二元运算是 可交换的，则称群G为交换群，也叫做 阿贝尔（Abel）群。
13
5.3 代数系统的同态与同构


定义5.15 设代数系统V1=<S1，￮> ， V2=<S2，>， ￮和是二元运算。 如果存在映射：S1 S2，对于x,yS1 都有 ( x ￮ y )= (x) (y)， 则称是V1到V2的同态映射，称V1和V2 同态。
14
同构
17
群




定义6.4 设<G，￮> 是代数系统，￮是 二元运算。如果￮是可结合的，存在幺 元eG，并且G中的任意元素x都有x1G，则称G为群。 有限群 n阶群 定义6.7 置换
18


定理6.1 设G为群,则G中的幂运算满足 (1) xG，(x -1) -1=x. (2) x,yG，(xy) -1= y -1 x -1 . (3) xG，xn xm = xn+m . (4) xG，(xn)m=xnm, m,n是整数。 定理6.2 G为群, a,bG,方程ax=b和 ya=b在G中有解，且有唯一解。
24
￮ e a b c d f
子群


定义6.5 设群<G，>，H是G的非空 子集。如果H关于G中的运算构成群， 则称H为G的子群，记作HG。 定理6.5.1 设< G， >为群，H是G 的非空子集。如对a,bH，都有 ① a bH， ② a-1H， 则< H， >是< G， >的二元运算，如果 对xS，都有x ￮ x= x，则称运算￮在S 上适合幂等律。 S中的元素为幂等元。