第一章集合

1.集合的表示

①使用叙述法 ②使用枚举法

2.求解幂集

算出给定集合的所有子集组合成一个集合。注意空集是任何集合的子集。

3.证明两个集合相等A=B

①首先证明AB：xA，......，xB，AB

②其次证明BA：xB，......，xA，BA

xP(A) xA

AB={x|xA或xB}

AB={x|xA且xB}

A-B={x|xA且xB}

AB={x|(xA且xB)或(xB且xA)}

4.判断元素与集合的关系、集合与集合之间的关系：注意空集是任何集合的子集。

5.计算集合的交、并、差

第二章命题逻辑

1.命题符号化

先分析自然语言描述的语义，然后用正确的语法加以表示。

“但”，“虽然...但是”对应合取联结词。

蕴涵联结词的几种说法：

如果P，则Q；因为P，所以Q；只要P，就Q；P仅当Q；只有Q，才有P；除非Q，才P；除非Q，否则┐P

2.判断自然语言描述中是否是命题

分析是否是能唯一判断其真假的陈述句。

3.化简命题公式

利用命题公式的基本等价关系。

4.求析取范式和合取范式

①利用等价公式中的等价关系和蕴涵关系将公式中的、用联结词┐、、来取代。

②重复使用德摩根律和双重否定律可将否定号┐移到各个命题变元的前端，并消去多余的否定号。

③重复利用分配律，可将公式化成一些合取式的析取，或化成一些析取式的合取。

5.极小项和极大项的编码问题

每个极小项只有一组成真赋值，因此可用于给极小项编码，编码规律为：命题变元与1对应，命题变元的否定与0对应。

每个极大项只有一组成假赋值，因此可用于给极大项编码，编码规律为：命题变元与0对应，命题变元的否定与1对应。

6.极小项和极大项的性质

任意两个不同的极小项的合取必为0；

任意两个不同的极大项的析取必为1；

极大项的否定是极小项，极小项的否定是极大项；

所有极小项的析取为永真公式，所有极大项的合取是永假公式。

7.求主合取范式和主析取范式

等价公式转换法：

①先求出该公式所对应的析取范式和合取范式

②在析取范式的短语和合取范式的子句中，如果同一命题变元出现多次，则将其化成只出现一次。

③去掉析取范式中所有永假公式的短语和合取范式中所有永真公式的子句，即去掉短语中含有形如┐PP的子公式和子句中含有形如┐PP的子公式。

④若析取范式的某一个短语中缺少该命题公式中所规定的命题变元，则加入，用(┐PP)Q=Q，然后分配律展开。

若合取范式的某一个子句中缺少该命题公式中所规定的命题变元，则加入，用(┐PP)Q=Q，然后分配律展开。

⑤利用幂等律将相同的极小项和极大项合并，根据极小项和极大项的编码规则，利用交换律进行由小到大的顺序调整。

真值表技术：

①从真值表中选出公式的真值结果为真的所有行，在这样的每一行中，找到其每一个解释对应的极小项（利用极小项编码规则），将这些极小项进行析取就可以得到相应的主析取范式。

②从真值表中选出公式的真值结果为假的所有行，在这样的每一行中，找到其每一个解释对应的极大项（利用极大项编码规则），将这些极大项进行合取就可以得到相应的主合取范式。

8.判断命题公式类型（永真公式（重言式）、永假公式（矛盾式）、可满足公式）或证明给定公式是否是永真公式。

①利用真值表技术，若每一个解释下，公式都为真，则为永真公式。

②利用基本等价关系对公式进行化简，从而判断公式的类型。

③将公式化简成范式来判断公式的类型：

公式G为永真公式，则公式G的合取范式中的每个子句至少包含一个命题变元及其否定。

公式G为永假公式，则公式G的析取范式中的每个短语至少包含一个命题变元及其否定。

④将公式化简成主范式来判断公式的类型：

如果命题公式为永真公式，它的主析取范式包含所有的极小项。

如果命题公式为永假公式，它的主合取范式包含所有的极大项。

9.判断两个公式是否等价

①利用真值表技术判断两个公式的真值情况是否一致，一致则等价。

②利用PQ是否是永真公式，来判断公式P、Q是否等价。

③利用等价公式转换法看是否能转换到另一个公式。

④将两个命题公式化成对应的主范式

两个命题公式等价，则它们对应的主析取范式之间等价，或者它们对应的主合取范式之间等价。

10.命题逻辑的推理理论：证明结论有效性（往往倒推，从结论来考虑整个问题）

①真值表技术：

对所有G1，G2，...，Gn都具有真值1的行，如果在每一个这样的行中，H也具有真值1，则H是G1，G2，...，Gn的逻辑结果。

对所有H具有真值0的行，如果在每一个这样的行中，G1,...,Gn中至少有一个公式的真值为0，则H是G1，...，Gn的逻辑结果。

