《数理逻辑》第七章-3.pdf

马琦 2010.12.4 maqi08@ 半群半群 半群半群 代数 逻辑 集合S ，其上有二元运算• ： S×S→S 。若•满足结合律结合律，即 结合律结合律 ∀∀x,y,z ∈S ，有 字问题 (x • y) • z=x •(y • z) 则称有序对(S, •) 为半群半群，运 群 半群半群 算•称为该半群的乘法乘法。实际 乘法乘法 半群 使用中，在上下文明确的情况 可换群 下，可以简略叙述为“半群S” 。 A={a ,…,a } 字 毗连运算 1 k • 形式符号的 • 字母表的有 • 第一个字后 集合 （字母 穷符号串 添上第二个 表） 字的复合字 字母表 毗连运算 半群 S A 规定a a 和a a 是恒等恒等的，若P和Q是字， 1 2 2 1 恒等恒等 生成元 关系 则Pa a Q~Pa a Q且Pa a Q~Pa a Q 。 1 2 2 1 2 1 1 2 a ,…,a a a =a a 1 k 1 2 2 1 定义定义SS 上的上的等价关系等价关系等价关系等价关系：：对任意字对任意字UU和和VV ，， AA 等价关系等价关系等价关系等价关系 U 等价于V ，若存在字的序列W ,…,W ，