离散数学课本定义和定理

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

1.2 集合的运算
定义1.2.1（并集）：设A和B是两个集合，则包含A和B的所有元 ，但不包含其他元的集
合，称为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的
补集，记为.
定义1.2.6（对称差）：A和B是两个集合，则定义A和B的对称差为


1.3 包含排斥原理
定理1.3.1 设为有限集，其元素个数分别为

定理1.3.2 设为有限集，其元素个数分别为

定理1.3.3 设为有限集，则
，则
，则

重要例题 P11 例1.3.1

.. .

..
第2章 二元关系
2.1 关系
定义2.1.1（序偶）：
若和是两个元，将它们按前后顺序排列，记为，则成为一个序偶。
※ 对于序偶和，当且仅当并且时，才称和相等，记为

定义2.1.2（有序元组）：
若是个元，将它们按前后顺序排列，记为，则成为一个有序元组
（简称元组）。
定义2.1.3（直接积）：
和是两个集合，则所有序偶
定义2.1.4（直接积）：
设是个集合，
的笛卡尔积（或直接积），记为
定义2.1.5（二元关系）
若和是两个集合，则的任何子集都定义了一个二元关系，称为
关系。如果，则称为上的二元关系。
定义2.1.5（恒等关系）：
设是上的二元关系，，则称是上的恒等关系。
上的二元
的集合，称为和的直接积（或笛卡尔积），记为.
，则所有元组
.
的集合，称为
定义2.1.7（定义域、值域）：若是一个二元关系，则称
为的定义 域。
定义2.1.8（自反）：设是集合上的关系，若对于任何
．．
，都有
为 的值域。
即则称
关系是自反的。
定义2.1.9（反自反）：设是集合上的关系， 若对于任何，都满足,即对
任何都不成立，则称关系是反自反的。
定义2.1.10（对称） ：设是集合上的关系，若对于任何，只要,就有,那
么称关系是对称的。
定义2.1.11（ 反对称）：设是集合上的关系，若对于任何，只要并且时,
就有，那么称关系是对称的。
定义2.1.11（传递） 设是集合上的关系，若对于任何，只要并且时，
就有，则称关系是传递的。

定理2.1.1 设是集合上的关系，若是反自反的和传递的，则是反对称的。

2.2 关系矩阵和关系图
定义 无 定理 无

2.3 关系的运算
定义2.3.1（连接）：设为上的关系，为

.. .
上的关系，则定义关系

..
称为关系和的连接或复合，有时也记为
定义2.3.2（逆关系）：设
.
定理2.3.1 设和都是
（1）
（3）
（5）
定理2.3.2 设为

2.4 闭包运算

为
.
为上的关系：上的关系，则定义的逆关系为
上的二元关系，则下列各式成立



上的关系，为上的关系，则
（2）


（4）
定义2.4.1（自反闭包）： 设是集合上的二元关系，如果
称是关系的自反闭包，记为.
是包含的最小自反关系，则
定义2.4.2（对称闭包）： 设是集合上的二元关系，如果
称是关系的对称闭包，记为.
是包含的最小对称关系，则
定义2.4.3（传递闭包）： 设是集合上的二元关系，如果
称是关系的传递闭包，记为或.
是包含的最小传递关系，则
定理2.4.1 设是集合上的二元关系，则
（1） 是自反的，当且仅当.
（2） 是对称的，当且仅当.
（3） 是传递的，当且仅当.
定理2.4.2 设是集合上的二元关系，则
定理2.4.3 设是集合上的二元关系，则
定理2.4.4 设是集合上的二元关系，则
定理2.4.5 设是一个元集，是上的二元关系，则存在一个正整数
.

2.5 等价关系和相容关系
定义2.5.1（覆盖、划分）： 是一个集合，
.. .
.
.
“

恒等关系”
“逆关系”
. “
，使得
幂集”
,如果，则称

..
是的一个覆盖。如果，并且，则称是
的一个划分，中的元称为的划分块。
定义2.5 .2（等价关系）：设是上的一个关系，如果具有自反性、对称性和传递性三个
性质，则称是一个等价关 系。设是等价关系，若成立，则称等价于.
定义2.5.3（等价类）：设是上的一个等价关系，则对 任何
称为关于的等价类，简称为的等价类，
，令
.
，
也可以简记为
定义2.5.4（同余）：对于整数


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

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

..
每个良序集都是全序集。