也就是G1G2...GnH为永真公式，则H是G1，...，Gn的逻辑结果。

②直接证明法

可以构造一个描述推理过程的命题公式序列。

若是一个已知的前提，此时使用的是规则P。

若是其中某些前提的结论或中间结论，此时使用的是规则T。

若要证明“PQ”的公式形式，则可将P作为假设前提，引入到推理过程中作为附加前提，设法证明公式Q也会出现在推理公式的序列中，此时使用的是规则CP（确实是一对）

③间接证明方法

将要证明的结论的否定作为假设加入到前提集合当中，若能与原有的前提集合一起推导出一个矛盾式（P┐P）来，则说明原结论是有效的，否则原结论是无效的。

④等价公式转换法

利用等价公式得出G1G2...GnH为永真公式，则论断是有效的。

11.综合证明题

给出命题的自然语言描述，要求先进行符号化，然后证明结论的有效性，一般使用前面总结的解题技巧即可完成证明。

第三章谓词逻辑（分析构成原子命题的内部成分）

1.谓词公式的符号化

找出命题中的量词、个体词、谓词。在对一个命题进行符号化之前假定其个体域都是全总个体域，对具体问题的个体域，可用一特性谓词来表示；

这种特性谓词在加入命题函数时必定遵循如下原则:

①对于全称量词（x），刻画其对应个体域的特性谓词作为蕴涵式的前件加入。

②对于存在量词（x），刻画其对应个体域的特性谓词作为合取式的合取项加入。

2.判断谓词公式中的约束变元和自由变元

主要就是找量词的辖域。在量词辖域内的个体变量就是约束变元，反之就是自由变元。

具体来讲就是：

①若量词后有括号，则括号内的子公式就是该量词的辖域。

②若量词后无括号，则与量词邻接的子公式为该量词的辖域。

3.判断谓词公式是否是有效公式

一般先用等价关系，从整体上分析给定的谓词公式，有等价取代的方法将原公式简化为一个有效公式的形式。若能断定是有效公式给出严格证明，否则举出一个反例。

谓词公式的可判定性：

①谓词逻辑是不可判定的。

②只含有一元谓词变项的公式是可判定的。

③如下形式的公式：

(x1)(x2)...(xn)P(x1,x2...,xn)

(x1)(x2)...(xn)P(x1,x2,...,xn)

若P中无量词和其他自由变元时，也是可判定的。

④个体域有穷时的谓词公式是可判定的。

4.对约束变元的改名和对自由变元的代入

改名规则：

①将量词中出现的变元以及该量词辖域中此变量之所有约束出现都用新的个体变元替换。（修改完整）

②新的变元一定要有别于改名辖域中的所有其他变量。（修改后不能再有混淆）

代入规则：

①将公式中出现该自由变元的每一处都用新的个体变元替换。

②新变元不允许在原公式中以任何约束形式出现。也可用个体常量代入。

5.计算谓词公式的前束范式（量词都在母式之前的公式）

谓词逻辑中的任一个公式都可化为与之等价的前束范式，但前束范式不唯一

求解过程：

①如果公式中有联结词“”、“”，则消去联结词“”、“”；

②反复运用德摩根律和双重否定律，直接将“┐”内移到原子谓词公式的前端；

③使用谓词的等价关系将所有量词提到公式的最前端。

6.证明两个公式之间是等价关系

①完全同命题逻辑中的证明过程，利用已知的一些等价关系，从所给两个公式中的一个向另一个的表示形式进行推导，或从两个公式同时进行推导而得到一个相同的公式表示形式，从而证明了两个给定公式彼此是等价的。

②或者利用公式GH，证明公式为有效公式。

7.谓词逻辑之间的蕴涵关系的证明

①在推导的过程中，可以引用命题演算中的规则P和规则T；

②如果结论是以条件的形式（或析取形式）给出，还可以使用规则CP；

③为了在推导过程中消去量词，可以引用规则US和规则ES；

④当所要求的结论可能被定量时，此时可引用规则UG和规则EG将其量词加入；

⑤证明时可采取如命题演算中的直接证明方法和间接证明方法；

⑥在推导过程中，对消去量词的公式或公式中不含量词的子公式完全可以引用命题演算中基本的等价关系和基本的蕴涵关系

⑦在推导过程中，对含有量词的公式可以引用谓词中基本的等价关系和基本的蕴涵关系。

一些难点：

①如果既要使用规则US又要使用规则ES消去公式中的量词，而且选用的个体是同一个符号，则必须先使用规则ES，再使用US。

②如果一个变量用规则ES消去量词，则对该变量在添加量词时，只能使用规则EG，而不能使用规则UG；

如果使用规则US消去量词，则对该变量在添加量词时，可使用规则EG和规则UG；

