1.1　代数

1.1.1　集合与映射

将所研究问题涉及的诸对象视为一个整体，称为 集合 ，常用大写字母 表示. 常见的由数组成的集合有自然数集、整数集、有理数集、实数集和复数集，分别记为 、 、 、 和 . 组成集合的每一个对象，称为该集合的一个 元素 ，常用小写字母 表示. 若 是集合 中的元素，则记为 ，否则记为 . 例如， 但 ， 但 . 若集合 中的元素均为集合 中的元素，即 ，必有 ，称 是 的 子集 ，记为 . 例如， .

无任何元素的集合称为 空集 ，记为 . 如果非空集合 中的元素可一一罗列出来，则可用花括号把这些罗列出来的元素括起来. 例如，不超过 5 的正整数组成的集合 . 也可以用描述的方式表示一个具体的集合，例如，不超过 5 的正整数组成的集合可表示为 .

常将集合直观地表示为平面上的封闭区域，集合中的元素为区域内的点，子集的图示如图 1.1 所示.

实践中所面对的问题往往涉及两个甚至更多的集合. 集合的元素之间，通常具有某种关系.

定义1.1 设 为两个非空集合，若按确定的法则 与之对应 ^[1] ，记为 ，则称 为 到 的一个 映射 （或 变换 ），记为 . 若 ，即 ，则称 为 上的映射.

若 ，称 是 的 像 ， 是 的 原像 . 中元素 的像，常记为 .

例1.1 有限集合（元素个数有限）间的映射，可以列表表示. 设 ，定义 到 的对应法则 :

就是 中元素对应相反数的映射.

练习1.1 设 ，即比特集，其中的元素 0 和 1 是二进制数. 用列表方式表示比特集 上的映射 .

（参考答案： ）

非空集合 的元素之间的对应法则 要成为 到 的映射，需满足如下两个条件.

（1） 中每个元素 均有在 中的像 .

（2） 中任一元素 在 中只有一个像 .

图 1.2（a）表示 到 的映射；图 1.2（b）中由于 中存在元素在 中无像，故对应法则不是 到 的映射；图 1.2（c）中由于 中存在元素对应 中的两个元素，故对应法则也不是 到 的映射.

例1.2 设 ，考虑函数 ，不难理解它们均为 上的映射. 然而，函数 [见图1.3（a）]是 上“1-1”的映射，即一个原像 仅对应一个像 . 反之，任一 也仅有一个原像 . 这样的映射是 可逆 的，因为据此对应法则，我们可以得到逆映射（即反函数） . 但是函数 [见图1.3（b）]却不是可逆的. 这是因为，首先对于 且 ，在 中没有与之对应的原像. 其次，对于 且 中有两个原像 和 与之对应. 换句话说，根据映射 的对应法则，不能构造出其逆映射.

以上讨论的集合 到 的映射，原像均为取自集合 的一个元素，这样的映射称为一元映射. 实践中，集合 的结构也许要稍稍复杂一些.

定义1.2 设集合 和 非空，有序二元组集合 称为 与 的 笛卡儿积 ，记为 .

在代数学中，非空集合 上的映射称为 一元运算 ， 到 的映射称为 上的 二元运算 . 常用运算符来表示运算，如例 1.1 中，集合 上的取相反数的映射 即负数运算，这是一个一元运算，其运算符常表示为“-”. ，对应 . 练习1.1 中的 上的一元映射即对比特位（二进制位）的取反运算，这也是一个一元运算，其运算符常表示为“ ”. ，对应 . 利用练习1.1 的计算结果得比特集 上的取反运算表为

例1.3 考虑比特集 上的“或”运算“V”： 当且仅当 时成立. 根据 运算的这一定义，可得其运算表：

练习1.2 比特集 上的“与”运算“ ”： 当且仅当 时成立. 试给出 的运算表.

（参考答案： ）

例1.4 自然数集 上的加法运算就是 到 的二元映射. 但是，减法运算不是 上的二元运算，因为对于 ，且 . 换句话说，对于 ，若 则 ，即 在 中没有像.

集合 上的运算结果必须属于集合 的要求，称为运算对集合 的 封闭性 . 不难验证，数的加法和乘法运算对 、 、 、 和 都是封闭的. 例 1.4 说明数的减法运算对 不具有封闭性，但对 、 、 和 都是封闭的. 数的除法运算对 和 不具有封闭性，但对 和 都是封闭的.

将 到 的映射 ，视为二元运算“ ”： . 这时，需注意一个细节：一般而言， 是一个序偶，由于 与 未必相同，故 ，但未必有 . 即使 ，但 未必与 相同. 例如， . 不全为零，则 . 对于一个二元运算“o”： 及 ， ，则称该运算具有 交换律 . 例如，数的加法运算“+”，在数集 、 、 、 和 上都具有交换律.

1.1.2　代数系统

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

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

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

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

（1）或运算交换律： .

（2）或运算结合律： .

（3）或运算 0-元律： .

（4）与运算交换律： .

（5）与运算结合律： .

（6）与运算 1-元律： .

（7）与运算对或运算的分配律： .

（8）或运算对与运算的分配律： .

（9）反演律： .

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

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

练习1.3 运用真值表，验证布尔代数 中的反演律 . （提示：参考对 的证明）

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

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

若将 上的“加法”定义为： ，

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

---

[1] 数理逻辑中，存在量词 表示“至少存在一个……”. 本书用 表示“恰存在一个……”.

[2] 中的元素 0 和 1 可视为比特位，也可视为逻辑假（False）和逻辑真（True）. f3ur8nwIMql3uCkMlv3J9gQ/mtOlKr+8gHM0CV/OhRZhCZRihV5L9468/cI5jzsT