离散数学课本定义和定理

1、.第1章集合1.1集合的基本概念1. 集合、元（元素） 、有限集、无限集、空集2. 表示集合的方法：列举法、描述法3.定义 （子集 ）：给定集合A 和 B，如果集合A 的任何一个元都是集合B 中的元，则称集合 A 包含于 B 或 B 包含 A，记为或，并称 A 为 B 的一个子集。如果集合 A 和 B 满足，但 B 中有元不属于A，则称集合A 真包含于 B，记为，并且称 A 为 B 的一个真子集。4. 定义（幂集）：给定集合 A，以 A 的所有子集为元构成的一个集合，这个集合称为A 的幂集，记为或1.2 集合的运算定义 1.2.1（并集）：设 A 和 B 是两个集合，则包含 A 和 B 的所有

2、元，但不包含其他元的集合，称为 A和 B 的并集，记为.定义 1.2.2 （交集 ）：A 和 B 是两个集合， 包含 A 和 B 的所有公共元， 但不包含其他元的集合，称为 A 和 B的交集，记为.定义 1.2.3（不相交 ）： A 和 B 是两个集合，如果它们满足，则称集合 A 和 B 是不相交 的。定义 1.2.4（差集 ）：A 和 B 是两个集合，属于 A 而不属于 B 的所有元构成集合，称为A 和 B的差集 ，记为.定义 1.2.5（补集）：若 A 是空间 E 的集合，则 E 中所有不属于A 的元构成的集合称为A 的补集 ，记为.定义（对称差 ）： A 和 B 是两个集合，则定义A 和

3、 B 的对称差为1.3包含排斥原理定理设为有限集，其元素个数分别为，则定理设为有限集，其元素个数分别为，则定理设为有限集，则重要例题P11 例.第 2 章二元关系2.1关系定义 2.1.1（序偶）：若 和 是两个元，将它们按前后顺序排列，记为，则成为一个 序偶 。 对于序偶和，当且仅当并且时，才称和相等，记为定义 2.1.2（有序 元组）：若是个元，将它们按前后顺序排列，记为，则成为一个 有序 元组（简称 元组）。定义 2.1.3（直接积 ）：和是两个集合， 则所有序偶的集合，称为和的 直接积（或笛卡尔积） ，记为.定义 2.1.4（直接积 ）：设是 个集合，则所有元组的集合，称为的笛卡尔积

4、（或直接积），记为.定义 2.1.5（二元关系 ）若 和 是两个集合，则的任何子集都定义了一个二元关系，称为上的二元关系。如果，则称为上的 二元关系 。定义 2.1.5（恒等关系 ）：设 是 上的二元关系，则称是 上的恒等关系。定义 2.1.7（定义域、值域 ）：若 是一个二元关系，则称为 的定义域。为 的值域。定义 2.1.8（自反）：设是集合上的关系，若对于 任何，都有即则称关系是自反的。定义 2.1.9（反自反 ）：设是集合上的关系， 若对于任何，都满足, 即对任何都不成立，则称关系是反自反的。定义 2.1.10 （对称 ）：设是集合上的关系，若对于任何，只要, 就有, 那么称关系是对称

5、的。定义 2.1.11 （反对称 ）：设是集合上的关系，若对于任何，只要并且时 ,就有，那么称关系是对称的。定义2.1.11 （传递 ） 设是集合上的关系，若对于任何，只要并且时，就有，则称关系是传递的。定理 2.1.1设 是集合上的关系，若 是反自反的和传递的，则是反对称的。2.2关系矩阵和关系图定义无定理无2.3关系的运算定义 2.3.1（连接 ）：设为上的关系，为上的关系，则定义关系.称为关系和 的连接 或复合，有时也记为.定义（逆关系 ）：设为上的关系，则定义的逆关系为为上的关系：.定理 2.3.1设和都是上的二元关系，则下列各式成立（1）（ 2）（3）（4）（ 5）定理设为上的关系，

