当前位置：文档之家 › 大连理工大学软件学院 离散数学 第六章 代数系统1：1st-2nd

大连理工大学软件学院 离散数学 第六章 代数系统1：1st-2nd

  • 格式：ppt
  • 大小：428.00 KB
  • 文档页数：70

下载文档原格式

  / 70

合集下载

大连理工大学软件工程课件06综述

大连理工大学软件工程课件06综述

2019/1/23
大连理工大学软件学院
11
6.2.1 设计问题
•
–
在设计用户界面的过程中，几乎总会遇到下述 四个问题：
系统响应时间
–
–
用户帮助设施
出错信息处理
–
命令交互
2019/1/23
大连理工大学软件学院
12
6.2.1 设计问题
1. 系统响应时间
• 系统响应时间指从用户完成某个控制动作(例如， 按回车键或点击鼠标)到软件给出预期的响应(输
2019/1/23
大连理工大学软件学院
26
6.2.3 人机界面设计指南
• 让用户控制交互流。用户应该能够跳过不必要的动作，改变 所需做的动作的顺序(在应用环境允许的前提下)，以及在不 退出程序的情况下从错误状态中恢复正常。 • 对所有输入动作都提供帮助(参见6.2.1节)。 • 消除冗余的输入。除非可能发生误解，否则不要要求用户指 定工程输入的单位；不要要求用户在整钱数后面键入00；尽
– 信息描述易于理解 – 提供恢复错误的建设性意见
– 指出错误可能导致的负面结果
– 多感官提示
2019/1/23
– 不能责怪用户大连理工大学软件学院
15
6.2.1 设计问题
面向用户的错误信息
面向系统的错误信息
2019/1/23
大连理工大学软件学院
16
6.2.1 设计问题
4. 命令交互
•

命令行曾经是用户和系统软件交互的最常用方式，而且也曾 经广泛地用于各种应用软件中。

• 用户界面设计是一个迭代的过程，也就是说，通常先创建设 计模型，再用原型实现这个设计模型，并由用户试用和评估， 然后根据用户的意见进行修改。

《离散数学》课件第6章 (2)

《离散数学》课件第6章 (2)

〈SS, , 〈Σ*, τ〉不是可交换半群。
定义 6.1.3 含有关于*运算的幺元的半群〈S， *〉， 称
它为独异点(monoid)， 或含幺半群， 常记为〈S, *, e〉(e是
幺元)。
第六章 几个典型的代数系统
【例6.1.4】
〈Z, +〉是独异点， 幺元是0， 〈Z, +, 0〉;
〈Z, ×〉是独异点， 幺元是1， 〈Z, ×, 1〉；
(4) A≠ , 〈P(A), ∩〉是半群， 幺元为A， 非空集合无逆
元， 所以不是群。
(5) A≠ , 〈P(A), 是S， 所以是群。
S∈P(A), S的逆元
(6) 〈Q+, ·〉(正有理数与数乘)为一群， 1为其幺元。 〈Q, ·〉不是群， 因为数0无逆元。
因为零元无逆元， 所以含有零元的代数系统就不会是群。
逻辑关系见图6.1.1。
第六章 几个典型的代数系统
图6.1.1
第六章 几个典型的代数系统
定义 6.1.1 设〈S， *〉是代数系统， *是二元运算， 如果*运算满足结合律， 则称它为半群(semigroups)。
换言之， x, y, z∈S, 若*是S上的封闭运算且满足 (x*y)*z=x*(y*z)， 则〈S， *〉是半群。
设半群〈S, *〉中元素a(简记为a∈S)的n次幂记为an， 递 归定义如下：
a1=a an+1=an*a1 n∈Z+ 即半群中的元素有时可用某些元素的幂表示出来。
因为半群满足结合律， 所以可用数学归纳法证明
am*an=am+n， (am)n=amn。
第六章 几个典型的代数系统
普通乘法的幂、 关系的幂、 矩阵乘法的幂等具体的代 数系统都满足这个幂运算规则。

大连理工Chapter5(格与布尔代数)(2008-3-27)(4)

大连理工Chapter5(格与布尔代数)(2008-3-27)(4)

2020年3月25日4时53分
13
6.1布尔代数的定义与性质
定理6.1.10(可约律) 若x，y，z∈S，则 (xy=xz)∧(xy=xz)y=z
定理6.1.11 若x，y，z∈S，则 (xy)(yz) (zx)=(xy)(yz)(zx)
定理6.1.12 若x,y∈S, 则xy = xxy = y。
2020年3月25日4时53分
10
6.1布尔代数的定义与性质
定理6.1.5(等幂律) 若x∈S，则x x = x且x x = x。
定理6.1.6(零律) 若x∈S，则x 1= 1且x 0 = 0。
2020年3月25日4时53分
11
6.1布尔代数的定义与性质
定理6.1.7(吸收律) 若x，y∈S，则 x(x y)= x∧x (xy)= x。
2020年3月25日4时53分
6
6.1布尔代数的定义与性质
由布尔代数的定义可知，分配律成立。利用归纳法 可以证明推广的分配律:
❖ a (bi)= (abi) ❖ a (bi)= (abi) ❖ 更一般地有:
❖ (ai)( bj)= ( (aibj)) ❖ (ai)(bj)= ( (aibj))
2020年3月25日4时53分
ø (c) X={a,b,c}
17
6.2 格
定理6.2.1 给定布尔代数<S，， ，′，0，1>和 S上的偏序关系≤，若任意x，y，z∈S，则
(1) x y ≤ x (2) x ≤x y (3) x≤z∧y≤z xy≤z，x≤y∧x≤z x≤y z (4) x≤y x y′ = 0 (5) (x)(x∈S→0≤x∧x≤1)
且|f(S)|≥2，其中f(S)={y | f(x)= y∈T∧x∈S}，

离散数学第二版答案(6-7章)

离散数学第二版答案(6-7章)

离散数学第二版答案(6-7章)LT第六章 代数系统6.1第129页1． 证明：任取,x y I ∈，(,)*(,)g y x y x y x yx x y xy g x y ==+-=+-=，因此，二元运算*是可交换的； 任取,,x y z I ∈，(,(,))*(*)*()()g x g y z x y z x y z yz x y z yz x y z yz x y z xy xz yz xyz==+-=++--+-=++---+((,),)(*)*()*()(,(,))g g x y z x y z x y xy zx y xy z x y xy z x y z xy xz yz xyz g x g y z ==+-=+-+-+-=++---+=因此，运算*是可结合的。

该运算的么元是0，0的逆元是0，2的逆元是2，其余元素没有逆元。

2．证明：任取,,x y N x y ∈≠，由*,*x y x y x y x ==≠知，**y x x y ≠，*运算不是可交换的。

任取,,x y z N ∈，由(*)**x y z x z x ==，*(*)*x y z x y x ==知，(*)**(*)x y z x y z =，*运算是可结合的。

任取x N ∈，*x x x =，可知N 中的所有元素都是等幂的。

*运算有右么元，任取,x y N ∈，*x y x =，知N 中的所有元素都是右么元。

*运算没有左么元。

证明：采用反证法。

假定e 为*运算的左么元，取,b N b e ∈≠，由*的运算公式知*e b e =，由么元的性质知，*e b b =，得e b =，这与b e ≠相矛盾，因此，*运算没有左么元。

3．解： ① 任取y x I y x ≠∈,,的最小公倍数和y x y x =*的最小公倍数和的最小公倍数和y x x y x y ==*因此对于任意的y x I y x ≠∈,,都有x y y x **=，即二元运算*是可交换的。

2020年大连理工大学软件学院 离散数学 第六章 代数系统2

2020年大连理工大学软件学院 离散数学 第六章 代数系统2
6
群中元素的幂
定义6(2).3 设G是群，a∈G，n∈Z，则a 的 n次幂.
e an an1a
(a1)m
n0 n0 n 0, n m
群中元素可以定义负整数次幂. 在<Z3, >中有
23 = (21)3 = 13 = 111 = 0 在<Z,+>中有
(2)3 = 23 = 2+2+2 = 6
(2) |ab| = |ba|
证 (1) 设 |a| = r，|b1ab| = t，则有
(b1ab)r (b1ab)(b1ab)...(b1ab)
r个
b1arb b1eb e
从而有t | r. 另一方面，由 a = (b1)1(b1ab)b1可知 r | t. 从而 有 |b1ab| = |a|.
14
6(2).2 子群与群的陪集分解
定义6(2).5 设G是群，H是G的非空子集， (1) 如果H关于G中的运算构成群，则称H是G的子群, 记作
H≤G. (2) 若H是G的子群，且HG，则称H是G的真子群，记作
H<G.
例如 nZ (n是自然数) 是整数加群<Z,+> 的子群. 当n≠1时, nZ是Z的真子群.
法. 这些半群中除<Z+,+>外都是独异点 (2) 设n是大于1的正整数，<Mn(R),+>和<Mn(R),·>都是半
群，也都是独异点，其中+和·分别表示矩阵加法和矩阵 乘法 (3) <P(B),>为半群，也是独异点，其中为集合对称差运算 (4) <Zn, >为半群，也是独异点，其中Zn={0,1,…,n1}， 为模n加法 (5) <AA,◦>为半群，也是独异点，其中◦为函数的复合运算 (6) <R*,◦>为半群，其中R*为非零实数集合，◦运算定义如 下：x, yR*, x◦y=y

离散数学第六章代数系统

离散数学第六章代数系统

6.2 代数系统的基本性质
性质4 吸收率
给定<S，⊙，*>，则 ⊙对于*满足左吸收律：(x)(y)(x，y∈S→x⊙(x*y)=x) ⊙对于*满足右吸收律：(x)(y)(x，y∈S→(x*y)⊙x=x) 若⊙对于*既满足左吸收律又满足右吸收律，则称⊙对于*满足吸收律或
者可吸收的。
*对于⊙满足左、右吸收律和吸收律类似地定义。 若⊙对于*是可吸收的且*对于⊙也是可吸收的，则⊙和*是互为吸收的或
代数﹝Algebra﹞是数学的其中一门分支，可大致分为初等代数学和抽象 代数学两部分。
代数的由来
初等代数学：是指19世纪中期以前发展的方程理论，主要研究某一方程﹝ 组﹞是否可解，如何求出方程所有的根﹝包括近似根﹞，以及方程的根有 何性质等问题。
抽象代数：是在初等代数学的基础上产生和发展起来的。它起始于十九世 纪初，形成于20世纪30年代。在这期间，挪威数学家阿贝尔(N.H. Abel)、 法国数学家伽罗瓦(E′. Galois)、英国数学家德·摩根(A. De Morgan) 和布尔(G. Boole)等人都做出了杰出贡献，荷兰数学家范德瓦尔登(B.L. Van Der Waerden)根据德国数学家诺特(A.E. Noether)和奥地利数学家阿 廷(E. Artin)的讲稿，于1930年和1931年分别出版了《近世代数学》一卷 和二卷，标志着抽象代数的成熟。
同态与同构
PART 同余、商代数、积代数
04
PART 05
代数系统实例
6.1 代数系统的定义
定义6.1 设S是个非空集合且函数f： Sn→S ，则称f为S上的一个 n元运算。其中n是自然数，称为运算的元数或阶。
当n = 1时，称f为一元运算，当n = 2时，称f为二元运算，等等。 定义6.2 如果对给定集合的成员进行运算，从而产生了象点，而

离散数学第六章

离散数学第六章

6.1.6 循环群和置换群
§循环群 在循环群G=<a>中, 生成元a的阶与群G的阶是一样 的. 如果a是有限阶元, |a|＝n, 则称G为n阶循环群. 如 果a是无限阶元, 则称G为无限阶循环群. 例如: <Z,+>是无限阶循环群; <Z6,>是n阶循环群. 注意:(1) 对9 无限阶循环群G=<a>, G的生成元是a和a-1; (2) 对n阶循环群G=<a>=<e,a,…,an-1>,G的生成元是at 当且仅当t与n互素, 如12阶循环群中, 与12互素的数 有1、5、7、11. 那么G的生成元有a1=a、a5、a7、 a11. (3) N阶循环群G=<a>, 对于n的每个正因子d, G恰好有 一个d阶子群H=<an/d>.
6.1.3 子群
例如, 群<Z6,>中由2生成的子群包含2的各次 幂, 20=e=0, 21=2, 22=22=4, 23=222=0, 所 以由2生成的子群：<2>={0,2,4}.
对于Klein四元群G={e,a,b,c}来说, 由它的每个 元素生成的子群是 <e>={e}, <a>={e,a}, <b>={e,b}, <c>={e,c}
6.1.6 循环群和置换群
§循环群
定义6.7 在群G中, 如果存在aG使得 G={ak|kZ} 则称G为循环群, 记作G=<a>,称a为G的生成元. ☆ 循环群必定是阿贝尔群, 但阿贝尔群不一定 是循环群. 证明: 设<G,*>是一个循环群, 它的生成元是a, 那么,对于任意x,yG, 必有r,sZ, 使得 x=as,y=at, 而且x*y=as*at=as+t=at*as=y*x 由此可见<G,*>是一个阿贝尔群. 例如,<Z,+>是一个循环群, 其生成元是1或-1.

离散数学第六章

离散数学第六章

第六章几个典型的代数系统6.1 半群与群引言：简略介绍群论产生的背景1. 图形的对称性如正三角形、正方形（一般地正n 边形）、长方形、 等腰三角形、等腰梯形等；三维空间中的正四面体、 正方体、长方体等都各有自己的对称性。

画图解释：2．用根式求解代数方程的根（1）一元二次方程：20x bx c ++=⇒122b x -±=，。

注：①约公元前2000年即出现二次方程求根问题； ②约公元9世纪时，阿拉伯人花拉子米首次得到上述求根公式。

（2）三次及四次方程的求根公式一般三次方程: 320x ax bx c +++=。

先作变换：用3a x -代替x 后可化成 3x mx n +=（不含二次项）， （*）其中 332,3327a ab a m b n c =-=--。

利用恒等式：333()3()u v uv u v u v -+-=-，把它与（*）比较得：33,3,x u v uv m u v n =-=-=。

由后面两个关于33,u v 的方程可得u x u v v ⎫⎪=⎪⇒=-= （即*方程的解） 以上求解三次方程的公式叫做卡丹公式， 出现在公元1545年出版的著作《大书》中。

关于四次方程的求根公式这里从略，可以肯定的是， 四次一般方程也有求根公式，并且也叫卡丹公式。

（3从1545年之后的近300年间，人们都没能找到五次(当然，这并不排除对 某些特殊的五次及五次以上的方程可以求出它们的根）。

直到1830年由法国人Galois （伽珞瓦）解决，证明出：五次及五次以上的一般方程不存在用加、减、乘、除及开方表示的求根公式，所用方法就是现在已广为接受的群的思想。

可是在当时，很多同时代的大数学家都无法理解和接受他的思想方法。

3．群在其它方面的应用：如编码理论、计算机等。

一．群的定义及简单性质1定义：设,G ⋅是一个具有二元运算⋅的代数系统，如果⋅同时满足（1）结合律：即,,a b c G ∀∈，()()a b c a b c ⋅⋅=⋅⋅总成立；（2）存在单位元（也称为幺元，记为e ），即 ,;a e e a a a G ⋅=⋅=∀∈（3）中每个元素a 都有逆元（记为1a -）：即存在1a G -∈，使得11a a a a e --⋅=⋅=，则称G 关于运算⋅构成一个群。

大连理工大学软件学院计算机组成原理ppt

大连理工大学软件学院计算机组成原理ppt
13
虚拟机器 M4
虚拟机器 M3
软 件 虚拟机器 M2
硬 实际机器 M1 件
微程序机器 M0
用编译程序翻译 成汇编语言程序
用汇编程序翻译 成机器语言程序
1.1
用机器语言解释操作系统
用微指令解释机器指令
由硬件直接执行微指令
14
三、计算机体系结构和计算机组成 1.1
有无乘法指令
计算机 程序员所见到的计算机系统的属性 体系结构 概念性的结构与功能特性
x3 3!
+
x5 5!
-
x7 7!
+
x9 9!
-
…
√x =
1 2
(
yn +
x yn
)
(
n
=
0,
1,
2,
…)
• 编制解题程序
程序 —— 运算的 全部步骤
指令 —— 每 一个步骤
1.2
21
编程举例
1.2
计算 ax2 + bx + c = (ax + b)x + c
取x 至运算器中 乘以x 在运算器中 乘以a 在运算器中 存ax2 在存储器中 取b 至运算器中 乘以x 在运算器中 加ax2 在运算器中 加c 在运算器中
16
冯·诺依曼计算机硬件框图
1.2
存放数据 将信息和转程换序成机 器能识别的形式
存储器
算将术结运果算转换成 人逻们辑运熟算悉的形式
输入设备
运算器
输出设备
控制器
指挥程序 运行
17
冯·诺依曼计算机硬件框图
1.2
输入设备
存储器 运算器 控制器
输出设备

离散数学 代数系统 ppt课件

离散数学 代数系统 ppt课件

1
33 0 1 2 8
代数系统举例
设A={1，2，3，4，6，12} A上的运算*定义为：a*b=|a-b| （1）写出二元运算的运算表； （2）<A,*>能构成代数系统吗？
9
解答
由运算表可知*运算在集合A上不封闭
所以： <A,*>不能构成代数系统
* 1 2 3 4 6 12
1 0 1 2 3 5 11
U=<I,+, > 证明：V=< m,+m, m >
满同态
g:I→Nm 对于所有的iI,有：
g(i)=(i)(modm)
32
证明
类型映射f定义为：f(+)=+m,f()=m (1)显然U=<I,+, >和V=< Nm,+m, m >同类型
(2)运算的象=象的运算
对任意的x,yI: g(x+y)=g(x) +m g(y) g(x y)=g(x) m g(y)
12
4、同类型的代数系统
V1=<S1，Ω1>:代数系统 类型映射 V2=<S2，Ω2>:代数系统 同元运算
存在一个双射函数f: Ω1 → Ω2 每一个ω∈Ω1和f(ω) ∈Ω2具有相同的阶 ωf V1和V2是同类型的代数系统
13
同类型的代数系统举例
V1=<Nm,+m , m > 和V2=<R,+, >是 同类型的代数系统吗？其中：
41
满同态举例（续）
(5)对“＋”存在e=0,则: 对“+3”存在e=g(0)=0; (6)对“”存在e=1,则: 对“3”存在e=g(1)=1; (7)对“”存在零元=0,则: 对“3”存在零元=g(0)=0;

大连理工大学软件学院 离散数学 第六章 代数系统1：-3rd

大连理工大学软件学院 离散数学 第六章 代数系统1：-3rd

• 例6(1).4.1 给定<Z，+，×>，其中Z是整数集 合，+和×是一般加、乘法。假设Z中的关系R 定义如下： • i1Ri2：= | i1 | = | i2 | 其中i1、i2∈Z • 试问，R为该结构的同余关系吗？ • 其中| i1 | 表示i1的绝对值. • 相等关系是等价关系是明显的，只要证它满足 代换性即可．即证对任意的i1,i2,i3,i4Z和 i1Ri2i3Ri4 | i1 | = | i2 | | I3 | = | i4 | • | i1+i3 |= | i2+i4 | • 对i1=1, i2=1, I3 =3, i4=-3
• | i1+I3 |=4 • | i2+i4 | =2 • 即对+不满足代换性，即Ｒ不是 <Z，+，×>的 同余关系．
• 可见，考察一个等价关系E对于有多个运算的 代数结构是否为同余关系，这里有个次序先后 问题，选择得好，即你一下子就考察到了E对 某个运算是不具有代换性质，那么立刻便可断 定E不是该结构的同余关系，否则验证应继续 下去，直至遇到不具有代换性质的运算为止。 如果对于所有运算都有代换性质，则E为该结 构的同余关系。在例6.4.1中，首先发现R对于 +不具有代换性质，那么可断定R不是该结构的 同余关系。如果你首先验证是R对于×的代换 性质，结果R对于×有代换性质，至此你只是 有希望E是同余关系，但还得继续工作，考察R 对于+的代换性质，由此结果才能判定R是否为 该结构的同余关系。
定义6补.2 设*是定义在集合A上的二元运 算，如果对于任意的x，y∈A，都有x*y＝ y*x，则称该二元运算*是可交换的。 例题2 设Q是有理数集合，△是Q上的二 元运算，对任意的a，b∈Q，a△b＝a+ba· b，问运算△是否可交换。 解 因为 a△b＝a+b-a· b＝b+a-b· a＝b△a 所以运算△是可交换的。

第六章 代数系统--复习

第六章 代数系统--复习
27/66
群论-基本概念
• 变换群：集合X是无限的，令TX表示所有从集合X到X的变 换的集合，具有下列性质：
– – – – (∀f)(∀g)(f，g∈TX →f ○ g，g○f ∈TX) (∀f)(∀g)(∀h)(f，g，h∈TX →(f ○ g)○h = f ○(g○h)) (∃idA)(idA∈TX∧(∀f)(f ∈TX →idA○f = f ○idA = f )) (∀ f)(f ∈TX →(∃ f -1)(f -1∈TX∧ f ○ f -1= f -1○ f = idA))
9/66
代数系统-基本性质
• 结合律 • 交换律 • 分配律
– 左分配律 – 右分配律
• 吸收律
– 左吸收律 – 右吸收律
10/66
代数系统—基本性质
• 等幂律与等幂元 • 幺元或单位元
– 左幺元 – 右幺元 – 幺元唯一
Байду номын сангаас
• 零元
– 左零元 – 右零元 – 零元唯一
11/66
代数系统—基本性质
1/66
第六章-复习
第一部分：代数系统基本概念及性质 第二部分：半群与群 第三部分：格与布尔代数
2/66
代数系统基本概念及性质
3/66
代数系统—基本定义
代数系统：设S是个非空集合且fi是S上的ni元 运算，其中i = 1，2，…，m。由S及f1， f2，…，fm组成的结构，称为代数系统，记 作< S， f1，f2，…，fm >。 • 有限代数 • 无穷代数
17/66
代数系统—基本性质
(e)如果⊙和*满足等幂律，则⊕和⊗也满足等幂律。 (f)如果e1和e2分别是关于⊙和*的幺元，则f(e1)和f(e2) 分别为关于⊕和⊗的幺元。 (g)如果θ1和θ2分别是关于⊙和*的零元，则f(θ1)和f(θ2) 分别为关于⊕和⊗的零元。 (h)如果对每个x∈X均存在关于⊙的逆元x -1，则对每 个f(x)∈Y也均存在关于⊕的逆元f(x -1)；如果对每个 z∈X均存在关于*的逆元Z -1，则对每个f(z)∈Y也均 存在关于⊗的逆元f(z -1)。

大连理工大学软件学院离散数学作业答案

大连理工大学软件学院离散数学作业答案

A( x)
(x ) A ( x )
(x ) P ( x ) P( x)
P（假设前提） US（1）
（3） （4） （5） （6） （7）
(x ) (P (x ) Q (x ) ) P( x) Q( x) Q( x )
(x )Q ( x )
P US（3） T（2） （4） UG（5） CP（1） （6）
P
P
P 规则（假设前提） T 规则（1） P 规则 T 规则（2） （3） P 规则
P Q
Q
S Q
（6） （7） （8）
S
RS
R
T 规则（4） （5） P 规则 T 规则（6） （7） P 规则 T 规则（8） （9） F 规则（1） （10）
（9） R （10） R R （11） P
( A ( P Q)) C ( A (P Q)) C (A (P Q)) C A ( P Q ) C ( A C ) ( P Q )
因此， (( Q
A) C ) ( A ( P C )) ( A ( P Q )) C ，得证。
(x ) P ( x ) ( x ) Q (x )
（b） (x)( P( x) Q( x)) (x) P( x) (x)Q( x)
证明：由于
(x) P( x) (x)Q( x) (x)(Q( x)) (x) P( x) (x)(Q( x)) (x) P( x)
因此，原题等价于证明 (x)( P( x) Q( x)) (x)(Q( x)) (x) P( x) （1） （2） （3） （4） （5） （6） （7）
A) C ) ( A ( P C )) ( A ( P Q )) C

