第一章命题逻辑

数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科，它与数学的其他分支、计算机科学、人工智能、语言学等学科均有密切的联系，并且日益显示出它的重要作用和更加广泛的应用前景。数理逻辑的内容相当丰富，本章主要介绍命题逻辑。 通过本章的学习，弄清命题与陈述句的关系；弄清由5种基本联结词联结的复合命题的逻辑关系及其真值；记住24个基本等值式；能够准确求出主析取范式和主合取范式；会用多种方法判断公式的类型及其判断两个公式是否等值；弄清楚推理的形式结构，掌握判断推理是否正确的方法，以及对某些正确的推理会构造它的证明。

●1.1命题符号化及联结词

数理逻辑研究的中心问题是推理，而推理的前提和结论都是表达判断的陈述句。因而，表达判断的陈述句构成了推理的基本单位。本节主要介绍命题与真值，五种常用的联结词，以及其由它们组成的基本复合命题否定式、合取式、析取式、蕴涵式、等价式的概念。

●1.2命题公式

命题公式是由命题常项、命题变项、联结词、括号等组成的符号串。但并不是由这些符号任意组成的符号串都是命题公式，本节学习命题公式的定义、公式的层次、赋值或解释、真值表等相关概念，以及公式的分类。

●1.3命题公式的等值演算

给定大于等于1的n个命题变项，按合式公式的形成规则可以形成无穷多个命题公式，而在这无穷多个命题公式中，有些具有相同的真值表。例如，n=2时，只能生成16个真值不同的命题公式，这就存在着如何判断哪些命题公式具有真值的问题。本节主要学习等值式、基本的等值式、等值演算及置换规则等知识。

●1.4范式

本节介绍命题公式的标准型——主析取范式和主合取范式。同一真值函数所对应的所有命题公式具有相同的标准型，这为判断两命题公式是否等值以及判断公式的类型又提供了一种方法。

●1.5联结词全功能集

在一个形式系统中，多少个联结词最“合适”呢？一般来说，在自然推理系统中，联结词集中的联结词可以多些，而公理系统中联结词集中的联结词越少越好。但联结词集中的联结词无论是多些还是少些，它必须能够具备所有真值函数的能力，具有这样性质的联结词集叫全功能集。本节主要介绍真值函数、联结词全功能集、与非式、或非式的概念，以及联结词全功能集的两个定理。

●1.6推理理论

推理是从前提推出结论的思维过程，前提是指已知的命题公式，结论是指从前提出发应用推理规律推出的命题公式。本节主要学习推理的形式结构、推理定律与推理规则、判断推理是否正确的方法、构造证明法等内容。

第二章一阶逻辑

本章主要介绍一阶逻辑（谓词逻辑）。在命题逻辑中，命题是命题演算的的基本单位。命题只是一种比较简单的陈述，常常不足以表现人们想要表达的内容，甚至无法处理一些简单而又常见的推理，为了表达出一句话的内在含义，需要进一步区分量词、个体词和谓词，这就是一阶逻辑所研究的内容，一阶逻辑也称谓词逻辑。 通过本章的学习，知道同一个命题在不同个体域内可能有不同的符号化形式，也可能有不同的真值，因而在将一个命题符号化之前，必须弄清楚个体域，若没有指定个体域，应采用全总个体域；掌握一阶逻辑命题符号化时，经常使用的两种形式的公式；掌握一阶逻辑公式的3中类型；记住主要的等值公式。

●2.1一阶逻辑基本概念

本节主要学习个体词、量词与谓词的相关概念，以及一阶逻辑中命题的符号化。在一阶逻辑中，简单命题被分解成主语和谓语两部分。表示主语的词被称为个体词，具体或特定的个体词称为个体常项，抽象的或泛指的个体词称为个体变项，个体变项的取值范围称为个体域。表示谓语的用来刻画个体词性质或个体词之间关系的词称为谓词，谓词分为谓词常项和谓词变项。表示数量的词称为量词。

●2.2一阶逻辑合式公式及解释