6、为上的关系，则2.4 闭包运算定义 2.4.1（自反闭包 ）： 设 是集合上的二元关系，如果是包含的最小自反关系，则称 是关系的自反闭包，记为.定义 2.4.2 （对称闭包 ）： 设是集合上的二元关系，如果是包含的最小对称关系，则称 是关系的对称闭包，记为.定义 2.4.3 （传递闭包 ）： 设是集合上的二元关系，如果是包含的最小传递关系，则称 是关系的传递闭包，记为或.定理 2.4.1设 是集合 上的二元关系，则（1）是自反的，当且仅当.（2）是对称的，当且仅当.（3）是传递的，当且仅当.定理 2.4.2设 是集合上的二元关系，则.“恒等关系 ”定理 2.4.3设 是集合上的二元关系，则.“

7、逆关系 ”定理 2.4.4设 是集合上的二元关系，则.“幂集”定理 2.4.5设 是一个元集， 是 上的二元关系，则存在一个正整数，使得.2.5等价关系和相容关系定义（ 覆盖、划分）：是一个集合，, 如果，则称.是 的一个覆盖。如果，并且，则称 是的一个划分，中的元称为的划分块。定义 2.5.2（等价关系 ）：设 是 上的一个关系，如果具有自反性、对称性和传递性三个性质，则称是一个等价关系。设是等价关系，若成立，则称等价于 .定义 2.5.3 （等价类 ）：设 是 上的一个等价关系， 则对任何，令，称为 关于的等价类，简称为的等价类，也可以简记为.定义 2.5.4（同余 ）：对于整数和正整数,

8、 有关系式：如果，则称对于模同余的，记作定义 2.5.5（商集）：设 是 上的一个等价关系，由引出的等价类组成的集合称为集合 上由关系 产生的商集，记为.“等价类的集合 ”定理 2.5.1若是上的一个等价关系，则由可以产生唯一的一个对的划分。 “商集 ”定义 2.5.6（相容关系 ）：设 是 上的一个关系，如果是自反的和对称的，则称是一个相容关系。相容关系可以记为.所有的等价关系都是相容关系，但相容关系却不一定是等价关系。定义 2.5.7（最大相容块 ）：设是一个集合，是定义在上的相容关系。如果,中的任何两个元都有关系，而的每一个元都不能和中所有元具有关系，则称是的一个最大相容块。2.6偏序关

9、系定义 2.6.1（偏序关系 ）： 是定义在集合上的一个关系，如果它具有自反性、反对称性和传递性，则称是 上的一个偏序关系，简称为一个偏序，记为. 更一般地讲，若是一个集合，在 上定义了一个偏序，则我们用符号来表示它， 并称是一个偏序集。定义 2.6.2（全序 / 链）：是一个偏序集，对任何，如果或这两者中至少有一个必须成立，则称是一个全序集或链，而称是 上的一个全序或线性序。定义 2.6.3（盖住 ）：是一个偏序集，若，并且不存在, 使并且，则称盖住 . “紧挨着 ”定义 2.6.4（最小元、最大元 ）：是一个偏序集，如果中存在有元，对任何都满足，则称 是的最小元。如果中存在有元，对任何都满

10、足，则称是的最大元。定义 2.6.5 （极小元、极大元 ）：是一个偏序集， 如果, 而 中不存在元，使,则称 是的极小元。如果, 而 中不存在元, 使,则称是的极大元。定义 2.6.6（上界、下界、上确界、下确界）：是一个偏序集，, 如果对于所有的, 都有,则称 是 的一个 上界。如果对于所有的, 都有,则称 是的一个 下界 。如果是 的一个上界，对于的任一上界, 都有,则称 是 的最小上界（上确界） .如果 是 的一个上界，对于的任一上界,都有,则称 是 的最大下界（下确界） .定义 2.6.5（良序集 ）：设是一个偏序集，对于偏序，如果的每个非空子集都具有最小元，则称是一个良序集，而称是