③如果有两个含有存在量词的公式，则当用规则ES消去量词时，不能选用同一个常量符号来取代两个公式中的变元，而应使用不同的常量符号取代他们；

④在用规则US和规则ES消去量词时，此量词必须位于整个公式的最前端；

⑤在添加量词x、x时，所选用的x不能在公式G(c)或G(y)中以任何约束出现。

注:若公式G中无自由出现的个体变元，则称为闭式，闭式是一个命题。

第四章二元关系（关系是以序偶为元素的特殊集合）

1.关系性质的判定

①自反性

（1）定义：如果对xA,都有<x,x>R,那么称R在A上是自反的，R具有自反性。

（2）如果关系R是反自反的，那么R一定不是自反的。

（3）关系图法：关系R是自反的当且仅当R的关系图中每个结点都有自环。

（4）关系矩阵法：关系R是自反的当且仅当R的关系矩阵的主对角线上的元素全为1.

（5）判定定理：R是自反的R

②反自反性

（1）定义：如果对xA,都有<x,x>R,那么称R在A上是反自反的，R具有反自反性。

（2）如果关系R是自反的，那么R一定不是反自反的。

（3）关系图法：关系R是自反的当且仅当R的关系图中每个结点没有自环。

（4）关系矩阵法：关系R是自反的当且仅当R的关系矩阵的主对角线上的元素全为0.

（5）判定定理：R是反自反的R=

③对称性

（1）定义：对x，yA，如果<x,y>R，那么<y,x>R,则称关系R是对称的，R具有对称性。

（2）关系图法：关系R是对称的当且仅当R的关系图中，任何一对结点之间，要么有方向相反的两条边，要么无任何边。

（3）关系矩阵法：关系R是对称的当且仅当R的关系矩阵为对称矩阵。

（4）判定定理：R是对称的R=

④反对称性

（1）定义:对x，yA，如果<x,y>R且<y,x>R，那么x=y,则称关系R是反对称的，R具有反对称性。

（2）关系图法：关系R是反对称的当且仅当R的关系图中，任何一对结点之间至多有一条边。

（3）关系矩阵法：关系R是反对称的当且仅当R的关系矩阵满足=0，i,j=1,2,...,n，ij。

（4）判定定理：R是反对称的R=

⑤传递性

（1）定义：对x，y，zA，如果<x,y>R且<y,z>R，那么<x,z>R，则称关系R是传递的，R具有传递性。

（2）关系图法：关系R是传递的当且仅当在R的关系图中，任何三个结点x,y,z（可以相同）之间，若从x到y有一条边存在，从y到z有一条存在，则从x到z一定有一条边存在。

（3）关系矩阵法：关系R是传递的当且仅当在R的关系矩阵中，对i,j,k{1,2,...,n}，若=1且=1，必有=1。

（4）判定定理：R是传递的RR=R

2.关系性质的保守性

设R，S是定义在非空集合A上的二元关系，则

①若R，S是自反的，则，RS，RS，RR也是自反的；

②若R，S是反自反的，则，RS，RS，R-S也是反自反的；

③若R，S是对称的，则，RS，RS，R-S也是对称的；

④若R，S是反对称的，则，RS，R-S也是反对称的；

⑤若R，S是传递的，则，RS也是传递的。

3.计算关系的交、并、补、差、复合、求逆以及幂运算

关系的交、并、补、差跟集合的运算一致。

关系复合可以用复合定义或者用关系矩阵的布尔积进行运算。

4.运算定律

①笛卡尔积

（1）A(BC)=(AB)(AC)

（2）(BC)A=(BA)(CA)

（3）A(BC)=(AB)(AC)

（4）(BC)A=(BA)(CA)

②复合运算

设A，B，C和D是任意四个非空集合，R是从A到B的关系，S1，S2是从B到C的关系，T是从C到D的关系，则：

（1）=

（2）

（3）

（4）

③逆运算

（1）=

（2）

（3）

（4）

④幂运算

，则

5.关系闭包的计算

①加入最少的序偶元素，使其具有自反性或对称性或传递性。为自反闭包r(R)，对称闭包s(R)，传递闭包t(R)。

②利用关系图进行添加边，使其具有相应的性质。

在没有自环的结点处加上自环，可得r(R)的关系图。

将每条单向边全部改成双向边，可得s(R)的关系图。

从每个结点出发找到其终点，如果该结点到其终点没有边相连，就加上此边，可得t(R)的关系图。

③利用定理计算

设R是集合A上的二元关系

（1）r(R)=R

（2）s(R)=R

（3），若，则

6.关系性质的证明，关系运算律的证明

与关系运算有关的证明，通常是证明等式成立或者包含关系成立，因此，可以利用集合相等或集合包含的定义采用“按定义证明方法”证明。

第五章特殊关系

1.给定等价关系，计算其等价类和商集

