閩有京大赞 NANJING UNIVERSITY 离散数学 Discrete Mathematics 第十三讲：代数系统引论 南京大学计算机科学与技术系 2018年5月
2018 年 5 月 第十三讲：代数系统引论 离 散 数 学 Discrete Mathematics 南京大学计算机科学与技术系
&易 前情提要 ·偏序关系 ■偏序集与哈斯图 ■偏序集中的特殊元素 ■特殊元素的性质 ·偏序格 前情提要 2
前 情 提 要 前 情 提 要 2 偏序关系 偏序集与哈斯图 偏序集中的特殊元素 特殊元素的性质 偏序格
本讲主要内容 运算及其封闭性 运算的性质 ALGEBRA元DALDOR 运算表 代数系统 代数系统的性质 0 结合性、交换性、分配性 。单位元、零元、逆元 代数系统的同构与同态 本讲主要内容 3
本讲主要内容 本讲主要内容 运算及其封闭性 运算的性质 运算表 代数系统 代数系统的性质 结合性、交换性、分配性 单位元、零元、逆元 代数系统的同构与同态 3
&原 Abū‘Abdallah Muhammad ibn Musa al-Khwarizmi(B.C.780-8502 Arab mathematician,born in Khwarizm(now in Uzbekstan).His works on algebra,arithmetic,and astronomical tables greatly advanced mathematical thought,and he was the first to use for mathematical purposes the expression al jabr,from which the English word algebra is derived.The Latin version of his treatise on algebra was responsible for much of the mathematical knowledge of medieval Europe.His work on algorithm,a term derived from his name,introduced the method of calculating by MMe use of Arabic numerals and decimal notation. -from Funk Wagnalls:New Encyclopedia 实际上，al jabr一词出自他的著名的书“Kitab al jabr w'al-mugabala" (《复原和化简的规则》)的标题，这个词在阿拉伯语中意思相当于“reunite'。 而中文“代数”一词作为学科名，首先出现于在华的英国人维列利于 1853年为介绍西方数学而写的《数学启蒙》(1853)，此时距离A-Khwarizmi 那本书的出版已经超过一千年了。几年后，维列利与中国学者李善兰合作， 先后将欧几里德《几何原本》后9卷以及德摩根的代数学翻译成中文。 引子 4
Abū ʿAbdallāh Muḥammad ibn Mūsā al-Khwārizmī (B.C. 780 – 850 ?) 实际上，al jabr 一词出自他的著名的书“Kitab al jabr w’al-muqabala” (《复原和化简的规则》) 的标题, 这个词在阿拉伯语中意思相当于“reunite” 。 而中文“代数”一词作为学科名，首先出现于在华的英国人维列利于 1853年为介绍西方数学而写的《数学启蒙》(1853)，此时距离Al-Khwarizmi 那本书的出版已经超过一千年了。几年后，维列利与中国学者李善兰合作， 先后将欧几里德《几何原本》后9卷以及德∙摩根的代数学翻译成中文。 Arab mathematician, born in Khwarizm(now in Uzbekstan). His works on algebra, arithmetic, and astronomical tables greatly advanced mathematical thought, and he was the first to use for mathematical purposes the expression al jabr, from which the English word algebra is derived. The Latin version of his treatise on algebra was responsible for much of the mathematical knowledge of medieval Europe. His work on algorithm, a term derived from his name, introduced the method of calculating by use of Arabic numerals and decimal notation. —— from Funk & Wagnalls: New Encyclopedia 引 子 4
引子（续) 代数系统一般称为“抽象代数（abstract algebra)”或“近世代数”，20世纪初被 命名，但其研究的主要内容却于19世纪便 已开展 ,代数系统研究的主要内容：有代数结构、 群、环、域、模、向量空间、格、布尔代 数、李代数等等 引子 5
引 子（续） 代数系统一般称为“抽象代数（abstract algebra）”或“近世代数”，20世纪初被 命名，但其研究的主要内容却于19世纪便 已开展 代数系统研究的主要内容：有代数结构、 群、环、域、模、向量空间、格、布尔代 数、李代数等等 引 子 5
运算的函数定义 函数f:An→B称为（从A到B的）n元运算 以下主要讨论二元运算 例如：利用普通四则运算定义实数集上的一 个新运算“*”： X*y=x+y一Xy 则：2*3=-1；0.5*0.7=0.85 有限集合上的m元运算的个数是确定的 运算的定义 6
运算的函数定义 函数𝑓: 𝐴 𝑛 → 𝐵称为(从𝐴到𝐵的) 𝒏元运算 以下主要讨论二元运算 例如：利用普通四则运算定义实数集上的一 个新运算“∗”： 𝒙 ∗ 𝒚 = 𝒙 + 𝒚 − 𝒙𝒚 则：2 ∗ 3 = −1；0.5 ∗ 0.7 = 0.85 有限集合上的𝑚元运算的个数是确定的 运算的定义 6
&易 运算表 通常用于定义有限集合（一般元素很少）上的一 元或二元运算（如在集合{a,b,c,d}上定义如下的运算） a a M b & M 7 运算的定义
运 算 表 通常用于定义有限集合(一般元素很少)上的一 元或二元运算 (如在集合{𝑎, 𝑏, 𝑐, 𝑑}上定义如下的运算∗) * a b c d a 1 M b & 6 K M c 7 6 Q 0 d G # ~ 运算的定义 7
运算的封闭性 对于运算f:An→B,若B≤A,则称该运算在集合 A上封闭(closeness) 例： 加法在自然数集上封闭，但减法在自然数集上不封闭 减法在整数集上封闭，但除法在整数集上不封闭 对集合A={1,2,3,…,10},gcd运算封闭，lcm则否 运算的定义 8
运算的封闭性 对于运算𝑓: 𝐴 𝑛 → 𝐵 ，若𝑩 ⊆ 𝑨，则称该运算在集合 𝐴上封闭（closeness） 例： 加法在自然数集上封闭，但减法在自然数集上不封闭 减法在整数集上封闭，但除法在整数集上不封闭 对集合𝐴 = {1,2,3, ⋯ , 10}，gcd运算封闭，lcm则否 运算的定义 8
&易 证明运算封闭的例子 普通加法在正整数集之子集A={n921n} 上封闭 证明： o设x,y是A中任意元素，存在p,q∈Z+,满足： 21x=9p,21y=9q,则21(x+y)=9(p+q), 由于p+q∈Z+,故921(x+y),即x+y∈A.口 运算的定义 9
证明运算封闭的例子 普通加法在正整数集之子集𝑨 = 𝒏 𝟗|𝟐𝟏𝒏 上封闭 证明： 设𝑥, 𝑦是𝐴中任意元素，存在𝑝, 𝑞 ∈ ℤ +，满足： 21𝑥 = 9𝑝 ，21𝑦 = 9𝑞 ，则21 𝑥 + 𝑦 = 9(𝑝 + 𝑞)， 由于𝑝 + 𝑞 ∈ ℤ +，故9|21(𝑥 + 𝑦)，即𝑥 + 𝑦 ∈ 𝐴. □ 运算的定义 9
代数系统 定义（代数系统) 。给定1个非空集合（其元素可以是任何对象)； 0 给定1个或者若干个运算（以下主要讨论存在1 个二元运算的情况)； 。运算对上述集合封闭. 记法：(S,)》 例子： 。整数集与普通加法：(Z,+)构成代数系统 代数系统 10
代 数 系 统 定义（代数系统）： 给定1个非空集合（其元素可以是任何对象）； 给定1个或者若干个运算（以下主要讨论存在1 个二元运算的情况）； 运算对上述集合封闭. 记法： 𝑺, ∘ 例子： 整数集与普通加法： ℤ, + 构成代数系统 代数系统 10