离散数学

代数系统

半群与独异点
定义：

(1)设V=<S, ∘ >是代数系统，∘为二元运算，如果∘运算是可结合的（满足结合律），则称V为半群(semi-group)
(2)设V=<S, ∘ >是半群，若e∈S是关于∘运算的单位元，则称V是含幺半群，也叫做独异点(monoid)，有时也将独异点V记作V=<S，∘ ，e>

半群和独异点的性质：

• 半群<S, ∘ >中的幂，由于半群中的运算是可结合的，可以定义该运算的幂。对任意x∈S，规定：x¹=x，xⁿ⁺¹=xⁿ ∘ x, n∈Z+
• 独异点<S, ∘,e>中的幂对于任意的x∈S，可以定义x的零次幂，即x⁰=e，xⁿ⁺¹=xⁿ ∘ x ，n∈N独异点的幂运算也遵从半群的幂运算规则，其中m和n是自然数.
• 设<S, ∘ >是半群，如果S是有限集合，则必存在a∈S, 使得 a ∘ a=a
• 设<M，∘ ，e>为独异点，则关于∘ 的运算表中任两列或任两行均不相同
• 给定独异点<M， ∘ ，e>，对任意a，b∈M且a，b均有逆元，则
  (1) (a-1)-1=a
  (2) a ∘ b有逆元，且(a ∘ b)-1=b-1 ∘ a-1

子半群与子独异点：
定义： 半群的子代数叫做子半群，独异点的子代数叫做子独异点。

• 子半群的判别方法：
  V=<S,∘ >是半群，T⊆S，T非空，如果T对V中的运算∘封闭，则<T,∘ >是V的子半群.
• 子独异点的判别方法：V=<S,∘, e>是独异点，T⊆S，T非空，如果T对V中的运算∘封闭，而且e∈T，那么<T,∘, e>构成V的子独异点.

半群与独异点的直积：
设V1=<S1, ∘ >，V2=<S2,∗>是半群(或独异点)，令S=S1×S2，定义S上的 •运算如下：∀<a, b>,<c, d>∈S，<a, b> • <c, d> = <a ∘ c, b ∗ d>称<S, • >为V1和V2的直积，记作V1×V2。

• 可以证明V1×V2是半群.
• 若V1和V2是独异点，其单位元分别为e1和e2，则<e1, e2>是V1×V2中的单位元，因此V1×V2也是独异点. .

半群与独异点的同态映射：

：
(1) 设V1=<S1,∘ >, V2=<S2,∗>是半群，ϕ：S1→S2. 若对任意x,y∈S1有 ϕ(x ∘ y)= ϕ(x) ∗ ϕ(y)则称ϕ为半群V1到V2的同态映射，简称同态.
(2) 设V1=<S1,∘, e1>, V2=<S2,∗, e2>是独异点，ϕ: S1→S2. 若对任意x, y∈S1有 ϕ(x ∘ y)= ϕ(x) ∗ ϕ(y) 且 ϕ(e1)= e2,则称ϕ为独异点V1到V2的同态映射，简称同态

群

定义：
设<G,∘ >是代数系统， ∘ 为二元运算。如果 ∘ 运算是可结合的，存在单位元e∈G，并且对G中的任何元素 x 都有x^-1∈G，则称G为群(group)。

群<G,∘ >满足下列条件：

• ① 运算 ∘ 满足封闭性；
• ②运算 ∘ 满足结合律；
• ③存在单位元；
• ④ G中每个元素存在逆元。

有穷集 若群G是有穷集，则称G是有限群，否则称为无限群.
群G的阶 群G 的基数称为群 G 的阶，有限群G的阶记作|G|.
平凡群 只含单位元的群称为平凡群.
交换群 若群G中的二元运算是可交换的，则称G为交换群

设G是群，a∈G，n∈Z，则a 的 n次幂：

元素的阶： 设G是群，a∈G，使得等式 a^k=e 成立的最小正整数 k 称为a 的阶，记作| a |=k，称 a 为 k 阶元. 若不存在这样的正整数k，则称 a 为无限阶元.

群的性质：幂运算规则：
定理： 设G 为群，则G中的幂运算满足：

• ∀a∈G，(a⁻¹)⁻¹=a
• ∀a,b∈G，(ab)⁻¹=b⁻¹a⁻¹
• ∀a∈G，aⁿa^m = a^n+m，n, m∈Z
• ∀a∈G，(aⁿ)^m = a^nm，n, m∈Z
• 若G为交换群，则 (ab)ⁿ = aⁿbⁿ
  方程存在唯一解
• G为群，∀a,b∈G，方程ax=b和ya=b在G中有解且仅有惟一解.
  消去律
• G为群，则G中适合消去律，即对任意a,b,c∈G 有
  (1) 若 ab = ac，则 b = c.
  (2) 若 ba = ca，则 b = c.
  元素的阶：

G为群，a∈G且 |a| = r. 设k是整数，则
(1) ak = e当且仅当r | k
(2) |a−1| = |a|