第3章 函数和运算
3.1 函数
定义3.1.1（映射、象）： 关系定义在上，如果对于每一个
．．．
，都有唯一的 一个
．．．．．
，
使，则称是从到的一个函数（或映射），记为
为变元在下的 值（或象），记为.
注意：
.称为函数的变元，称
（1） 定义域，而不是.
（2） 每一个，有唯一的，使. 多值函数不符合定义
（3） 值域.
定义3.1.2（受限、扩展）： 若是从到的一个函数，，则也是一个函数，
它定义于到，我 们称它是在上的受限。如果是函数的一个受限，则称是的一个扩
展。
★定义3.1.3（映上、映、一对一、一一对应）： 若
数是映上的（或满射）。如果的值域
则有
，则的值域时，称函
，
）.
时，则称函数是映的。如果
时，有,则称是一对一的（单射）（即
如果映上的，又是一对一的，则称是一一对应的（或双射）。
定义3.1.4（复合运算）：若，则定义和的复合运算
即.
注：逆函数若要存在需要满足以下条件：
为：
（1）函数是映上的（2）函数必须是一对一的
定义3.1.5（恒等函数） 函数
定理3.1.1

3.2 运算
定义3.2.1（二目运算）： 若是一个集合，是从
一个二目运算。一般地，若是从
到的一个映射（函数），则称为
， 则
称为恒等函数。
的充分必要条件是，并且
到的一个映射（是正整数），则称是一个目运算。
运算的封闭：运算的结果总是集合中的一个 元，因此这个定义保证了运算的施行，这
种情况又称为集合对于该种运算是封闭的。
定义3. 2.2（可交换）：若是一个运算，对于任何，都有，
则称运算是可交换的（或者说，服从交换律）.
定义3.2.3（可结合）：若是一个运算，对于任何,都有
，则称运算是可结合的（或者说， 服从结合律）.
定义3.2.4（可分配）：若是一个运算，是一个运算，对于任何，
都有， 则称运算对于运算是可分配的（或者说，对于服从
分配律）
.. .

..
定义3.2.5（左单位元、右单位元）：设是上的一个运算，如果中存在有一个元，对
于任何
何
，有
，有
，则称是运算的左单位元；如果中存在有一个元，对于任
，则称是运算的右单位元。
，并且是定理3.2.1 若是上的一个运算，和分别是它的左、右单位元，则
唯一的（因此，称为运算的单位元）.
定 义3.2.6（左零元、右零元）：设是上的一个运算，如果中存在有一个元，对于任
何
有，有
，则称
，则称是运算的左零元；如果中存在有一个元
是运算的右零元. ，对于任何，
定义3.2.7（等幂）：若是上的一个运算，，对于运算，有，则称元对
于 运算是等幂的。

定义3.2.8（左逆元、右逆元）：若是上的一个运算，它具有单位元，对 于任何一个,
如果存在有元，使，则称是的左逆元；如果存在有元，使，
则称是的右逆元；
定理3.2.3 若是上的一个运算，它具有单位元，并且是可结合的，则当元可逆时，
．． ．
它的左、右逆元相等，并且唯一的（此时称之为的逆元，并且记为）.
定义3.2.9（可消去）：若是上的一个运算，对于任何，如果元满足：
则；或则，则称元对于运算是可消去的。


第4章 无限集合
4.1 基数
★定义4.1.1（等势）： 若和是两个集合，如果在和之间可以建立一个一 一对应
．．．．
关系，则称集合和等势，并记为。
定理4.1.1 令是由若干个集合为元所组成的集合，则上定义的等势关系是一个等价关
系。
定义4.1.2 （有限集、无限集）：若是一个集合，它和某个自然数集
则称是一有限集，不是有限集的集合称为无限集 。
定理4.1.2 有限集的任何子集都是有限集
定理4.1.3 有限集不与其任何真子集等势
定理4.1.4 自然数集

4.2 可列集
是无限集
等势，
定义4.2.1（可列集）：若是一个集合，它和所有自然数的集合 等势，则称是一个可列
.. .

..
集。可列集的基数用符号表示。
的定理4.2.1 若是一个集合，可列的充分必要条件是可以将它的元排列为
序列形式。
定理4.2.2 任何无限集必包含有可列子集。
定理4.2.3 可列集的子集是有限集或可列集（记为：
定理4.2.4 若是可列集，是有限集，并且
定理4.2.5若和都是可列集，并且
推论4.2.1 设
定理4.2.6 设
列集（记为：
推论4.2.1设
）
都是可列集，则是可列集.
都是可列集，则
都是可列集，并且
，则
，则
）
是可列集（记为：
是可列集（记为：
是可列集（记为：
，则
）
）.
）
是可
定理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（） 设集合的基数是.如果与的真子集等势，而和不等势，则
称的基数小于的基数，记为.
定理4.4.1：是两个集合，若与的某一子集等势，与的某一子集等势，则.
定理4.4. 2：是任意两个集合，的基数为,的基数为，则下列三个关系：
中必有一个且只有个成立。
定 理4.4.3：若是有限集的基数，则
定理4.4.4：若是无限集合，则
定理4.4.5：若

