1-1-1 命题 命题是一个能表达判断并具有确定真值的陈述句。
1-1-2 真值 作为命题的陈述句所表达的判断结果称为命题的真值。真值只有真和假两种，通常记为T 和F。真值为真的命题称为真命题，真值为假的命题称为假命题。真命题表达的判断正确，假命题表达的判断错误。任何命题的真值都是唯一的。
1-1-3 命题变项 用命题标识符（大写字母）来表示任意命题时，该命题标识符称为命题变项。
1-1-4 简单命题 无法继续分解的简单陈述句称为简单命题或原子命题。(不包含任何与、或、非一类联结词的命题)
1-1-5 复合命题 由一个或几个简单命题通过联结词复合所构成的新的命题，称为复合命题，也称分子命题。
1.2 命题联结词及真值表
1-2-1 命题联结词 命题联结词可将命题联结起来构成复杂的命题，是由已有命题定义新命题的基本方法。命题联结词又可分为一元命题联结词、二元命题联结词和多元命题联结词。常用的命题联结词包括否定词、合取词、析取词、蕴涵词和双条件词。其它联结词还包括异或（不可兼或）、与非和或非等。
1-2-2 否定词 否定词是一元命题联结词。设P为一命题，P的否定是一个新的命题，记作
P，读作非P。若P为T，
P为 T；若P为F，
P为T。
1-2-3 合取词 合取词是二元命题联结词。两个命题P和Q的合取构成一个新的命题，记作P∧Q 。读作P、Q的合取（或读作P与Q，P且Q）。当且仅当P、Q同时为T时，P∧Q 为T。 否则，P∧Q 的真值为F。
1-2-4 析取词 析取词是二元命题联结词。两个命题P和Q的析取构成一个新的命题，记作P∨Q。读作P、Q的析取（也读作P或Q）。当且仅当P、Q同时为F时，P∨Q的真值为F。否则，P∨Q的真值为T。
1-2-5 蕴涵词 蕴涵词是二元命题联结词。两个命题P和Q用蕴涵词“→”联结起来，构成一个新的命题，记作P→Q。读作如果P则Q，或读作P蕴涵Q。当且仅当P的真值为T，Q的真值为F时，P→Q的真值为F，否则P∨Q的真值为T。 1-2-6 双条件词 双条件词是二元命题联结词。两个命题P和Q用双条件“结起来，构成一个新的命题，记作P当P和Q的真值相同时，P1-2-7 命题的解释 设
Q的真值为T，否则P
Q的真值为F。
”联
Q。读作P当且仅当Q，或读作P等值Q。
是出现在命题A中的全部命题变项，给
各指定一个真值，称为对命题A的一个解释或一个赋值，命题的解
释用符号I表示。
1-2-8 真值表 在命题公式中，对于全部命题变项指定不同真值的所有可能的解释，确定了该命题公式的各种真值情形，把所有解释（赋值）下的取值情形列成表，称作命题公式的真值表。 1.3 合式公式
1-3-1 合式公式 将命题变项用联结词和圆括号按照一定的逻辑关系连接起来的符号串称为合式公式（Well Formed Formula）。当使用联结词集{
}中的联结词时，合式公式可归纳定义如下：
A）也是合式公式；
B）也是
(1)简单命题是合式公式； (2)若A是合式公式，则（合式公式；
(4)当且仅当经过有限次地使用（1）-（3）所形成的符号串才是合式公式。 合式公式也称为命题公式，并简称为公式。
1-3-2 联结词运算的优先级 由命题变项、命题联结词和圆括号组成命题逻辑的基本符号。本书约定的联结词运算的优先次序为：
个同一优先级的联结词，按照从左到右的次序，先出现者先运算。 1.4 重言式
1-4-1 重言式 如果一个命题公式，对于它的任一解释I下其对应的真值都为真，则称该命题公式为重言式或永真式。
1-4-2 矛盾式 如果一个命题公式，对于它的任一解释I下其对应的真值都为假，则称该命题公式为矛盾式或永假式，也称为不可满足式。 1-4-3 可满足式 一个命题公式，如存在某个解释
，在
下该公式真值为真，则
。多
(3)若A、B是合式公式，则（A∧B），（A∨B），（A∨B），（A
称该命题公式是可满足的。重言式是一类特殊的可满足式。
1-4-4 代入规则 一个重言式，对其中所有相同的命题变项都用一合式公式代换，其结果仍为一重言式。这一规则称为代入规则。换句话说，A是一个公式，对A使用代入规则得到公式B，若A是重言式，则B也是重言式。代入规则的具体要求为： 1.公式中被代换的只能是命题变项（原子命题），而不能是复合命题。 2.对公式中某命题变项施以代入，必须对该公式中出现的所有同一命题变项施以相同的代换。 1.5 命题形式化
1-5-1 异或（不可兼或）联结词 异或（又称不可兼或）词是二元命题联结词。两个命题P和Q的异或构成一个新的命题，记作P异时，P
Q。当且仅当P与Q的真值相
Q为T，否则PQ的真值为F。
2.1 等值定理
2-1-1 等值 给定两个命题公式A和B，设命题变项，则公式A和B共有
为出现于A和B中的所有
个解释，若在其中的任一解释下，公式A和B的
B。 B为一个重言
真值都相同，则称A和B是等值的（或称等价）记作A=B或A定理2-1-1 设A，B为两个命题公式，A=B的充分必要条件是A
式。 2.2 等值公式
2-2-1 逆命题 若将P→Q视为正命题，则称Q→P为它的逆命题。 2-2-2 否命题 若将P→Q视为正命题，则称2-2-3 逆否命题 若将P→Q视为正命题，则称为公式A的子公式。
2-2-5 置换规则 设X为公式A的子公式，用与X等值的公式Y将A中的X施以代换，称为置换，该规则称为置换规则。置换后公式A化为公式B，置换规则的性质保证公式A与公式B等值，即A=B。且当A是重言式时，置换后的公式B也是重言式。
2-2-6 基本的等值公式（命题定律） 1． 双重否定律 2． 结合律
P→Q→
Q为它的否命题。 P为它的逆否命题。
2-2-4 子公式 若X是合式公式A的一部分，且X本身也是一个合式公式，则称X
3． 交换律
4． 分配律
5． 等幂律（恒等律）
6． 吸收律
7． 摩根（De Morgan）律
对蕴涵词，双条件词作否定有
8． 同一律
还有
9． 零律
还有
10． 补余律
还有
2.3 命题公式与真值表的关系 对任一依赖于命题变元
的命题公式A来说，可由
到A的真值表。
的真值根据命题公式A给出A的真值，从而建立起由因此由命题公式列写真值表的过程是相对容易的。
反之，若给定了由式A对
到A的真值表，可以用下述方法写出命题公
的逻辑表达式。
1．从取T 的行来列写 看A的真值表中取T 的行，若取T 的行数共有m行，则命题公式A可以表示成如下形式： 其中
=
，则
，，若
或，则
。
若该行的
2．从取F 的行来列写 看A的真值表中取F的行，若取F的行数共有k行，则命题公式A可以表示成如下形式： 其中 若该行的
，则
，，若
或，则
。
2.4 联结词的完备集
2-4-1 与非联结词 与非词是二元命题联结词。两个命题P和Q用与非词“↑”联结起来，构成一个新的复合命题，记作P↑Q。读作P和Q的“与非”。当且仅当P和Q的真值都是T 时，P↑Q的真值为F，否则P↑Q的真值为T 。P↑Q
。
2-4-2 或非联结词 或非词是二元命题联结词。两个命题P和Q用或非词“↓”联结起来，构成一个新的复合命题，记作P↓Q。读作P和Q的“或非”。当且仅当P和Q的真值都为F时，P↓Q的真值为T，否则P↓Q的真值为F。P↓Q
。
2-4-3 真值函项 对所有的合式公式加以分类，将等值的公式视为同一类，从中选一个作代表称之为真值函项。对一个真值函项就有一个联结词与之对应。 2-4-4 联结词的完备集 设C是一个联结词的集合，如果任何n元
真值函项
都可以由仅含C中的联结词构成的公式表示，则称C是完备的联结词集合，或说C是联结词的完备集。 2.5 对偶式
2-5-1 对偶式 将给定的命题公式A中出现的得到公式
，则称
是公式A的对偶式，或说A和
分别以互为对偶式。
代换，
在以下定理2.5.1至定理2.5.6中，
记定理2.5.1定理2.5.2定理2.5.3定理2.5.4 若定理2.5.5 若定理2.5.6 A与2.6 范式
永真，必有同永真，同可满足；
永真。 与
同永真，同可满足。
2-6-1 文字与互补对 命题变项P及其否定式对。
P统称文字。且P与P称为互补
2-6-2 合取式 由文字的合取所组成的公式称为合取式。 2-6-3 析取式 由文字的析取所组成的公式称为析取式。 2-6-4 析取范式 析取范式是形如
的公式，其中
为合取式。
2-6-5 合取范式 合取范式是形如
的公式，其中
为析取式。
2-6-6 范式存在定理 任一命题公式都存在与之等值的合取范式和析取范式。但命题公式的合取范式和析取范式不是唯一的。 2-6-7 极小项 n个命题变项 其中
或
。即每个命题变项与它的否定式不同时出现，但
为极小项，并以
组成的合取式
二者之一必出现且仅出现一次。则称合取式 表示。
2-6-8 极大项 n个命题变项
组成的析取式
其中
或
。即每个命题变项与它的否定式不同时出现，但
为极大项，并以
二者之一必出现且仅出现一次。则称析取式 表示。
2-6-9 主析取范式 设由n个命题变项构成的析取范式中所有的合取式都是极小项，则称该析取范式为主析取范式。（仅由极小项构成的析取范式称为主析取范式）。 2-6-10 主合取范式 设由n个命题变项构成的合取范式中所有的析取式都是极大项，则称该合取范式为主合取范式。（仅由极大项构成的合取范式称为主合取范式）。 2-6-11 主析取范式定理 任一含有n个命题变项的公式，都存在唯一的与之等值的且恰仅含这 个命题变项的主析取范式。
2-6-12 主合取范式定理 任一含有n个命题变项的公式，都存在唯一的与之等值的且恰仅含这 个命题变项的主合取范式。 2-6-13 极小项的性质
（1） 任一含有n个命题变项的公式，所有可能的极小项的个数和该公式的解释个数相同，都是2n 。
（2） 每个极小项只在一个解释下为真。 （3） 极小项两两不等值，并且
（4） 任一含有n个命题变项的公式，都可由k个（5） 恰由2n 个极小项的析取构成的公式必为重言式。即
。
极小项的析取来表示。
2-6-14 极大项的性质
（1） 任一含有n个命题变项的公式，所有可能的极大项的个数和该公式的解释个数相同，都是2n。
（2） 每个极大项只在一个解释下为假。 （3） 极大项两两不等值，并且
（4） 任一含有n个命题变项的公式，都可由k个（5） 恰由2n个极大项的合取构成的公式必为矛盾式。即
。
极大项的合取来表示。
2.7 推理形式
2-7-1 推理形式 将以自然语句描述的推理关系引入符号，抽象化并以条件式的形式表示出来便得到推理形式，推理形式由前提和结论部分组成。前提真，结论必真
的推理形式为正确的推理形式。
2-7-2 重言蕴涵 给定两个公式A,B如果当A取值为真时，B就必取值为真，便称A重言（永真）蕴涵B。或称B是A的逻辑推论。并用符号
表示。
2-7-3 重言蕴涵的几个结果 （1） 如果（2） 若（3） 若（4） 若（5） 若
且且且且
成立，若A为重言式则B也是重言式。
同时成立，必有同时成立，则有同时成立，则有同时成立，则有
。反之亦然。 。
。 。
2.8 基本的推理公式 定理2.8.1 定理2.8.2
成立的充分必要条件是成立的充分必要条件是
为重言式。 是矛盾式。
2-8-1 基本的推理公式
2.9 推理演算
2-9-1 使用推理规则的推理演算方法 从前提
几条推理规则和基本的推理公式，逐步推演出结论B。 2-9-2 基本推理规则
（1） 前提引入规则 在推理过程中，可以随时引入前提。
（2） 结论引入规则 在推理过程中所得到的中间结论，可作为后续推理的前提。 （3） 代入规则 在推理过程中，对重言式中的命题变项可使用代入规则。 （4） 置换规则 在推理过程中，命题公式中的任何子公式都可以用与之等值的命题公式来置换。
（5） 分离规则（假言推理） 若已知命题公式2.10 归结推理法
2-10-1 归结法 归结法是仅用一条归结推理规则的机械推理法，是机器定理证明的重要方法。
2-10-2 归结证明过程 1．为证明2．从
是重言式，依定理2.8.2，等价于证明出发，建立子句集S：先将
是矛盾式。
和A成立，则有命题公式B。
出发，通过使用引入的
化成合取范式，进而由所有子句
（析取式）构成子句集S。
3．对S中的子句作归结（消互补对），并将归结式仍放入S中。重复该过程。 4．直至归结出空子句（矛盾式）。 2-10-3 归结推理规则 1．归结式的定义 设
，
称作
为两个子句，有互补对L和的归结式。
L。则新子句
归结过程就是对S的子句求归结式的过程。
2．可以证明。于是归结式是子句的逻辑
推论，从而归结是正确的推理规则。
3.1 公理系统的结构
3-1-1 公理系统 从一些公理出发，根据演绎规则推导出一系列定理，这样形成的演绎体系叫做公理系统，或称作理论。命题演算的重言式可组成一个严谨的公理系统，它是从一些作为初始命题的重言式（公理）出发，应用明确规定的推理规则，进而推导出一系列重言式（定理）的演绎体系。命题逻辑的公理系统是一个抽象符号系统，不再涉及到真值。
3-1-2 公理系统的结构 一个公理系统通常包括以下几个部分： 1．初始符号 公理系统内允许出现的全体符号的集合。
2．形成规则 公理系统内允许出现的合法符号序列的形成方法与规则。 3．公理 精选的最基本的重言式，作为推演其它所有重言式的依据。 4．变形规则 公理系统所规定的推理规则。
5．建立定理 公理系统所作演算的主要内容，包括所有的重言式和对它们的证明。 3.2 命题逻辑的公理系统
3-2-1 罗素（Russell）公理系统 罗素公理系统由以下几部分组成： 1．初始符号
大写英文字母（表示命题）
（表示联结词） （ ） （圆括号）
┣ （断言符，写在公式前，如┣2．形成规则 （1） 符号（2） 若（3） 若
是合式公式（
取值为
）。
是合式公式。
是合式公式。
表示
是所要肯定的，或说
是重言式）
是合式公式，则是合式公式，则
（4） 只有符合（1）（2）（3）的符号序列才是合式公式。 3．定义 1．2．3．4．公理
定义为定义为定义为
。 。
公理1 ┣公理2 ┣公理3 ┣公理4 ┣
5．变形（推理）规则
1．代入规则 如果┣合式公式
）。
，那么┣（将合式公式中出现的符号处处都代以
2．分离规则 如果┣，┣那么┣。
，替换后为
，则如果┣
，
3．置换规则 定义的左右两方可互相替换。设公式那么┣
。
6．定理的推演
定理的证明必须依据公理或已证明的定理，同时证明的过程（符号的变换过程）必须依据变形规则。
3.3 公理系统的完备性和演绎定理
3-3-1 公理系统的完备性 公理系统的完备性是指，是否所有的重言式或所有成立的定理都可由所建立的公理系统推导出来。形象地说，完备性是指所建立的系统所能推演出的定理少不少。
3-3-2 公理系统的可靠性 公理系统的可靠性是指，非重言式或者不成立的定理是否也可由所建立的公理系统推导出来。形象地说，可靠性是指所建立的系统所能推演出的定理多不多。不具备可靠性的系统是不能使用的。
3-3-3 演绎定理 在命题逻辑的公理系统中，在有前提的推理下，如果从前提推出公式
，而推理过程又不使用变项的代入，那么┣
成立。
可
3.4 命题逻辑的另一公理系统——王浩算法
3-4-1 王浩算法—定理证明自动化系统 王浩算法是利用计算机来实现定理证明的机械化方法，由美籍华裔科学家王浩于1959年提出。作为命题逻辑的一个公理系统，其结构组成与罗素系统类似，下面重点给出与罗素系统的主要差别： （1） 初始符合中的联结词扩充为5个常用联结词，分别是便描述推理规则和公理，引入公式串（2） 定义了相继式。即，如果
和
。
都是公式串，则称
是相继式。其中
；为方
为前件，为后件；
是公理（为真）的充分必要条件是
和
中至少含
（3） 公理只有一条：
有一个相同的命题变项；
（4） 变形（推理）规则共有10条，分别为5条前件规则和5条后件规则； （5） 定理推演的过程将所要证明的定理写成相继式形式，然后反复使用变形规则，消去全部联结词以得到一个或多个无联结词的相继式。若所有无联结词的相继式都是公理，则定理得证，否则定理不成立。 3.5 命题逻辑的自然演绎系统
3-5-1 自然演绎系统 自然演绎系统也是一种逻辑演算体系，与公理系统的明显区别在于它的出发点只是一些变形规则而没有公理，是附有前提的推理系统。自然演绎系统可导出公理系统的所有定理，同时自然演绎系统的所有定理也可由重言式来描述，从而可由公理系统导出。
3-5-2 自然演绎系统示例 以下给出一个简单的自然演绎系统： 1．初始符合 除罗素公理系统所使用的符号外，引入
表示有限个命题公式的集合。提（集合），
┣
表示
，
间有形式推理关系，
得
。
为形式前
为形式结论，或说使用推理规则可由
2．形成规则 与罗素公理系统相同。 3．变形规则 共有5条变形规则： （1）肯定前提律 为结论。 （2）传递律 如果（3）反证律 如果又假设
┣，
，┣┣
则 且
，┣
。 ┣
，则推出
┣。
。在前提
下，
┣
，前提中任何命题均可作
是假的，若可推出矛盾命题时，便可由前提
┣
则
┣那么
。
（4）蕴涵词消去律（分离规则）（5）蕴涵词引入律 如果可得
。那么在原前提
，┣
。在前提。
下，又知为真，
下可推得，如果
4．定理的证明 定理的证明中不涉及公理，而将前提作为条件，使用推理规则进行推演，推演过程较使用公理的情形来得容易。 3.6 非标准逻辑
3-6-1 非标准逻辑 前面的命题逻辑通常称作标准（古典）的命题逻辑，而除此之外的命题逻辑可统称作非标准逻辑。其中一类是与古典逻辑有相违背之处的非标准
逻辑，如多值逻辑，模糊逻辑等。另一类是古典逻辑的扩充，如模态逻辑，时态逻辑等。
3-6-2 多值逻辑 在古典命题逻辑中，命题定义的取值范围仅限于真和假两种，故又称作二值逻辑。多值逻辑将命题定义的取值范围推广到可取多个值，因此，多值逻辑是普通二值逻辑的推广，并在此基础上研究如何给出各种取值含义的解释以及命题运算规律是否保持等问题。已有的多值逻辑研究以三值逻辑为主，具有代表性的包括Kleene逻辑（1952），Lukasiewicz逻辑（1920），Bochvar逻辑（1939）等。
3-6-3 模态逻辑 考虑必然性和可能性的逻辑是模态逻辑。引入“可能的世界”作为参量（条件），必然真表示所有可能的世界下为真，而可能真表示在现实世界下为真，不要求所有可能的世界下为真。存在的问题是可能的世界如何描述还有待研究。有一种观点认为，命题逻辑是用来描述永恒或绝对真理的，模态逻辑和谓词逻辑则是描述非永恒或相对真理的。
3-6-4 不确定性推理与非单调逻辑 不确定性推理与非单调逻辑是人工智能系统中经常使用的知识表示和推理方法。首先，标准逻辑是单调的。一个正确的公理加到理论
中得到理论
，
。如果
┣
必有
┣
。即随着条件的增加，
中，有时反
所得结论也必然增加。而对于非单调逻辑，一个正确的公理加到理论而会使预先所得到的一些结论失效。
4.1 谓词和个体词
4-1-1 个体词（ 主词） 个体词是指所研究对象中可以存在的具体的或抽象的客体。在一个命题中，个体词通常是表示思维对象的词, 又称作主词。
4-1-2 个体常项与个体变项 将表示具体或特定客体的个体词称作个体常项，用小写字母
表示，而将表示抽象或泛指的个体词称作个体变项，用小写字母表示。并称个体变项的取值范围为个体域或论域，以D表示。并约定有
一个特殊的个体域，它由世间一切事物组成，称之为总论域。
4-1-3 谓词 谓词是用来刻划个体词的性质或多个个体词间关系的词。谓词又可看作是给定的个体域到集合
上的一个映射。
4-1-4 谓词常项与谓词变项 表示具体性质或关系的谓词称作谓词常项，表示抽象或泛指的性质或关系的谓词称作谓词变项。谓词常项与谓词变项都用大写英文字母
表示，可根据上下文区分。
4-1-5 一元与多元谓词 在一个命题中，如果个体词只有一个，这时表示该个体词性质或属性的词便是一元谓词，以P(x)，Q(x),Λ表示。如果一个命题中的个体词多于一个，那么表示这几个个体 词间关系的词便是多元谓词，以P(x,y),Q(x,y,z),Λ等表示。一般地，用P(α)表示个体常项α具有性质P，用P(x)表示个体变项χ具有性质P 。用P(α,b)表示个体常项α,b具有关系P 用P(x,y)表示个体变项x,y具有关系
P 。更一般地，用元谓词。
表示含个命题变项的n
4-1-6 谓词逻辑与命题逻辑 谓词逻辑是命题逻辑的推广，命题逻辑是谓词逻辑的特殊情形。有时将不带个体变项的谓词称作零元谓词。当此时的零元谓词又为谓词常项时，零元谓词即化为命题。因此，命题逻辑中的命题均可以表示成零元谓词，或认为一个命题是没有个体变项的零元谓词。 4.2 函数和量词
4-2-1 谓词逻辑中的函数 在谓词逻辑中可引入函数，它是某一个体域（不必是实数）到另一个体域的映射。谓词逻辑中的函数不单独使用，而是嵌入在谓词中。约定函数符号用小写字母表示。
4-2-2 量词 表示个体常项或变项之间数量关系的词称为量词。也可将量词看作是对个体词所加的或约束的词。一般将量词分为全称量词和存在量词两种。 4-2-3 全称量词 日常生活和数学中常用的“所有的”，“一切的”，“任意的”，“每一个”，“凡”等词可统称为全称量词，将它们符号化为体域中所有的个体。用质P 和性质Q 。
4-2-4 存在量词 日常生活和数学中常用的“存在一个”，“有一个”，“有些”，“有的”等词可统称为存在量词，将它们符号化为的个体。用
在个体具有性质Q。
4-2-5 约束变元与自由变元 量词所约束的范围称为量词的辖域。在公式
中，A为相应量词的辖域。在
和
和
并用
等表示个体域中有
，并用
等表示个
等分别表示个体域中所有个体都有性
等分别表示在个体域中存在个体具有性质P，存
的辖域中，x 的所有出现都称为
约束出现，所有约束出现的变元称为约束变元。A中不是约束出现的其它变元均称为自由变元。 4.3 合式公式
4-3-1 一阶谓词逻辑 在所讨论的谓词逻辑中，限定量词仅作用于个体变项，不允许量词作用于命题变项和谓词变项，也不讨论谓词的谓词。在这样的限定范围内的谓词逻辑称为一阶谓词逻辑。一阶谓词逻辑是相对于高阶谓词逻辑而言的。 4-3-2 一阶谓词逻辑的符号集 1．个体常项：2．个体变项：3．命题变项：
（小写字母）。 （小写字母）。 （小写字母）。
4．谓词符号：5．函数符号：6．联结词符号：7．量词符号：
。
（大写字母）。 （小写字母）。
。
8．括号与逗号：（ ）， ， 。 4-3-3 合式公式定义：
1． 命题常项、命题变项、和原子谓词公式（不含联结词的谓词公式）是合式公式。 2． 若A是合式公式，则3． 若A,B是合式公式，则A式公式。
4． 若A是合式公式，则
,
也是合式公式。
也是合式公式。
，
也是合
5． 只有有限次地应用（1）-（4）构成的符号串才是合式公式。 谓词逻辑中的合式公式也称为谓词公式，简称公式。 4.4 自然语句的形式化
4-4-1 对谓词变元多次量化的分析 1．2．3．4．5．
4.5 有限域下公式的表示法
4-5-1 有限域下全称量词和存在量词的表示 将论域限定为有限集，不失一般性，用量词可化为如下公式：
因此可以说，全称量词
是合取词
的推广，存在量词是析取词
的推广。
来表示，这时全称量词和存在
4.6 公式的普遍有效性和判定问题
4-6-1 普遍有效公式 设A为一个谓词公式，若A在任何解释下真值均为真，则称A为普遍有效的公式。
4-6-2 不可满足公式 设A为一个谓词公式，若A在任何解释下真值均为假，则称A为不可满足的公式。
4-6-3 可满足公式 设A为一个谓词公式，若至少存在一个解释使A为真，则称A为可满足的公式。普遍有效的公式一定是可满足的公式。
4-6-4 有限域上公式普遍有效性的几个结论 有限域上一个公式的可满足性和普遍有效性依赖于个体域个体的个数。即在某个含个元素的个体域上普遍有效（或可满足），则在任一个体域上也普遍有效（或可满足）。 如果某公式在个体域上普遍有效，则在如果某公式在个体域上可满足，则在
个体域上也普遍有效。 个体域上也可满足。
4-6-5 谓词逻辑的判定问题 谓词逻辑的判定问题，指的是任一公式的普遍有效性的判定问题。若说谓词逻辑是可判定的，就要求给出一个能行的方法，使得对任一谓词公式都能判定是否是普遍有效的。 4-6-6 谓词逻辑的判定问题的几个结论
1． 一阶谓词逻辑是不可判定的。对任一谓词公式而言，没有一个能行的方法判明它是否是普遍有效的。
2． 一阶谓词逻辑的某些子类是可判定的。其中包括： （1）只含有一元谓词变项的公式是可判定的。 （2）
和
型公式，若P 中无量词和其它自由变项也
是可判定的。
（3） 个体域有穷时的谓词公式是可判定的。
5.1 否定型等值式
5-1-1 等值 设A，B是一阶谓词逻辑中任意两个公式，若A式，则称A与B 等值，记作A=B或5-1-2 否定型等值式
。
B是普遍有效的公
5.2 量词分配等值式
5-2-1 量词对析取词、合取词的分配律
其中是命题变项，与个体变元无关。 5-2-2 量词对蕴涵词的分配律
其中,是命题变项，与个体变元无关。 5-2-3 全称量词
对，存在量词对
的分配律
5-2-4 变元易名与
对
，对的分配等值式
5.3 范式
5-3-1 前束范式 设A 为一个一阶谓词逻辑公式，如果A 中的所有量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到整个公式的末端，则称A 为前束范式。前束范式的一般形式为
其中
为
或，M 为不含量词的公式，称作公式A 的基式或母式。
5-3-2 前束范式存在定理 一阶谓词逻辑的任一公式都存在与之等值的前束范式，但其前束范式并不唯一。 5-3-3 化前束范式的基本步骤： 1． 消去联结词 →，2． 右移否定词
。
（利用否定型等值式与摩根律）。
3． 量词左移（使用量词分配等值式）。 4． 变元易名（使用变元易名分配等值式）。
5-3-4 SKOLEM标准型 一阶谓词逻辑的任一公式A，若其前束范式中所有的存在量词都在全称量词的左边，或是仅保留全称量词而消去存在量词，便得到公式A 的SKOLEM标准型。公式A 与其SKOLEM标准型只能保持某种意义下的等值关系。
5-3-5 前束范式 一阶谓词逻辑的任一公式A 的前束范式（或称SKOLEM标准
型） 的形式为
即所有的存在量词都在全称量词的左边，且应保证至少有一个存在量词（同时
中不含量词也无自由个体变项。
），
5-3-6 前束范式存在定理 一阶谓词逻辑的任一公式A 都存在与之等值的 前束范式，并且A 是普遍有效的当且仅当其 前束范式是普遍有效的。 5-3-7
前束范式 一阶谓词逻辑的任一公式A 的
前束范式（或称SKOLEM标
准型）是仅保留全称量词的前束范式。 5-3-8
前束范式存在定理 一阶谓词逻辑的任一公式A 都可化成相应的
前束
范式（仅保留全称量词的前束范式，或称SKOLEM标准型），并且A 是不可满足的当且仅当其
前束范式是不可满足的。
5.4 基本推理公式
5-4-1 一阶谓词逻辑的推理形式和推理公式 在一阶谓词逻辑中，从前提
出发推出结论B 的推理形式结构，依然采用如下的蕴涵式形式：
若上式为永真式，则称推理正确，否则称推理不正确。于是，在一阶谓词逻辑中判断推理是否正确便归结为判断上式是否为永真式，并称满足永真式的蕴涵式为推理公式，用如下形式的符号表示
5-4-2 基本推理公式 1．2．3．4．5．
6．7．8．9．10．5.5 推理演算
5-5-1 谓词逻辑中使用推理规则的推理演算方法 在命题逻辑中，由引入几条推理规则，配合基本推理公式所进行的推理演算方法，可以容易地推广到谓词逻辑中。事实上，由于在谓词逻辑中不能使用真值表法，又不存在判别A →B 是普遍有效的一般方法，从而使用推理规则的推理方法已成为谓词逻辑的基本推理演算方法。所使用的推理规则除命题逻辑的推理演算中用到的六条基本推理规则外（参见2.9节），还包括四条有关量词的消去和引入规则。 5-5-2 全称量词消去规则（简记为UI规则或UI）
两式成立的条件是：
（1） 第一式中，取代 的 应为任意的不在（2） 第二式中，C 为任意个体常项。 （3）用 或 C 去取代方进行取代。
5-5-3 全称量词引入规则（简记为UG规则或UG）
中自由出现的 时，必须在 自由出现的一切地
中约束出现的个体变项。
该式成立的条件是： （1） 无论
中自由出现的个体变项 取何值，
应该均为真。
（2）取代自由出现的 的 也不能在 中约束出现。
5-5-4 存在量词消去规则（简记为EI规则或EI）
该式成立的条件是：
（1） C 是使P 为真的特定的个体常项。
（2） C 不在（3）
中出现。
中没有其它自由出现的个体变项。
5-5-5 存在量词引入规则（简记为EG规则或EG）
该式成立的条件是： （1） C是特定的个体常项。 （2）取代C 的 不在
中出现过。
5-5-6 使用推理规则的推理演算过程 首先将以自然语句表示的推理问题引入谓词加以形式化，若不能直接使用基本的推理公式则消去量词，在无量词下使用规则和公式推理，最后再引入量词以求得结论。 5.6 谓词逻辑的归结推理法
5-6-1 谓词逻辑的归结推理法 命题逻辑中的归结推理法可以推广到谓词逻辑中。其证明过程与命题逻辑相似。所不同的是需对谓词逻辑中的量词和变元进行特殊的处理。
5-6-2 归结推理法步骤 1． 欲证矛盾式。
2． 将G 化为前束范式。进而化为SKOLEM标准型。消去存在量词，得到仅含全称量词的前束范式
（由于全称量词的前束范式保持不可满足的特性，故G 与
是定理，等价于证
是
在不可满足的意义下是一致的）。 3． 略去集
中的全称量词，
中的合取词 以“，”表示，便得到 与
的子句集。
的子句
。实用中可分别求出诸
4． 对 作归结。直至归结出空子句□。 归结举例：设换
是两个无共同变元的子句，如下式。
与
在置
。
下将变元 换成，构成互补对可进行归结。得到归结式
6.1 谓词逻辑的公理系统
6-1-1 谓词逻辑的公理系统 谓词逻辑的公理系统是从一些公理（普遍有效式）出发，使用推理规则建立起一系列定理（普遍有效式）的完整体系，所建立的公理系统是完全形式化的理论体系。
6-1-2 公理系统的构成 一个谓词逻辑的公理系统通常包括以下几个部分： 1． 初始符号 公理系统内允许出现的全体符号的集合。
2． 形成规则 公理系统内允许出现的合法符号序列的形成方法与规则。 3． 定义 除形成规则构成的合式公式外所引入的新的合式公式。 4． 公理 精选的最基本的普遍有效式，作为推演其它所有定理的依据。 5． 变形规则 公理系统所规定的推理规则。
6． 定理的推演 从公理出发，使用推理规则建立所有的定理。
6-1-3 谓词逻辑公理系统举例 该公理系统是建立在第三章介绍的命题逻辑公理系统之上的。且该公理系统不会出现 逻辑矛盾，在语义上是完备的。 1． 初始符号
命题变项：以小写字母，，个体变项：以小写字母，谓词变项：以大写英文字母命题联结词：量词：
，
，
表示； 表示； 表示；
括号和逗点： （ ） ， 2． 形成规则
（1） 命题变项是合式公式， 如，。 （2） 谓词变项如
，
，是合式公式。
（3） 若X，Y是合式公式，且无一个体变项在二者之一中是约束的但在另一个中是自由的，则是合式公式。
（4） 若X 是合式公式，且Δ 是X 中的自由个体变项，则式公式。
（5） 只有满足以上五条的才是合式公式。
是合
3． 定义 1． 2． 3． A4． 公理
定义为定义为B 定义为
5． 变形（推理）规则
（1）代入规则 包括命题变项，自由个体变项和谓词变项的代入（要求保持合式 公式和普遍有效性不被破坏）。
（2）分离规则 如果┣A 和┣A→B 可得┣B 。 （3）置换规则 定义的左右两方可相互替换。 （4）约束个体易名规则 公式A 中的一个约束个体变项（5）后件概括规则 如果┣
（6）前件存在规则 如果┣6． 定理的推演
定理的证明必须依据公理或已证明的定理，同时证明的过程（符号的变换过程）必须依据变形规则。
6-1-4 谓词逻辑公理系统的完备性 谓词逻辑公理系统的完备性是指，任一普遍有效的谓词公式，在该公理系统中是否都可以得到证明。谓词逻辑公理系统的完备性较命题逻辑的公理系统完备性证明复杂得多，1929年首先由Godel给出了谓词逻辑公理系统完备性的证明，随后又有一些不同的证明方法。
6-1-5 谓词逻辑公理系统的完备性定理 谓词逻辑任一普遍有效的公式，都是可以证明的。该定理也可描述为，在谓词逻辑中，对于任一公式A ，或者A 是可以证明的，或者
A 是可满足的。
6-1-6 演绎定理 在谓词逻辑的公理系统中，如果从前提A 经使用推理规则得B ，而在推理过程中又不使用代入规则、前件存在规则和后件概括规则时，只要A→B 是合式公式，必有┣A→B 成立。 6.2 谓词逻辑的自然演绎系统
6-2-1 谓词逻辑的自然演绎系统 自然演绎系统是由已给的前提（而不是公理）出
，且Δ在B 中不出现，则┣
，可由另一个体变项
替换。
，且Δ 在A 中不出现，则┣
发，使用变形规则来推导出所要求的结论。从而自然演绎系统不设立公理，是有前提的推理体系。
6-2-2 自然演绎系统的构成 下面是一个简单的自然演绎系统的基本构成： 1． 初始符号 除6.1公理系统所使用的符号外，引入
表示有限个公式的集合。 Γ┣A 表示Γ，A ，间有形式推理关系， Γ为形式前提（集合），A为形式结论，或说使用推理规则可由Γ得?/font>A 。 2． 形成规则 同6.1公理系统形成规则和定义 3． 变形规则 共有15条变形规则， 参见教材6.2节。 4． 定理 该系统可推演出6.1公理系统的所有定理。
所建立的自然演绎系统同节6.1的公理系统是等价的，凡自然演绎系统的定理都可由 公理系统来证明，反之公理系统的定理也可由自然演绎系统来证明。 6.3 递归函数
6-3-1 Turing机 Turing机是由英国数学家Turing于1936年提出的一种可计算的模型。它是一个结构非常简单但功能又十分强大的理想计算机，在一定程度上反映了人类最基本的原始的计算能力。Turing机以一条无限长的带（可读写）为存储器，处理的符号以二值逻辑表示。指令共六条，写1、写0、右移、左移、遇1转移和遇0转移，相当于运算器控制器。这个计算机可实现当今计算机的功能，是计算机的理论模型。与今日的计算机相比主要区别是有无限的存储能力，但效率十分之低。正是Turing机模型推动了1946年第一台电子计算机的诞生。
6-3-2 可计算性 凡Turing机可做的都是可计算，凡Turing机可计算的就叫做可计算的。可计算的与直觉实际上的可计算是有区别的。一个Turing机可计算的不一定是实际上可计算的；而Turing机不可计算的必为实际不可计算。
6-3-3 递归函数 递归函数是数论函数，即以自然数为研究对象，定义域和值域均是自然数。递归函数是一种构造性函数，不只限于存在性（非构造性）的讨论。给出一个递归函数，相当于给该函数一个计算的算法。一般而言，由初始函数经有限次代入和原始（一般）递归规则所得到的函数叫做原始（一般）递归函数。递归函数就是由几个初始函数出发，通过代入和递归规则（变换）来建立的。 6-3-4 可计算性与递归函数 Turing机可计算的函数必是递归函数，反之递归函数必是Turing机可计算的，它们是等同的概念。
7.1 一阶语言及一阶理论
7-1-1 一阶语言 一阶语言的理论是十九世纪末二十世纪初数学形式化的产物。一个一阶语言由字符表、形成规则、公式（既按形成规则构成的字符串）组成。 7-1-2 一阶语言与一阶理论 以 L 表示一个一阶语言，L 将由以下的各部分组成： 1. 字符表
(1) 个体变元 x,y,z,… 或者 x1, x2, x3 , … (2) 常项变元 a,b,c, … 或者 c1, c2,c3, …
(3) 函词符号 F1, F2, …, Fn ( 函词符号集可以是一个无穷的集合) (4) 谓词符号 P1,P2,…,Pm （谓词符号集也可以是一个无穷的集合）
(5) 特殊谓词 = （ 等号 (6) 逻辑联结词 (7) 量词
，
(8) 括号 ( , )
说明 每一个函词符号，或者谓词符号都带一个预先设置好的整数 k > 0 , 称为该函词（谓 词）的变目个数。若 F 的预设整数 k = 2, 则 F 是一个二元函词。若 P 的预设整数 k = 1, 则 P 是一个一元谓词。有些一阶语言不带函词。 2. 形成规则 (1) 项的形成规则
(i) 任一个体变元 x , 任一常项 c 都是一个项。 (ii) 若 F 是一个带 k 个变目的函词，项。
(iii) 只有由定义 (i) ,(ii) 归纳定义得到的字符串是项。 (2)公式的形成规则
(i) F 是一个 k 目函词， (ii) P 是一个 k 目谓词， (iii) A, B 是公式，则
(iv) A 是公式，x 是一变元，则 x A ,
是项，则 是项， 则
是一公式。
是一公式。 是公式。
x A 是公式。
是项，则
是一个
(v) 仅由 (1) - (iv) 归纳定义得到的字符串是公式。
3. 语句的定义 公式 A 是一个语句，如果 A 中不含任何变元的自由出现。（见 4.2.3.）
4. 给定一阶语言 L , T 是一个一阶理论，如果它包括： （１） 谓词演算的所有公理。
（２） 一个 L 中的语句组成的集合，有穷或者无穷。它们称为非逻辑公理。 （３） 谓词演算的所有推理规则。 5. 定理的定义
L 中的一个语句 A 是理论 T 的一个定理，如果 A 是4中(1)或 (2)语句，或者是以逻辑公理或非逻辑公理为前提，使用 T 的推理规则得到的语句。 7.2 结构、赋值及模型
7-2-1 一阶语言的结构 给定一阶语言 L , 其中的函词及谓词分别为
；
，L 的结构是一个数学结构
，满足：
（１）U 是一个非空集合，有穷或者无穷。
（２）对应于 L 的每一个函词符号 Fj , Fj 是 k 目函词，则 fj 是 A 上的一个 k
元函数。
（３）对应于 L 的每一个谓词符号 Pj , Pj 是 k 目谓词，则 Rj 是 A 上的一个k 元关系。
L 在结构 M 上的一个赋值 I 由以下个映射组成：
(1)L 的常项符号集合 C 到集合 A 的一个影射 r : C →A 。如果对所有常项
c 在 A 中出现，我们以 r( c ) 置换 c 在 A 中的所有出现，这个置换称为 r-置换。 Ar 将表示由 A 通过 r-置换所得到的以 A 为论域的公式。 (2)L 的语句到 {0,1} 集合的一个映射（记为 I ）归纳定义如下： (i)中成立。 (ii) (iii) (iv)
当且仅当
当且仅当 I (A) = 0 。
当且仅当 I (A) = 1 或者I (B) = 1 。对的定义类似。
(v) (vi)立 。
令 T 是一阶理论，L 是 T 的语言，L 的一个结构 M , 一个赋值 I 组成的序对 < M, I> 是 T 的一个模型， 如果对所有 T 的非逻辑公理 A ,I(A) = 1， 通常记为 M │= A 。为表示 M 在某一赋值下是 T 的模型， 也写成 M │= T 。 7.3 理论与模型的基本关系 ---- 完全性定理
7-3-1 理论 T 是协调的（语法定义） 一个理论 T 是协调的，如果对任一语句 A , T│- A 及 T│-
A 不可能同时成立。
紧致性定理 T 是协调的，当且仅当 T 的任一有穷子集合是协调的。
7-3-2 理论 T 是协调的（语义定义） 一个理论 T 是协调的，如果它有一个模型 M , M│= T 。该定义与定义7-3-1是等价的。
定理7.3.1 一阶理论 T 在语法上是协调的，当且仅当 T 有一个模型。
该证明是一阶形式理论发展史上的一个里程碑。它的证明思想为以后几十年计算机程序理论的形式语义学奠定了基础。证明的主要思想是所谓的\"项模型\"方法：在 T （语法上的）协调的前提下，通过语法运作，将语句集合本身看作模型，或者引入新的常项变元代替语句，由所有的常项变元（原有的及新引入的）组成论域，定义论域上的相应函数及关系，从而得到 T 的一个模型。证明过程需要建立以下几个
当且仅当 存在 A 中的元素 c , 使当且仅当 对所有 A 中的元素 a , 使
在 M 中成立 。 在 M 中皆成在 M 中成立。
当且仅当
在 M
引理。
引理 1 如果 T 是协调的， A 是任一语句，一个是协调的。
引理 2 如果 T 是协调的，T 中的任一语句都不含量词符号，则 T 有一个模型。 引理 3 若 T 是协调的，则
也是协调的。
或者
其中至少有
上述定理的证明方法由Henkin 创建。
7-3-3 Godel 完全性定理 T 是一阶理论，A 是任一语句，T│- A 当且仅当 A 在所有 T 的模型中都成立。
7-3-4 紧致性定理的语义形式 任一一阶理论 T，如果它的任意有穷子集合有模型，则 T 有一个模型。
7.4 Lowenheim-Skolem 定理及 Herbrand 方法
一阶语言 L 的基数定义为 L 的符号集合的基数，记为 │L│ 。该节仅限于讨论 │L│≤ω 的情形，令 T 是语言 L 上的一阶理论。
7-4-1 Lowenheim-Skolem 定理 如果 T 有一个无穷模型，则 T 有一个基数 ≤ω的模型，即该模型或者是有穷的，或者是可数无穷的。
谓词演算的一个公式 A 是不可满足的，如果它没有任何模型，或者说它是矛盾的。Herbrand 方法就是判定一个公式 A 是否不协调的、非确定性的算法。
7-4-2 Herbrand 域 设 A 是 L 的一个无前束范式，定义A 的 Herbrand 域 H为{
是由在 A 中出现的个体常项符号，自由变元符号和函词符号生成的项。
（如果在 A 中不出现个体常项符号或自由变元符号，则取任何一个新的常项符号。）}
7-4-3 Herbrand 定理 任一一阶公式 A 是不可满足的，当且仅当存在 S 中的有穷子集合
,
是不可满足的。
的母式的特例集
其中S 不是 A 的母式的特例集合，而是 A 的无前束范式 合。S 不含任何量词、变元。 7.5 一阶形式理论7-5-1 一阶形式理论
在对一阶形式理论及其模型的研究中， Godel 的不完全
性定理，被认为是二十世纪最重要的数学定理。它深刻地揭示了语法及语义的关系，直接对数学以及哲学、认识论都有深刻的影响。重要结果之一就是否定了 Hilbert 关于将一切数学领域形式化的所谓“Hilbert 纲领”。 Godel 定理断言 对任一足够复杂的一阶理论，都存在一个形式语句 A , T 推不出 A , 也推不出
A 。
为了比较具体详细地介绍 Godel 不完全性定理，有必要介绍一个特殊的形式
理论系统在
。是一个比初等算术的形式理论“稍微大一点”的形式理论，我们将
上介绍和证明 Godel 不完全性定理。可以理解成关于非负整数的一个形式
理论，它的语言 L 中的谓词是 R1(x,y,z) 及 R2(x,y,z) ，分别 表示 加法关系x+y= z 和乘法关系 x · y = z 。 7.6 Godel 不完全性定理
7-6-1 Godel 不完全性定理 若及
A 都不可能形式证明。
是协调的，则存在的一个语句 A ，在中 A
7-6-2 配数方法 任给一个公式 A , [A] 表 A 的Godel 数。 7-6-3 可定义性 为区别分别写为一个关系
, 有
。在
中的常项 0 、1 与 N 中的元素 0、1。将
中的0、1 。 N 上的
中定义新的常项是的公式
中可定义的，如果对任意的 N 中的元素组
使得
当且仅当
7-6-4 Godel 不完全性定理的三个引理
引理1 对任一 递归函数 r , 关系 Rr 在 Z1 中是可定义的。 引理2 对任一 递归函数 r , 关系 Rr 是一个递归关系。 引理3 令 A(x) 是
的一个公式，[A(X)] = m 是它的 Godel 数，n 是一个整数，
代表某一个项 t ，则 Sub( m , n ) = Sub( [A(x)], [t]) = [A(t)]。 引理 4 （对角线定理） 令φ(x) 是变元是 x ，则存在语句Ψ，使得
7-6-5 Godel 的第二不完全性定理 令 CON(CON(（ 如果
) 可以表达为
) 表示
是协调的。通过编码，
中不可证明。
的语言 L 的任一个公式，它的唯一的自由
的一个形式公式。某一
中可证。）
的语句Ψ 在
不协调，任何公式都在
实际上，Ψ与 CON() 是等价的。
7-6-6 广义 Godel 不完全性定理 令 T 是任何一个理论，它的公理是归纳地给出的，同时原始递归函数在 T 中可以定义，那么， 若 T 协调，则 (1) 存在语句 A , A 及
A 在 T 中都不可证。
(2)CON(T)在 T 中是不可证的。
8.1 λ-演算
8-1-1 λ-演算 λ-演算由美国的逻辑学家 Kleen 于1930 年创建。λ-演算可以说是最简单、最小的一个形式系统。简单地说，λ- 演算就是表达“代入”或者“置换”这一数学上、计算机计算中最简单、但又是最普遍的运作的。它是函词式程序理论的基础，在 λ- 演算的基础上发展起来的π-演算、χ-演算，成为近年来的并发程序理论的理论工具之一，许多经典的并发程序模型就是以π-演算为框架的。 8-1-2 λ- 演算的描述 1 字母表 （1） （2）→归约 （3）= 等价
（4）λ，), ( 辅助工具符号 2 λ-项
（1）任一个变元是一个项。
（2）若 M, N 是项，则 (MN) 也是一个项。
（3）若 M 是一个项，而 x 是一个变元，则 (λxM) 也是一个项。 （4）仅仅由以上规则归纳定义得到的符号串是项。 3 公式
若 M, N 是λ-项，则 M→N , M = N 是公式。
说明（1） 在任一λ-项 M 中，变元x 的自由出现的定义与谓词演算中的公式中的自由变元的出现类似，可归纳地定义。
（2） 在任一λ-项 M 中，λx 的控制域的定义与谓词演算中量词的控制域的定义类似，但它们是相对于λx 而言的，亦可归纳定义。
（3） 令 M , N 是λ-项，x 在 M 中有自由出现，若以 N 置换 M 中所有 x 的自由出现（ M 中可能含有 x 的约束出现 ）， 我们得到另外一个 λ-项，记为 M[x/N]。
（4）一个λ-项的子项亦可归纳定义。 4 理论 λ-演算的公理和规则组成 I.（1）. (λx.M) N→M[x/N] (β- 归约) （2）M→M （3）M→N , N→L （4）(a) M→
M→N ZM→Z
变元
（b）M→ （c）M→II. （1）M→ （2）M =
（3）M = N , N = L （4）(a) M = (b) M =
MZ→ Z
λx . M→λx . M =
= M
M = L
Z
ZM = ZMZ =
(c) M = λx . M = λx .
如果某一公式 M→N , 或者 M = N 可以由以上公理推出，则记为λ│- M = N ,λ│- M→ N 。一个λ-项 M 中不含任何形为
的子项，则称 M 是一个范式，
简记为 n.f. 。如果λ-项 M 通过有穷步β归约后，得到一个范式，则称 M 有 n.f.， 没有 n.f. 的λ-项称为 n.n.f 。
8-1-3 不动点定理 对每一个 FΛ , 存在 M 表所有的λ-项组成的集合。
定义 ω=λx . F(xx) ， 又令 M =ωω，则有 λ│- M =ωω= (λx . F(xx))ω = F(ωω) = FM 。
8-1-4 Church - Rosser 定理 如果λ│- M = N , 则对某一个 Z ,λ│- M→ Z 并且 λ│- N→ Z 。该定理有下面的等价定理： 8-1-5 Diamond Property 定理 如果 M→ → Z ,
→ Z 。
, M→
，则存在某一 Z, 使得
Λ ， 使得 λ│- FM = M 。其中Λ
8.2 Scott 域 8-2-1 序关系
1．定义 令 < D , ≤> 是一个偏序集合。这里 D 是集合， ≤是序关系。一个子集合
是有向的, 如果 X 非空而且
2． 定义 ( c.p.o )
一个偏序集合< D , ≤> 称为完全偏序集, 如果以下二条件成立 ： （1） D 有一个最小元素，称为⊥ 。 （2） 每一个有向集合d , 满足
都有一个最小上界（ l.u.b ），是 D 的一个元素
, 而且，任意 D 的元素，如果 大于 X 中的所有的
X 。
元素，则 d≤ ，这个 l.u.b 记为
3．连续函数定义 （1）令φ(a)≤φ(b) 。
（2） φ 是连续的，如果对所有4． 定义 令
, D2 是 c.p.o. ，
→
] 定义为由[→
→
到
的连续函数的全体所组成的集合。
。 →
]
的有向子集合 X , φ(
X) =
(φ(X))。
,
是两个 c.p.o. ， 映射 φ：
→
是单调的，如果 a≤ b→
（1）[ （2）引理1 [
] , 定义φ≤Ψ当且仅当
] 在 4.（2） 定义的序关系下是一个 c.p.o. 。而且，对[
。
的每一个有向子集合 X ,
引理2 任两个连续函数φ，Ψ的复合φ·Ψ , 仍然是一个连续函数。这里φ [→
]， Ψ[
→
] ， 那么
。
8-2-2 同构和投影 1． 同构 令
,
是两个 c.p.o. ， 如果存在 φ[ , Ψ·φ= ,
,
上的恒等映射，则称
与
是同构的。
→
], Ψ
[
→
] , 使得
φ·Ψ =这里
分别是
2． 投影 令
,
是两个 c.p.o. ，,
分别是它们到自身上的恒等映射。由
→
], Ψ[
→
到
的
一个投影是一函数对 <φ，Ψ> 。这里φ[?/font>Ψ·φ =
, φ·Ψ≤
。
]，使得
如果这样的一对函数存在，称<φ，Ψ> 将 如果这样的一个投影存在，则=⊥定义 (1)
，Ψ(⊥) =⊥
。
将同构于
投影到上。
）。同时φ (⊥)
的一个子集合φ（
这里 N 是整数的全体，两两之间无序关系。但所有的 n≥⊥。
这是一个最简单的 c.p.o.。 (2) 定义 (1) (2) 3． 定理 引理
是由
到
。
的一个投影.
定义 （ n 阶投影的归纳定义 ） 令 n≥1 . 对所有的 f
, 所有的 g
, 定义
引理
定义 ( Scott 域
的构成 )
>组成的集合，这里
当且仅当
, 同时
是由
到
的一个投影。
是由所有的无穷序列D = <, 定理
。对
是λ-演算系统的一个模型。
8.3 Gentzen 串形演算 8-3-1 自然推理系统 1 基本概念
在该自然推理系统中，一个证明是一个类似于树形的图，可能有一个或者多个假设，或者没有假设，只含一个结论。 2 推理规则 （1） 前提 A （2） 导入规则 （3） 消除规则
3 自然推理系统的可计算语义 4 Curry - Howard 同构
已看到自然推理的推理（证明）与函数项之间的一一对应关系，对一个结构式形式的类型项的集合来说，将成为自然推理的所有推理的集合及这个项的集合之间的一个同构。这就是著名的 Curry - Howard 同构。 （1） 类型 （2） 项
8.3.2 Gentzen 串形演算 1 规则
一个串形是形为 A!│- B! 的一个表达式。这里 A! , B! 分别是公式的有穷序列
及
取式（1）恒等式
a．对任意公式 C , C │- C 称为恒等公理。 b．Cut 规则 （2）结构性规则 a．变位规则 b．弱减规则 c．收缩规则 （3）逻辑规则 a．否定规则 b．合取规则 c．析取规则 d．蕴涵规则 e．全称量词规则 f．存在量词规则 2 直觉主义的串形演算
直觉主义逻辑，或者构造性逻辑，其本质是不接受排中律，或者矛盾律：对任何一个断言 A, 或者 A 为真，或者
A 为真，别无其他选择。
在经典的一阶形式推理系统中，矛盾律表达为 若
同时
, 则
。 -- （1）
。
。该表达式的直觉解释为由
可推出析
而在自然主义推理系统中，此推理规则被减弱为两部分： 若 若
, 同时, 同时
, 则
。 -- （2）
, 则 ∑可推出任一 A。 --（3）
Gentzen 的串形演算的优点之一就是要在其逻辑框架下描述直觉主义的逻辑系统十分简明、清楚。直觉主义的串形演算系统中，接受同样的恒等式 C│- C , C 是任一公式。 8.4 线性逻辑
8-4-1 线性逻辑 在 Gentzen 的串形演算中, 结构性规则包括弱减及收缩，简单地说，如果 将这两条规则去掉，就导致了线性逻辑的建立。线性逻辑是在 1986 年左右，由法国逻辑学家 J.Y. Girard 创建的，被认为是证明论中的一个里程碑。在语法上的一个重要特征是该逻辑中的任一证明中的任一前提 A , 在证明中仅使用了一次。 8-4-2 近邻空间
定义1. 一个近邻空间 X 是一个集合 │X│ , 它的元素称为原子。X = < │X│, ︾ > 其中︾ 是│X│ 上的一个自反的、对称的二元关系。任给二元素
x,y │X│, 为了强调 x, y 的近邻关系是在近邻空间 X 中的关系，有时写成：a ︾
X 。如果我们将< │X│, ︾ > 看作一个图，也可以称它为
b [mod X] 。│X│ 的一个子集合 a 称为 X 的一个团体, 如果 a 中每两个元素都有近邻关系。记为 aX 的网络图。
除了近邻关系︾之外，可以定义以下的│X│上的关系：
定义２. 令 X 是一个近邻空间，X 的线性否定空间，记为（1）│
│ =│X│
] 当且仅当 x ︽y [mod X]
, ￡,
分别定义由 X, Y 产生, 满足
（2）x ︾ y [mod
定义３．对任二近邻空间 X, Y ，以乘法连接词
的一个新的近邻空间 Z , 这里 │Z│ = │X│x│Y│; 近邻关系分别为 （1） (x,y) ︾(x1,y1) [mod X
Y] 当且仅当 x︾x1 [mod X] 并且y︾y1 [mod Y]
（2） (x,y) ︶(x1,y1) [mod X￡Y] 当且仅当 x︶x1 [mod X] 或者y︶y1 [ mod Y ] （3） (x,y)︶(x1,y1) [mod XY] 当且仅当 x︾x1 [mod X] 蕴涵 y︶y1 [mod Y] 定义 ３．在同构的意义下，存在一个唯一的近邻空间，它仅含一个元素 0 ．该空间是自对偶的（它的线性否定空间就是它自己）．在语法上引入两个常项 1 和┴ ，将这两个常项都对应到这个特殊的近邻空间上，形式公理
在这个空
间上是成立的．同时，这个空间对乘法联结词是中性的：对任一近邻空间 X , X
1
X, X
．
, & ,分别定义一个新的近邻空间
定义４．任给近邻空间 X, Y ， 对加法联结词Z ,
, 同时
（1） (x,0) ︾(x1,0) [mod Z] 当且仅当 x︾x1 [mod X] （2） (y,1) ︾(y1,1) [mod Z] 当且仅当 y︾y1 [mod Y] （3） (x,0)︶(y,1) [mod X&Y] （4） (x,0)︵(y,1) [mod X
Y]
, & 也是中性的：X
0
X ,
定义５．类似于定义３，同样存在唯一的一个近邻空间，它的网络图是空集，它是自对偶的．它将成为常项 T 与 0 的指派．对X&T
8-4-3 线性串形演算 a. 恒等式及否定规则 b. 结构规则
X.另外，对于乘法联结词，并有
．
c. 逻辑规则
8-4-4 线性命题串形演算在近邻空间中的语释
这里只考虑命题演算部分，令 p, q , r … 是原子命题。对每一个原子命题，指派一个近邻空间：p* , q*, r* …。由公式的归纳定义，它们正好对应于 8.4.1 中的近邻空间的\"算子\"：对任意的近邻空间 X, Y , 已有 X┴ , XY, X￡Y, X
Y. X&Y ,
XY 的定义。所以，任一公式 A 在原始指派下，对应于一个唯一确定的近邻空间。要将这个对应扩充到串形及推理规则的每一执行过程，最后扩充到每一个证明上。 定义1. 假定
是一个串形，对每一个
中的公式
是
已经指派了的近邻空间。串形├ G 对应的近邻空间（1）（2）
定义2. （1） 恒等公理
对应于集合
。
定义为
A 的证明，通过 cut
（2） cut 规则 令π是 ├Γ,A 的证明， λ是 ├Δ,规则，我们得到的串形是 ├Γ，Δ。这形成├Γ，Δ的证明ρ。 （3） 交换规则 若π是├Γ的一个证明，由此产生的 ├
的证明ρ对应的团体
是Γ中成员的位置交换结果。；δ是该位置交换，
。 的近
定义 3. 对于所有其他的规则，给出以该规则为“最后使用了的规则”的证明邻语义，同样
必定是一个团体。
（1） 公理 ├ 1 解释为特殊的近邻空间 1 的团体 {0}。（ 0 是唯一的那个元素）。 （2） 公理 ├Γ,T 解释为空间
的空团体。
（3） false 规则 令π是 ├Γ 的证明，ρ是 ├Γ, ┴ 的以该规则结尾的证明，则定义
={
} 。
= {β(y,z) ;
（4） par 规则 π是 ├Γ, A, B 的证明，ρ是 ├Γ, A￡B 的证明，则βyz
}。
（5） times 规则 π是 ├Γ, A , λ是├Γ, B 的证明，ρ是├Γ, AB 的证明，则=
。
（6） lest plus 规则 令π是 ├Γ,A 的证明，ρ是├Γ,Aβy
}
B 的证明，则={β(y,0) ;
（7） right plus 规则 令π是 ├Γ, B 的证明，ρ是├Γ,A{β(y,1);βy
}.
B 的证明, 则=
（8） with 规则 π是 ├Γ,A,λ是├Γ, B 的证明，ρ是├Γ, A&B 的证明, 则=
定义 4. 令 X , Y 是近邻空间，由 X 到 Y 的映射 F 是线性的，如果 （1） 若 a（2） 若 （3） 若 定义 5.
（1） 对任一由 X 到 Y 的线性映射，定义 Tr(F)Tr(F) = {(x,y) ; y （2） 对任一 A若 a
F({x})}
XY , 定义线性函数 A(.) : X→Y :
A }
XY ( 称为 F 的迹 ，trace ):
X 则 F(a)
Y.
X, 则 A(a) ={y ;xa , (x,y)
定理 存在 XY 的全体团体之集与由 X 到 Y 的全体线性映射之集之间的 1 - 1 映射。
证明论专家普遍认为，线性逻辑系统的证明是最类似\"算法\"的语义对象，将为计算机科学，特别是并行算法提供一个新的、有力的工具。
9.1 集合的概念与表示方法
9-1-1 集合的概念 集合是无法给出严格精确定义的最基本的数学概念之一。以下是两则典型的叙述。
集合是一些确定的、可以区分的事物汇聚在一起组成的一个整体。组成一个集合的每个事物称为该集合的一个元素。
吾人直观或思维之对象，如为相异而确定之物，其总括之全体即谓之集合，其组成此集合之物谓之集合之元素。
9-1-2 集合的元素与集合之间的关系 一个集合的元素和该集合之间是隶属关系，即属于或不属于。若元素 属于集合 ，记作αΑ，否则记作对任何集合Α都有Α
Α 。
。
本书采用的体系中规定集合的元素都是集合。同时为保持体系上的严谨性，规定：9-1-3集合的表示法 表示一个集合的方法有两种：外延表示法和内涵表示法。前一
种方法又称之为列元素法，即列出集合的所有元素。后一种方法又称之为谓词表示法，即用谓词来概括集合中元素的性质。一般而言，如果P(χ) 表示一个谓词，则可以用
或
表示一个集合。
是使P(χ)为真的所有元素χ
组成的集合。即，若P(α)为真，则 α 属于该集合。 9.2 集合间的关系和特殊集合
9-2-1 集合的相等（定义9.2.1） 两个集合Α，Β 相等，当且仅当它们具有相同的元素。若集合Α和Β相等，则记作Α=Β ；否则记作Α≠Β 。该定义的符号化表示为
9-2-2 子集（定义9.2.2） 设Α，Β 为集合，若Α 中的每个元素都是Β 的元素，则称Α 为Β 的子集合，简称子集。这时称Β 包含Α，记作Α号化表示为
定理9.2.1 两个集合相等的充要条件是它们互为子集。符号化表示为
定理9.2.2 对任意的集合Α，Β 和C，包含关系（1） Α（2） （3）
分别具有下列性质：
Β 。该定义的符
Α （自反性）
（反对称性） （传递性）
Β 且Α≠Β ，则称Α 是
9-2-3 真子集（定义9.2.3） 对任意两个集合Α 和Β，若ΑΒ 的真子集，或称Β 真包含Α。记作Α
Β。该定义的符号化表示为
9-2-4 不相交（定义9.2.4） 若两个集合Α和Β 没有公共元素，就称Α 和Β 是不相交的。该定义也可写成
9-2-5 空集（定义9.2.5） 不含任何元素的集合称为空集，记作Φ。空集可符号化为 Φ={x│x≠x}
定理9.2.3 空集是一切集合的子集。即，对任意的集合Α，Φ
Α。
9-2-6 全集（定义9.2.6） 在给定的问题中，所考虑的所有事物的集合称为全集，
记作E。
该定义亦可叙述为，在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为全集。全集的定义可符号化表示为
E={x│x=x}
全集是有相对性的，不同的问题有不同的全集。即使同一个问题也可以取不同的全集。
9.3 集合的运算
9-3-1 集合的基本运算（定义9.3.1） 集合的基本运算包括并，交，差（相对补）和对称差。分别定义如下。对集合Α 和Β （1）（2）（3）
（4）余集-Α 定义为
称Α 的绝对补集，也是Α 对E 的相对补集） （5）
（又称Β 对Α 的相对补集） （其中E 为全集。Α 的余集又
9-3-2 广义并和广义交（定义9.3.2） 设Α 为集合，Α 的所有元素的元素组成的集合称为Α 的广义并，记作YΑ ；设Α 为非空集合，把Α 的所有元素的公共元素组成的集合称为Α 的广义交，记作I Α。分别符号化表示为
此外，对空集Φ 可以进行广义并，YΦ=Φ 。但I Φ不是集合，没有意义。 9-3-3 幂集（定义9.3.3） 设Α 为集合，把Α 的所有子集组成的集合称为Α 的幂集，记作P(Α) 。符号化表示为
对任意的集合Α ，有Φ
Α 和Α
Α ，因此有ΦP(Α)和ΑP(Α) 。
9-3-4 有序对 由两个元素x 和y （允许 x=y ）按给定次序排列组成的二元组称为一个有序对或序偶，记作 2． 9-3-5 元组（定义9.3.5） 若nN且n>1,组 定义为 ， 是n 个元素，则n 元 9-3-6 集合Α和Β的笛卡儿积 设Α,Β 为集合，用Α中元素为第一元素，Β中元素为第二元素构成有序对。所有这样的有序对组成的集合称为Α 和Β 的笛卡儿积，记作ΑxΒ 。 Α和Β 的笛卡儿积的符号化表示为 9-3-7 阶笛卡儿积 若nN，且n>1，卡儿积记作 , 并定义为 9-3-8 集合运算的优先顺序 对集合运算的优先顺序做如下规定： 称广义并，广义交，幂集，绝对补运算并，交，对称差，笛卡儿积，相对补运算一类运算优先于二类运算； 二类运算优先于集合关系运算同时，上述集合运算优先于逻辑运算 ； 。 为一类运算； 为二类运算。 是n 个集合，它们的n 阶笛 括号内优先于括号外的；同一层括号内，相同优先级的，一类运算之间按由右向左顺序进行；其它按从左到右的顺序进行。 9.4 集合的图形表示法 9-4-1 文氏图（Venn Diagram） 英国逻辑学家J.Venn(1834-1923)于1881年在《符号逻辑》一书中，首先使用相交区域的图解来说明类与类之间的关系。后来人们以他的名字来命名这种用图形来表示集合间的关系和集合的基本运算的方法。其构造如下：用一个大的矩形表示全集的所有元素（有时为简单起见，可将全集省略）。在矩形内画一些圆（或任何其它形状的闭曲线），用圆的内部的点表示相应集合的元素。不同的圆代表不同的集合。用阴影或斜线的区域表示新组成的集合。文氏图的优点是形象直观，易于理解。缺点是理论基础不够严谨。因此只能用于说明，不能用于证明。 9.5 集合运算的性质和证明 定理9.5.1 集合恒等式 对任意的集合A,B,C，下列恒等式成立： （1） 交换律 A A（2） 结合律 (A（3） 分配律 A A（4） 幂等律 A A（5） 吸收律 （6） 狄摩根律 （7） 同一律 （8） 零律 （9） 补余律 （10）补律 B =BB＝BB)(B A A (BB)B) C(A(A(A B)C) C) C)=A (B C) C =AC)=(A (BC)=(AA=A A=A (排中律) (矛盾律) （11） 双补律 -(-Α)=Α 定理9.5.2 差集的性质 对任意的集合A,B,C， （1） （2） （3） （4） 定理9.5.3 对称差的性质 对任意的集合A,B,C， （1） 交换律 （2） 结合律 （3） 分配律 （4） 同一律 （5） 零律 （6） 吸收律 定理9.5.4 集合间的（1） （2） （3） （4） （5） （6） 关系的性质 对任意的集合A,B,C 和Ｄ， 定理9.5.5 幂集合的性质1 对任意的集合A 和B， （1） （2） 定理9.5.6 幂集合的性质2 对任意的集合A 和B， 定理9.5.7 幂集合的性质3 对任意的集合A 和B， （1） （2） 定理9.5.8 幂集合的性质4 对任意的集合A 和B， 9-5-1 传递集合(定义9.5.1) 如果集合A 的任一元素的元素都是A 的元素，就称A 为传递集合。该定义也可写成 定理9.5.9 传递集合的性质1 对任意的集合A， 定理9.5.10 传递集合的性质2 对任意的集合A， A是传递集合 是传递集合 定理9.5.11 广义并和广义交的性质1 对集合的集合A 和B， （1） （2） 定理9.5.12 广义并和广义交的性质2 对集合的集合A 和B， （1） （2） （其中A 和B非空） 定理9.5.13 广义并和幂集运算的关系性质 对任意的集合A， 定理9.5.14 传递集合的性质3 若集合A 是传递集合，则YA 是传递集合。 定理9.5.15 传递集合的性质4 若集合A 的元素都是传递集合，则YA 是传递集合。 定理9.5.16 传递集合的性质5 若非空集合A 是传递集合，则IA 是传递集合，且 IA=Φ。 定理9.5.17 传递集合的性质6 若非空集合 的元素都是传递集合，则 是传递集合。 定理9.5.18 幂集的性质 若A 是集合， 定理9.5.19 笛卡儿积与（1） （2） （3） （4） 定理9.5.20 笛卡儿积与 , 运算的性质 对任意的集合A,B 和C， 运算的性质1 对任意的集合A,B 和C，若C≠Φ，则 ，则 。 定理9.5.21 笛卡儿积与运算的性质2 对任意的集合A,B,C和D， 9.6 有限集合的基数 9-6-1 有限集合的基数（定义9.6.1） 如果存在nN ，使集合A与集合 的元素个数相同，就说集合A 的基数是 n ，记作 。空集Φ的基数是O 。 9-6-2 有限集合（定义9.6.2） 如果存在nN，使n 是集合A 的基数，就说A 是有限集合。如果不存在这样的n ，就说A 是无限集合。 定理9.6.1 幂集的基数 对有限集合A， 定理9.6.2 笛卡儿积的基数 对有限集合A 和B， 定理9.6.3 基本运算的基数 对有限集合A 和B， （1） （2） （3） （4） 定理9.6.4 包含排除原理 对有限集合A 和B， 该定理可推广到n 个集合的情形。若nN且n>1, 是有限集合，则 9.7 集合理系统 9-7-1 集合理系统 集合理系统是一阶谓词公理系统的扩展，它包括一阶谓词公理系统和几个集合理。集合理系统可以推出一阶谓词的所有定理，也可以推出集合论的概念和定理。它从理论上防止了集合论中悖论的出现。 集合理系统的一个基本思想是“任一集合的所有元素都是集合”。 集合论研究的对象只是集合。除集合外的其它对象（如有序对、数字、字母）都要用集合定义。 9-7-2 ZF（Zermelo-Fraenkel）集合理系统 ZF集合理系统由德国数学家 E.Zermelo和A.Fraenkel 提出，是一个非常著名的集合理系统。它包括10条集合理，但并非彼此。其中的无序对集合存在公理和子集公理模式可由其他公理推出。 （1） 外延公理 两集合相等的充要条件是它们恰好具有同样的元素。 （2） 空集存在公理 存在不含任何元素的集合（空集Φ）。 （3） 无序对集合存在公理 对任意的集合 x 和 y，存在一个集合 z , 它的元素恰好为 x 和 y。 （4） 并集合存在公理 对任意的集合 x ，存在一个集合 y , 它的元素恰好为 x 的元素的元素。 （5） 子集公理模式（分离公理模式） 对任意的谓词公式 P(z) ，对任意的集合 x ，存在一个集合 y , 它的元素 z 恰好既是 x 的元素又使P(z) 为真。 （6） 幂集合公理（集合的幂集是集合） 对任意的集合x ，存在一个集合 y , 它的元素恰好是x 的子集。 （7） 正则公理 对任意的非空集合x ，存在x 的一个元素，它和x 不相交。 （8） 无穷公理 存在一个由所有自然数组成的集合。 （9） 替换公理模式 对于任意的谓词公式P(x,y) ，如果对任意的 x存在唯一的 y 使得P(x,y) 为真，那么对所有的集合 t 就存在一个集合δ，使δ 中的元素 ,y 恰好是 t 中元素 x 所对应的那些 ,y 。 其中表示符号 表示存在唯一的一个y 。 （10） 选择公理 对任意的关系R ，存在一个函数F，F 是R 的子集，而且F 和R 的定义域相等。 定理9.7.1 交集存在定理 对任意的集合Α 和Β，交集Α Β是集合。 定理9.7.2 差集存在定理 对任意的集合Α 和Β，差集Α-Β 是集合。 定理9.7.3 广义交存在定理 对任意的非空集合Α ，广义交IΑ 是集合。 定理9.7.4 笛卡儿积存在定理 对任意的集合Α 和Β，笛卡儿积ΑxΒ 是集合。 定理9.7.5 万有集不存在定理 不存在集合Α ，使任一集合都是Α 的元素。 9-7-2 极小元（定义9.7.1） 对任意的集合Α 和Β，当满足ΑΒ 且Α称Α 为Β 的一个极小元。 定理9.7.6 集合的重要性质1 对任意的集合Α， 。 。 。 Β=Φ ，就 定理9.7.7 集合的重要性质2 对任意的集合Α 和Β，有定理9.7.8 传递集合的性质7 对任意非空的传递集合Α ，有9-7-3 奇异集合（定义9.7.2） 如果集合Α 中有集合的序列 使得满足 ， 就称Α 为奇异集合。 定理9.7.9 奇异集合的性质1 奇异集合不满足正则公理。 定理9.7.10 奇异集合的性质2 若非空集合Α 不是奇异集合，则Α 满足正则公理。 9-7-4 前驱与后继（定义9.7.3） 对任意的集合Α ，定义集合 称为Α 的后继，Α 称为 的前驱。 ，把 9-7-5 用后继定义自然数（定义9.7.4） 集合O=Φ是一个自然数。若集合 n 是一个自然数，则集合 也是一个自然数。 9-7-6 自然数的性质1（定义9.7.5） 对任意的自然数m 和 n， 9-7-7 集合的三岐性（定义9.7.6） 对集合Α，如果对任意的集合使 三式中恰好有一个成立，就称集合Α 有三岐性。 定理9.7.11 自然数的三岐性 集合N 有三岐性。每个自然数都有三岐性。即 ， 10.1 二元关系 10-1-1 二元关系（有序对的集合） 如果一个集合满足以下条件之一： （1）集合非空，且它的元素都是有序对（见9-3-4）； （2）集合是空集； 则称该集合为一个二元关系，记作R 。二元关系也简称关系。对于二元关系R，如果 ，也可记作 。 定义10.1.1 到 的二元关系 设A,B为集合，AxB 的任一子集所定义的二元关系称为A到B 的二元关系。特别当A=B 时，AxA 的任一子集称为A上的一个二元关系。 定义10.1.2 n元关系（n元组的集合） 若nN且n>1,合，则 的任一子集称为从 是n 个集 上的一个n 元关系。 10-1-2 集合族上的包含关系与真包含关系 设A是集合族，A上的包含关系可定义为： A上的真包含关系可定义为： 例如对任意的集合A，则A的幂集P(A) 上的包含关系可定义为： 定义10.1.3 三个特殊的关系--（恒等关系、全域关系和空关系） 对任意的集合A， （1） A上的恒等关系 （2） A上的全域关系（全关系） （3） 空集Φ是AxA的子集，定义为A上的空关系。 定义10.1.4 定义域和值域 设R是A到B的二元关系 （1） R中所有有序对的第一元素构成的集合称为R的定义域，记作dom(R)。 形式化表示为 化表示为 。 。 定义为 定义为 （2） R中所有有序对的第二元素构成的集合称为R的值域，记作ran(R) 。形式 （3） R的定义域和值域的并集称为R的域，记作fld(R) 。形式化表示为 10.2 关系矩阵和关系图 定义10.2.1 关系矩阵 设集合 是X到Y 的一个关系。则R的关系矩阵是m x n 矩阵，矩阵元素是 。 若R 若R是X上的一个关系，则R的关系矩阵是m x n方阵，定义与上述类似。 定义10.2.2 关系图 设集合 是X到Y 的一个关系，则R 的关系图是一个有向图是 ，边集是E，从 的有向边 ，当且仅当 。若R，它的顶点集 。 若R是X上的一个关系，则R 的关系图是上述情形的特例。 10.3 关系的逆、合成、和象 定义10.3.1 关系的逆、合成、和象 对X到Y 的关系R， Y到Z的关系S，定义 （1） R的逆 为X到Y的关系 （2） R与S的合成SoR （有些书中称之为关系的左复合）为X到Z的关系 （3） 对任意的集合A，定义R在A上的R↑A为A到Y 的关系 （4） A在R下的象R[A] 为集合 10-3-1 SoR的关系矩阵 设A是有限集合，│A│=n。关系R和S都是A上的关系，R和S的关系矩阵 都是n×n 的方阵。于是R与S的合成SoR 的关系矩阵 可以用下述的矩阵逻辑乘计算（类似于矩阵乘法）。记作 其中 定理10.3.1 关系R的逆关系的性质 对X到Y的关系R和Y到Z的关系S， 定理10.3.2 关系的合成的结合律 对X到Y的关系Q，Y到Z 的关系S ，Z到W 的关系R， 定理10.3.3 关系的合成的其它性质 对X到Y的关系 对X到Y的关系 ，Y到Z的关系 ， （规定关系合成运算符优先于集合运算符） 定理10.3.4 集合在关系下的象的性质 对X到Y的关系R和集合A 、B， ， ，Y到Z的关系 ， 10.4 关系的性质 定义10.4.1 自反性与非自反性 设R为集合上A的关系， 定义10.4.2 对称性与反对称性 设R为集合上A的关系， 反对称性的另一种等价的定义为 定义10.4.3 传递性 设R为集合A上的关系， 定理10.4.1 几个特殊关系的自反性 设 、 、 是A上的自反关系，则 也是A上的自反关系。 、 是A上的对称关系，则 定理10.4.2 几个特殊关系的对称性 设 、也是A上的对称关系。 定理10.4.3 几个特殊关系的传递性 设 是A上的传递关系。但 定理10.4.4 几个特殊关系的反对称性 设 是A上的反对称关系。但 、、 是A上的传递关系，则不一定是传递的。 是A上的传递关系，则不一定是反对称的。 定理10.4.5 对称性与反对称性的两个性质 设R是A上的关系， 10.5 关系的闭包 定义10.5.1 多个关系的合成 设R为上A的关系，nN，关系R的n 次幂定义为： 定理10.5.1 有限集合上只有有限个不同的二元关系 设A是有限集合，│A│=n。R是A上的关系， 则存在自然数s和t，s≠t，使得 。 定理10.5.2 有限集合上关系的合成 设A是有限集合， R是A上的关系，m 和n 是非零自然数， 定理10.5.3 有限集合上关系的幂序列具有周期性 设A是有限集合， R是A上的关系，若存在自然数s 和 t，使得 ，则R 的各次幂均为Ｂ 的元素，即对任意的 。 定义10.5.2 闭包的定义 设R是非空集合A 上的关系，如果A上有另一个关系足： （1） （2） 是自反的（对称的或传递的）； ； 。 满 ，则 （3） 对A上任何自反的（对称的或传递的）关系则称关系 为R的自反（对称或传递）闭包。 一般将R 的自反闭包记作r(R) ，对称闭包记作s(R) ，传递闭包记作t(R) 。它们分别是具有自反性（对称性或传递性）的R 的\"最小\"超集合。 定理10.5.4 闭包的性质1 对非空集合A上的关系R， 定理10.5.5 闭包的性质2 对非空集合A上的关系 定理10.5.6 闭包的性质3 对非空集合A上的关系 ，，若，则 ，， 定理10.5.7 自反闭包的构造方法 对非空集合A上的关系R， 定理10.5.8 对称闭包的构造方法 对非空集合A上的关系R， 定理10.5.9 传递闭包的构造方法 对非空集合A上的关系R， 定理10.5.10 传递闭包的有限构造方法 A为非空有限集合，│A│=n。R是A上的关系，则存在正整数k≤ n ，使得 定理10.5.11 闭包同时具有的多种性质1 对非空集合A上的关系R， 定理10.5.12 闭包同时具有的多种性质2 对非空集合A上的关系R， 10.6 等价关系和划分 定义10.6.1 等价关系 设R非空集合A上的关系，如果R 是自反的、对称的和传递的，则称R 为A 上的等价关系。 定义10.6.2 等价类 设R 为非空集合A 上的等价关系，对任意的xA，令 称集合 为x关于R 的等价类，简称x 的等价类，也可简记作[x]或 。 定理10.6.1 等价类的性质 R是非空集合A上的等价关系，对任意的x,yA， 定义10.6.3 商集 设R非空集合A上的关系，以R 的所有等价类为元素的集合称为A的商集，记作A/R 。即 定义10.6.4 划分 设A为非空集合，若存在A 的非空子集构成的集合π满足下列条件： 则称π为A的一个划分，称π中的元素为A的划分块。 定理10.6.2 等价关系R诱导出的A的划分 对非空集合A上的等价关系R， A的商集A/R 就是A的划分，称为由等价关系R诱导出的A的划分，记作πR。 定理10.6.3 划分π诱导出的A上的等价关系 对非空集合A上的一个划分π，令A上的关系 为 则 为A上的等价关系，它称为划分π诱导出的A上的等价关系。 定理10.6.4 划分π和A上的等价关系R 对非空集合A上的一个划分π，和A上的 等价关系R， π诱导R 当且仅当R 诱导π。 10.7 相容关系和覆盖 定义10.7.1 （相容关系） 对非空集合A上的关系R，如果R是自反的、对称的，则称R 为A上的相容关系。 定义10.7.2 （相容类） 对非空集合A上的相容关系R，若C A，且C 中任意两 个元素x 和y 有xRy，则称C是由相容关系R 产生的相容类，简称相容类。 这个定义也可以写成 定义10.7.3 （最大相容类） 对非空集合A上的相容关系R，一个相容类若不是任何相容类的真子集，就称为最大相容类，记作对最大相容类 有下列性质： 和 。 定理10.7.1 （最大相容类的存在性） 对非空有限集合A上的相容关系R，若C是一个相容类，则存在一个最大相容类 ，使C 。 定义10.7.4 （覆盖） 对非空集合A，若存在集合Ω满足下列条件： 则称Ω为A的一个覆盖，称Ω中的元素为Ω的覆盖块。 定理10.7.2 （完全覆盖） 对非空集合A上的相容关系R，最大相容类的集合是A的一个覆盖，称为A的完全覆盖，记作 (A)。而且 (A)是唯一的。 定理10.7.3 （覆盖与相容关系） 对非空有限集合A上的一个覆盖 ，由Ω确定的关系 10.8 偏序关系 定义10.8.1 （偏序关系 半序关系） 对非空集合A上的关系R，如果R是自反的、反对称的和传递的，则称R为A上的偏序关系。 在不会产生误解时，偏序关系R通常记作≤。当xRy 时，可记作x≤y，读作x“小于等于”y。偏序关系又称弱偏序关系，或半序关系。 定义10.8.2 （拟序关系 强偏序关系） 对非空集合A上的关系R，如果R是非自反的和传递的，则称R为A上的拟序关系。 在不会产生误解时，拟序关系R通常记作< 。当xRy 时，可记作x< y，读作x“小于”y。拟序关系又称强偏序关系。 定理10.8.1 R为A上的拟序关系，则R是反对称的。 定理10.8.2 对A上的拟序关系R，定理10.8.3 对A上的偏序关系R， 是A上的偏序关系。 是A上的拟序关系。 定义10.8.3 （偏序集） 集合A与A上的关系R一起称为一个结构。集合A与A上的偏序关系R一起称为一个偏序结构，或称偏序集，并记作 定义10.8.5 （最小元 最大元 极小元 极大元） 对偏序集 定义10.8.6 （上界 下界 上确界 下确界） 对偏序集 定义10.8.7 （可比） 对偏序集 定义10.8.8 （全序关系与全序集） 对偏序集 A A， A， (1) 如果对任意的x,yB，x和 y 都是可比的，则称B为A上的链，B中元素个数称为链的长度。 (2) 如果对任意的x,yB，x和 y 都不是可比的，则称B 为A上的反链，B中元素个数称为反链的长度。 定理10.8.4 （偏序集的分解定理） 对偏序集 定理10.8.5 对偏序集 定义10.8.10 （良序关系与良序集） 对偏序集 定理10.8.8 （良序定理）任意的集合都是可以良序化的。 定义10.8.11 （闭区间 开区间） 在全序集 都称为从a到b的半开区间， (4) 还可以定义下列区间 11.1 函数和选择公理 定义11.1.1 （函数） 对集合 到集合 的关系 ，若满足下列条件： ，使 成立； (1)对任意的 (2) 则称 为从 到 ，存在唯一的 的函数，或称 到 或 的函数 把 映射到 （有的书称 ： 为全函数、 ， 映射、变换）。一个从 则可记作 ： ，可以写成 。这时若 。 函数的两个条件可以写成 (1) (2) 定义11.1.2 （从 对集合 于是， 若 和 是有限集合，且 和 到 。 的所有函数的集合 到 ） （有的为 ）。 ， ，从 的所有函数的集合记为 。 ， ，则 。 定义11.1.3 （函数的象） 设 ： ， ，定义 把 设 称为函数的象。 ，定义 在 下的完全原象 定义11.1.4 （满射 单射 双射） 设 ： ， ，则称 ， ，则称 (3) 若 称双射。 定义11.1.5 （常函数） 设 即有 ： ，如果存在一个 ，则称 ： ，使得对所有的 为常函数。 ， ， 是满射的，或称 ，都有 是 到 上的； 为 在 下的象 为 (1) 若 (2) 若对任意的 是单射的，或的，或一对一的； 是双射的，或一对一 到 上的。简 是满射的又是单射的，则称 定义11.1.6 （恒等函数） 上的恒等关系 。 ： 称为恒等函数。于是，对任意的 ，有 定义11.1.7 （单调函数） 对实数集 ，设 ： ，如果 ，则称 ，则称 为 单调递增的；如果 可定义单调递减和严格单调递减的函数。 定义11.1.8 （ 对集合 ， 元运算） ，把函数 ： 为严格单调递增的。类似 称为 上的 元运算。 定义11.1.9 （泛函） 设 ， ， 是集合， 为从 ： 到 的所有函数的集合，则 ： 称为一个泛函（有时将 称为一个泛函）。 定义11.1.10 （特征函数） 设 是全集，对任意的 ， 的特征函数 定义为： 定义11.1.11 （典型映射或自然映射） 设 是 上的等价关系，令 ： ， ，则称 为从 到商集 的典型映射或自然映射。 11-1-1 （选择公理） （形式1） 对任意的关系 且 ，存在函数 ，使得 11.2 函数的合成与函数的逆定理11.2.1 （函数的合成） 设 (1) ： 是函数 ， ： ： ，有 ，则 ， 。 (2)对任意的 定理11.2.2 （函数的合成的性质1） 设 (1)若 (2)若 (3)若 ： ， ， ， ， ： ， 是满射的， 是单射的， 是双射的。 是满射的，则 是单射的，则 是双射的，则 定理11.2.3 （函数的合成的性质2） 设 (1)若 (2)若 (3)若 ： ， ： ， 是满射的， 是单射的， 是满射的， ，则 是单射的。 。 是满射的，则 是单射的，则 是双射的，则 ： 定理11.2.4设 定理11.2.5 （函数的逆） 若 ： 是双射的，则 是函数 ： 。 定义11.2.1 （反函数） 设 ： 是双射的，则称 ： ： ，有 ： 为 ： 的反函数。 是双射的。 ，有 ， 定理11.2.6 若 定理11.2.7 若 对任意的 是双射的，则 是双射的，则对任意的 。 定义11.2.2 （函数的左逆和右逆） 设 如果 定理11.2.8 设 ： ， 存在左逆,当且仅当 存在右逆，当且仅当 ，则 是单射； 是满射的； ： ， ： 为 ，如果 的右逆。 ，则称 为 的左逆； ，则称 （1） （2） （3） （4）若 存在左逆又存在右逆，当且仅当 是双射的，则 是双射的； 的左逆等于右逆。 11.3 函数的性质 定义11.3.1 （函数的相容性） 设 就说 ： 和 ， ： ，如果对任意的 ，都有 ， 是相容的。 定义11.3.2 （函数集的相容性） 设 就说 是由一些函数组成的集合，如果 是相容的。 中任意两个函数 和 都是相容的， 定理11.3.1 设 ： ， ： ，则 和 是相容的当且仅当 是函 数。 定理11.3.2 设 ： ， ： 。 定理11.3.3 对函数的集合 ，若 是相容的，且 ，则 是函数 ： ，则 与 是相容的当且仅当 ，且 。 定义11.3.3 （关系与函数的相容性） 设 是 上的等价关系，且 ： ，则称关系 定理11.3.4 设 是 上的等价关系，且 ： 。 ： ，使 ，如果 与 是相容的，则存在 与 不相 ，如果对任意的 与函数 是相容的。 ，有 唯一的函数 ；如果 容，则不存在这样的函数 11.4 开集与闭集 定理11.4.1 （距离） 对实数集 ，若 ： 为 定义为 上的距离函数，对任意 。 ，其中 ，把 是 的绝对值，则称 称为 和 的距离，并可写为 定义11.4.2 （邻域） 对实数集 且 ，＜是 上的小于关系， 是 上的距离函数，若 ， ，则集合 称为 的 邻域。 定义11.4.3 （极限点） 对实数集 于 ， ，且 ， ，如果在 ，则称 是 的任一个 邻域中，都存在不等 的元素 的一个极限点（或凝聚点）。 定义的条件可以写成 定理11.4.1 对实数集 列 使得 定理11.4.2 若 是有界无限集，则 具有极限点。 。 ， ， ， 是 的极限点当且仅当在 中存在点 定义11.4.4 （孤立点） 对实数集 孤立点。 定义11.4.5 （导集与闭集） 对实数集 ， ， 的所有极限点的集合称为 的导集，记作 。如 ， ， ，若 不是 的极限点，则称 为 的 果 ，则称 为闭集。 ， ，则 是闭集，即 。 定理11.4.3对实数集 定理11.4.4 任意个闭集的交集是闭集。有限个闭集的并集是交集。 定义11.4.6 （内点） 对实数集 素，则称 ， 为 ， 的一个内点。 ，如果存在 的 邻域，其中全是 的元 定义的条件可以写成 定义11.4.7 （开集） 对实数集 定理11.4.5 任意个开集的并集是开集，有限个开集的交集是开集。 定理11.4.6 对实数集 (1) 若 (2)若 ， 是开集，则 是闭集，则 ， 是闭集。 是开集。 ， ，若 的元素都是 的内点，则称 为开集。 11.5 模糊子集 定理11.5.1 （特征函数的性质） 设 (1) (2) (3) (4) (5) (6) (7) (8) , , , 是论域， ， , , , ， ，＋、－、＊是算术加、减、乘法， 定义11.5.1 （模糊子集与隶属函数） 设 并称 是论域， 为 上的一个模糊子集 是指：存在一个函数 ， 的隶属函数。 是全集， ，则 、 、 具有下 定义11.5.2 设 列隶属函数 , . 、 、 分别称为并集、交集、绝对补集。 定义11.5.3 （截集） 设 是全集， 称为 的 截集， 可以写作 。 ，对 ，集合 定理11.5.2 设 (1) (2) 定理11.5.3 设 (1) (2) . 是全集， , ， ，则 是全集， ， ， ，则 定理11.5.4 （分解定理） 设 是全集， ， . ， 是 的特征函数，则 （其中 表示集合的上确界， 表示集合的下确界） 定义11.5.4 （支集 核 边界 正规模糊集） 设 是全集， ，则 称为 核 就称 的支集，截集 的元素完全隶属于 称为 。若 的核， ，就称 ：称为 的边界。 ， 为正规模糊集；若 为非正规模糊集。 11.1 函数和选择公理 定义11.1.1 （函数） 对集合 到集合 的关系 ，若满足下列条件： ，使 成立； (1)对任意的 (2) 则称 为从 到 ，存在唯一的 的函数，或称 到 或 的函数 把 映射到 （有的书称 ： 为全函数、 ， 映射、变换）。一个从 则可记作 ： ，可以写成 。这时若 。 函数的两个条件可以写成 (1) (2) 定义11.1.2 （从 对集合 于是， 若 和 是有限集合，且 和 到 。 的所有函数的集合 到 ） （有的为 ）。 ， ，从 的所有函数的集合记为 。 ， ，则 。 定义11.1.3 （函数的象） 设 ： ， ，定义 在 下的象 为 把 设 称为函数的象。 ，定义 在 下的完全原象 为 定义11.1.4 （满射 单射 双射） 设 ： ， ，则称 ， ，则称 (3) 若 是满射的，或称 ，都有 是 到 上的； (1) 若 (2) 若对任意的 是单射的，或的，或一对一的； 是双射的，或一对一 到 上的。简 是满射的又是单射的，则称 称双射。 定义11.1.5 （常函数） 设 即有 ： ，如果存在一个 ，则称 ： ，使得对所有的 为常函数。 ， ， 定义11.1.6 （恒等函数） 上的恒等关系 。 定义11.1.7 （单调函数） 对实数集 ，设 ： ，如果 ，则称 ，则称 为 ： 称为恒等函数。于是，对任意的 ，有 单调递增的；如果 可定义单调递减和严格单调递减的函数。 定义11.1.8 （ 对集合 ， 元运算） ，把函数 ： 为严格单调递增的。类似 称为 上的 元运算。 定义11.1.9 （泛函） 设 ， ， 是集合， 为从 ： 到 的所有函数的集合，则 ： 称为一个泛函（有时将 称为一个泛函）。 定义11.1.10 （特征函数） 设 是全集，对任意的 ， 的特征函数 定义为： 定义11.1.11 （典型映射或自然映射） 设 是 上的等价关系，令 ： ， ，则称 为从 到商集 的典型映射或自然映射。 11-1-1 （选择公理） （形式1） 对任意的关系 且 11.2 函数的合成与函数的逆 定理11.2.1 （函数的合成） 设 (1) ： 是函数 ， ： ： ，有 ，则 ， 。 ，存在函数 ，使得 (2)对任意的 定理11.2.2 （函数的合成的性质1） 设 (1)若 (2)若 (3)若 ： ， ， ， ， ： ， 是满射的， 是单射的， 是双射的。 是满射的，则 是单射的，则 是双射的，则 定理11.2.3 （函数的合成的性质2） 设 (1)若 (2)若 (3)若 ： ， ： ， 是满射的， 是单射的， 是满射的， ，则 是单射的。 。 是满射的，则 是单射的，则 是双射的，则 ： 定理11.2.4设 定理11.2.5 （函数的逆） 若 ： 是双射的，则 是函数 ： 。 定义11.2.1 （反函数） 设 ： 是双射的，则称 ： ： ，有 ： 为 ： 的反函数。 是双射的。 ，有 ， 定理11.2.6 若 定理11.2.7 若 对任意的 是双射的，则 是双射的，则对任意的 。 定义11.2.2 （函数的左逆和右逆） 设 如果 定理11.2.8 设 （1） （2） （3） （4）若 ： ， ： 为 ， ，如果 的右逆。 ，则 ，则称 为 的左逆； ，则称 ： 存在左逆,当且仅当 存在右逆，当且仅当 是单射； 是满射的； 是双射的； 存在左逆又存在右逆，当且仅当 是双射的，则 的左逆等于右逆。 11.3 函数的性质 定义11.3.1 （函数的相容性） 设 就说 ： 和 ， ： ，如果对任意的 ，都有 ， 是相容的。 定义11.3.2 （函数集的相容性） 设 就说 是由一些函数组成的集合，如果 是相容的。 ： ， ： ，则 和 是相容的当且仅当 中任意两个函数 和 都是相容的， 定理11.3.1设 是函数。 定理11.3.2 设 ： ， ： ，则 与 是相容的当且仅当 。 定理11.3.3对函数的集合 ，且 。 定义11.3.3 （关系与函数的相容性） 设 是 上的等价关系，且 ： ，则称关系 定理11.3.4 设 是 上的等价关系，且 ： 。 ，如果对任意的 与函数 ： ，使 是相容的。 ，如果 与 是相容 与 ，有 ，若 是相容的，且 ，则 是函数 ： 的，则存在唯一的函数 ；如果 不相容，则不存在这样的函数 11.4 开集与闭集 定理11.4.1 （距离） 对实数集 ，若 ： 为 定义为 上的距离函数，对任意 。 ，其中 ，把 是 的绝对值，则称 称为 和 的距离，并可写为 定义11.4.2 （邻域） 对实数集 且 ，＜是 上的小于关系， 是 上的距离函数，若 ， ，则集合 称为 的 邻域。 定义11.4.3 （极限点） 对实数集 于 ， ，且 ， ，如果在 ，则称 是 的任一个 邻域中，都存在不等 的元素 的一个极限点（或凝聚点）。 定义的条件可以写成 定理11.4.1 对实数集 列 使得 定理11.4.2 若 是有界无限集，则 具有极限点。 。 ， ， ， 是 的极限点当且仅当在 中存在点 定义11.4.4 （孤立点） 对实数集 孤立点。 定义11.4.5 （导集与闭集） 对实数集 果 ， ，则称 ， 的所有极限点的集合称为 的导集，记作 。如 ， ， ，若 不是 的极限点，则称 为 的 为闭集。 ， ，则 是闭集，即 。 定理11.4.3对实数集 定理11.4.4 任意个闭集的交集是闭集。有限个闭集的并集是交集。 定义11.4.6 （内点） 对实数集 素，则称 ， 为 ， 的一个内点。 ，如果存在 的 邻域，其中全是 的元 定义的条件可以写成 定义11.4.7 （开集） 对实数集 定理11.4.5 任意个开集的并集是开集，有限个开集的交集是开集。 定理11.4.6 对实数集 (1) 若 (2)若 ， 是开集，则 是闭集，则 ， 是闭集。 是开集。 ， ，若 的元素都是 的内点，则称 为开集。 11.5 模糊子集 定理11.5.1 （特征函数的性质） 设 (1) (2) (3) (4) (5) (6) (7) (8) , , , 是论域， ， , , , ， ，＋、－、＊是算术加、减、乘法， 定义11.5.1 （模糊子集与隶属函数） 设 并称 是论域， 为 上的一个模糊子集 是指：存在一个函数 ， 的隶属函数。 定义11.5.2 设 是全集， ，则 , . 、 、 分别称为并集、交集、绝对补集。 、 、 具有下列隶属函数 定义11.5.3 （截集） 设 是全集， 称为 的 截集， 可以写作 。 ，对 ，集合 定理11.5.2 设 (1) (2) 定理11.5.3 设 (1) (2) . 是全集， , ， ，则 是全集， ， ， ，则 定理11.5.4 （分解定理） 设 是全集， ， . （其中 表示集合的上确界， 表示集合的下确界） ， 是 的特征函数，则 定义11.5.4 （支集 核 边界 正规模糊集） 设 是全集， ，则 称为 核 就称 的支集，截集 的元素完全隶属于 称为 。若 的核， ，就称 ：称为 的边界。 ， 为正规模糊集；若 为非正规模糊集。 12.1实数集合 定义12.1.1（整数） 对自然数集合 , , 则称 的元素为正整数， 的元素为负整数， 的元素为整数。 ，令 定义12.1.2一个整数的相反数分别是 当 , 当 定义12.1.3在集合 当且仅当 在集合 上定义小于关系 当且仅当 定义12.1.4（等价关系 为，对任意的 . ） 对整数集合 ，令 ，并称 集合。对 意的 当且仅当 其中 是在 上定义的乘法，＝是 是等价关系。 ，即 表示 是集合 中的元素 对等价关系 的商集， 上的相等关系。 ，可以用 ， 代替 ， 。在 是 上的因式的为，对任 , 。 上定义小于等于关系 为，对任意的 ， , 上定义关系 定理12.1.1 上的关系 定义12.1.5 （有理数集合） 则称 、 的元素为有理数，一般用 是互素的整数，且 。 ，并习惯上取 定义12.1.6在 上定义等于关系 当且仅当 为，对任意的 。 ： ， ， 定义12.1.7（基本函数） 如果 满足条件， (1) (2) , 则称 值 称为一个基本序列，它有时写为 。 在以下定义与定理中， 本函数。 定理12.1.2当 ： 取常数值时， , 是一个基本函数，或有界非递减函数。当 是一个基本函数时，则函数 表示所有基本函数的集合。 表示 是一个基 是基本函数。即对任意的 ， 是一个基本序列。 定理12.1.3存在不是常值函数的基本函数。 定义12.1.8对基本函数的集合 ， 当且仅当 ，定义 上的关系 为，对任意的 ， . 直观上说， 定理12.1.4 定理12.1.5设 。 定义12.1.9（实数集）令 称 的元素为实数，称 ，即 为实数集合。 是集合 对等价关系 的商集，则 等价于 上的关系 : 和 的序列的极限相同。 是等价关系. 和 : 都是常值函数，且 ，则 定义12.1.10在 上定义小于关系 为，对任意的 ， 当且仅当 。 定义12.1.11在 ，即对 上定义小于等于关系 和 ， 。 和小于关系 ， 为，对任意的 当且仅当 当且仅当 12．2集合的等势 定义12.2.1（集合的等势）对集合 就称 和 和 等势，记作 ，有 不等势，记作 和 ，如果存在从 到 到 的双射函数， ，如果不存在从 的双射函数，就称 定理12.2.1 对任意的集合 定理12.2.2对任意的集合 (1) (2) 若 (3) 若 (1) ，则 且 ， ， 、 ， 和 ， ，则 。 定理12.2.3 （康托尔）定理 (2) 对任意的集合 12．3 。 定义12.3.1 （有限集合与无限集合）集合 使 ，集合 。 是无限集合当且仅当 是有限集合，当且仅当存在 不是有限集合，即不存在 ，使 定理12.3.1不存在与自己的真子集等势的自然数。 推论12.3.2 不存在与自己的真子集等势的有限集合。 推论12.3.3任何与自己的真子集等势的集合是无限集合。 推论12.3.4任何有限集合只与唯一的自然数等势。 和 都是无限集合。 12．4集合的基数 定义12.4.1对任意的集合 示，并且 。（有时把 对有限集合 和 。 12-4-1（自然数集合 的基数） 的基数不是自然数，因为 记作 。 12-4-2（实数集合 通常把 的基数） 记作 的基数不是自然数，也不是 （因为 ）。 不与任何自然 ，若 ，则 记作 或 。） 和 ，它们的基数分别用 和 表 数等势。通常用康托尔的记法，把 ，读作“阿列夫零”。 因此， ，读作“阿列夫壹”。因此， 。 12．5基数的算术运算 定义12.5.1 对任意的基数 (1) 若存在集合 ， (2) 若存在集合 和 (3) 若存在集合 和 ，其中 定理12.5.1 对任意的基数 (1) ， 是从 、 到 和 ， ，则 ， ， ，则 和 , ，则 和 ， , 的函数的集合。 ， (2) (3) (4) (5) (6) 12．6基数的比较 定义12.6.1对集合 和 ， 优势于 ， ，记作 ，如果存在从 ，且称基数 到 的单射函数，则称集合 ，记作 。 不大于基数 定义12.6.2对基数 和 ，如果 、 和 且 ， ，则称 小于 ，记作 。 定理12.6.1 对任意的基数 (1) (2) 若 (3) 若 (4) 或 且 且 ，则 则 ， ， 定理12.6.2对任意的基数 (1) (2) (3) (4) 若 或 则 和 、 和 ，如果 ， ，如果 、 ， 是无限基数，则 定理12.6.3对基数 定理12.6.4 (1) 对任意的无限集合 (2) 对任意的无限基数 ， ， 。 。 12．7可数集合与连续统假设 定义12.7.1（可数集合）对集合 定理12.7.1（可数集的性质） (1) 可数集的任何子集是可数集。 (2) 两个可数集的并集和笛卡儿积是可数集。 (3) 若 是无限集合，则 是不可数的。 是可数集， 的元素都 ，如果 ，则称 是可数集合。 (4) 可数个可数集的并集是可数集（该结论可写为：若 是可数集，则 是可数集）。 已知的基数按从小到大的次序排列就是 12-7-1（连续统假设）“连续统假设”就是断言不存在基数 这个假设至今未经证明。有人已证明：根据现有的公理系统，即不能证明它是对的，也不能证明它是错的。 ，使
因篇幅问题不能全部显示，请点此查看更多更全内容
Copyright © 2019- huatuo9.cn 版权所有 赣ICP备2023008801号-1
违法及侵权请联系：TEL:199 18 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务