第六章 代数系统2：-3rd-li

第六章 代数系统2：-3rd-li
第六章 代数系统
李豪杰 副教授 大连理工大学软件学院 数字媒体技术系 Email: hjli@
1/36
回顾
• 群
给定代数系统Ｖ＝ ， 给定代数系统Ｖ＝<G，⊙>，若<G，⊙>是独异点且 Ｖ＝ ， ， 是独异点且 每个元素存在逆元， 每个元素存在逆元，或者 是可结合的， ① ⊙是可结合的， 关于⊙存在幺元， ② 关于⊙存在幺元， 中每个元素关于⊙ 是群。 ③ G中每个元素关于⊙是可逆的，则称 ，⊙>是群。 中每个元素关于 是可逆的，则称<G， 是群
15/36
•
接下来讨论子群的陪集。 接下来讨论子群的陪集。
• 定义 定义6.12.3 令<H，⊙>是群 ，⊙>的子群且 ∈G， 是群<G， 的子群且a∈ ， ， 是群 的子群且 则把下面集合： 则把下面集合： • a⊙H = {a⊙h | h∈H} ⊙ ⊙ ∈ • 称为由元素 所确定的群 ，⊙>中的 的左陪集，或 称为由元素a所确定的群 所确定的群<G， 中的H的左陪集 中的 的左陪集， 简称为左陪集并简记aH。此外， 是左陪集aH的代 简称为左陪集并简记 。此外，称a是左陪集 的代 是左陪集 表元素。 表元素。 • 类似地可定义由 所确定群 ，⊙>中的 的右陪集 。 类似地可定义由a所确定群 所确定群<G， 中的H的右陪集 中的 的右陪集Ha。 • 显然，若<G，⊙>是Abel群，并且 ，⊙>是其子群， 显然， 是其子群， ， 是 群 并且<H， 是其子群 则aH = Ha，即循环群的任意元素的左陪集等于其右 ， 陪集。 陪集。
17/36
• 若aCHb且bCHc，则b-1⊙a∈H和 且 ， ∈ 和 • c-1⊙b∈H，所以 -1⊙a = ∈ ，所以c • (c-1⊙b) ⊙(b-1⊙a)∈H，故有 Hc，因而满足传递性。 传递性。 ∈ ，故有aC ，因而满足传递性 • 显然，左陪集关系能把集合G划分成等价类。若a∈G， 显然，左陪集关系能把集合 划分成等价类。 ∈ ， 划分成等价类 则 • [a]= {b | bCHa} = {b | <b，a>∈CH} ， ∈ • = {b | a-1⊙b∈H} = {b | a-1⊙b=h, h∈H} = {b | b = ∈ ∈ a⊙h，h∈H} ⊙ ， ∈ • = {a⊙h | h∈H} = aH ⊙ ∈ • 其中 = a-1⊙b。 其中h 。 • 也就是说，a的等价类等于 确定的 的左陪集 也就是说， 的等价类等于 确定的H的左陪集 的等价类等于a确定的
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

