1.1.2　代数系统

代数学研究的主要对象是代数系统,简称代数,即非空集合及定义在上的若干运算. 其中的运算可以是一元运算,也可以是二元运算. 通常将代数记为,在不会产生混淆的情况下可将代数系统简记为. 代数学对各种代数系统研究定义在上各种运算的性质以及由这些运算及其性质所决定的集合的逻辑结构.

例1.5　设表示字符集,表示由中字符组成的有限长度的字符串全体 (含空字符串构成的集合.,定义为与连接而成的字符串,则构成一个代数系统, 该代数系统是信息技术中最重要的处理对象之一.

例1.6　考虑比特集[2],练习1.1、例1.3及练习1.2,在上定义的3个运 算分别为

---

[2]　中的元素0和1可视为比特位,也可视为逻辑假 (False) 和逻辑真 (True).

代数系统即为著名的布尔代数. 其中和是二元运算,分别称为或和与运算. コ为一元运算, 称为非运算. 布尔代数的运算有如下性质.

(1) 或运算交换律:.

(2) 或运算结合律:.

(3)或运算0-元律:.

(4) 与运算交换律:.

(5) 与运算结合律:.

(6)与运算1-元律:.

(7) 与运算对或运算的分配律:.

(8) 或运算对与运算的分配律:.

(9) 反演律:.

布尔代数是数理逻辑乃至电子计算机技术的基础数学模型. 其中各运算的所有性质均可用 “真值表” 加以验证. 以证明性质 (9) 中反演律之一的为例,说明如下:

注意,真值表中的前两列罗列出了的所有可能的取值,而最后两列分别表示和在的所有可能的取值下均相等,故.

练习1.3　运用真值表,验证布尔代数中的反演律. (提示: 参考对的证明)

我们知道,代数系统中定义在集合上的各个运算必须是 “封闭” 的,即运算结果必须仍属于集合.

例1.7　设,整数加法并非定义在上的运算,因为虽然,但. 同样地,也不属于. 换句话说,中元素对整数加法运算不是封闭的. 所以并不能够成为一个代数系统.

若将上的 “加法” 定义为:,

即的运算结果是除以4的余数——称为模4的加法. 此时,,因此 “+” 对是封闭的,于是,构成一个模4的剩余类加法系统 (详见例1.10).