根据一阶逻辑命题符号化的有关概念及方法，为了使符号化能更准确和规范以及正确进行谓词演算和推理，必须给出一阶逻辑中合式公式严格的形式定义。本节首先给出了本书中使用的字母表，然后介绍项、原子公式、合式公式、指导变元和辖域、解释和赋值、公式的分类、代换实例等概念。

●2.3一阶逻辑等值式与前束范式

本节首先学习等值式的定义，并以定理的形式给出了一阶逻辑中一些重要的等值式，如量词否定等值式、量词辖域收缩或扩张等值式、量词分配等值式；然后给出前束范式的定义及求给定公式的前束范式的方法。

第三章集合的基本概念和运算

本章学习集合的基本概念和运算。通过学习能够正确表示一个集合，会画文氏图；能够判定元素是否属于给定的集合；能判定两个集合之间是否存在包含、相等或真包含的关系；能熟练进行集合的并、交、相对补、绝对补、对称差运算，会计算幂集；并能够求解与有穷集合计数相关的实际问题。

●3.1集合的基本概念

集合是不能精确定义的基本的数学概念，一般认为一个集合指的是一些可确定的、可分辨的事物构成的整体。本节主要学习集合与元素，集合与集合的关系，以及空集、全集与幂集的概念。

●3.2集合的基本运算

给定两个集合，可以通过集合的并、交、相对补、绝对补、对称差等运算产生新的集合。本节主要介绍集合的这些基本运算，以及集合的基本运算遵从的算律。

●3.3集合中元素的计数

根据集合中所含元素的量，即集合的基数，将集合分为有穷集和无穷集。解决有穷集合的技术问题有两种方法：文氏图和包含排斥原理。通过本节内容的学习，能够求解与有穷集合计数相关的实际问题。

第四章二元关系和函数

本章学习集合的笛卡儿积与二元关系，关系的运算、性质和闭包，等价关系和偏序关系，函数的定义和性质，以及函数的复合和反函数相关知识。

●4.1集合的笛卡儿积与二元关系

本章学习有序对与笛卡儿积的概念，关系、从A到B的关系和A上的关系，关系表示法和关系的性质，等价关系和划分等知识。能够正确地使用集合表达式、关系矩阵和关系图表示给定的二元关系。通过学习能正确的使用集合表达式、关系矩阵和关系图表示给定的二元关系；给定A上的关系R，能判别R的性质；给定A上的等价关系R，求所有的等价类和商集；给定A上的偏序关系画出偏序集的哈斯图；确定偏序集的极大元、极小元、最大元、最小元、最大下界、最小上界；给定集合A、B和函数f，能够判别函数是否是单射、满射或双射。

●4.2关系的运算

本节学习以下几种关系的基本运算：定义域、值域、域、逆、合成、限制、像、幂，并给出这些运算主要性质的几个定理。

●4.3关系的性质

设R是A上的关系，R的性质主要有以下5种：自反性、反自反性、对称性、反对称性和传递性。本节给出了这5种性质的定义及其在关系矩阵、关系图中的特点。

●4.4关系的闭包

本节研究关系的自反、对称和传递的闭包，主要学习自反闭包的定义，以及如何求A上的关系R的闭包，并通过定理给出了构造的方法。

●4.5等价关系和偏序关系

本节讨论两种最重要的关系--等价关系和偏序关系，给出偏序集、全序集的概念，以及偏序集的极大元、极小元、最大元、最小元、最大下界、最小上界。

●4.6函数的定义和性质

函数也称作映射，它是一种特殊的二元关系。本节学习函数的定义，以及某些函数具有的单射、满射或双射的性质。

●4.7函数的复合和反函数

函数是特殊的二元关系，两个函数的复合本质上就是两个关系的合成，本节学习复合函数的概念，以及双射函数的反函数。

第五章图的基本概念