a1 a2 1 2 … a1 a1 a1 a2 … 1 1 1 2 a 1 a 2 2 … a2 2 1 2 a2 … … … an a1 an a2 … n 1 n 2
an n a1 an 1 n a n a2 2 n
ai i
an an n n
a1 1 a2 2 . . . an n
• 6(1).2.4吸收律 • 给定<S，⊙，*>，则 • ⊙对于*满足左吸收律：(x)(y)(x， y∈S→x⊙(x*y)=x) • ⊙对于*满足右吸收律：(x)(y)(x， y∈S→(x*y)⊙x=x) • 若⊙对于*既满足左吸收律又满足右吸收律，则 称⊙对于*满足吸收律或者可吸收的。 • *对于⊙满足左、右吸收律和吸收律类似地定义。 • 若⊙对于*是可吸收的且*对于⊙也是可吸收的， 则⊙和*是互为吸收的或⊙和*同时满足吸收律。
• 代数系统是以研究数字、文字和更一般元素 的运算的规律和由这些运算适合的公理而定 义的各种数学结构的性质为中心问题。它对 现代数学如扑拓学、泛函分析等以及一些其 他科学领域，如计算机科学、编码理论等， 都有重要影响和广泛地应用。
第六章
本章分三个部分 第一部分：代数系统基本概念及性质 第二部分：半群与群，环与域 第三部分：格与布尔代数
• 运算的例子很多。例如，在数理逻辑中，否 定是谓词集合上的一元运算，合取和析取是 谓词集合上的二元运算；在集合论中，并与 交是集合上的二元运算；在整数算术中，加、 减、乘运算是二元运算，而除运算便不是二 元运算，因为它不满足封闭性。
运算表：表示有穷集上的一元和二元运算