11、上的一个良序。.每个良序集都是全序集。第 3 章 函数和运算3.1函数定义（映射、象）：关系定义在上，如果对于 每一个，都有唯一的一个，使，则称是从到 的一个函数（或映射） ，记为.称为函数的变元，称为变元在下的值（或象） ，记为.注意：（1）定义域，而不是.（2）每一个，有唯一的，使.多值函数不符合定义（3）值域.定义 3.1.2（受限、扩展）： 若 是从到 的一个函数，则也是一个函数，它定义于到 ，我们称它是在 上的受限。如果 是函数的一个受限，则称是 的一个扩展。定义 3.1.3 （映上、映、一对一、一一对应）： 若，则 的值域时，称函数 是映上的（或满射）。如果 的值域时，则称函数是映

12、的。如果，则有, 则称 是一对一的 （单射）（即时，有） .如果 映上的，又是一对一的，则称是一一对应的 （或双射）。定义 3.1.4（复合运算 ）：若，则定义 和 的复合运算为：即.注：逆函数若要存在需要满足以下条件：（1）函数是映上的（ 2）函数 必须是一对一的定义 3.1.5（恒等函数 ） 函数称为恒等函数。定理 3.1.1，则的充分必要条件是，并且3.2 运算定义 3.2.1（二目运算 ）： 若 是一个集合，是从到 的一个映射（函数） ，则称 为一个二目运算。一般地，若是从到 的一个映射（是正整数），则称 是一个 目运算。运算的封闭：运算的结果总是集合中的一个元，因此这个定义保证了运算

13、的施行，这种情况又称为集合对于该种运算是封闭的。定义 3.2.2（可交换 ）：若是一个运算，对于任何，都有，则称运算是可交换的（或者说，服从交换律） .定义 3.2.3 （可结合）：若是一个运算，对于任何, 都 有，则称运算是可结合的（或者说，服从结合律） .定义 3.2.4（可分配 ）：若是一个运算，是一个运算，对于任何，都有，则称运算对于运算是可分配的 （或者说，对于 服从分配律）.定义 3.2.5（左单位元、右单位元）：设是 上的一个运算，如果中存在有一个元，对于任何，有，则称是运算的左单位元；如果中存在有一个元，对于任何，有，则称是运算的右单位元。定理 3.2.1若 是上的一个运算，和

14、分别是它的左、 右单位元， 则，并且 是唯一的（因此，称为运算的单位元） .定义 3.2.6 （左零元、右零元）：设是 上的一个运算，如果中存在有一个元，对于任何，有，则称是运算的左零元；如果 中存在有一个元，对于任何，有，则称是运算的右零元 .定义 3.2.7（等幂 ）：若 是 上的一个运算，对于运算，有，则称元对于运算是等幂的。定义 3.2.8 （左逆元、右逆元 ）：若是 上的一个运算， 它具有单位元，对于任何一个,如果存在有元，使，则称是 的左逆元；如果存在有元，使，则称是 的右逆元；定理 3.2.3若 是 上的一个运算，它具有单位元，并且是 可结合 的，则当元可逆时，它的左、右逆元相等

15、，并且唯一的（此时称之为的逆元，并且记为） .定义 3.2.9（可消去 ）：若 是 上的一个运算，对于任何，如果元 满足：则；或则，则称元 对于运算是可消去的。第 4章无限集合4.1 基数定义 4.1.1 （等势 ）： 若 和是两个集合，如果在和 之间可以建立 一个一一 对应关系，则称集合和 等势，并记为。定理 4.1.1令是由若干个集合为元所组成的集合，则上定义的等势关系是一个等价关系。定义 4.1.2（有限集、无限集 ）：若 是一个集合，它和某个自然数集等势，则称 是一有限集，不是有限集的集合称为无限集。定理 4.1.2有限集的任何子集都是有限集定理 4.1.3有限集不与其任何真子集等势定

16、理 4.1.4自然数集是无限集4.2可列集定义（可列集 ）：若是一个集合，它和所有自然数的集合等势，则称是一个可列.集。可列集的基数用符号表示。定理 4.2.1若 是一个集合，可列的充分必要条件是可以将它的元排列为的序列形式。定理 4.2.2任何无限集必包含有可列子集。定理 4.2.3可列集的子集是有限集或可列集（记为：）定理 4.2.4若 是可列集， 是有限集，并且，则是可列集（记为：）.定理 4.2.5若 和 都是可列集，并且，则是可列集（记为：）推论 4.2.1设都是可列集，则是可列集（记为：）定理 4.2.6设都是可列集，并且，则是可列集（记为：）推论 4.2.1设都是可列集，则是可列