本章学习图论的知识，图论的内容十分丰富，应用相当广泛，很多学科，像运筹学、信息论，控制论、计算机科学等，都以图作为工具解决实际问题和理论问题，本章主要学习图的基本知识。主要知识有无向图和有向图的定义，端点、边的关联与相邻，多重图与简单图，n阶完全图、子图等基本概念，以及图论中的基本定理握手定理和图的同构；通路、回路和图的连通性的定义及定理，图的关联矩阵、邻接矩阵和可达矩阵，以及图的最短路径、关键路径和着色问题等基本概念及方法。

●5.1无向图与有向图

本节学习无向图和有向图的定义，端点、边的关联与相邻，多重图与简单图，n阶完全图、子图等基本概念，以及图论中的基本定理握手定理和图的同构。

●5.2通路、回路和图的连通性

本节学习图论中两个重要而又基本的概念通路与回路，根据不同情况，通路和回路分为简单通路、简单回路、初级通路、初级回路、复杂通路、复杂回路；还学习图的连通性，包括弱连通、单向连通和强连通，以及图的点割集和边割集。

●5.3图的矩阵表示

本节学习图的矩阵表示，用矩阵表示图便于用代数方法研究图，同时也便于计算机的存储和处理。由于矩阵的行列有固定的顺序，因此在用矩阵表示图之前，必须规定图的顶点和边的顺序。本节讨论图的关联矩阵、邻接矩阵和可达矩阵。

●5.4最短路径、关键路径和着色

本节学习带权图的最短路径、关键路径和着色。最短路径问题是求带权图中指定两点之间的最短路径和举例，Dijkstra标号法是最短路径问题常用的有效算法，它适用于所有的权非负的情况。项目网络图中从始点到终点的最长路径为关键路径。给无环的无向图的每一个顶点涂一种颜色，使得相邻的顶点涂不同的颜色，称为图的点着色，简称着色。

第六章特殊的图

本章学习四种特殊的图，二部图、欧拉图、哈密顿图和平面图。主要学习四种特殊的图的定义以及如何判别一个图是哪一种图的方法。弄清完美匹配与完备匹配的区别；注意区分有哈密顿回路或哈密顿通路的必要条件和充分条件，注意K5和K3,3在平面图理论中的特殊地位，掌握卡拉图斯基定理。

●6.1二部图

本节学习二部图、完全二部图、匹配、完备匹配等相关概念的定义。给出判断一个图是否是二部图的定理，并给出存在完备匹配充分必要条件的定理。

●6.2欧拉图

经过图中每条边一次且仅一次并且行遍图中每个顶点的回路（通路），称为欧拉回路（欧拉通路）。存在欧拉回路的图称为欧拉图。本节学习欧拉图的定义及是否存在欧拉通路和回路的判别法，并给出实例讲解。

●6.3哈密顿图

经过图中每个顶点一次且仅一次的回路（通路）称为哈密顿回路（通路），存在哈密顿回路的图称为哈密顿图，本节学习哈密顿图的定义，以及判断有哈密顿回路或哈密顿通路的必要条件和充分条件，

●6.4平面图

如果图G能画在平面上使得除顶点处外没有边交叉出现，则称G为平面图。本节学习平面图的相关定义，如平面嵌入、平面图的面与次数、极大平面图、极小非平面图、平面图的对偶图、地图着色等，以及一些关于平面图性质及判定的重要定理。

第七章树

本章学习无向树和生成树、基本回来与基本回路系统、基本割集与基本割集系统、最小生成树，有向树及树根、家族树、根子树、有序树、树根的分类、最优树等概念，给出了相应的定理及应用，并介绍树在计算机科学技术中的两个应用前缀码与最佳前缀码。

●7.1无向树及生成树

不含回路的连通无向图称为无向树，若无向图G的生成子图T是一棵树，则称T为G的生成树。本节还学习基本回来与基本回路系统、基本割集与基本割集系统、最小生成树的概念，以及相应的定理及实例。

●7.2树根及其应用

本节学习有向树及树根、家族树、根子树、有序树、树根的分类、最优2叉树等概念，并给出求最优2叉树的算法，及树在计算机科学技术中的两个应用前缀码与最佳前缀码。