离散数学第6章+代数系统

0 0
a
R，
则TS，且T对矩阵乘法·是封闭的。
∴ <T, ·>是V1=<S, ·>的子半群。
11/2/2020 8:50 AM
第三部分：代数结构（授课教师：向胜军）
6
在<T, ·>中存在自己的幺元
1 0
00 ，因为
a 0
00 T， 有
a 0
00
1 0
00
a 0
00，
1 0
00 a0
00
a 0
00，
第三部分：代数结构（授课教师：向胜军）
13
定理1：
设G为群，则G中的幂运算满足 (1) 对xG，(x-1)-1=x. (2) 对x, yG，(xy)-1=y-1x-1. (3) 对xG，xnxm=xn+m. (4) 对xG，(xn)m=xnm. m, n是整数。
11/2/2020 8:50 AM
第三部分：代数结构（授课教师：向胜军）
(x ·y)= (x) ·(y)，
但是
1 0
10 10
00,
而
1 0
00 不是独异点V2的幺元，
∴ 不是独异点V2的自同态。
11/2/2020 8:50 AM
第三部分：代数结构（授课教师：向胜军）
9
DEFINITION 3.
设<G, ◦>是代数系统，◦为二元运算。如果◦ 是可结合的，存在幺元eG，并且对G中的 任意元素x都有x-1G，则称G为群。
14
定理2：
设G为群，对a, bG，方程ax=b和 ya=b在G中有解，且有唯一解。
第六章 几个典型的代数系统
§1 半群与群 §2 环与域 §3 格与布尔代数

在一个集合上构造映射之后，可以利用映射得到集合元素的像，从而形成了运 算。
[定义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元运算

例2:某学校有12位教师,已知有8位老师可以教数学,6位 可教物理,5位可教化学.其中有5位教师既教数学又教 物理.4位老师兼教数学和化学,3位老师兼教物理和化 学,3位老师兼教这三门课. 1.求不教任何课的老师有几位? 2.只教一门课的老师有几位? 3.正好教其中两门课的老师有几位?
例3: 4个x ，3个y，2个z的全排列中，求不出现xxxx，yyy ，zz图象的排列。
设x不具有性质P1,P2,…,Pm ，那么x∉Ai，i＝ 1，2，…m。则它对等式左边计数的贡献为1，对 等式右边的计数的贡献也是1。
根据牛顿二项式定理不难得到上面式子的结果是0．而 由于x具有n个性质，它对等式左边的贡献也为0。
4.3 几个例子
例1:求1-1000之间(包括1和1000)不能被5,也不能被6, 还不能被8整除的整数有多少个?
总体上还是多采用命题逻辑中的等值式，但在叙述
上采用半形式化的方法。
例6.6 证明A-(B∪C)=(A-B)∩(A-C).
证明: 对于∀x
x ∈ A-(B∪C) Ù x ∈ A ∧ x ∉(B∪C) Ù x ∈ A ∧ ⎤ (x∈B ∨ x∈C) Ù x ∈ A ∧ (⎤x∈B ∧ ⎤x∈C) Ù x ∈ A ∧ (x ∉ B ∧ x ∉ C) Ù x∈A∧x∉B∧x∉C Ù (x ∈ A ∧ x ∉ B) ∧ (x ∈ A ∧ x ∉ C) Ù x ∈ A- B ∧ x ∈ A- C Ù x ∈( A- B) ∩(A- C)
全排列的个数为：9！/（4！3！2！）=1260； 所以要求的排列数为
1260－(60+105+280)+(12+20+30)－6 =871.
4.4 三个练习
练习1：求由a,b,c,d构成的n位符号串中，a,b,c,d都至 少出现一次的符号串的数目。

得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。