的基
.
是可列个互不相交的集合，它们的基数都是，则
.. .

..
数是（记为：）
）
.
定理4.4.6：可列集的幂集，其基数是（记为 ：
定理4.4.7：若是一个集合，
此定理说明：不存在最大的基数。
补充：

是的幂集，则

第5章 形式语言
5.1 文法和语言
定义5.1.1（产生式）： 一个产生式或重写规则是一个有序对，通常写成,其中，< br>是一个符号，而是一个符号的非空有限串，是这个产生式的左部，而是产生式的右部.
产生式将简 称为规则。
定义5.1.2（非终极符号、字母表、终极符号、开始符号）：一个文法是一个四元组< br>其中，
极符号，
.
是元语言的语法类或变元的集合，它生成语言的串，这些语法 类或变元成为非终
是符号的非空有穷集合，称为字母表，的符号称为终极符号.是之一，是
词汇 表的一个识别元素，称为开始符号.是产生式的集合。
定义5.1.3（直接产生、直接推导，直接规 约）：设是一个文法，如果，
而中有规则，就称串直接产生串，或称是直接推导出来的，或直接规约到,
记为.
定义5.1.4（产生、规约到、推导）：设是一个文法，如果存在产生式序列
使得，而
,
,就说产生（规约到,或是的推导），记为
.
定义5.1.5 （句型）：令是一个文法，如果串可从开始符号推导出来，即如果
称为一个句型。
补充： 若，则
（不含空串）

5.2 文法的类型
,其中
，则
是空串，
定义5.2.1（0-型文法）：在上的0-型文法由以下组成：
（1） 不在中的不同符号的非空集合,称为变量表，它包含一个纲符号,称为开始变
量。
（2） 产生式的有限集合。
由产生的所有字集称为由产生的语言。
定义5.2.2（0-型语言）：在上可由某一0-型文法产生的字集称为0-型语言。
.. .

..
定义5.2.3（1-型文法）：如果在0-型文法中，对于中的每个产生式
则这文法称为1- 型文法或上下文敏感文法.
定义5.2.4（2-型文法）：设文法
（有的人要求
, 对于中的每一个产生式
，要求,
有且
），则此文法叫2-型文法或前后文无关文法。
为一文法，又设中的每一个产生式都是或定义5.2.5（3-型文法）：设

，其中和都是变量，而为终极符号，而此文法为3-型文法或正规文法。

第1章 代数系统
1.1 代数系统的实例和一般性质
定义1.1.1（代数系统）： 若是序偶，是一个非空集合，是定义在上的某些运算的
非空集合，则称是一个代数系统，或称代数。
代数系统的类型：
（1） 代数系统
符。
（2）

1.2 同态和同构
定义1.2.1（同态象、同态映射）:
和
和是两个同 类型的代数系统，映射
，及其对应的运算
,则称代数
到的一个同态映射。
是
，当
的
，分别为目运算符，则的类型为.
的类型是，其中代表目 运算
也构成一一对应.如果对于任意目运算
时，都有
同态象，称是从
定义1. 2.2（同态象、同态映射）：若和是两个同类型的代数系统，和都是二
目运算，映射.如果对于任何, 都有，则称是的
一个同态象，称是从到的一个同态映射。
注：如果就是，则映射是从到它自身。当上述条件仍然满足时，我们就称是
的一个自同态映射。
定义1.2.3（同构、同构映射、自同构映射）：如果和是同态的，映射不仅
是同态映射，而 且是一一对应的，则称和同构，称是从到的一个同
．．．．
构映射。如果就是，则称是上的一个 自同构映射
定义1.2.4（同余关系）：设是一个代数系统，是上的一个等价关系，如果存在
,当
余关系。
时，成立，则称是上的一个同
.. .

..
定理1.2.1：设～是上的一个等价关系，如果存在同态映射
时，当且仅当，则～是上的同余 关系。
,使得当