17、集 .定理 4.2.7所有有理数的集合是可列集。4.3 不可列集定理 4.3.1区间中所有实数构成的集合是不可列的。定义 4.3.1（连续基数 ）： 开区间中所有数组成集合的基数记为，具有基数的集合称为连续统，称为连续基数。推论：集合的基数也是 .定理 4.3.2所有实数的集合是不可列的，它的基数是.定理 4.3.3对于任何数，若，则区间,以及都具有连续基数定理 4.3.4一个无限集和一个可列集作并集时，并集的基数等于集的基数。推论 4.3.2一个无限集和一个有限集的并集，其基数等于集的基数。4.4 基数的比较定义 4.4.1（） 设集合的基数是. 如果 与 的真子集等势，而和 不等势，则称

18、的基数小于的基数，记为.定理 4.4.1：是两个集合，若与 的某一子集等势，与 的某一子集等势，则.定理 4.4.2 ：是任意两个集合，的基数为,的基数为，则下列三个关系：中必有一个且只有个成立。定理 4.4.3：若 是有限集的基数，则.定理 4.4.4：若是无限集合，则定理：若是可列个互不相交的集合，它们的基数都是，则的基.数是（记为：）定理 4.4.6：可列集的幂集，其基数是（记为：）定理 4.4.7：若 是一个集合，是 的幂集，则.此定理说明：不存在最大的基数。补充：第 5章形式语言5.1 文法和语言定义 5.1.1 （产生式 ）： 一个产生式或重写规则是一个有序对，通常写成, 其中，是

19、一个符号，而是一个符号的非空有限串，是这个产生式的左部，而是产生式的右部 .产生式将简称为规则。定义 5.1.2（非终极符号、 字母表、终极符号、开始符号 ）：一个文法是一个四元组.其中，是元语言的语法类或变元的集合，它生成语言的串，这些语法类或变元成为非终极符号 ，是符号的非空有穷集合，称为字母表，的符号称为 终极符号 .是之一，是词汇表的一个识别元素，称为开始符号 .是产生式的集合。定义 5.1.3（直接产生、直接推导，直接规约）：设 是一个文法，如果，而 中有规则，就称串直接产生串，或称 是 直接推导出来的，或直接规约到 ,记为.定义 5.1.4 （产生、规约到、推导）：设 是一个文法，

20、 如果存在产生式序列,使得，而, 就说产生 （ 规约到, 或 是 的推导），记为.定义 5.1.5（句型 ）：令 是一个文法，如果串可从开始符号 推导出来，即如果，则称为一个句型。补 充 ：若， 则,其 中是空串，（不含空串）5.2 文法的类型定义 5.2.1（ 0- 型文法 ）：在 上的 0- 型文法由以下组成：（1）不在 中的不同符号的非空集合, 称为变量表，它包含一个纲符号,称为开始变量。（2）产生式的有限集合。由 产生的所有字集称为由产生的语言。定义 5.2.2（ 0- 型语言 ）：在上可由某一0- 型文法产生的字集称为0- 型语言。.定义 5.2.3（ 1- 型文法 ）：如果在0-

21、型文法中，对于中的每个产生式，要求,则这文法称为 1- 型文法或上下文敏感文法 .定义 5.2.4（ 2- 型文法 ）：设文法, 对于 中的每一个产生式有且（有的人要求），则此文法叫2- 型文法或前后文无关文法。定义（ 3- 型文法 ）：设为一文法， 又设中的每一个产生式都是或，其中和都是变量，而为终极符号，而此文法为3- 型文法或正规文法。第 1章代数系统1.1代数系统的实例和一般性质定义（代数系统 ）： 若是序偶，是一个非空集合，是定义在上的某些运算的非空集合，则称是一个代数系统，或称代数。代数系统的类型：（1）代数系统的类型是，其中代表目运算符。（2），分别为目运算符，则的类型为.1.2

