离散数学 课件 chapter 12 其他代数系统.pptx

12 其他代数系统 主要内容12.1 环12.2 域12.3 格12.4 布尔代数 12.1 环 设A,+,*是一个代数系统，如果满足： （1）A,+是阿贝尔群； （2）A,*是半群； （3）“*”对“+”满足分配律；则称A,+,*是环（ring）。 如果运算“*”满足交换律，则称A,+,*为可交换环；如果A,*是独异点，称A,+,*为含幺环或单元环。 12.1 环 在环A,+,*中，第一个运算通常称为“加法运算”，第二个运算通常称为“乘法运算”，A,+的单位元通常用“0”表示，元素的逆元用“-a”表示；如果A,*也有单位元，通常用“1”表示，这与环Z,+,?中的相关概念是一致的。 12.1 环 环A,+,*中，对加法运算的单位元一定是对乘法运算的零元。 环A,+,*中，A,*不可能是群。??? 12.1 环 环A,+,*中，对任意a,b?A，有??????? 12.1 环 环A,+,*中，如果存在非0元素a,b?A，满足a*b=0，则称环A,+,*中有零因子。环A,+,*中不含零因子等价于运算*满足消去律。?aa?环A,+,*中不含零因子? 12.1 环 给定环A,+,*，R?A，如果R,+,*也是环，则R,+,*称为A,+,*的子环。 代数系统R,+,*称为A,+,*的子环，当且仅当?a?R，有a-1?R。R,+,*是环R,+是阿贝尔群R,*是半群*对+满足交换律??R,+是群+满足交换律单位元逆 元 12.1 环 给定环A,+,*，如果其中存在关于运算*的单位元，并且该运算满足交换律，同时无零因子，则A,+,*为整环。Z,+,?， R,+,?都是整环。 12.2 域 设A,+,*是一个代数系统，如果满足如下条件： （1）A,+是一个阿贝尔群； （2）A-{0},*是一个阿贝尔群； （3）运算“*”对运算“+”满足分配律。则称A,+,*是域（field）。域是整环。域阿贝尔群消去律不含零因子 12.2 域?整环不含零因子消去律??????? 12.3 格 设L是一个非空集合，“*”和“?”是上的两个二元运算，如果对任意a,b,c?L，有如下结论：（1）交换律：a*b=b*a，a?b=b?a：（2）结合律：(a*b)*c=a*(b*c)，(a?b) ?c=a?(b?c)（3）吸收律：a*(a?b)=a，a?(a*b)=a则称代数系统L,*,?是格（lattice），或称代数格。 12.3 格 （1）给定集合S，集合的交集运算“?”和并集运算“?”在该集合的幂集P(S)上满足交换律、结合律和吸收律，因此，P(S)，?，?构成了一个格。 （2）给定正整数集合Z+，定义两个二元运算GCD(a,b)和LCM(a,b)分别代表元素a和b的最大公约数和最小公倍数，因此，Z+,GCD,LCM也构成了一个格。 12.3 格 格满足幂等律。即a?L，有?? 12.3 格 设代数系统L,*,?是一个格，S?L，如果集合S非空且S,*,?是一个代数系统，则S,*,?是L,*,?的子格。 格的对偶式 设L,*,?是格，在该格中的任一公式F中，分别用“*”运算代替“?”运算，用“?”运算代替“*”运算，所得到的公式称为原公式的对偶式，记为FD。 （对偶定理）F是格L,*,?中的公式，如果F成立，则F的对偶式FD必定成立。 12.3 格 设L, ≤是偏序集，如果对任意的a,b?L，{a,b}都有最大下界和最小上界存在，则称L, ≤是偏序格。 12.3 格 给定一个代数格L,?,?，可以构造一个与它等价的偏序格L,≤，其中偏序关系“≤”如下定义：a≤b当且仅当a ? b=a成立证明L,≤是偏序格。L,≤是偏序集（自反性、反对称性、传递性）；L,≤中任意两元素存在最大下界和最小上界； 12.3 格代数格L,?,?，a≤b当且仅当a ? b=a??? 12.3 格代数格L,?,?，a≤b当且仅当a ? b=a????下 界?最大下界 12.3 格代数格L,?,?，a≤b当且仅当a ? b=a???????上 界?最小上界 12.3 格则称L,?,?是分配格（distributive lattice）。设L,?,?是格，如果对任意的a,b,c?L，都有下式成立： 设L,?,?是格，如果存在元素0,1?L，使对任意元素a?L，有：则称L,?,?是有界格（bounded lattice） 。 12.3 格