1.3 商代数与积代数
定义1.3.1（子代数）：设
的一个子代数。
定义1.3.2（直接积）：设
，定义运算于
的直接积，称和为的因子。
< br>到是两个同类型的代数系统，如果对任意的
，称是
和
和
是一个代数系统 ，在运算下封闭的，则称是
第2章 半群和群
2.1 半群和有幺半群
定义2. 1.1（半群、有幺半群）：是一个非空集合，如果中定义了一个二目运算，对于
任何,都有，则称是一 个半群.如果半群中具有单位
元，使得对任何,都有,则称是一个有幺半群。
（1）是一个由有限个符号组成的集合，其中的元称为字母。
表示非空串组成的集合。
（2）自由半群：半群的各元相互间没有任何关系。
表示所有的字构成的集合，
说明：
半群是一个定义了二目运算，并且服从结合律的代数系统。有幺半群则是具有单位元的半群。

2.2 群和循环群
定义2.2.1（群）：在代数系统
（1）对于任何,有
（2）中存在单位元，对任何
（3）对于任何
注：对于群
，存在有逆元
中， 如果二目运算满足
；
,有；
,使则称是一个群。
来说，单位元是唯一的，每个元的逆元也是唯一的。
“存在逆元的有幺半群叫做群”
定义2.2.2（阶数）：若
记为.
定理2.2.1 若
定义2.2.3（ 幂）：
是一个群，当是有限集时，则称中元的个数为群的阶数，
是一个群，
是一个群，
，则
，则记个的积
，其中即.
称为幂，为,
.. .

..
记为表示单位元。
. 定理2.2.2（指数律）：若和是整数，则
定理2.2.3 若则
是一个群，,使定义2.2.4（次数）：若
数。
定理2.2.4若
的最小正整数，称为元的次
是一个群，，的次数为，则都是中不同的元。
定义2.2.5（循 环群、生成元）：由一个单独元素的一切幂所组成的群称为循环群，称为
这个群的生成元。
定理2.2.5 在阶数为的循环群，由生成元所产生的元次数为，即是生成元的充分必
要条件是和互质。
定理2.2.6 若和不是互质的，则的次数是
定义2.2.6（阿贝尔群）： 如果群
阿贝尔群。
“满足交换律的群叫做阿贝尔群”
循环群是一个阿贝尔群。
定理2.2.7 若和


则是一个阿贝尔群。
群,为按位加 最简单的一个阿贝尔群是
，其中的是和的最小公倍数。
中的元对于运算满足交换律，则称这个群是一个
都是有限的阿贝尔群，定义

2.3 二面体群、置换群
二面体群是从图形的变换中到处，这些图形都是比较正规的图形。
定理2.3.1 更一般地讲，
定义2.3.1（置换）：若是一个非空的有限集合，则上任 何一个到它自身的一一对应的映
射，都称为上的置换。
定理2.3.2 两个置换的乘积仍是一个置换，并且置换的乘积服从结合律。
的恒等映射也是一个置换称为单位置换。 上所有置换的集合，对于置换乘法构成一个群，
这个群称为对称群，记为,是中元的个数。
定 义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 若和是群，
的子群。
定义2.4.3（同态核）：若

是一个群同态映射，则将的子群映射为
是一个群同态映射，
.
是的单位元，则中所有满足
的元的集合，称为同态核，记为
定理2.4.3 同态核是一个子群。
定理2.4.3 若
等价关系）.
群子集：假定
是群
都是群

特别地，当是一元集时，我们简记为
定理2.4.5若是群的子群都是群
件是.

2.5 陪集、正规子群、商群
定义2.5.1（左陪集）：若
一个左陪集.
是群
的子群，则定义了上的一 个划分（因而也定义了上一个
中的元构成的集合（称之为群子集），定义
,则
的子群，则

是一个群的充分必要条
的子群，对于,称称为的< br>定理2.5.1若是群的子群，则的所有左陪集构成的一个划分。
定理2.5.2（拉格朗日定理）每个左陪集的元和中的元都是一样多。
推论2.5.1 子群中元的个数一定是群中元的个数的因子。
定义2.5.2（正规子群）：若是群
是群的一个正规子群.
一个阿贝尔群的任何子群都是正规子群。
的子群，对于任何,都满足,则称
当是群的正规子群时，对于关于的陪集.定义运算为
考虑所有关于的陪集组成的集合和运算构成的系统为一个群。这
个群称为关于的商群，记为.
定理2.5.3 若是从群到群的映上的同态映射，则核是正规子群，商群
同构于.
群同态基本定理：商群是由陪集构成的群，也是同余类的集构成的群，所以它
.. .