22、 同态和同构定义 1.2.1（同态象、同态映射 ）:和是两个同类型的代数系统，映射和 也构成一一对应. 如果对于任意 目运算，及其对应的运算， 当时，都有, 则称代数是的同态象，称是从到的一个同态映射。定义 1.2.2（同态象、同态映射 ）：若和是两个同类型的代数系统，和都是二目运算，映射. 如果对于任何, 都有，则称是的一个同态象，称是从到的一个同态映射。注：如果就是，则映射是从 到它自身。当上述条件仍然满足时，我们就称是的一个自同态映射。定义 1.2.3（同构、同构映射、自同构映射）：如果和是同态的，映射不仅是同态映射，而且是一一对应 的，则称和同构，称是从到的一个同构映射。如果就是，则称

23、 是上的一个自同构映射定义 1.2.4（同余关系 ）：设是一个代数系统，是 上的一个等价关系，如果存在,当时，成立 ，则称是上的一个同余关系。.定理：设是上的一个等价关系，如果存在同态映射, 使得当时，当且仅当，则是上的同余关系。1.3商代数与积代数定义（子代数 ）：设是一个代数系统，在运算下封闭的，则称是的一个子代数。定义（直接积 ）：设到是两个同类型的代数系统，如果对任意的和，定义运算于，称是和的直接积，称和为的因子。第 2章半群和群2.1半群和有幺半群定义（半群、有幺半群）： 是一个非空集合，如果中定义了一个二目运算，对于任何, 都有，则称是一个半群 . 如果半群中具有单位元 ，使得对任

24、何, 都有, 则称是一个有幺半群。（1） 是一个由有限个符号组成的集合，其中的元称为字母。表示所有的字构成的集合，表示非空串组成的集合。（2）自由半群：半群的各元相互间没有任何关系。说明：半群是一个定义了二目运算，并且服从结合律的代数系统。有幺半群则是具有单位元的半群。2.2群和循环群定义 2.2.1 （群）：在代数系统中，如果二目运算满足（1）对于任何, 有；（2） 中存在单位元，对任何, 有；（3）对于任何，存在有逆元, 使则称是一个群。注：对于群来说，单位元是唯一的，每个元的逆元也是唯一的。“存在逆元的有幺半群叫做群”定义（阶数 ）：若是一个群，当是有限集时，则称中元的个数为群的阶数，记

25、为.定理若是一个群，则，其中即.定义（幂）：是一个群，则记个 的积为,称为幂，.记为表示单位元。定理 2.2.2（指数律）：若和 是整数，则.定理 2.2.3若则定义 2.2.4（次数 ）：若是一个群，, 使的最小正整数 ，称为元的次数。定理 2.2.4若是一个群， 的次数为，则都是 中不同的元。定义 2.2.5（循环群、生成元 ）：由一个单独元素的一切幂所组成的群称为循环群，称为这个群的生成元。定理 2.2.5在阶数为的循环群，由生成元所产生的元次数为 ，即 是生成元的充分必要条件是 和 互质。定理 2.2.6若 和 不是互质的，则的次数是，其中的 是 和 的最小公倍数。定义 2.2.6（阿

26、贝尔群 ）： 如果群中的元对于运算满足交换律，则称这个群是一个阿贝尔群。“满足交换律的群叫做阿贝尔群”循环群是一个阿贝尔群。定理 2.2.7若和都是有限的阿贝尔群，定义则是一个阿贝尔群。最简单的一个阿贝尔群是群,为按位加2.3二面体群、置换群二面体群是从图形的变换中到处，这些图形都是比较正规的图形。定理 2.3.1更一般地讲，定义 2.3.1（置换 ）：若 是一个非空的有限集合，则上任何一个到它自身的一一对应的映射，都称为上的置换。定理 2.3.2两个置换的乘积仍是一个置换，并且置换的乘积服从结合律。的恒等映射也是一个置换称为单位置换。上所有置换的集合，对于置换乘法构成一个群，这个群称为对称群