等价关系：如果关系R是自反的、对称的、传递的，则称R为非空集合A上的等价关系。

计算等价类：给定非空集合A上的等价关系R，对每一个A中的元素，将A中与之有关系的元素放在一个集合中，就可以得到该元素生成的等价类。

计算商集：将所有不同的等价类构成集合就得到A关于R的商集。

2.给定集合的划分（或商集）计算对应的等价关系

集合A上的一个商集A/R实际上对应了集合A的一个划分。

利用定理求解：给定集合A上的一个划分π={S1,S2,...,Sn}，则由该划分确定的关系

R=(S1S1)(S2S2)...(SnSn)

是A上的等价关系。

3.证明等价、偏序、全序、良序关系

等价关系：用定义证明自反性、对称性和传递性同时成立。

偏序关系：用定义证明自反性、反对称性和传递性同时成立。

全序关系：首先是偏序关系，然后若对任意x，yA，总有xy或yx，二者必居其一。其中“”是偏序关系。全序关系的哈斯图是一条链。

良序关系：首先是全序关系，然后说明A的任何一个非空子集都有最小元，则是良序关系。

注：良序关系全序关系偏序关系

有限全序集一定是良序集

4.画出等价关系的关系图、偏序关系的哈斯图

等价关系的关系图：确保其关系图每个结点都有自环，两节点之间有边则一定有两条边，x到y有边，y到z有边，则x到z一定有边。

偏序关系的哈斯图：首先正确画出其关系图，根据关系图作如下操作：

①取消每个结点的自环（因自反性）

②取消所有由于传递性出现的边，即若x到y有边，y到z有边，则去掉x到z这条边。（因传递性）

③重新排列每条边，使得边的箭头方向全部向上，然后去掉这些箭头。（因反对称性）

简化所得为哈斯图。

5.寻找偏序关系的8个特殊元素

首先画出其对应的哈斯图，根据哈斯图和特殊元素的定义找出特殊元素。

求最大元、最小元、极大元、极小元：

设<A,>是偏序集，B是A上的任何一个子集，若存在元素bB，则

（1）B的最大元、最小元、极大元、极小元如果存在，一定在B中。

（2）b是B的最大元 B中所有元素都比b小

（3）b是B的最小元 B中所有元素都比b大

（4）b是B的极大元 B中没有比b大的元素

（5）b是B的极小元 B中没有比b小的元素

求上界、上确界、下界、下确界：

（1）子集合B的上下界和上下确界可在集合A中寻找

（2）一个子集合B的上下界不一定存在，如果存在，可以不唯一

（3）一个子集合B的上下确界不一定存在，如果存在，一定唯一

（4）一个子集合B有上（下）确界，一定有上（下）界，反之不然

定理1：

（1）若b是B的最大元b是B的极大元、上界、上确界

（2）若b是B的最小元b是B的极小元、下界、下确界

（3）若a是B的上界，且aBa是B的最大元

（4）若a是B的下界，且aBa是B的最小元

定理2：

（1）若B存在最大元，则B的最大元是唯一的

（2）若B存在最小元，则B的最小元是唯一的

（3）b是B的最大元b是B的唯一极大元

（4）b是B的最小元b是B的唯一极小元

（5）若B存在上确界，则B的上确界是唯一的

（6）若B存在下确界，则B的下确界是唯一的

6.拟序关系（反自反、反对称性、传递性）和偏序关系

R是集合A上的偏序关系，则R-是A上的拟序关系

S是集合A上的拟序关系，则S是A上的偏序关系

第六章函数（特殊关系）

1.对给定的有限集合A和B上的函数，求有多少个不同的函数，多个不同的单满双射

如果A的基数为m，B的基数为n，对A中的每个元素，在B中都有n中选择，所以不同的函数个数为

单射：当m=n时，有m！个，当mn时，具体分析。

双射：n=m，有m！个

2.判断给定的关系是否是函数

利用定义去判断

设f是从集合A到B的关系，如果对每个xA，都存在唯一的yB，使得<x,y>f，则关系f为从A到B的函数。

3.判断或证明具体函数是单射、满射、双射

利用定义去判断和证明

单射：对x1，x2A，如果x1x2，有f(x1)f(x2)，则f是从A到B的单射。

满射：对yB，一定存在xA，使得f(x)=y，则f是从A到B的满射

双射：先证单射，再证满射。

4.函数的复合运算

函数的复合运算的运算次序是从左到右依次计算，与关系的计算顺序一致，但是函数的复合运算则是要求前一函数的值域包含与后一含函数的定义域。

对任意xA，由

定理1：

设f和g分别是从A到B和从B到C的函数，则

（1）若f，g是满射，则也是从A到C的满射。

（2）若f，g是单射，则也是从A到C的单射。

（3）若f，g是双射，则也是从A到C的双射。