..
同构于象代数，即同构于.
如果群没有真正的正规子群，则该群为单群。
正规群的任何子群都是正规子群。

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

引理3.1.1若是 一个格，
定理3.1.3（分配不等式）：若
，则
是一个格，则对于任何

，


定理3.1.4（模数不等式）若是一个格，则对于任何，的充分必要条件
是
定理3.1.5 若是一个代数系统，和是上的二目运算，它服从交换律、结合律和
吸收律.则是一个格.
定义3.1.2（子格） 是一个格，，当且仅当对于运算和是封闭的，运算
结果和在中相同时，则称代数系统是的一个子格。
定义3.1.3（直接积） 若和是两个格，则称为这两个格的直
接积，其中的运算和定义为：对于任何的


定义3.1.4（同态映射）设和是两个格，.如果对任何，有
,

则称 是到的一个同态映射.特别地，当是一个一一对应时，称是一个
同构映射，并且称格和同构的。
如果是格上一个同态映射，则称是一个自同态映射.如果是一个同构
映射，则称是一个自同构映射.
定义3.1.5（完备）： 对于一个格，如果它的每一个非空子集在格中都具有一个上确界和下
确界，则这个格称为完备的。 显然每个有限的格都是完备的。对于一个格，它的上确界和下确界如果存在，我们称它
们为这个格的 边界，并分别记为1和0，因此有时这种格称为有界格。
定义3.1.6（补元）：是一个有界格，，如果存在元,使且
，则称为的补元。
定义3.1.7（补格）：中的每个元都至少具有一个补元，则称这个格是一个补格。
.. .

..
定义3.1.8（分配格）：是一个格，如果对任何，有


则称是一个分配格。
定理3.1.6 任何两个分配格的直接积是分配格。
定理3.1.7 若是一个分配格，则对于任何,如果，并且
,则
推论3.1.2 如果一个格是分配格，同时又是补格，则它的每一个元都具有唯一的一个补元。

3.2 布尔代数
定义3.2.1（布尔代数） 一个既是补格，又是分配格的格，称为布尔代数。
定义3.2.2（对偶命题） 如果
它可以由中变元元通过运算
代换为；代换为
是一个布尔代数，是关于中变元的一个命题，
来表示.如果对的表示式进行下列代换：
,它 成；代换0；0代换为1，则这样代换后也将得到一个命题
为命题的对偶命题，简称为对偶。
定理3.2.1（对偶原理）如果是一个命题，它在任何一个布尔代数中都成立，并且可以由
运算来表示 ，则对它的对偶命题也在任何一个布尔代数中成立。
定理3.2.1*（对偶原理）如果是一个命题， 它在任何一个布尔代数中都成立，并且可以由
运算
代换0；
和关系
换为，来表示，则将中的运算
换为
代换为；代换为；0代换为1，
，所得到的对偶命题也 在任何一个布尔代数中成立。
是一个同态映射，则在中的同态象是定理3.2.2 若和是两个布尔代数，
的一个子布尔代数。
定义3.2.3（基元）：是一个布尔代数，,如 果中不存在元,使
都存在有基元,则称这个布,则称是的一个基元。如果对于任何
尔代数是基元 的。
定理3.2.3 若
（1）是一个基元
（2）对于所有的
（3）对于所有的
是一个布尔代数，,则下列命题是等价的。
,若
，
,则或



推论3.2.1 若和是不同的基元，
定理3.2.4
,则
是一个基元的布尔代数，是其基元的集合， 对任一令
,并且作为基元的析取式，这个表达式是唯一的。
.. .

..
定理3.2.5 若
同构
是一个非空有限的布尔代数，是它的所有基元构成的集合，则
.
推论3.2.2 一个有限的布尔代数具有个元，其中的是它的基元的个数。
推论3.2.3 对于任意正整数,具有个元的布尔代数是同构的。

3.3 其他代数系统
定义（环）3.3.1 若代数系统满足下列条件：
（1）对于二目运算是一个可交换的加法群。
（2）对于二目运算（即乘法）是封闭的。
（3）乘法结合律成立，即对中任何三个元和,有

（4）分配律成立，即对中任何元和，有