27、，记为, 是 中元的个数。定义 2.3.2（ 阶置换群 ）若 是非空有限集合，是 上的 个置换所构成的群，则称是一个 阶置换群。定理 2.3.3任何一个（阶）群都同构于一个（阶）置换群。2.4子群、群的同态.定义 2.4.1（子群）：是一个群，, 如果（1）单位元（2）若，则 的逆元（3）若, 则则称是的一个子群。定理 2.4.1是一个群，是一个子群的充分必要条件是：若, 则定义 2.4.2（ 同态象、群同态映射）：和是群，. 若对任何, 有群的同态映射具有下列性质 ：（ 1）将单位元映射为单位元（ 2）将逆元映射为逆元（3）对运算封闭，即对任何，有定理 2.4.2若和是群，是一个群同态映射，

28、则将的子群映射为的子群。定义 2.4.3（同态核 ）：若是一个群同态映射，是的单位元，则中所有满足的元 的集合，称为同态核，记为.定理 2.4.3同态核是一个子群。定理 2.4.3若是群的子群，则定义了 上的一个划分（因而也定义了上一个等价关系） .群子集 ：假定都是群中的元构成的集合（称之为群子集），定义特别地，当是一元集时，我们简记为, 则定理 2.4.5若是群的子群都是群的子群，则是一个群的充分必要条件是.2.5陪集、正规子群、商群定义 2.5.1（左陪集 ）：若是群的子群，对于, 称称为 的一个左陪集 .定理 2.5.1若是群的子群，则的所有左陪集构成的一个划分。定理 2.5.2（拉格

29、朗日定理）每个左陪集的元和中的元都是一样多。推论 2.5.1子群中元的个数一定是群中元的个数的因子。定义 2.5.2（正规子群 ）：若是群的子群，对于任何, 都满足, 则称是群的一个正规子群 .一个阿贝尔群的任何子群都是正规子群。当是群的正规子群时，对于关于 的陪集 . 定义运算为考虑所有关于的陪集组成的集合和运算构成的系统为一个群。这个群称为关于的商群，记为.定理 2.5.3若是从群到群的映上的同态映射，则核是正规子群，商群同构于 .群同态基本定理： 商群是由陪集构成的群， 也是同余类的集构成的群，所以它.同构于象代数，即同构于.如果群没有真正的正规子群，则该群为单群。正规群的任何子群都是正

30、规子群。第 3 章 格和布尔代数3.1 格定义 3.1.1 （格）：表示一个偏序集，如果对于中的任何两个元和 , 在 中都存在一个元是它们的上确界，存在一个元是它们的下确界，则称是一个格。对于 中的元，它们的上确界常常记为，它们的下确界常常记为, 前者又称为 和析取或和（或），后者又称为和 的合取或积（或或 ）。定理 3.1.1若是一个格，则对于任何，有（1）的充分必要条件是.（2）的充分必要条件是.定 理 3.1.2（保序性）若是一个格，则对于任何， 当时 ， 有引理 3.1.1若是一个格，则定理 3.1.3（分配不等式） ：若是一个格，则对于任何，定理 3.1.4（模数不等式）若是一个格，

31、则对于任何，的充分必要条件是定理 3.1.5若是一个代数系统，和 是 上的二目运算， 它服从交换律、 结合律和吸收律 .则是一个格 .定义 3.1.2（子格 ）是一个格，当且仅当对于运算和是封闭的，运算结果和在中相同时，则称代数系统是 的一个子格。定义 3.1.3（直接积） 若和是两个格，则称为这两个格的直接积，其中的运算和 定义为：对于任何的,定义（同态映射 ）设和是两个格，. 如果对任何，有则称是到的一个同态映射. 特别地，当是一个一一对应时，称是一个同构映射，并且称格和同构的。如果是格上一个同态映射，则称是一个自同态映射. 如果是一个同构映射，则称是一个自同构映射.定义（完备 ）： 对于

