[ Read ] 北京大学离散数学视频回顾
集合论
第一课
overview, 离散数学研究的领域:
- 集合论, 图论
- 代数结构 - 研究各种代数的定律,交换律等等 组合数学-研究排列组合
- 数理逻辑-使用数理推理逻辑,
集合论包括: 集合、二元关系、函数、自然数、基数(势)
图论包括: 图、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配/覆盖/独立/匹配、带权图
逻辑演算: 命题逻辑演算,谓词逻辑演算
p q r 代表命题, 为真或者为假
- ~ 否
- v 或者
- ^ 并且 合取式
- -> 蕴含 implies
- <-> 等价
以上存在优先级,从上至下。
- 可满足
- 矛盾式 永假
- 重言式 永假
等值演算
A <=> B: A <-> B 是用真式
公式之间可以进行演算。
16 组等值演算律
- 幂等律 A <=> A v A , A <=> A ^ A
- 交换律 A v B <=> B v A, A ^ B <=> B ^ A
- 结合律 (A v B) v C <=> A v (B v C) / (A ^ B) ^ C <=> A ^ (B ^ C)
- 分配律
- 德摩根定律
- 吸收率
- 零律
- 同一律
- 排中律
- 矛盾律
…
值得记忆的是, 德摩根定律
~(A v B) <=> ~A ^ ~B
第二课
- 双重否定律
- 蕴含等值 A -> B <=> ~A v B
- 等价等值式
- 等价否定等值式 A <-> B <=> ~B <-> ~A
- 假言易位 A -> B <=> ~B -> ~A
- 归谬论 (A -> B) ^ (A -> ~B) <=> ~A (或者说,反证法经常用)
根据上面的等值式, 可以开始进行等值演算。
例子: p -> (q -> r)
重要的推理定律 9:00 若 A -> B 是永真式, 则 A => B
- 附加律
- 化简律
- 假言推理
- 拒取式
- 析取三段论
- 假言三段论
- 等价三段论
- 构造性两难
一阶谓词逻辑基本概念与命题符号化
全总个体域: 限定范围内所有的东西
量词: ForAll ThereExist
辖域:
指导变元:
自由变元:
约束出现:
有限个体域可以消去量词
量词可以进行否定 ~ForAqjjj1jjjjjjjjjjj:jkjkjkjlx A(x) <=> ThereExist ~A(x)
量词管辖域的收缩与扩张
第三课
等价 <=>
推理 =>
接着上一课仍然讲量词辖域的收缩与扩张
量词分配
ForAll(A(x) ^ B(x)) <=> ForAllA(x) ^ ForAll B(x)
ThereExist(A(x) v B(x)) <=> ThereE A(x) v ThereEB(x)
前束范式: 存在量词在最前面, 且作用到公式尾部。
重要的推理定律:
- ForA x A(x)v ForA B(x) => ForA (A(x) v B(x))
- ThereE x (A(x) ^ B(x)) => ThereE x A(x) ^ ThereE x B(x)
- ForA (A(x) -> B(x)) => ForA x A(x) -> ForA x B(x)
- ForA x (A(x) -> B(x) ) => ThereE x A(x) -> ThereE x B(x)
28:00 开始讲集合论
- 集合的概念
- 集合之间的关系
- 集合的运算
- 文氏图,容斥原理
谈到罗素悖论
集合的表示方法有哪些? 列举法/描述法/特征函数法/文氏图
谈到集合的概念, 集合用来定义数学基础。但是因为如果没有公理定义,则存在悖论。引出罗素悖论。所以谈到公理集合论,和朴素集合论。本课程是朴素集合论。
第四课
集合的运算方式
集合,子集,真子集,空集,幂集,n元集,指标集
交并补, 相对补集,对称差,绝对补,广义并,广义交
容斥原理, principle of inclusion/exclusion
主要是用于 counting, 可以说是用数论来计数,但是计算的是集合交集的运算方式。
AuB | = | A | + | A | - | A^B |
第五课
集合恒等式,与等值演算类似。
11:00 提到对偶原理,用于讲解公式的对称性。
集合可以通过形式化的证明, 也就是讲集合转换成逻辑语句,然后进行等值演算。
28:00 讲解对称差的性质。也是对称差存在的一些定律。
43:00 特征函数与集合运算。
第六课
集族的一些性质,以及其证明
第七课 第二章
二元关系
有序对与笛卡尔集
有序三元祖, 有序 n 元组
笛卡尔集
笛卡尔集性质
36:00 开始讲解二元关系
A 上的二元关系。 举例来说, 三个元素存在多少种不同的二元关系。 512 种。 为啥? 3x3 ,然后从当中取出两个元素,也就是 2^9,512 种不同的取法。
第八课
一些特殊关系。
- 空关系,
- 恒等关系,
- 全域关系,
- 整除关系,
- 小于等于,
- 包含关系,
- 真包含
二元关系有关的一些概念
- 定义域(domain),值域(range),域(domain)
- 逆(inverse),合成(compose)
- 限制(restriction) 象(image)
- 单根,单值
comments: 感觉这个部分,mit 的课程更加清晰一些。
injection, surjection, bijection, total, function
第九课
关系的表示/性质/闭包
关系的表示方法
集合,关系矩阵,关系图
关系矩阵在效率上存在一定的优势,关系图对理解层面,存在优势。
关系
自反,反自反,对称,反对称,传递
闭包
自反闭包,对称闭包,传递闭包
第十课
继续讲解关系当中,传递性
30:00 开始讲解闭包
一个对象刚开始不具备自反性,添加最小集合的元素,从而使对象具有自反性。
则,增加的这些元素的集合,称之为自反闭包。
以此类推。
第十一课
等价关系: 自反,对称,传递的二元关系。
具体实践有: 等价类,商集,划分,块,加细。
第二类, Stirling 数, Bell 数。
偏序关系:自反,反对称,传递的二元关系。
表达偏序关系使用哈斯图
特殊元素,链,反链。
线序,拟序,良序。
等价关系
R 是等价关系 <=> R 是自反的,对称的,传递的
提到 mod 关系。这个关系是等价关系。
A = {a,b,c} 上的全体等价关系有 5 种。
{a,b,c}/ {a},{b},{c},/ {a,b}, {c}/ {a,c},{b}/{b,c}, {a}
划分: partition
stirling 子集数 将 n 个不同的球放到 k 个相同的盒子,要求无空盒,不同放法的总数,称之为 striling 数。
30:00 左右开始讲划分
第十二课 偏序关系
3:00
partial order.
poset ,偏序集
12:00 哈斯图
- 用顶点表示 A 中元素。
- 当且仅当 y 覆盖(自然数当中,大于关系中,3 覆盖 2) x 时,y 在 x 上方,在 x 与 y 之间画无相边。
- 组织架构图可以理解为一种哈斯图
16:00 开始讲各种偏序关系的哈斯图的例子。
21:00 全序关系(线序关系) – 哈斯图是一条直线。
拟序关系: 反自反的,传递的 -> 反对称性
30:00 上确界, 下确界。
33:00 链, 反链 ,哈斯图当中的一个分支,就是一个链。
反链,就是链上元素互相都不可比较。
42:00 良序关系, well ordering principle…,良序集可以做数学归纳法
每一个集合都可以良序化。
良序原理 <=> 选择公理
第十三课 函数
偏函数: A 到 B 的偏函数 partial function – domF 属于 A ^ ranF 属于 B
全函数 total function: bijection + function
13:00 真偏函数
真偏函数,就是偏函数减去全函数
本节只讨论全函数。
单射: injection , F 是单根的。
满射: surjection, ran F = B
双射: bijection , 一一对应
函数的计数
33:00 image ,象与原象
特殊函数:
- 常数函数 对于所有的 input, 输出均为常数
- 恒等函数 对于所有的 input, 输出也为 x
- 特征函数 对于所有的 input, 如果 x 属于 A, 则 output 为1, 否则为 0.
- 单调函数 单调增, 单调减, input & output 是偏序集。
- 自然映射/典型映射 一个元素对应到等价类,或者说等价关系。例如,所有男人都是渣男,看看谁谁谁都那么渣。
A = {a,b,c,d,}
A/R={{a,b},{c},{d}}
F:A -> A/R, F(x) = [x]
F(a) = {a,b},
F(b) = {a,b},
F(c) = {c},
F(d) = {d},
函数合成 fOg:A -> C; fOg(x) = f(g(x))
第十四课
反函数 f: A -> B f^-1: B -> A 是其反函数。
构造双射, 这个对应 mit 当中的 counting。这个很适合用来证明 countable and uncountable
19:00 单边逆,左逆, 右逆。
21:00 使用集合论定义自然数。
封闭性, A 在 F 函数下封闭,F(A) 属于 A , F: A -> A <=> F 是一元运算
例如: f: N -> N , f(x) = x+1
对于偶数不封闭, 对于 {2,3,4…} 封闭。
使用三元组定义自然数 <M,F,e> , F: M -> M ; Peano 系统
- e 属于 M( e for element)
- M 在 F 下封闭
- e 不属于 ranF
- F 是单射 injection
- A 属于 M ^ e 属于 A ^ A 在 F 下封闭 => A = M 极小性公理。
第五条: 如果 A 是 M 的子集, e 也属于 A, 并且 A 也在 F 下封闭, 那么 A 就是 M。
保证 M 是最小的, 或者说只有一个 M。
上面提出需求, 如何使用集合来实现上面的 peano 系统 ?
35:00 提到后继, A+ = A U {A} , 拥有 A 属于 A+, 并且 A 是 A+ 的子集
37:00 归纳集,空属于 A, 所有的 x, x 属于 A ,则 x+ 属于 A
A 是归纳集,A 含有空,且对后继封闭。
自然数是什么呢: 属于于每个归纳集的集合。 自然数集: 是包含于每个归纳集的集合.
问,所以自然数是有归纳集所拥有的性质吗?
所以,自然数的各种运算方式, 可以转换成集合的运算。
D = {v | v 是归纳集}
D 不是集合, 否则导致悖论!
D 是类
自然数集 N = 广义交 D
N 是归纳集需要被证明
第十五课
5:00 证明 N 是归纳集
后继函数: 西格玛: N -> N, ForA n 属于 N,西格玛(n) = n+
自然数的定义是: <N, 西格玛, 0> 是 Peano 系统
28:00 传递集: 广义并属于其本身, 与之相对应的是归纳集。
42:00 开始用基本内容定义自然数的各种基本定律,或者说运算。
第十六课
基数
无穷集合如何比较大小?
A 与 B 等势。A 与 B 无穷集形成双射。
(0,1) 与 R 可以构造 bijection。
(0,1) 与 [0,1] 也可以构造双射。
hilbert 旅馆
6:40 讲如何让 0,1 开/闭区间建立一一映射。很有趣,值得一看。
x = 0, 对应 1/2
x = n, 对应 1/(n+2)
其他一一对应。
等势关系是一个等价关系。
12:00 N 与 R 不能等势
A 与 P(A) 不能等势。
28: 00 康托定理的证明
证明不可等势的一些方式方法。 uncountable 的一些方式方法。
对角化证明
公元前5世纪: 这句话是假的,悖论
公元13世纪: 我是说谎者。
1874: cantor 实数不可数。
1901: 罗素悖论 , 不以自身作为元素的集合的全体。
1931: 哥德尔不完全定理, 这句话没有证明。
哥德尔想表达的是,不是所有的东西都是有证明的。
1936: 图灵 停机问题是不可判定的。p np
任何东西都是一个字符串在计算机当中。所以计算机程序可以和自然数建立双射。
所以,实数比自然数多,所以存在一些 np 问题。
可能判定一个程序是否有 bug。也是使用对角线法证明。
对于所有的输入,形成矩阵,因为输入是无穷的,所以也就是一个无穷的矩阵。 这个时候,沿着对角线取反,形成新的输入,这个输入与任何的输入都不同, 所以输入是不可数的, 也就是说,停机问题不可解决。
证明了通用机的存在性。
第十七课
基数的定义
card A = card B, <=> A 与 B 可以建立双射。
有穷集 A card A = n <=> A 与 n 可以建立双射。
N card N = 阿列夫
实数集R, card R= 阿利夫1 = 阿列夫
0, 1, 2 … 阿列夫0, 阿利夫 都称作基数。
B 比 A 优势 <=> A 比 B 劣势 <=> 存在 f:A -> B 单射。
绝对优势, 绝对劣势。
第十八课
基数运算的定义。
10: 00 基数运算的一些性质。
17:00 连续统假设 CH
19:00 ZF系统
20:00 ZFC 系统
选择公理的等价形式。
25:00 well ordering principle 良序
序数
38:00 3n+1 猜想。
图论
第十九课
无序积,对应的概念是笛卡尔集(卡氏积)
(a,b)
A & B = {{a,b} | x 属于 A ^ y 属于 B }
(a,b) = (b,a)
使用无序积, 可以定义无向图。
G = <V,E> (Graph)
V != null, 顶点集
E 是 V & V 的子集。
有向边,形成有向边。
V !=- null.
D =- <V,E>
E 是 V x V 的子集。
顶点集 V(), 边集E()
V(G) = V, E(G) = E
V(D) = V, E(D) = E
有几个顶点,就是几阶。
有限,就是有限图。
没有边的图, 是零图。Nn (null graph)
一阶零图(平凡图),二阶零图 … n 阶零图
空图代表 V = null, E = null
标定图:各个 V 都有标记。可用于计数。
对应的概念就是非标定图。
基图(低图)由有向图去掉方向得出。
相邻: 有边连接的两个顶点。有公共顶点的两条边。
有向图中,邻接与,邻接到。
关联,以及关联次数。无向图中,两个邻接的顶点,两个顶点的关联次数都是1.
环的关联次数是2.
有向图,出是+1, 入是 -1。
环,只与一个顶点关联的边。
孤立点: 不与任何点产生关联的顶点。
平行边,端点相同的两条无向边,是平行边。
起点与终点相同的两条有向边,是平行边。
邻域,Ng(V) ,就是与 V 相邻的所有的其他的顶点。
闭邻域。 Ng[V]. 与 V 相邻的所有顶点,包括 V 本身。
– 相邻表示同类元素之间的关系,关联表示不同元素之间的关系。
关联集: Ig(V) = {e | e 与 V 关联} |
前驱与后继。和链表类似。
顶点的度: 与顶点 v 关联的边的数量. d()
出度, 入度。
有向图的度,是入度与出度之和。
最大度,就是图里面 V 最大的度。
最大出度,最大入度。最小度。
27:00 图论的基本定理: 握手定理
G=<V,E> 是无向图。
V = {v1,v2,v3…,vn}, |E|=m
则 d(v1) + d(v2) + d(v3) + … + d(vn) = 2m.
对于有向图, 则 d(v1) + d(v2) + d(v3) + … + d(vn) = m.
可以推断出: 奇数度的顶点的个数,一定是偶数
简单图(simple graph): 既没有环也没有平行边的图。
度数列: 不同顶点的度的数列。
可图化的: 非负整数度数列,如果度数列能够被表示出图,则度数列可图化。
可简单图化:
推断的第一种方法:
d1 + d2 + d3 + … + dn = 0(mod2)
n-1 >= d1 >= d2 >= … >= dn >= 0 可简单图化 <=>
d’ = (d2-1, d3-1 … , dd1+1-1, dd1+2, …, dn) 可简单图化。
重复递推到平凡情况,得出是否可简单图化。
第二种方法:
d1 + d2 + d3 … + dn = 0(mod2)
并且对 r = 1,2,…,n-1 有
d1+d2+d3+…+dr <= r(r-1) + min{r,dr+2} + … + min{r, dn}.
介绍埃尔特希。
第二十课
图同构: 两个图能够完全重合。形式上讲,顶点可以双射。
~
=
当G1 的两个顶点存在边,那么对应的顶点也有存在边。
如何判定图同构?
NAUTY 算法。
提到零知识证明。
有向图同构。
17:00 图族
完全图, 有向完全图, 竞赛图
柏拉图图,彼得森图,库拉图斯基图
r 部图,二部图(偶图), 完全 r 部图
路径,圈,轮,超立方体
简单图中,边达到最大,则称之为完全图。
有向完全图,边数是无向的两倍。
无向完全图,给每个边添加上方向,形成竞赛图, 可以用来表达竞赛结果。
柏拉图图: 五种正多面体。
- 正四面体
- 正六面体
- 正八面体
- 正十二面体
- 正二十面体
彼得森图: 中间一个五角星,外面套一个五边形。
库拉图斯基图(判定图是否能够被画成平面图):
- 完全 2 部图 K3,3。
- 完全图。
r 部图:
顶点集合可以分为 r 个部分, 每个部分的顶点不能相连。
2 部图:
偶图。
完全 r 部图
路径, paths, P1, 下标指代边数。
圈 , cycles , 就是有环路。
轮,wheel 在圈当中多一些轴心。有几个轴就是 W 几
超立方体。两个正方形,形成立方体,两个立方体,内外又可以嵌套。
子图。
G’ 是 G 的子图,就是
V’ 是 V 的子集, E’ 是 E 的子集。
真子图, 生成子图(顶点集和原图一样)。
导出子图,取出一部分的顶点,然后把这些顶点相关的边留下来。
补图: 完全图,拿掉简单图, 就形成了部图。
自补图: 图与其部图同构,则为自补图。
画图,可以先求度数列,然后根据度数列再画图。
图的运算:
- 删除,收缩,加新边,不交。
- 并图,交图,差图,环和。
- 联图,积图。
删除,删除边直接删除,删除顶点需要同时删除其相关的边。
搜索,删除一个边后,两个相连的顶点合并。
加新边
两个图没有公共顶点,图不相交。
联图(join)不交无向图。
就是将两个图连起来。
积图(product)
第二十一课
图的连通性。
通路 walk, 起点,终点,通路长度。
顶点与边的交替序列, 是 walk。
回路。 closed walk, start v = end v.
simple walk: no repeat path.
element walk 初级通路 .没有重复顶点的通路。
element 初级回路。 没有重复顶点的回路。
可以用顶点序列表示通路(walk)。
G 是含圈的图。周长,最长圈的长度,就是图的周长。无圈的,周长要么为零,要么为无穷大。
最短圈的长度是围长。
在 n 阶图G中,若从不同顶点 vi 到 vj 有通路,则最多 n-1 条边。
极大路径法。
在无向简单图中,路径的两个端点不与路径本身以外的顶点相邻,这样的路径称之为极大路径。
扩大路径法。任何一条路径,只要不是,则至少有一个端点可以更大。
扩大路径法证明,如果每个顶点的度>=2. 则存在长度 >= 最小度数 + 1 的圈。
- 联通 无向图, u v 之间有通路, 联通关系是等价关系。
- 联通分支, 联通图的等价类。
- 联通分支数, 等价类的个数。
- 联通图, p(G) = 1. 就是联通图。
- 短程线(测底线), u, v 之间最短距离。
- 距离(短程线的长度), 两个点之间的通路长度。
- 顶点之间的最大距离, 直径。两个点之间的最大距离。
距离函数:
满足两个点距离非负, 两个点对称, d(u,v) + d(v,w) >= d(u,w).
任何函数满足以上性质,那么就是一个距离函数。
G 是一个二部图 <=> G 中无奇圈。
证明: 使用染色法
二部图在资源分配是一个基本模型。
有一些对象,如何分配一些资源。
无向图是联通的, 则 G 的边数 m > n-1
图的联通度。
- 如何定量的比较连通性?
中央控制机构的连通性最差。
提到点连通度: 为了破坏连通性,至少需要删除多少个顶点?
边连通度: 至少要删除多少条边?
破坏连通性是什么?
– 联通分支数增加。
点割集, 最小的破坏连通性的集合。
一个点构成的点割集,就是割点。
边割集。
第二十二课
扇形割集。
割边,桥
扇形割集。
点连通度。最小的点割集的数量。
边连通度。同理。
k 连通图。至少要删除 k 个顶点,才能破坏连通性。
k 边连通图。
彼得森图是: 1/2/3-连通图。
但是不是 4 连通图。
1/2/3 边连通图。
边不交路径(edge-disjoint)路径。
K边连通的充分必要条件。
3阶以上的无向图 G 是 k 连通图,当且仅当 G 中 任意 2 低昂定剑佑 k 条以上独立路径。
block 块:极大无割点连通子图。
块的充分必要条件。
可达, reachable: 有向图某两个当中存在通路。
双向可达, 有向图某两个存在双向的通路。
单向连通。
竞赛图一定有初级通路(路径)过每个顶点,恰好一次。可用来排序。
强连通(双向连通),任何一对顶点双向可达。
单向连通,有向图 D 中有通路至少经过每个顶点一次。
强连通分支。单向连通分支,弱连通分支。
第二十三课
欧拉图与哈密顿图
欧拉图: 走过所有边一次,并且恰好一次。
欧拉被称之为有史以来最多产的科学家。
1736 年, 7桥问题,图论与拓扑学诞生。
每一个顶点的度都是偶数度,7 桥问题就被解决了。
经过图中所有的边的简单通路,就被称之为欧拉通路。
有欧拉通路的图,就是半欧拉图
经过图中搜有边的简单回路,就是欧拉回路。
有欧拉回路的图,就是欧拉图。
若欧拉回路总共 k 次经过顶点 v, 则 d(v)= 2k.
无向欧拉图的充要条件:
G是无向连通图,G 是欧拉图 <=> G 中所有的顶点都是偶数度。 <=> G 是若干个边不交的圈的并。
无向半欧拉图的充要条件:
G 中桥好有 2 个奇数度顶点。
有向欧拉图的充要条件:
有向半欧拉图的充要条件:
25:00 Fleury 算法(避桥法)可以得到欧拉回路。
欧拉回路的应用之一: 轮盘设计
41:00 哈密顿图: 走过顶点,并且恰好一次。
哈密顿通路: 经过图中所有顶点的初级通路。
有哈密顿通路的图,就是半哈密顿图
哈密顿回路: 经过所有顶点的回路。
有哈密顿回路的图。
目前没有简单判断是否为哈密顿图的算法。
目前没有充分必要条件。
必要条件:
p(G-V1) <= |v1|
半哈密顿图的必要条件
p(G-V1) <= |v1| + 1
有向哈密顿图充要条件。
有向半哈密顿充要条件。
二十四课 树
代数结构
第三十五课
现代数学的特点
结构与分析
学科的交叉: 运筹学与管理学,离散数学与计算机科学
确定性与非确定性的交叉: 离散概率
CS: computer Science IS: Information System CE: Computer Engineering SE: Software Engineering
研究离散个体以及其结构。
数理逻辑主要研究推理,以及逻辑, 形式化证明。
集合论,主要是表示方法。
组合数学, 是离散结构的存在性。如何计数?如何枚举?如何优化?
28:00 离散数学的知识架构图。
数理逻辑: 人工智能,程序正确性证明及验证。
集合论: 关系数据库模型
图论: 数据结构,数据库模型,网络模型。
代数结构: 软件规约,形式化语义,编译系统,编码理论,密码学,数据仓库
组合数学: 算法设计与分析,编码理论,容错。
30:00 汉诺塔问题。指数爆炸。涉及到组合数学问题。
数据仓库的视图格: OLAP 联机分析处理。如何组织视图,才能够让查询足够快?
每一个聚类就是一个划分,多个维度,再进行笛卡尔积。再形成一个格结构。
引出格的结构。
进程的资源共享模型。命题的迁移,与图有关。
第三十六课
代数系统的基本概念 – 8 学时
- 二元运算的性质
- 代数系统的构成
- 子代数与积代数
- 代数系统的同态与同构
- 代数系统上的同余关系与商代数
半群,独异点与群 – 12 学时
- 半群与独异点的定义与性质
- 群的定义与分类
- 群的基本性质
- 子群
- 循环群
- 变换群
- 置换群
- 群的分解(陪集分解与 Lagrange 定理,共轭类分解与分类方程)
- 正规子群
- 商群及性质
- 群的同态与同构
- 群的直积
环与域
- 环的定义及基本性质
- 特殊的环
- 子环
- 理想
- 商环及环同态 格与布尔代数
- 格的定义与性质
- 子格
- 格同态与格的直积
- 特殊的格
- 布尔代数
代数结构的组成
- 载体
- 运算
- 公理
在以上的基础上,如何构成新的东西。 由已知的代数系统构成新的代数系统。
- 子集: 子代数
- 不同的代数系统进行笛卡尔积: 积代数
- 等价关系: 商代数
通过映射,可以映射到另外一个代数系统。
那么代数系统就是同构的。
通过同态,同构,可以把一些些系统理解为同样的系统。
比如说线性代数系统和自然数可以理解为同构的
对代数系统的典型应用系统研究:
- 半群与群,包含一个运算 只有一个二元运算
- 环域, 包含两个运算
- 格与布尔代数
进一步可以推广至 西格玛代数: 理解下来感觉就是不封闭的。
二元运算以及性质
f:AxA -> A 称之为为 A的二元运算。
0元, 就是选择一个元素。
1元, 针对一个元素的操作, 比如说取反。
2元, 乘法,加法等。
算律
和一个运算相关的
- 交换律
- 幂等律
- 结合律
- 消去律
和两个及多个元素有关
- 分配律
- 吸收率
特异元素
- 单位元
- 零元
- 可逆元素
第三十七课
二元运算的性质体现为两类
- 算律
- 特异元素
幂等律: a o a = a
特异元素
特异元素名称:
- 单位元 幺元,e ( eoa = a0e = a, 比如说自然数当中的 + 和 0 )
- 零元 0 ( aoa = a00 = 0 , 比如说 0 和 x )
- 幂等元 (aoa = a ,乘法有两个幂等元, 0,1)
- 可逆元和逆元 (存在单位元的系统, xoy = yoa = e )
打个比方: 加法当中, 单位元是0,没有零元,幂等元也是0,逆元就是正数与负数。
乘法当中,单位元是 1, 零元是 0, 幂等元是 1,0. 逆元就是自然数及其倒数。
特异元素有时候也可以作为算律
- 同一律(存在单位元)
- 零律(存在零元)
单位元与零元在整个系统当中具有唯一性。
若存在逆元,针对元素其唯一。
第三十八课
形式化的记法: V = < A, 欧米茄, K >
A: 载体, 比如说集合。
欧米茄: 运算集,非空
K: 代数常数集
V = < A, 欧米茄 >
从高元到低元进行列举
V = < A, o1, o2, o3, … on >
例子
- < Z, +, * >
- < Zn, mod+,mod * > …
同类型的: 构成成分相同。
同种的: 构成成分与公理都相同。
22:00
子代数
B 是某代数系统的非空子集。 若 B 对于 A 中所有的运算封闭, 则 B 是 A 的子代数。
子代数与原系统是同种的系统。
子代数一定存在。
29:00 积代数
两个代数系统, 做笛卡尔积。
运算相当于对与对的运算。