则称是一个环。
定义3.3.2（交换环） 一个环中的任何两个元
换环。
,如果都满足,则称是一个交
定义3.3.3 （逆元、零元）一个环中如果存在有元,使得对中任何一个元都有
,则称是的一个单位元。
定义3.3.4（逆元、零元） 在一个有单位元的环里，如果和是环中的元，满足,
则称是的 逆元。对任意,若,则称0是的零元。环的零元通常用表
示。
定义3.3.7（域）：一个可交换的除环称为一个域。
定义3.3.8（子环）：一个环的一个子集本身对的代数运算也构成一个环，则称为的
子环。
定义3.3.9（理想子环，理想）：若是环的一个非空子集，满足
（1）
（2）
则称是的一个理想子环，简称理想。

第4章 群码
4.1 通信模型和错误校正的基本概念
4.2 二进制编码
定义4.2.1（海明距离） 设
定理4.2.1 设
（1）
（2）
,则


与之间的海明距离是的权，用表示。
.. .

..
（3） 当且仅当
（4）
定义4.2.2（码字）：码字是元组的码的最小距离 ，是该码中所有码字之间的海明距离的最
小值。
定理4.2.2 当且仅当一个编码的任意两个码字之间的最小距离至少时，能够检查出个
或至少个错误的所有组合。
定理4.2.3 当且仅当任意两个码字之间的距离至少是时，这中编码就能够纠正个或
少于个错误的组合。
定义4.2.3（群码） 设
的子群，则称是编码函数.
和是群，函数
是群码。
,使得是
定理4.2.4 一个群码的非零码字的最小权等于它的最小距离。
定义4.2.4 设
.
定义4.2.5（布尔矩阵）： 设
是布尔矩阵，其中
定理4.2.5 设和是非负整数，且
是从群
推论4.2.1 设
,并设是
到的同态映射。
,并设是布尔矩阵，函数
是布尔矩阵，布尔矩阵的积
.
布尔矩阵，则函数
,其中
和是非负整数，且
使得是正规子群。
,则
是
当且仅当某. 定理4.2.6 设
推论4.2.1

4.3 解码和错误校正
定义4.3.1（解码函数）：若
有噪声时，,则称是与对应的
的一个子群。
是映上函数，如果
解码函数。
,使得当传送通道没
定义4.3.2（级校正） 设是一个编码函数，是与对应的解码函数，如果是
正确传送或具有级错误，则称是级校正。
定理4.3.1 假设是编码函数，是对应的最大似然译码函数，则能够校正级错
误，当且仅当的最小距离至少是.
定义4.3.3（陪集头）的左陪集中，具有最小权的元素称为陪集头。
定理4.3.2 如果和定义如前，则是映上的。
.. .

..
定理4.3.3 设和是的元素，则和处于的同一左陪集，当且仅当,即当
且仅当它们有相同的并发错。
第1章 命题演算
1.1 命题和逻辑连接词
定义1.1.1（命题）： 如果有一个述语句，它可 以取值：“真”或“假”，并且只能取其中一
个值，这样的述语句就成为一个命题。
5中基本逻辑连接词：
（1）：否定词：“非”
（2）：合取词：“并且”
（3）：析取词：“或者”
（4）：蕴涵词：“若则”
（5）：等值词：“等值于”

1.2 合式公式
能成为命题的式子称为合式公式，简记为
定义1.2.1（合式公式）：
。
（1）一个命题变元是.
（2）若是一个,则是一个.
（3）若和是,则和都是
（4）只限于有限次使用（1）（2）（3）所得到的符号串。
定义1.2.2（部分合式公式） 如果和都是,是的一部分，则称是的部分合式公
式或子公式，部分合式公式简记为.
结论：在 都是且是符号串的一个组成部分时。如果用代换中全部的,所得到
的是.当且仅当是时，是.
判断符号串是否是的算法：
（1）空公式不是
（2）对中的用命题变元代换，得到新的符号串
（3）检查是否还能作进一步代换，以消除逻辑连接词.如何能则转（2）
（4）检查最后的符号串是否是简单的命题变元，如果是，则原来的是,否则不是。
重要例题1.2.7

1.3 真值表、永真式
定义1.3.1（永真式、重言式、有效） 对于一个的命题变元无论作何指派，所得到的
值永 为,即命题永远是真命题，则称该为永真式或重言式，并称它是有效的。
定义1.3.2（永假公式、不可满足公式） 对于一个的命题变元无论作何指派，所得到
的值 永为,即命题永远是假命题，则称该为永假公式或不可满足公式。
定义1.3.3（可满足公式） 不是永真式的称为非永真公式。不是永假公式的称为可
满足公式。