a1 1 a2 2 . . . an n
15/65
• 下面举例说明上述各个概念。 • 例6(1).1.1 设R是实数集合，且+和×是R上的普 通加法和乘法运算，则<R，+，×>是一代数系 统。因为运算+和×在R中是封闭的。 • 例6(1).1.2 设S是非空集合，P(S)是它的幂集。对 任意集合A，B∈P(S)上的运算和如下: • AB =(A-B)∪(B-A) • AB = A∩B • 则<P(S)，，>是一代数系统。因为，显然 和是闭运算。
• 例6(1).2.2 给定<Q，*>，其中Q为有理数集合， 并且对任意a，b∈Q有a*b = a + b - a· b，问运算 *是否可交换? • 可见，如果一代数结构中的运算⊙是可结合和 可交换的，那么，在计算a1⊙a2⊙…⊙am时可按 任意次序计算其值。特别当a1 = a2 = … = am = a 时，则a1⊙a2⊙…⊙am = am。称am为a的m次幂， m称a的指数。下面给出am的归纳定义： • 设有<S，⊙>且a∈S。对于m∈N+，其中N+表 示正整数集合，可有 • (1) a1 = a • (2) am+1 = am ⊙ a
• 6(1).2 代数系统的基本性质
• 对于代数系统的性质的考察方法不是一个一个 研究各个结构，而是列举一组性质，并且对于 具有这些性质的任何代数结构推导可能的结论。 把那些被选出的性质看成是公理并且由这些公 理推导出的任何有效结论，对于满足这些公理 的任何代数结构也都必定成立。
• 因此，为了作出这样的讨论，将不考虑任何 特定的集合，也不给所涉及到的运算赋予任 何特定的含义。这种系统的集合及集合上的 诸运算仅仅看成是一些符号，或更确切地说， 它们都是些抽象对象。因此，与此相应的代 数系统，通常称为抽象代数。对于那些特定 的代数系统只能是具有基本性质中的某些性 质。
• 例6(1).2.4 给定<N，⊙，*>，其中N是自然数集 合，⊙和*定义如下： • 对任意a，b∈N有a⊙b = max{a，b}，a*b = min{a，b}，试证，⊙和*互为吸收的。 • 6(1).2.5等幂律与等幂元 • 给定<S，⊙>，则 • “⊙”是等幂的或“⊙”满足等幂律： (x)(x∈S→x⊙x = x) • 给定<S，⊙>且x∈S，则 • x是关于“⊙”的等幂元： x⊙x = x
12/65
定义6(1).1.2 设S是个非空集合且fi是S上的ni元运 算，其中i = 1，2，…，m。由S及f1，f2，…，fm 组成的结构，称为代数系统，记作 < S， f1，f2，…，fm >。 此外，集合S的基数即 | S | 定义代数系统的基数。 如果S是有限集合，则说代数结构是有限代数系 统；否则便说是无穷代数系统。 有时，要考察两个或多个代数系统，这里就有个 是否同类型之说，请看下面定义：
第六章 代数系统
回顾
• 数理逻辑
–命题逻辑 –谓词逻辑
• 关系理论
–集合理论 –关系理论 –函数理论
什么是代数？
爱因斯坦小时候曾好奇的问他的叔叔：“代数是什 么”？（那时候他只学过算术）他的叔叔回答的很 妙：“代数是一种懒惰人的算术，当你不知道某些 数时，你就暂时假设它为x、y，然后再想办法去寻 找它们。” 道理一经点破，就好象“哥伦布立蛋” 的故事一样，人人都会做了。 代数是什么？以符号代替数的解题方法就是代数。
• 于是，不难证明下面定理： • 定理6(1).2.2 若x是<S，⊙>中关于⊙的等幂元， 对于任意正整数n ，则xn = x。 • 例6(1).2.5 给定<P(S)，∪，∩>，其中P(S)是集 合S的幂集，∪和∩分别为集合的并和交运算。 • 验证：∪和∩是等幂的。
• 例6(1).1.4 设有一台字长为8位的计算机，它以 定点加、减、乘、除以及逻辑加和逻辑乘为运算 指令，并分别用01，02，…，06表示之。则在计 算机中由28个不同数字所组成集合S同该机中运 算指令构成一代数结构<S，01，02，…，06>。 • 在结束本节时，声明记号 • <S， f1，f2，…，fm >即为一代数系统，除特别 指明外，运算符f1，f2，…，fm均为二元运算。 根据需要对S及f1，f2，…，fm可置不同的集合符 和运算符。
Байду номын сангаас
代数是从算术精炼出来的结晶，虽平凡但妙用无穷。 因此它又叫做广义算术(generalized arithmetic) 或进阶算术(advanced arithmetic)或普遍算术 （universal arithmetic）。
代数的由来
Algebra一名来自阿拉伯文al-jabr，al为冠词，jabr 之意为恢复或还原，解方程式时将负项移至另一边变 成正项，也可说是还原，也有接骨术的意思。 中国在1859年正式使用代数这个名词（李善商在代微 积拾级一书中的序中指出“中法之四元，即西法之代 数也”），在不同的时期有人用算术作为代数的名称， 中国古书九章算术其实是一本数学百科全书，代数问 题分见于各章，特别是第八章方程，主要是论述线性 （一次）联立方程组的解法，秦九韶（1249）的数书 九章中有“立天元一”的术语，天元就是代表未知数， 用现在的术语来说就是“设未知数为x” 。
8/65
第一部分 代数系统基本概念及性质 6(1).1 代数系统的定义 定义6(1).1.1 设S是个非空集合且函数f： Sn→S ，则称f为S上的一个n元运算。其中n是 自然数，称为运算的元数或阶。 当n = 1时，称f为一元运算，当n = 2时，称f为 二元运算，等等。 注意到，n元运算是个闭运算，因为经运算后产 生的象仍在同一个集合中。封闭性表明了n元 运算与一般函数的区别之处。此外，有些运算 存在幺元或零元，它在运算中起着特殊的作用， 称它为S中的特异元或常数。
•
表6(1).2.1
⊙ 0 1
0 0 0 1 0 1 * 0 1 1 1 0 0 1 1
• 形如表6(1).2.1的表常常称为运算表或复合表， 它由运算符、行表头元素、列表头元素及复合元 素四部分组成。对于集合S的基数很小，特别是2 或3时，代数结构中运算常常用这种表给出。优 点是简明直观，一目了然。
定义6(1).1.3 设两个代数系统 <S， f1，f2，…，fm>和 <T， g1，g2，…，gm>，如果fi和gi(1≤i≤m)具有相 同的元数，则称这两个代数系统是同类型的。 可见，判定两个代数系统是否同类型，主要是对 其运算进行考察。 此外，有时还需要在代数系统中集合的某个子集 上讨论其性质，这就引出子代数结构的概念。
a1 1 a 2
. . . an n
2
二元运算的运算表
一元运算的运算表
• 在本章讨论的代数结构中，主要限于一元和二元 运算。将用 ′ 、┐或 ˉ 等符号表示一元运算 符；用、、⊙、*、∨、∧、∩、∪等表示二 元运算符。一元运算符常常习惯于前置、顶置或 肩置，如 ┐x、、x′；而二元运算符习惯于前 置、中置或后置，如：+ xy，x + y，xy +。 • 有了集合上运算的概念后，便可定义代数系统了。
代数﹝Algebra﹞是数学的其中一门分支，可大致 分为初等代数学和抽象代数学两部分。 初等代数学是指19世纪中期以前发展的方程理论， 主要研究某一方程﹝组﹞是否可解，如何求出方 程所有的根﹝包括近似根﹞，以及方程的根有何 性质等问题。
抽象代数是在初等代数学的基础上产生和发展起 来的。它起始于十九世纪初，形成于20世纪30年 代。在这期间，挪威数学家阿贝尔(N.H. Abel)、 法国数学家伽罗瓦(E′. Galois)、英国数学家 德·摩根(A. De Morgan)和布尔(G. Boole)等人 都做出了杰出贡献，荷兰数学家范德瓦尔登(B.L. Van Der Waerden)根据德国数学家诺特(A.E. Noether)和奥地利数学家阿廷(E. Artin)的讲稿， 于1930年和1931年分别出版了《近世代数学》一 卷和二卷，标志着抽象代数的成熟。
• 类似地可定义*对于⊙是满足左或右分配律。
• 若⊙对于*即满足左分配律又满足右分配律， 则称⊙对于*满足分配律或是可分配的。同 样可定义*对于⊙满足分配律。