离散数学 第六章：几个典型的代数系统

在一个集合上构造映射之后，可以利用映射得到集合元素的像，从而形成了运 算。
[定义6-1：n元运算] 设A是一个非空集合，一个映射 f：An→A 称为A上的n元代 数运算，简称 n 元运算（n-ary operation）。其中，n ≥ 1为自然数，称为运算的 元、阶或目。
[最常见的运算]一元运算和二元运算。 ► 程序设计语言中的取正、取负、否定和按位取反为一元运算。 ► 算术运算、关系运算、其他逻辑运算、按位运算等都是二元运算。
6.1.1 n元运算
Discrete mathematics
[例6-1] 设A={x|x=2n，nN}，问算数乘法和加法是否为A上的二元运算？
解： 问题等同于衡量运算是否对A封闭。对A的任意两个元素x=2p 和y=2q，因为
x y = 2p +q
但p=1且q=2时，有 21+22=6 A
故乘法 是A上的二元运算，加法+不是A上的二元运算。
[定义6-4：等幂元] 如果有 xA ，使 x2=x∗x=x，则 x 是 ∗ 运算的等幂元（或幂 等元）。若对 ∀xA，有 x2=x ，则称 ∗ 是等幂（或幂等）的，或称 ∗ 满足等幂 律 (或幂等律，idempotent)。 例=> 一个集合的幂集上的∪、∩运算都是等幂运算。例6-3中的∗运算也是等 幂运算。
例=> ► 实数集R上的+ 、- 和 ； ►集合A的幂集P (A)上的∪、∩、- 和。 ► 一个集合A到A的函数集AA上的函数复合运算∘。 ► n 阶（n≥1）实数矩阵集合上的矩阵加法和乘法都是二元运算。 ► C语言中实数集 R 上的“？：”是一个三元运算。
6.1.1 n元关系
Discrete mathematics
6.1.1 n元运算

符号化表示为：B A x ( xB xA ) B ⊈ A x ( xB xA )
例如N Z Q R C，但Z ⊈ N。显然对任何集合A都有A A。
定义6.2 设A，B为集合，如果A B且B A，则称A与B相等，记作A＝B。 如果A与B不相等，则记作A≠B。
符号化表示为： A = B A B B A
1. 集合的广义并与广义交
定义6.10 设A为集合，A的元素的元素构成的集合称为A的广 义并，记为∪A。符号化表示为
广义并 A = { x | z ( zA xz )}
定义6.11 设A为非空集合，A的所有元素的公共元素构成的 集合称为A的广义交，记为∩A。符号化表示为
广义交 A= { x | z ( zA xz )}
A B＝B A
(6.29)
(A B) C＝A (B C) A ＝A A A＝ A B＝A C B＝C
(6.30) (6.31) (6.32) (6.33)
离散数学 第六章的
25
书本88页
例6.5 设A＝{{a},{a,b}}
计算∪∪A，∩∩A和∩∪A∪(∪∪A－∪∩A)。
解: ∪A＝{a,b}
∩A＝{a}
∪∪A＝a∪b
∩∩A＝a
∩∪A＝a∩b
∪∩A＝a
∩∪A∪(∪∪A－∪∩A)
＝(a∩b)∪((a∪b)－a)
＝(a∩b)∪(b－a)
＝b
所以∪∪A＝a∪b，∩∩A＝a，∩∪离散A∪数学(∪第∪六A章－的 ∪∩A)＝b。
26
6.4 集合恒等式（P92）
集合算律 1．只涉及一个运算的算律：
离散数学 第六章的
12
集合运算的表示
文氏图
A
B
AB

得Computer仍是字母串。
第6章 群论
定理6.1 一个半群(S，)，如果它有一个子代 数 (M， ) ，则此子代数也是一个半群。
定义6.2 一个半群(S，)的子代数 (M， )也是 半群，称为(S，)的子半群。
第6章 群论
一个半群(S，)中的元素a ，可定义它的幂： a1=a , a2=a a , …，an+1=an a
第6章 群论
定理6.5 一个单位半群(S，)，如果存在一个
子代数 (M， ) ，且其单位元 e ∈M，则 (M， )
也是一个单位半群。
定义6.5 一个单位半群(S，)，如果存在一个
子代数 (M， ) ，且其单位元 e ∈M，则 (M， )
也是一个单位半群，称为(S，)的子单位半群 。
Hale Waihona Puke 第6章 群论定义6.5 ：一个单位半群(S，)如果由它的一个 元素a 所生成，则称为由 a 所生成的循环单位半 群，元素 a 称为此单位半群的生成元素。
定理6.6 ：一个循环单位半群是一个可换单位半 群。
第6章 群论
6.2 群
一、群与群的同构 1、群的有关定义
定义6.7 如果代数系统(G， )满足 （1） (G， )为一半群； （2） (G， )中有单位元e； （3） (G，)中每一元素a∈G都有逆元 a-1 则称代数系统(G， )为群。
第6章 群论
第六章 群论 6.1 半群与单元半群 6.2 群
第6章 群论
群在代码的查错、改错的研究，自动机理论等 方面都有应用。
第6章 群论
6.1 半群与单元半群
半群与群都是具有一个二元运算的代数系 统，群是半群的特殊例子。事实上，群是历史 上最早研究的代数系统，它比半群复杂一些， 而半群概念是在群的理论发展之后才引进的。 逻辑关系见图6.1.1。

18
6-2 分配格（续）
定理：如果在一个格中交运算对并运算可分配，则并运算 对交运算一定可分配。反之亦然。
定理：每个链是分配格。
定理：设〈A， ≤ 〉为一个分配格，则对任意的a，b，c A，如果有a b = a c且a b = a c，则b=c。
19
6-2 分配格（续）
定义：设〈A,,〉是由格〈A， ≤ 〉所诱导的代数系统。 如果对任意的a,b,cA，当b ≤ a时，有： a (b c) = b (a c) 则称〈A， ≤ 〉是模格。
5
6-1 格的概念（续）
偏序集但不是格
e d f
格
c a b
6
6-1 格的概念（续）
代数系统
设〈A， ≤ 〉是一个格，如果在A上定义两个二元运 算和，使得对于任意的a，bA，ab等于a和b的最小 上界，ab等于a和b的最大下界，那么就称〈A， ， 〉 为由格〈A， ≤ 〉所诱导的代数系统。二元运算， 分 别称为并运算和交运算。
定理：分配格一定是模格。
21
6-3 有补格
定义：设〈A， ≤ 〉是一个格，如果存在元素aA，对 任意的xA，都有a ≤ x， 则称a为格〈A， ≤ 〉的全下界。记作 0。 定义：设〈A， ≤ 〉是一个格，如果存在元素bA，对 任意的xA，都有x ≤ b， 则称b为格〈A， ≤ 〉的全上界。记作 1。
{a,b} {a,b} {a,b} {a,b} {a,b}
{b} {a,b}
6-4 布尔代数（续）
定理：对布尔代数中的任意两个元素a，b，有
(a ) a
ab a b
a b ab
定义：具有有限个元素的布尔代数称为有限布尔代数。
26