定理1.3.1 永真公式的合取式或析取式仍然是永真公式。
定理1.3.2 在一个永真公式中，对某个变元用同一个置换，其结果仍然为永真公式。
定理1.3.3 若和都是的充要条件是是一个永真式。
定理1.3.4 一个的永真式、永假性、非永真性和可满足性是可判定的。
.. .

..

1.4 命题演算的等价关系
定理1.4.1（代换定理）若是一个
中的 一个或若干个代换
，是它的一个
为,则.
,在将中各处出现的
时，如果得到的

1.5 逻辑连接词的可省略性 如果能找到一个更小的逻辑连接词的集合，用它们也能完成上述五个连接词的全部功能，则
我们把这 种连接词的集合称为连接词的功能完全集。
功能完全集：、、、
：读为“与非”（2）读为“或非”
、



1.6 式
定义1.6.1（初等积）：命题变元和它们的否定的合取式称为初等积。
定义1.6.2（初等和）：命题变元和它们的否定的析取式称为初等和。
定义1.6.3（析取式）：如果一个
则它称为析取式。
定义1.6.4（合取式） ：如果一个具有形式而每个都是初等和，
具有形式而每个都是初等积，
则它称为合取式。
定义1.6.5 （最小项）：在初等积中，每个命题变元和它的否定不能同时出现，但两者中必
须出现一个，而且只能出现一次，这样的初等积称为最小项。
★定义1.6.6（标准析取式）：对于一个
它的标准析取式。
，仅由它的最小项的析取组成的等价公式称为
定理1.6.1 在真值表中，一个的真值为的指派所对应的最小项的析取式，即为此的
标准析取式。 “真值为的并集，变元取正”
定义1.6.7（最大项）：在初等和中，每个命题变元和它的否定不能 同时出现，但两者中必
须出现一个，而且只能出现一次，这样的初等和称为最大项。
★定义1.6.8（标准合取式）：对于一个
的标准合取式。
,仅由它的最大项的合取组成的等价公式称为它
定理1.6.2 一个的真值为的指派所对应的最大项的合取式，即为此的标准合取式。
“真值为的交集，变元取反”
1.7 推理和证明方法
定义1.7.1（逻辑前提、有效结论）：
1的任何代入 ，也一定取值1，则称
并记为
定理1.7.1：
.
的充分必要条件是为永真公式。
和都是,如果对于取值
的有效结论，是的逻辑前提，是
.. .

..
判断命题是否是有效结论的方法：
（1）真值表法
（2）直接证法



规则：在推导的任一步都可以引用任一前提
规则：如果公式在前面的推导中已经提到，则可以在以后的推导过程中引用，否则
不得引用。
等价规则：若结论形如,则可作为前提，与前提一起推出,即
永真.即可改写成.
（3）反证法
定义1.7.2（相容、不相容）：若
变元，在对
是一组,是 它们中出现的全部命题
的取值为1，则称
都取值0，
的各组真值指派中，至少有一组使
是相容的. 如果对于的任何真值指派
则称是不相容的.
和是，则的充分必要条件是定理1.7.2 若
是永假公式。


第2章 谓词演算
2.1 谓词
命题中的主词称为个体词，个体词扫描的客体，称 为个体。在定义谓词是，我们常常将谓词
局限于某一个体域上进行讨论，所以又将这个个体域称为该谓词 的论域。
定义1.2.1（目谓词） 在论域
射。

2.2 量词
量词：全称量词、存在量词?

2.3 合式公式
定义2.3.1（项）
（1） 每个个体常数是一个项
（2） 每个个体变元是一个项
（3） 若是一个元函数，是项，则是项
项.
上的目谓词，是从到的一个映
（4） 若是一个合式公式，和是项，则
.. .

..
（5） 所有项都是有限次使用（1）（2）（3）和（4）得到的符号串.
定义2.3.2（原子公式）
（1） 和（真假值符号）是原子公式
和命题变元是原子公式
是元命题函数，则
是原子公式
是原子公式.
（2） 称命题常数
（3） 若
（4） 若
是项，
是项，则
（5） 原子公式只限于此
定义2.3.3（合式公式）
（1） 原子公式是合式公式
（2） 若是合式公式，则是合式公式
（3） 若和是合式公式，则
合式公式
和都是
（4） 若是变量，是合式公式，则和是合式公式
（5） 合式公式只限于有限次使用上述几条规定所得到的符号串。
定义2.3.4（部分合式）一个是另一个 合式公式的一部分，则称它为的部分合式
公式，记为.
定义2.3.5（约束部分、约束出现、约束变元、自由变元）：
在一个中，如果它的某个具 有或的形式，则称这个称为原来的一
个约束部分，称为是约束出现的. 约束出现的变元称为约束变元，不是约束出现的变元称
为自由变元。
定义2.3.6（辖区） 若
的，则称为在中的辖区，

