离散数学 半群和独异点PPT课件.pptx

离散数学 半群和独异点PPT课件 半群和独异点是离散数学中重要的概念，它们广泛应用于计算机科学、信息安全、密码学等领域。半群是指满足结合律和封闭性的代数结构，而独异点则是半群的一个特殊类型，具有单位元和逆元。 定义3：如果〈S, *〉是半群，T ⊆S且关于运算*封闭，那么〈T, *〉是〈S, *〉的子代数，称〈T, *〉为〈S, *〉的子半群。 定理1：子半群是半群。证明：子半群是子代数，关于运算*封闭，结合律是继承的，所以是半群。 定义4：如果〈S, *, 1〉是独异点，T ⊆S且关于运算*封闭，1∈T，那么〈T, *, 1〉是〈S, *, 1〉的子代数，称〈T, *, 1〉是〈S, *, 1〉的子独异点。 定理2：子独异点是独异点。证明：子独异点是子代数，关于运算*封闭，含有么元，结合律是继承的，所以是独异点。 半群和独异点的关系是：独异点一定是半群，但半群不一定是独异点。但是，半群可以通过添加新元素变为独异点，如半群〈[0, 1), *〉添加么元1可变为独异点〈[0, 1], *, 1〉。 定理3：独异点〈S, *〉中，运算*的运算表没有两行和两列是相同的。证明：设S是有限集{e, a1, a2…an}，对任何ai, aj∈S，若ai≠aj则e * ai ≠e * aj，所以任意两列都不相同。又因为ai * e ≠aj * e，所以任意两行都不相同。 定义5：在半群（独异点）中，如果运算是可交换的，则称此半群（独异点）为可交换半群（可交换独异点）。 定理4：在任何可交换独异点〈S, *, e〉中，S的等幂元素集合T可以构成子独异点。证明:i）任取x, y∈T，则x * y=(x*x)*(y*y)=x*(x*y)*y=(x*y)*(x*y)，所以x*y∈T，故运算封闭；ii）T是S的子集，*在T上可结合；iii）e*e=e，e是等幂元素，所以e∈T。故〈T, *, e〉是子独异点。本定理对可交换半群也成立。 下面我们定义独异点〈S, *, e〉中任意元素a的幂。用归纳定义：(1)（基础）a0 = e；(2)（归纳）an+1 = an * a（n∈N）。由于独异点中，运算*是可结合的，容易证明如此定义的a的幂满足以下指数定律： 定义6：在独异点〈S, *, e〉中，如果存在一个元素g∈S，使每一元素a∈S，都有一个相应的h∈N能把a写成gh，即a=gh，则称此独异点为循环独异点。并称元素g是此循环独异点的生成元，又可说此循环独异点是由g生成的。 例3：① 〈N,+,0〉是循环独异点，生成元是1，因为任取i∈N，当i=0时，0=10；i≠0时，有i=1i。② 〈a, b, c,+,0〉是循环独异点，生成元为b,c；1=b0,a=b2,b=b1,c=b3；1=c0,a=c2,b=c3,c=c1。 定理5：每个循环独异点都是可交换的。证明：设〈S, *, e〉是循环独异点，其生成元是g，对任意a、b∈S，存在m、n∈N，使a=gm和b=gn，因此a*b=g^m*g^n=g^(m+n)=g^n*g^m=b*a。证毕。 半群和独异点是离散数学中重要的概念，它们广泛应用于计算机科学、信息安全、密码学等领域。了解半群和独异点的性质和定义对理解和应用这些概念非常重要。