离散数学sec15 代数结构

= x+y+z+2xy+2xz+2yz+4xyz
例题分析（续）
(2) 设∘运算的单位元和零元分别为 e 和 ，则对于 任意 x 有 x∘e = x 成立，即 x+e+2xe = x e = 0 由于 ∘ 运算可交换，所以 0 是幺元.
对于任意 x 有 x ∘ = 成立，即 x++2 x = x + 2 x = 0 = 1/2
对二元运算 ∘，如果 x 与 y 运算得到 z，记做 x∘y = z；
对一元运算∘, x 的运算结果记作 ∘x
表示二元或一元运算的方法： 公式、 运算表
注意：在同一问题中不同的运算使用不同的算符
10
二元与一元运算的表示（续）
公式表示 例 设 R 为实数集合，如下定义 R 上的二元运 算 ∗：
x, y∈R, x ∗ y = x. 那么 3 ∗ 4 = 3
右逆元，则称 y 为 x 的逆元. 如果 x 的逆元存在，就称 x 是可逆的.
23
实例分析
集合
Z, Q, R
运算 普通加法+ 普通乘法
Mn(R) 矩阵加法+ 矩阵乘法
P(B) 并 交
对称差
单位元
零元
逆元
24
实例分析
集合
Z, Q, R
运算 普通加法+ 普通乘法
单位元 0 1
Mn(R) 矩阵加法+ n阶全0矩阵
矩阵乘法 n阶单位 矩阵
P(B) 并
交
B
对称差
零元 无 0
无 n阶全0
矩阵 B 无
逆元
X 的逆元 x X 的逆元 x1 (x-1属于给定集合)
X逆元X X的逆元 X1 （X是可逆矩阵） 的逆元为 B 的逆元为 B X 的逆元为 X
25
惟一性定理
定理 设 ∘为S上的二元运算，el 和 er 分别为 S
(3) 复数集合 C 上的一元运算: 求共轭复数 (4) 幂集 P(S) 上, 全集为 S: 求绝对补运算~ (5) A 为 S 上所有双射函数的集合，ASS: 求反
函数 (6) 在 Mn(R) ( n≥2 )上，求转置矩阵
9
二元与一元运算的表示
算符：∘, ∗, ·, , 等符号
表示二元或一元运算
集合
运算
分配律
Z, Q, R 普通加法 + 与乘法 对 + 可分配
+ 对 不分配
Mn(R) 矩阵加法 + 与乘法 对 + 可分配
+ 对 不分配
P(B) 并 与交
对 可分配 对 可分配
交 与对称差 对 可分配
对 不分配
吸收律 无
无
有
无
20
二元运算的特异元素
单位元
定义 设∘为S上的二元运算, 如果存在el（或er）S，
22
二元运算的特异元素（续）
可逆元素及其逆元
令 e 为 S 中关于运算∘的单位元. 对于 x∈S，如
果存在yl（或 yr）∈S 使得
yl ∘ x = e（或 x ∘ yr = e），
则称 yl ( 或 yr )是 x 的 左逆元 ( 或右逆元 ).
关于 ∘运算，若 y∈S 既是 x 的左逆元又是 x 的
代数结构
代数：研究数、关系、结构和代数方程的通用解 法和性质的数学分支 代数结构：装备了一个及以上的运算的非空集合
1
复习
• 幂集 • 函数合成（复合） • 对称差 绝对补~ 相对补 • 双射 单射 满射
复习
• 幂集：集合所有子集组成的集合。 • 函数合成（复合）:g o f = g(f()) • 相对补- ：A-B属于A不属于B的元素集合 • 绝对补~：B是A的子集 • 对称差：AB= (A − B) ∪(B − A)
零元
设 ∘ 为 S 上的二元运算, 如果存在θl（或θr）∈S，使得
对任意 x∈S 都有
θl ∘ x =θl ( 或 x ∘θr =θr )， 则称θl ( 或θr )是 S 中关于 ∘ 运算的 左 ( 或右) 零元. 若θ∈S关于∘运算既是左零元又是右零元，则称θ为 S 上关于运算 ∘ 的 零元.
令 yl = yr = y, 则 y 是 x 的逆元.
假若 y’∈S 也是 x 的逆元, 则
y‘= y’∘ e = y’∘(x ∘ y) = (y’∘ x) ∘ y = e ∘ y = y
所以 y 是 x 惟一的逆元.
说明：对于可结合的二元运算，可逆元素 x 只有 惟一的逆元，记作 x1.
27
消去律
满足xx=x，则称x为运算15 的幂等元。
实例分析
Z, Q, R分别为整数、有理数、实数集；Mn(R)为 n 阶实 矩阵集合, n2；P(B)为幂集；AA 为 A上A，|A|2.
集合
运算
交换律 结合律 幂等律
Z, Q, R 普通加法+
普通乘法
Mn(R)
矩阵加法+ 矩阵乘法
P(B)
并
交
相对补
对称差
AA
中关于运算的左和右单位元，则 el = er = e 为 S 上关于∘运算的惟一的单位元.
证： el = el ∘ er = er
所以 el = er , 将这个单位元记作 e. 假设 e’ 也是
S 中的单位元，则有
e’ = e ∘ e’ = e.
惟一性得证. 类似地可以证明关于零元的惟一性定理. 注意：当 |S| 2，单位元与零元是不同的； 当 |S| = 1 时，这个元素既是单位元也是零元.
• 二元运算的特异元素
– 单位元 – 零元 – 可逆元素及其逆元
6
二元运算的定义及其实例
定义15.1 设 S 为集合,函数 f：S×S→S 称为 S 上 的二元运算, 简称为二元运算. 也称 S 对f 封闭.
7
二元运算的实例（续）
(1)所N 有上的函二数元的运集算合：：加合法成、乘运法算.∘.
f:N×N→N，f(<x,y>)＝x + y f:N×N→N，f(<x,y>)＝xy (2) Z 上的二元运算：加法、减法、乘法. (3) 非零实数集 R* 上的二元运算: 乘法、除法. （4）矩阵Mn(R)的加法、减法等
无
无
对称差
有
有
无
AA
函数复合
无
有
无 17
二元运算的性质（续）
定义 设 ∘ 和 ∗ 为 S 上两个不同的二元运算, (1) 如果 x, y, z∈S 有 (x ∗ y) ∘ z = (x ∘ z) ∗ (y ∘ z) 左分配律 z ∘(x ∗ y) = (z ∘ x) ∗ (z ∘ y) 右分配律 则称 ∘ 运算对 ∗ 运算满足分配律. (2) 如果∘ 和 ∗ 都可交换, 并且 x, y∈S 有 x ∘ (x ∗ y) = x x ∗ (x ∘ y) = x 则称 ∘ 和 ∗ 运算满足吸收律.
函数复合
16
实例分析
Z, Q, R分别为整数、有理数、实数集；Mn(R)为 n 阶实 矩阵集合, n2；P(B)为幂集；AA 为 A上A，|A|2.
集合
运算
交换律 结合律 幂等律
Z, Q, R 普通加法+
有
有
无
普通乘法
有
有
无
Mn(R) 矩阵加法+
有
有
无
矩阵乘法
无
有
无
P(B)
并
有
有
有
交
有
有
有
相对补
无
29
例题分析（续）
解 (1) ∘ 运算可交换，可结合. 任取x, yQ, x ∘ y = x+y+2xy = y+x+2yx = y ∘ x,
任取x, y, zQ, (x ∘ y) ∘ z= (x+y+2xy) + z + 2(x+y+2xy) z
= x+y+z+2xy+2xz+2yz+4xyz x ∘ (y ∘ z) = x + (y+z+2yz) + 2x(y+z+2yz
18
实例分析
Z, Q, R分别为整数、有理数、实数集；Mn(R) 为 n 阶实 矩阵集合, n2；P(B)为幂集；AA为 A上A，|A|2.
集合
运算
分配律
Z, Q, R 普通加法 + 与乘法
吸收律
Mn(R) 矩阵加法 + 与乘法 P(B) 并 与交
交 与对称差
19
实例分析
Z, Q, R分别为整数、有理数、实数集；Mn(R) 为 n 阶实 矩阵集合, n2；P(B)为幂集；AA为 A上A，|A|2.
给定 x，设 x 的逆元为 y, 则有 x ∘ y = 0 成立，即
12
运算表的实例
例4 A = P({a, b}), , ∼分别为对称差和绝对补运算
（{a,b}为全集）
的运算表
∼ 的运算表
{a} {b} {a,b}
X ∼X
{a} {b} {a,b} {a} {a} {a.b} {b} {b} {b} {a,b} {a} {a,b} {a,b} {b} {a}
二元运算的性质
定义 设 ∘ 为 S 上的二元运算, (1) 如果对于任意的 x, y S 有 x ∘ y = y ∘ x, 则称运算在 S 上满足交换律. (2) 如果对于任意的 x, y, z ∈S 有 (x ∘ y) ∘ z = x ∘ (y ∘ z), 则称运算在 S 上满足结合律. (3) 如果对于任意的 x ∈ S 有 x ∘ x = x, 则称运算在 S 上满足幂等律. 如果S中的某些x