2.4 合式公式的有效性
是
称为
或命题函数，
在中的辖区。
和是
定义2.4.1（可满足） 为一个,如果的所有解释都取值,则称是永真的或有效的.< br>如果的所有解释都取值,则称是永假的或不可满足的.如果至少存在一种解释使取值,
则称是可满 足的。
2.5 谓词演算的等价公式
定义2.5.1（等价） 和是两个,它们具有相同的 论域，如果对和中出现的约束量
和自由变量给予任何解释，和都取相同的值，则称和等价，记为.

2.6 谓词公式的式
定义2.6.1（前束合取式）：一个称为前束合取式，如果它具有下面的形式

定理2.6.1 每个都可以转换为等价的前束合取式
定义2.6.2（前束析取式） 一个称为前束析取式，如果它具有如下形式：

定理2.6.2 每个都可以转换为等价的前束析取式.
具有的形式，其中的是或?，定义2.6.3（前束式） 如果一个
.. .

..
是不同的命题函数或个体变元，中不含不包含量词，则称该

是一个前束式.
第3章 推理系统
3.1 自然推理系统
自然推理系统是对一阶谓词演算的完全推理系统.系统的核心是公理和推理规则。
定理3.1.1 （Godel）
（1）对于二阶谓词演算没有完全的推理系统
（2）对于一阶谓词演算具有完全的推理系统
自然推理系统：
（1） 公理和基本规则
（a） 假设





（b） 真值符号公理


（2） 连接词规则
（a） 规则


（b） 规则


（c） 规则


（d） 规则


（e） 规则
引入（）



引入（
消去（
）
）


引入（
消去（
）
）
引入（）
）
引入（
消去（
）
）




公理（
公理（
）
）



假设公理（）
假设引入（）
假设消去（）
消去（
.. .

..

（f） 规则
消去（）


（g）

引入（）
） 消去（
规则



引入（
消去（
消去（
）
）
）
导出规则
（1）（a）
（b）
（2）（a）
（b）
（3）（a）



（b）













替换规则 （
替换规则（
推广的
推广的
拒取式（
拒取式（
）
引入规则（）
）
）
）
）
替换规则（
替换规则（
）
）
拒取式（


左
（4）（a）
（b）
（3）量词规则
（a）规则：


（b）规则：


蕴含传递（）
） 等价传递（
引入规则（） 其中，不在中自由出现
） 其中，在中相当于在自由出现 消去规则（
引入规则（）
.. .

..
其特殊情况是：

其中的是不在
导出规则：
（a）
（b）
（c）
（d）


和
引入规则（

）
和中出现的个体常数。
左引入规则（



双引入规则（
左引入规则（
双引入规则（
）
）
）
）
其中，不在和中自由出现
其中，不在中自由出现
（4）运算符规则和等词规则
（a）


（b） 等词公理（
等词规则
中自由出现的项。
）
引入（
消去（
消去（
）
）
）
其中，和是替换
等词规则：
（a）
（b）
（c）




图论
定理5.4.1 连通图的一个割集至少包含生成树的一个树枝。
定义5.4.1（基本割集）：设是图，并设为的一个 割集，是的一棵生成树，
如果恰好含有的一个树枝，则称为的关于生成树的基本割集。
定理5.4.2 设是图的一棵生成树，的弦边包含在由树枝确定的基本割集中的充要条
件是树 枝包含在由弦确定的基本回路中。
定理5.4.3 设是图的基本割集组，那么线性无关。
.. .

..
定理5.4.4 图的任一断集可以表示成若干基本割集的环和。
定理5.4.5 图的关于生成树的基本割集组是的断集空间的一组基底。
定理5.4.6 阶连通图的断集空间的元素个数是
例5.4.1

P346
，这
（包含空集）.
定理8.2.1 设是一个连通平面图，并设有个顶点、条边，个面，则
就是著名的欧拉公式。
定理8.2.2 若是一个连通的
定理8.2.3若是一个连通的
定理8.2.4 是不可平面的。
定理8.2.5若连通的
定理8.2.6
平面图不含，则
图，则.
图，每个面的边界都是长为的回路，则
是不可平面的
定理8.2.7每个简单平面图包含一个其度数最多是的顶点。


.. .