32、一个格，如果它的每一个非空子集在格中都具有一个上确界和下确界，则这个格称为完备的。显然每个有限的格都是完备的。对于一个格， 它的上确界和下确界如果存在，我们称它们为这个格的边界，并分别记为1 和 0，因此有时这种格称为有界格 。定义（补元 ）：是一个有界格，如果存在元, 使且，则称为 的补元。定义（补格）：中的每个元都至少具有一个补元，则称这个格是一个补格。.定义（分配格 ）：是一个格，如果对任何，有则称是一个分配格。定理 3.1.6任何两个分配格的直接积是分配格。定 理 3.1.7若是一个分配格，则对于任何, 如 果， 并 且, 则推论如果一个格是分配格，同时又是补格，则它的每一个元都具有唯

33、一的一个补元。3.2 布尔代数定义 3.2.1（布尔代数 ） 一个既是补格，又是分配格的格，称为布尔代数。定义 3.2.2（对偶命题 ） 如果是一个布尔代数，是关于 中变元的一个命题，它可以由中变元元通过运算来表示 . 如果对的表示式进行下列代换：代换为； 代换为； 代换 0；0代换为 1，则这样代换后也将得到一个命题, 它成为命题 的对偶命题，简称为对偶。定理 3.2.1（对偶原理）如果是一个命题，它在任何一个布尔代数中都成立，并且可以由运算来表示，则对它的对偶命题也在任何一个布尔代数中成立。定理 3.2.1*（对偶原理）如果是一个命题，它在任何一个布尔代数中都成立，并且可以由运算和关系来表

34、示，则将中的运算代换为；代换为；0 代换为 1，代换 0；换为，换为，所得到的对偶命题也在任何一个布尔代数中成立。定理 3.2.2若 和是两个布尔代数，是一个同态映射，则在 中的同态象是的一个子布尔代数。定义（基元 ）：是一个布尔代数，, 如果中不存在元, 使, 则称是的一个基元。如果对于任何都存在有基元, 则称这个布尔代数是基元的。定理若是一个布尔代数，, 则下列命题是等价的。（1）是一个基元（2）对于所有的, 若, 则或（3）对于所有的，推论若和 是不同的基元，定理是一个基元的布尔代数，是其基元的集合，对任一令, 则, 并且作为基元的析取式，这个表达式是唯一的。.定理 3.2.5若是一个非

35、空有限的布尔代数，是它的所有基元构成的集合，则同构.推论 3.2.2一个有限的布尔代数具有个元，其中的是它的基元的个数。推论 3.2.3对于任意正整数, 具有个元的布尔代数是同构的。3.3其他代数系统定义（ 环）若代数系统满足下列条件：（ 1） 对于二目运算是一个可交换的加法群。（ 2） 对于二目运算（即乘法）是封闭的。（3）乘法结合律成立，即对中任何三个元和 , 有（4）分配律成立，即对中任何元和 ，有则称是一个环。定义（交换环 ） 一个环中的任何两个元, 如果都满足, 则称是一个交换环。定义（逆元、零元）一个环中如果存在有元, 使得对中任何一个元都有, 则称是的一个单位元。定义（逆元、零元

36、 ）在一个有单位元的环里，如果和是环中的元，满足,则称是的逆元。对任意, 若, 则称0 是的零元。环的零元通常用表示。定义（域）：一个可交换的除环称为一个域。定义（子环 ）：一个环的一个子集本身对的代数运算也构成一个环，则称为的子环。定义（理想子环，理想）：若 是环的一个非空子集，满足（1）（2）则称 是的一个理想子环，简称理想。第4章群码4.1通信模型和错误校正的基本概念4.2二进制编码定义 4.2.1（海明距离 ） 设与 之间的海明距离是的权，用表示。定理 4.2.1设, 则（1）（2）.（3）当且仅当（ 4）定义 4.2.2 （码字）：码字是元组的码的最小距离，是该码中所有码字之间的海明距离的最小值。定理 4.2.2当且仅当一个编码的任意两个码字之间的最小距离至少时，能够检查出个或至少 个错误的所有