0

本文只是复试复习的笔记，99%内容非原创，仅此而已。【使用的是华南理工大学的公开课】

1

1.1

1.1.1命题

命题：是用陈述句表示的一个为真或者为假，但不能同时即为真又为假的判断语句。（或判断结果唯一的陈述句，或客观上存在唯一真值的陈述句）

命题的真值：判断的结果，真（T或者1）或假（F或0）

真命题：真值为真的命题

假命题：真值为假的命题

下面的句子哪些是命题？若是请判断它的真值

1.北京是中国的首都。（Y 真）

2.2+3=6.（Y 假）

3.3-x=5.（N 真值不确定）

4.请关上门。（N 祈使句）

5.几点了？ （N 疑问句）

6.除地球外的星球有生物。（Y 真值确定，但未知）

7.多漂亮的花啊！ （N 感叹句）

8.我只给所有不给自己理发的人理发。（悖论）

引入英文字母表示任意的命题，如：

用p表示命题“2+3=6“，这时p的真值为假（F）。也可以用p表示命题”2+3=5“，这时p的真值为真（T）

1.1.2联接词

简单命题（原子命题）：不能分解为更简单的陈述语句的命题

如：

北京是中国的首都。这是一个简单命题，因为它是最简便的了，不能再分解了。

复合命题：由两个或几个简单句和连词组合而成的命题

如：

如果明天天气好，我们就去爬山。这个句子由明天天气好，我们去爬山这两个句子组成，然后用如果 就这两个连词连起来，所以是复合命题

命题的符号化：用英文字母或英文字母和联结词的组合表示命题，称为命题的符号化

联结词—–连词

否定$\neg$

设p是一个命题，$\neg$p表示一个新命题”非p“。命题$\neg$p称为p的否定。当且仅当p的真值为假时，$\neg$p的真值为真

下面是真值表

例如：

p：今天是晴天。

则

$\neg$p：今天不是晴天。

”非“，”不“，”没有“，”无“，”并非“等都可用$\urcorner$来表示。

合取$\wedge$

设p、q表示任意两个命题，p$\wedge$q可表示复合命题”p并且q“。当且仅当p和q的真值同时为真时，p$\wedge$q的真值为真。

真值表如下

例如：

p：今天是晴天

q：今天去公园

p$\wedge$q：今天是晴天并且今天去公园

”和“，”与“，”也“，”并且“，”既…又…“，”不仅…而且…“，”虽然…但是…“等都可用$\wedge$来表示

析取$\vee$

设p、q表示任意两个命题，p$\vee$q可表示复合命题”p或q“。当且仅当p和q的真值同时为假时，p$\vee$q的真值为假

真值表如下

例如：

p：今天去看电影

q：今天去公园

p$\vee$q：今天去看电影或今天去公园

”或“，”可能…可能…“，”或者…或者…“等可用$\vee$表示

在自然语言中的”或“具有二义性：兼容性或和不兼容性或

兼容性或：电灯不亮是灯泡或线路有问题所致。【这里是灯泡有问题或者线路有问题还或者两个都有问题，也就是说灯泡跟线路有没有问题是不矛盾的，所以这种或就叫兼容性或】

不兼容性或（排斥或）：派小王或小李中的一人去开会【要么小王去，要么小李去，不能两个人都去，所以这种或叫做排斥或】

$\vee$表示兼容性或

例如：

p：电灯不亮是灯泡有问题所致

q：电灯不亮是线路有问题所致

p$\vee$q:电灯不亮是灯泡或线路有问题所致

p：派小王去开会

q：派小李去开会

（p$\vee$$\neg$q)$\vee$($\neg$p$\wedge$q):派小王或小李中的一人去开会

蕴含$\rightarrow$

设p、q表示任意两个命题，p$\rightarrow$q可表示复合命题”如果p，则q“。当且仅当p的真值为真，q的真值为假时，p$\rightarrow$q的真值为假

下面是真值表

例如：

p:今天天启晴朗

q：我们去海滩

p$\rightarrow$q：如果今天天气晴朗，我们就去海滩

蕴含式p$\rightarrow$q

p为蕴含前件，q为蕴含后件

p是q的充分条件，q是p的必要条件

表示：”如果p，则q“，”如果p，那么q“，”当p则q“，”p仅当q“等

假设：

p：天气晴朗；q：我们去海滩

1. 如果天气晴朗，我们去海滩。p$\rightarrow$q
2. 仅当天气晴朗，我们去海滩。q$\rightarrow$p

等价⟷

设p、q表示任意两个命题，p⟷q可表示复合命题”p当且仅当q“。当且仅当p和q的真值同时为真或同时为假时，pq⟷的真值为真

真值表如下所示

例如：

p：两个三角形是全等的。

q：两个三角形的三条对应边相等。

p⟷q：两个三角形是全等的当且仅当他们的三条对应边相等

等值式p⟷q

表示p与q互为充分必要条件的逻辑关系

表示形如”p当且仅当q“，”如果p，那么q，反之亦然“等的命题。

例题：

将下列命题符号化：

1.虽然天气很冷，老王还是来了

设p：天气很冷。q：老王来了

则符号化为：p$\wedge$q

2.小王和小李是好朋友

p：小王和小李是好朋友【这句虽然有连词”和“，但是个简单句，所以用p表示即可】

3.小王和小李是好学生

设p：小王是好学生；q：小李是好学生。符号化为：p$\wedge$q

4.小王或小李中的一人是游泳冠军

设p：小王是游泳冠军；q：小李是游泳冠军。则符号化为：（p$\wedge$$\neg$q)$\vee$($\neg$p$\wedge$q)

5.只有你学过微积分或是数学系的学生，才可以选修这门课

设p：你学过微积分；q：你是数学系的学生；r：你可以选修这门课

符号化：r$\rightarrow$（p$\vee$q）【为什么不是（p$\vee$q）在前面，因为这句话的如果是r，即整句话是如果你可以选修这门课，那么你学过微积分或是数学系的学生】

6.如果明天早晨6点不下雨，我就去跑步

设p：明天早晨6点下雨；q：我就去跑步

符号化为：$\neg$p$\rightarrow$q或者$\neg$q$\rightarrow$p【我感觉也可以是p：明天早晨6点不下雨。p$\rightarrow$q。但仔细想了想，好像复合命题需要最简陈述句且添加连词，这样写好像不太行的样子】

7.今天下雨与3+3=6

设p：今天下雨；q：3+3=6。符号化为：p$\wedge$q

8.登录服务器必须输入一个有效的口令

设p：登录服务器；q：输入一个有效的口令。符号化：p$\rightarrow$q

9.2+3=5的充要条件是加拿大位于亚洲

设p：2+3=5；q：加拿大位于亚洲。符号化：p⟷q

优先级

由高到低，从左到右

(), $\neg$, $\wedge$, $\vee$, $\rightarrow$, ⟷

真值表如下

括号有时被省略，如$\neg$p$\wedge$q是$\neg$p和q的合取，这里是省略了$\neg$p的括号，即($\neg$p)$\wedge$q

1.2.1命题公式

命题常元：代表特定简单命题

命题变元：代表任意命题，取值1（真）或者0（假）的变量

例题

定义 命题公式（公式）的定义如下：

1.每一个命题常元或命题变元都是命题公式

2.如果A是命题公式，则（$\neg$A)是命题公式

3.如果A和B都是命题公式，则（A$\wedge$B），（A$\vee$B），（A$\rightarrow$B），（A$\Leftrightarrow$B）都是命题公式。

4.一个由命题常元或命题变元、联结词和括号所组成的符号串是命题公式，当且仅当这个符号串是有限次应用上面的步骤得到的。

一个含有命题变元的命题公式的真值是不确定的

只有当公式中的所有命题变元被指定代表特定的命题时，命题公式才成为命题，其真值才唯一确定

（也就是说含有命题变元的命题公式，并不算是命题）

如：

命题公式p$\wedge$q

若指定p：2是素数；q：3是奇数。

则p$\wedge$q就是真命题。

若p：2是素数；q：3为偶数

则p$\wedge$q为假命题。

所以只有在指定特定的命题时，它才会变成命题且真值被确定。

公式的赋值

定义：若命题公式A含有的全部命题变元为P₁，P₂,…,P_n，给P₁，P₂,…,P_n指定一组真值，称为对A的一个解释或赋值。使A的真值为真的赋值称为成真赋值，使A的真值为假的赋值称为成假赋值。

说明：通常赋值与命题变元之间按下标或字母顺序对应，即当A的全部命题变元为P₁，P₂,…,P_n时，给A赋值a₁，a₂,…,a_n，是指P₁=a₁，P₂=a₂,…,P_n=a_n；当A的全部命题变元为p，q，r…时，给A赋值a₁，a₂,…是指p=a₁，q=a₂，r=a₃，……。

真值表：命题公式在所有可能的赋值下的取值的列表含n个变项的公式有2ⁿ个赋值。

例：给出公式的真值表

1.p$\rightarrow$(q$\wedge$$\neg$r)

p	q	r	$\neg$r	q$\wedge$$\neg$r	p$\rightarrow$(q$\wedge$$\neg$r)
0	0	0	1	0	1
0	0	1	0	0	1
0	1	0	1	1	1
0	1	1	0	0	1
1	0	0	1	0	0
1	0	1	0	0	0
1	1	0	1	1	1
1	1	1	0	0	0

2.(p$\rightarrow$q)$\vee$($\neg$p$\rightarrow$q)

p	q	p$\rightarrow$q	$\neg$p$\rightarrow$q	(p$\rightarrow$q)$\vee$($\neg$p$\rightarrow$q)
0	0	1	0	1
0	1	1	1	1
1	0	0	1	1
1	1	1	1	1

3.$\neg$($\neg$p$\rightarrow$q)$\wedge$q

p	q	$\neg$p$\rightarrow$q	$\neg$($\neg$p$\rightarrow$q)	$\neg$p	$\neg$($\neg$p$\rightarrow$q)$\wedge$q
0	0	0	1	1	0
0	1	1	0	1	0
1	0	1	0	0	0
1	1	1	0	0	0

命题公式的分类

定义 设A为一个命题公式

1. 若A在它的各种赋值下取值均为真，则称A为重言式或永真式
2. 若A在它的各种赋值下取值均为假，则称A为矛盾式或永假式
3. 若至少存在一种赋值使A的真值为真，则称A为可满足式

例如：

p$\rightarrow$（q$\wedge$$\neg$r)为非重言式的可满足式

(p$\rightarrow$q)$\vee$($\neg$p$\rightarrow$q)为重言式

$\neg$($\neg$p$\rightarrow$q)$\wedge$q为矛盾式

这三类公式之间有下面的关系：

1. 公式A永真，则$\neg$A永假，反之亦然
2. 公式A是可满足的，当且仅当$\neg$A不是永真式
3. 公式A不是可满足的，则一定是永假式
4. 公式A不是永假式的，则一定是可满足的

判断这些关系和类型，最简单的方法就是像上面那样构造一个真值表，这样就可以一眼看出谁是永真，谁是永假，谁是可满足。

1.3.1等值演算

等价关系式

定义：设A和B是两个命题（或者命题公式），若A⟷B是永真式，命题A和B称为逻辑等价的，可记为A$\Leftrightarrow$B

说明：A$\Leftrightarrow$B是永真式，表示命题公式A和B在所有的赋值下都有相同的真值，也就是说命题公式A和B具有相同的真值表。所以我们可以利用真值表来判断两个命题是否等价。

例题：

1.证明:p$\rightarrow$q和$\neg$p$\vee$q是否等价

①想都不用想，先列出真值表

p	q	p$\rightarrow$q	$\neg$p	$\neg$p$\vee$q
0	0	1	1	1
0	1	1	1	1
1	0	0	0	0
1	1	1	0	1

②通过真值表进行判断

可以判断出这两个是等价的，所以证毕。

2.证明：p$\wedge$(q$\vee$r)和(p$\wedge$q)$\vee$(p$\wedge$r)逻辑等价

p	q	r	p$\wedge$(q$\vee$r)	(p$\wedge$q)$\vee$(p$\wedge$r)
0	0	0	0	0
0	0	1	0	0
0	1	0	0	0
0	1	1	0	0
1	0	0	0	0
1	0	1	1	1
1	1	0	1	1
1	1	1	1	1

所以等价

基本等值式

1. 双重否定律：$\neg$$\neg$p$\Leftrightarrow$p【否定的否定就是肯定】
2. 同一律：p$\vee$0$\Leftrightarrow$p，p$\wedge$1$\Leftrightarrow$p
3. 零元律：p$\vee$1$\Leftrightarrow$1，p$\wedge$0$\Leftrightarrow$0
4. 等幂律：p$\vee$p$\Leftrightarrow$p，p$\wedge$p$\Leftrightarrow$p
5. 交换律：p$\vee$q$\Leftrightarrow$q$\vee$p，p$\wedge$q$\Leftrightarrow$q$\wedge$p
6. 结合律：(p$\vee$q)$\vee$r$\Leftrightarrow$p$\vee$(q$\vee$r),(p$\wedge$q)$\wedge$r$\Leftrightarrow$p$\wedge$(q$\wedge$r)
7. 德摩根律：$\neg$(p$\vee$q)$\Leftrightarrow$$\neg$p$\wedge$$\neg$q,$\neg$(p$\wedge$q)$\Leftrightarrow$$\neg$p$\vee$$\neg$q【这个是重点】
8. 吸收律：p$\vee$(p$\wedge$q)$\Leftrightarrow$p，p$\wedge$(p$\vee$q)$\Leftrightarrow$p
9. 分配律：p$\vee$(p$\wedge$r)$\Leftrightarrow$(p$\vee$q)$\wedge$(p$\vee$r)，p$\wedge$(q$\vee$r)$\Leftrightarrow$(p$\wedge$q)$\vee$(p$\vee$r)
10. 排中律：p$\vee$$\neg$p$\Leftrightarrow$1
11. 矛盾律：p$\wedge$$\neg$p$\Leftrightarrow$0
12. 蕴涵等值式：p$\rightarrow$q$\Leftrightarrow$$\neg$p$\vee$q【这个也是重点】（这个东西是把蕴含式改写成析取和否定的式子）
13. 等价等值式：p⟷q$\Leftrightarrow$(p$\rightarrow$q)$\wedge$(p$\rightarrow$q)
14. 假言易位：p$\rightarrow$q$\Leftrightarrow$$\neg$p$\rightarrow$$\neg$q
15. 等价否定等值式：p⟷q$\Leftrightarrow$$\neg$p⟷$\neg$q
16. 归谬论：(p$\rightarrow$q)$\wedge$(p$\rightarrow$$\neg$q)$\Leftrightarrow$$\neg$q
17. 补交转换率：$A-B=A{\bigcap}$~B
18. $A{\bigcap}B = |A|+|B|-|A{\bigcap}B|$

以上东西可以直接运用，无须证明

置换规则

若公式G中的一部分A（包含G中几个连续的符号）是公式，称A为G的子公式；用与A逻辑等价的公式B置换A不改变公式G的真值。

命题的等价运算

利用已知的等价关系式，将其中的子公式用和它等价的公式置换可以推出其他一些等价关系式，这个过程就叫做命题的等价运算。

（用于判断两个命题是否等价，判断命题公式的类型，命题公式的化简等）

例题

1.证明：p$\rightarrow$q$\Leftrightarrow$$\neg$q$\rightarrow$$\neg$p

p$\rightarrow$q$\Leftrightarrow$$\neg$p$\vee$q（蕴含等价式）$\Leftrightarrow$$\neg$($\neg$q)$\vee$$\neg$p（交换律和双重否定律）$\Leftrightarrow$$\neg$q$\rightarrow$$\neg$p（蕴含等价式）【$\neg$q看成q，$\neg$p看成p，则可以变成p$\rightarrow$q，然后把p和q看回原来那样，就是$\neg$q$\rightarrow$$\neg$p了】

条件命题：p$\rightarrow$q；否命题：$\neg$p$\rightarrow$$\neg$q；逆命题：q$\rightarrow$p；逆否命题：$\neg$q$\rightarrow$$\neg$p

条件命题和它的逆否命题等价

化简公式：

1.(p$\wedge$q)$\vee$(p$\neg$q)

(p$\wedge$q)$\vee$(p$\wedge$$\neg$q)$\Leftrightarrow$p$\wedge$(q$\vee$$\neg$q)（分配律）

$\Leftrightarrow$p$\wedge$T（排中律）

$\Leftrightarrow$p（同一律）

1.3.2其他联结词

与非$\uparrow$

设p和q是任意两个命题，p$\uparrow$q可表示复合命题“p和q的与非”，$\uparrow$称为与非联结词。命题p$\uparrow$q称为p和q的与非式。当且仅当p和q的真值同时为真时，p$\uparrow$q的真值为假。

所谓的与非就是先作一次“与”运算后，再做一次“非”运算。

真值表如下所示

与运算

如果a和b都为真，则结果为真，如果a和b中有一个条件为假，则结果为假

非运算

如果a为假，则!a为真，如果a为真，则!a为假

或非$\downarrow$

设p、q是任意两个命题，p$\downarrow$q可表示复合命题“p和q的或非”。$\downarrow$称为或非联结词。命题p$\downarrow$q称为p和q的或非式。当且仅当p和q的真值同时为假时，p$\downarrow$q的真值为真。

所谓或非即作一次或者多次“或”运算后再做一次“非”运算

真值表如下所示

或运算

如果a和b有一个或以上为真，则结果为真，二者都为假时，结果为假

异或$\oplus$

设p和q是任意两个命题，p$\oplus$q可表示复合命题“p、q之中恰有一个成立”，$\oplus$称为异或（不兼容性或）联结词。命题p$\oplus$q称为p和q的异或式。当且仅当p和q的真值恰有一个为真时，p$\oplus$q的真值为真。

逻辑关系的数字门电路实现

直接上图好了

其中：$\neg$用数字电路中的非门实现；$\wedge$联结词用与门实现；$\vee$联结词用或门实现

联结词的应用

1.网络检索中，联结词AND（与门）用于匹配同时包含两个检索项的记录，联结词OR（或门）用于匹配至少包含一个检索项的记录，联结词NOT（非门） 用于排除某个特定的检索项

2.把自然语言表示的命题翻译成由命题变量和逻辑联结词组成的表达式，进行判断和推理

1.4.1主析取范式

范式就是规范的式子，它主要包含析取范式和合取范式

析取范式

一个命题公式具有形式A₁$\vee$A₂$\vee$…$\vee$A_n(n≥1)，其中A₁，A₂，…，A_n都是由命题变元或其否定所组成的合取式，则称该命题公式为析取范式。

如：p$\vee$(p$\wedge$$\neg$q$\wedge$$\neg$r)$\vee$($\neg$p$\wedge$q)$\vee$$\neg$q是析取范式。【整体来讲，这几个式子是由析取联结词联结而来的，并且是每一部分都可以看成是一个小的合取式】

合取范式

一个命题公式具有形式A₁$\wedge$A₂.$\wedge$..$\wedge$A_n(n≥1)，其中A₁，A₂，…，A_n都是由命题变元或其否定所组成的合取式，则称该命题公式为析取范式。

如：(p$\vee$$\neg$q$\vee$$\neg$r)$\wedge$($\neg$p$\vee$q)$\wedge$$\neg$q是合取范式【整体来讲，这几个式子是由合取联结词联结起来的，并且每一部分都可以看成是一个小的析取式】

范式存在定理

任何一个命题公式都存在着与之等值的析取范式与合取范式。

证明：设G为任意一个公式

1. 将公式化成只含有$\neg$、$\wedge$、$\vee$3个联结词的形式
2. 将否定联结词内移或消去
3. 利用分配律、交换律和结合律等将公式归纳为析取范式和合取范式。

通过这三个步骤就可以求出与G等价的析取范式和合取范式，任意一个命题公式都存在着与之等价的析取范式和合取范式

以上亦是求解析取范式和合取范式的步骤

例题：

求命题公式(p$\wedge$(p$\rightarrow$q))$\vee$q的析取范式和合取范式

p$\wedge$(p$\rightarrow$q)$\Leftrightarrow$p$\wedge$($\neg$p$\vee$q)$\Leftrightarrow$(p$\wedge$$\neg$p)$\vee$(p$\wedge$q)$\Leftrightarrow$p$\wedge$q

所以析取范式：(p$\wedge$$\neg$p)$\vee$(p$\wedge$q)$\vee$q$\Leftrightarrow$(p$\wedge$q)$\vee$q$\Leftrightarrow$q【q可以看成是特殊的析取范式】

合取范式：q$\Leftrightarrow$(p$\vee$q)$\wedge$q$\Leftrightarrow$(p$\vee$q)$\wedge$($\neg$p$\vee$q)$\Leftrightarrow$q【q可以看成是特殊的合取范式】

公式的析取范式与合取范式并不唯一

主析取范式与主合取范式

含有n个命题变元的合取式中，若每个命题变元与其否定不同时出现，而两者之一必出现且仅出现一次，这样的合取式称为极小项

含有n个命题变元的析取式中，若每个命题变元与其否定不同时出现，而两者之一必出现且仅出现一次，这样的析取式称为极大项

说明：

1. 由n个命题变元产生的不同的极大项和极小项的个数均为2ⁿ个
2. 每个极小项在它的2ⁿ个赋值中只有一个成真赋值
3. 每个极大项在它的2ⁿ个赋值中只有一个成假赋值

三个命题变元的极小项

$\neg$p$\wedge$$\neg$q$\wedge$$\neg$r m₀₀₀或m₀ 【意思是这个极小项成真赋值】

$\neg$p$\wedge$$\neg$q$\wedge$r m₀₀₁或m₁

$\neg$p$\wedge$q$\wedge$$\neg$r m₀₁₀或m₂

$\neg$p$\wedge$q$\wedge$r m₀₁₁或m₃

p$\wedge$$\neg$q$\wedge$$\neg$r m₁₀₀或m₄

p$\wedge$$\neg$q$\wedge$r m₁₀₁或m₅

p$\wedge$q$\wedge$$\neg$r m₁₁₀ 或m₆

p$\wedge$q$\wedge$r m₁₁₁或m₇

一般的，n个命题变元形成的极小项可表示为：m₀，m₁，…，或m_2ⁿ-1【这里的下标其实是二进制转十进制】

极大项跟上面类似，只是m变成M，M₁₁₁为成假赋值这里就不给出来了。

主析取范式

如果含n个命题变元的命题公式的析取范式的每个合取式都是极小项，则称该析取式为主析取范式

任何命题公式的主析取范式都是存在的，且唯一。

证明：给定命题公式A

1. 求A的析取范式A^‘
2. 若A^‘的某合取式B不是极小项，则补入没有出现的变元
3. 消去重复出现的命题变项、矛盾式及重复出现的极小项

按上述步骤求得的就是A的主析取范式。

其中第二步的一个例子：若p_i不在B中，则将B展开如下形式

B$\Leftrightarrow$B$\wedge$1$\Leftrightarrow$B$\wedge$(p_i$\vee$$\neg$p_i)$\Leftrightarrow$(B$\wedge$p_i)$\vee$(B$\wedge$$\neg$p_i)

例题

求命题公式(p$\vee$(q$\wedge$r))$\rightarrow$(p$\wedge$q$\wedge$r)的主析取范式

(p$\vee$(q$\wedge$r))$\rightarrow$(p$\wedge$q$\wedge$r)

$\Leftrightarrow$$\neg$(p$\vee$(q$\wedge$r))$\vee$(p$\wedge$q$\wedge$r) （蕴含等值式）

$\Leftrightarrow$($\neg$p$\wedge$($\neg$q$\vee$$\neg$r))$\vee$(p$\wedge$q$\wedge$r) （德摩根定律）

$\Leftrightarrow$($\neg$p$\wedge$$\neg$q)$\vee$($\neg$p$\wedge$$\neg$r)$\vee$(p$\wedge$q$\wedge$r)（分配律，获得析取范式）

$\Leftrightarrow$(($\neg$p$\wedge$$\neg$q)$\wedge$(r$\vee$$\neg$r))$\vee$(($\neg$p$\wedge$$\neg$r)$\wedge$(q$\vee$$\neg$q))$\vee$(p$\wedge$q$\wedge$r)（根据观察，发现第一项有p和q，缺少r，所以补上。第二项，有p和r，缺少q，补上。第三项，都有，就不用补了。）

$\Leftrightarrow$(($\neg$p$\wedge$$\neg$q$\wedge$r)$\vee$($\neg$p$\wedge$$\neg$q$\wedge$$\neg$r))$\vee$(($\neg$p$\wedge$$\neg$r$\wedge$q)$\vee$($\neg$p$\wedge$$\neg$r$\wedge$$\neg$q))$\vee$(p$\wedge$q$\wedge$r)（展开后发现有两项重复，于是对重复项进行合并）

$\Leftrightarrow$($\neg$p$\wedge$$\neg$q$\wedge$r)$\vee$($\neg$p$\wedge$$\neg$q$\wedge$$\neg$r)$\vee$($\neg$p$\wedge$$\neg$r$\wedge$q)$\vee$(p$\wedge$q$\wedge$r)（主析取范式）

$\Leftrightarrow$m₀$\vee$m₁$\vee$m₂$\vee$m₇

$\Leftrightarrow$$\sum$(0,1,2,7)

试由(p$\wedge$q$\vee$r)的真值表来求它的主析取范式

真值表如下

p	q	r	(p$\wedge$q$\vee$r)
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

所以它的成真赋值为001，011，101，110，111

(p$\wedge$q$\vee$r)$\Leftrightarrow$$\sum$(1,3,5,6,7)

$\Leftrightarrow$($\neg$p$\wedge$$\neg$q$\wedge$r)$\vee$($\neg$p$\wedge$q$\wedge$r)$\vee$(p$\wedge$q$\wedge$$\neg$r)$\vee$(p$\wedge$$\neg$q$\wedge$r)$\vee$(p$\wedge$q$\wedge$r)

一个命题公式的主析取范式中的每一个极小项的成真赋值就是该公式的一个成真赋值

主合取范式

如果含n个命题变元的命题公式的合取范式的每个析取式都是极大项，则称该析取式为主析合取式

任何命题公式的主合取范式都是存在的，且唯一。

求解方法跟主析取范式一样，只是主析取范式是用$\sum$符号，而主合取范式是用$\prod$符号。在补入步骤，主析取补入的是$\vee$，而主合取则是$\wedge$

析（合）取范式的用途

判断命题公式是否等价

例如：

判断($\neg$p$\vee$q)$\wedge$($\neg$q$\vee$r)$\wedge$($\neg$r$\vee$p)和(p$\vee$$\neg$q)$\wedge$(q$\vee$$\neg$r)$\wedge$(r$\vee$$\neg$p)是否等价

($\neg$p$\vee$q)$\wedge$($\neg$q$\vee$r)$\wedge$($\neg$r$\vee$p)

$\Leftrightarrow$(M₁₀₀$\wedge$M₁₀₁)$\wedge$(M₀₁₀$\wedge$M₁₁₀)$\wedge$(M₀₀₁$\wedge$M₀₁₁)

$\Leftrightarrow$M₄$\wedge$M₅$\wedge$M₂$\wedge$M₆$\wedge$M₁$\wedge$M₃

$\Leftrightarrow$$\prod$(1,2,3,4,5,6)

(p$\vee$$\neg$q)$\wedge$(q$\vee$$\neg$r)$\wedge$(r$\vee$$\neg$p)

$\Leftrightarrow$(M₀₁₀$\wedge$M₀₁₁)$\wedge$(M₀₀₁$\wedge$M₁₀₁)$\wedge$(M₁₀₀$\wedge$M₁₁₀)

$\Leftrightarrow$M₂$\wedge$M₃$\wedge$M₁$\wedge$M₅$\wedge$M₄$\wedge$M₆

$\Leftrightarrow$$\prod$(1,2,3,4,5,6)

所以两个等价

求公式的成真赋值和成假赋值

假设公式A含n个命题变项，A的主析取范式有s个极小项，则A有s个成真赋值，它们是极小项下标的二进制表示，其余2ⁿ-s个赋值都是成假赋值

例如$\neg$(p$\rightarrow$q)$\vee$$\neg$r

$\Leftrightarrow$m₀$\vee$m₂$\vee$m₄$\vee$m₅$\vee$m₆

成真赋值：000，010，100，101，110

成假赋值：001，011，111

判断公式的类型

设A含n个命题变项，则

1. A为重言式当且仅当A的主析取范式含2ⁿ个极小项
2. A为矛盾式当且仅当A的主析取范式不含任何极小项，记作0
3. A为可满足式当且仅当A的主析取范式中至少含有一个极小项
4. A为矛盾式当且仅当A的主合取范式含2ⁿ个极大项
5. A为重言式当且仅当A的主合取范式不含任何极大项，记作1
6. A为可满足式当且仅当A的主合取范式不是包含全部2ⁿ个极大项

判断公式G$\Leftrightarrow$(p$\rightarrow$q)$\rightarrow$($\neg$q$\rightarrow$$\neg$p)是否重言式

G$\Leftrightarrow$(p$\rightarrow$q)$\rightarrow$($\neg$q$\rightarrow$$\neg$p)

$\Leftrightarrow$$\neg$($\neg$p$\vee$q)$\vee$(q$\vee$$\neg$p)

$\Leftrightarrow$(p$\wedge$$\neg$q)$\vee$q$\vee$$\neg$p

$\Leftrightarrow$m₁₀$\vee$(m₀₁$\vee$m₁₁)$\vee$(m₀₀$\vee$m₀₁)

$\Leftrightarrow$m₂$\vee$m₁$\vee$m₃$\vee$m₀$\vee$m₁

$\Leftrightarrow$$\sum$(0,1,2,3)

所以公式G为重言式

总结

（图来源于华南理工的公开课，有空我在自己做这个图）

1.5.1推理定理

推理理论

设A和B是两个命题公式，当且仅当命题A$\rightarrow$B是重言式时（即A$\rightarrow$B$\Leftrightarrow$T时），称从A可推出B，或A蕴含B，或B是前提A的结论，可以表示成Ａ$\Rightarrow$B

一般的，推理的前提可以有多个，若(A₁$\wedge$A₂.$\wedge$..$\wedge$A_n)$\rightarrow$B是重言式，则称由前提A₁，A₂,…,A_n可推出结论B，克表示为(A₁$\wedge$A₂.$\wedge$..$\wedge$A_n)$\Rightarrow$B

例题

1.p$\wedge$(p$\rightarrow$q)$\Rightarrow$q

解：p$\wedge$(p$\rightarrow$q)$\Rightarrow$q

$\Leftrightarrow$p$\wedge$(p$\rightarrow$q)$\rightarrow$q

p	q	p$\wedge$(p$\rightarrow$q)$\rightarrow$q
0	0	1
0	1	1
1	0	1
1	1	1

p$\wedge$(p$\rightarrow$q)$\Rightarrow$q是正确的

证明“如果牛吃草，则马会飞；马不会飞，所以牛不吃草”是正确的推理

证明：设p：牛吃草；q：马会飞

则符号化为：(p$\rightarrow$q)$\wedge$$\neg$q$\rightarrow$$\neg$p

而(p$\rightarrow$q)$\wedge$$\neg$q$\rightarrow$$\neg$p

$\Leftrightarrow$$\neg$((p$\rightarrow$q)$\wedge$$\neg$q)$\vee$$\neg$p

$\Leftrightarrow$$\neg$(p$\rightarrow$q)$\vee$q$\vee$$\neg$p

$\Leftrightarrow$$\neg$(p$\rightarrow$q)$\vee$(p$\rightarrow$q)

$\Leftrightarrow$T

所以这个推理是正确的

注意：推理时，只要推理过程的每一步骤都遵循正确的推理规则，推出的结论都称为有效结论，推理都是有效的

推理定律

化简

p$\wedge$q$\Rightarrow$q

p$\wedge$q$\Rightarrow$p

附加

p$\Rightarrow$p$\vee$q

q$\Rightarrow$p$\vee$q

假言推理

p,p$\rightarrow$q$\Rightarrow$q【，前的内容为前提】

拒取式

$\neg$q,p$\rightarrow$q$\Rightarrow$$\neg$p【，前的内容为前提】

析取三段论

$\neg$p,p$\vee$q$\Rightarrow$q【，前的内容为前提】

合取

p,q$\Rightarrow$p$\wedge$q【，前的内容为前提】

构造性二难

p$\vee$q,q$\Rightarrow$r$\Rightarrow$p$\rightarrow$r

归结式

p$\rightarrow$q,r$\rightarrow$s,p$\vee$r$\Rightarrow$q$\vee$s

定理（CP规则）

若A₁，A₂,…,A_n和P推出Q，则A₁，A₂,…,A_n推出P$\rightarrow$Q【A₁，A₂,…,A_n为前提】

1.5.2推理证明方法

1. 真值表法
2. 等价演算法
3. 演绎法
4. 间接推演法（归谬法）（反证法）
5. 附加前提证明法
6. 归结证明法

真值表法

通过写出真值表判断A$\rightarrow$B的类型，若A$\rightarrow$B是重言式，则由前提A可以推出结论B

等价演算法

利用命题的等值演算判断A$\rightarrow$B的类型，若A$\rightarrow$B是重言式，则由前提A可以推出结论B

演绎法

演绎法是从前提（假设）出发，依据公认的推理规则和推理定律，推导出一个结论来

命题演算推理系统：

1. 推理规则
2. 推理定律
3. 基本等价公式

推理规则

前提引入规则

在推导的过程中，可随时引入前提集合中的任意一个前提

结论引入规则

在推导的过程中所得到的结论都可作为后续推导的前提

置换规则

在推导的过程中，命题公式的子公式都可以用等值的公式置换

CP规则（附加前提规则）

如果推出的结论形为P$\rightarrow$Q，则可以把P放到前提中取，设法推出Q即可

演绎法

证明：前提“今天下午有课且今天比昨天冷；只有今天下午没有课，我们才去游泳；如果我们不去游泳，则我们去打篮球；如果我们打篮球，我们就会感到精力充沛”

推出结论“我们感到精力充沛”是正确的

解：设P：今天下午有课；q：今天比昨天冷；r：我们去游泳；s：我们打篮球；h：我们感到精力充沛

则前提为：p$\wedge$q，r$\rightarrow$$\neg$p,$\neg$r$\rightarrow$s,s$\rightarrow$h，结论是h

步骤	公式	理由
1	p$\wedge$q	前提引入
2	p	1的化简
3	r$\rightarrow$$\neg$p	前提引入
4	$\neg$r	2，3拒取式
5	$\neg$r$\rightarrow$s	前提引入
6	s	4,5假言推理
7	s$\rightarrow$h	前提引入
8	h	6，7假言推理

所以证明完毕

附加前提证明法

证明r$\rightarrow$s是p$\rightarrow$(q$\rightarrow$s),$\neg$r$\vee$p,q的结论

证明：

步骤	公式	理由
1	r	附加前提引入
2	$\neg$r$\vee$p	前提引入
3	p	1，2析取三段论
4	p$\rightarrow$(q$\rightarrow$s)	前提引入
5	q$\rightarrow$s	3，4假言推理
6	q	前提引入
7	s	6，5假言推理

间接推演法（归谬法）

间接推演法就是把要推出的结论否定后与原来的前提一起使用推出矛盾结论的证明方法

例题

用间接推演法证明：$\neg$p是p$\rightarrow$$\neg$q,q$\vee$$\neg$r,r$\wedge$$\neg$s的结论

步骤	公式	理由
1	$\neg$$\neg$p	否定结论
2	p	1双重否定
3	p$\rightarrow$$\neg$q	引入前提
4	$\neg$q	2，3假言推理
5	q$\vee$$\neg$r	前提引入
6	$\neg$r	4，5析取三段论
7	r$\wedge$$\neg$s	前提引入
8	r	7化简
9	F	8，6合取

归结证明法

归结规则

(p$\vee$q)$\wedge$($\neg$p$\vee$r)$\Rightarrow$q$\vee$r

归结证明法：

1. 前提和结论必须被表示为子句
2. 对于非子句的语句，可以用一个或多个等价的是子句的语句替换它子句是变元或其否定的析取，如p$\vee$q，$\neg$p$\vee$r等是子句

例题

证明：如果小张守门或小李上场，则A队获胜；或者A队未获胜，或者A队称为联赛第一；A队没有成为联赛第一。因此小张没有守门并且小李没有上场

设p：小张守门；q：小李上场；r：A队获胜；s：A队成为联赛第一

前提：(p$\vee$q)$\rightarrow$r,$\neg$r$\vee$s,$\neg$s

结论：$\neg$p$\wedge$$\neg$q

前提中的(p$\vee$q)$\rightarrow$r$\Leftrightarrow$$\neg$(p$\vee$q)$\vee$r$\Leftrightarrow$($\neg$p$\vee$r)$\wedge$($\neg$q$\vee$r)

所以用两个子句($\neg$p$\vee$r)和($\neg$q$\vee$r)代替(p$\vee$q)$\rightarrow$r

结论为两个子句：$\neg$p和$\neg$q

步骤	公式	理由
1	$\neg$p$\vee$r	前提引入
2	$\neg$r$\vee$s	前提引入
3	$\neg$p$\vee$s	1,2归结规则
4	$\neg$q$\vee$r	前提引入
5	$\neg$q$\vee$s	2，4归结规则
6	$\neg$s	前提引入
7	$\neg$p	3，6归结规则
8	$\neg$q	5,6归结规则
9	$\neg$p$\wedge$$\neg$q	7,8合取

2

2.1.1谓词逻辑的基本概念

命题逻辑是有局限性的，对一些数学推理中的真命题，进行符号化后要证明是永真式，是没办法证明的，所以这就是命题逻辑的局限性

那么它局限性在哪呢？

在命题逻辑中，它对简单句并不会细分为某一些基本的元素（如：苏格拉底是人，它不会细分出苏格拉底表示什么）

所以我们要使用谓词

个体词

个体词是指可以独立存在的客体，可以是一个具体的事物或抽象的概念，是原子命题所描述的对象

谓词

谓词是用来说明个体的性质或个体间的关系

例如

1.小王是大学生

小王是个体词，是个大学生是谓词

2.3大于2

3，2是个体此，大于是谓词

形如b是A类型的命题，可以表达为A(b)

表示多个个体间关系的命题，可表达为B(a,b)或P(a,b,c)

和一个个体相关联系得谓词称为一元谓词，和两个个体相关联系得谓词成为二元谓词，和n个个体相关联系的谓词称为n元谓词

个体常元

表示具体的或特定的个体，如a,b,c……等

个体变元

表示抽象的或泛指的个体，如x,y,z…..等

谓词常项

表示具体性质或关系的谓词，R(a)表示a是人

谓词变项

表示抽象或泛指的谓词，如：P(a)表示a具有P性质

谓词表达式

一个原子命题可以同一个谓词常项p和几个个体常元，如a,b,c,……，表示成p(a,b,c,….)的形式。称p(a,b,c,….)为原子命题或命题的谓词表达式

命题函数

一个谓词常项p和几个个体变元如x,y,z,….表示成p(x,y,z,….)的形式，称为命题函数，其中的个体变元可以代表任意一个个体。

注意：命题的谓词表达式是有真值的，命题函数的真值是不确定的

例题

写出下列命题的谓词表达式

1.小王和小李是大学生。

设A(x)：x是大学生。a:小王，b：小李

A(a)$\wedge$A(b)

2.北京是中国的首都

设F(x,y)：x是y的首都。a:北京，b：中国

F(a,b)

3.如果你来，他就走

设P(x):x来，Q(x):x走。a：你，b：他

P(a)$\rightarrow$Q(b)

4.如果3＞2，2＞1，则3＞1

设B(x,y):x>y。a:3,b:2,c:1

B(a,b)$\wedge$B(b,c)$\rightarrow$B(a,c)

个体域

个体域可以是有限的，也可以是无限的。把宇宙中一切事物作为对象的集合称为全总个体域。通常，没有特别说明时，个体变元的论述域是指全总个体域。

如：A(x)表示：x是大学生

个体域：某大学计科1班学生，则A()是永真式

个体域：附中1班学生，则A(x)是永假式

个体域：xx公式员工，其中有些是大学生，有些不是大学生，则对有些人A(x)是真，而有些人则A(x)是假

量词

表示个体常元或个体变元之间数量关系的词称为量词

全称量词

符号：$\forall$

$\forall$x表示对个体域“所有的x”，“每一个x”，“一切x”等

$\forall$xF(x)表示个体域中所有个体都有性质F

存在量词

符号：$\exists$

$\exists$x表示个体域中“存在这样的x”，“某个x”，“至少有一个x”或“有一些x”等

$\exists$xF(x)表示个体域中存在个体有性质F

例题

设F(x)表示x选修离散数学，x的个体域是这个班的同学

1.这个班的所有学生都选修离散数学

$\forall$xF(x)

2.这个班有些学生选修离散数学

$\exists$xF(x)

若个体域是全总个体域时，要引入一个新的谓词表示个体的取值范围。成这个表示个体范围的谓词为特性谓词

设F(x)表示x选修离散数学

1.这个班的所有学生都选修离散数学。

因为这里没有规定，所以个体域是全总个体域

解：设特性谓词S(x)：表示x是这个班的学生

$\forall$x(S(x)$\rightarrow$F(x))

2.这个班存在学生选修离散数学

解：设特性谓词S(x)：表示x是这个班的学生

$\exists$x(S(x)$\wedge$F(x))

在使用全称量词时，特性谓词和表示个体性质的谓词构成条件关系式；在使用存在量词时，特性谓词和表示个体性质的谓词构成合取关系式。

1.所有的偶数均能被2整除

解：设A(x)：x是偶数，B(x)：x能被2整除

$\forall$x(A(x)$\rightarrow$B(x))

2.这个班有些学生有电脑

解：设A(x)：x是这个班的学生，B(x)：x有电脑

$\exists$x(A(x)$\wedge$B(x))

当论述域中的元素个数有限时，例如论述域为n个元素的集合{a₁，a₂,…,a_n}时，有

$\forall$xA(x)$\Leftrightarrow$A(a₁)$\wedge$A(a₂)$\wedge$A(a₃)….$\wedge$A(a_n)

$\exists$xA(x)$\Leftrightarrow$A(a₁)$\vee$A(a₂)$\vee$A(a₃)….$\vee$A(a_n)

例题

1.若P(x)是语句“x²＞10”，论述域为不超过4的正整数，$\forall$xP(x)和$\exists$xP(x)的真值是什么？

解：由于论述域为{1,2,3,4}，命题$\forall$xP(x)为

$\forall$xP(x)$\Leftrightarrow$P(1)$\wedge$P(2)$\wedge$P(3)$\wedge$P(4)

而P(1)即”1²＞10”为假，所以$\forall$xP(x)为假。

命题$\exists$xP(x)为

$\exists$xP(x)$\Leftrightarrow$P(1)$\vee$P(2)$\vee$P(3)$\vee$P(4)

而P(4)即”4²＞10”为真，所以$\exists$xP(x)为真。

2.设P(x)表示“x+y＞10”，论述域为实数，$\forall$x$\exists$yP(x,y)和$\exists$y$\forall$xP(x,y)的真值是什么？

解：

$\forall$x$\exists$yP(x,y)表示命题：“对每一个实数x，都存在实数y，使得x+y＞10成立”，这是个真命题，真值为1

$\exists$y$\forall$xP(x,y)表示命题：“存在实数y，对每一个实数x，都有x+y＞10成立”，这是个假命题，真值为0

注意：除非所有量词都是全称量词或存在量词，否则多个量词同时出现时，不能随意颠倒量词的顺序，颠倒后会改变原命题的含义

2.2.1谓词演算公式

假设谓词P和n个个体变元，如a₁，a₂,…,a_n，表示成P(a₁，a₂,…,a_n)的形式，称为n元原子谓词公式，简称n元谓词公式。

如果谓词公式中没有个体变元，即n=0，称为0元谓词公式。0元谓词公式就是原子命题

1. 每一个原子谓词公式都是谓词演算公式
2. 如果A是谓词公式，则($\neg$A)是谓词公式
3. 如果A和B都是谓词公式，则(A$\wedge$B),(A$\vee$)B,(A$\rightarrow$B),(A$\leftrightarrow$B)都是谓词公式
4. 如果A是谓词公式，ｘ是其中的任一变元，则$\exists$xA和$\forall$xA都是谓词公式
5. 当且仅当有限次地应用上面地步骤得到的符号串才是谓词公式

量词的辖域以及变元的约束

谓词公式$\forall$xA和$\exists$xA中出现在量词$\exists$和$\forall$后面的变元称为量词的指导变元

每个量词后面的最小的谓词子公式，称为该量词的辖域

在量词的辖域中，ｘ的所有出现都称为约束出现。约束出现的变元称为约束变元

除约束变元以外的其他变元的出现称为自由出现。自由出现的变元称为自由变元

例题

说明一下谓词公式中各量词的辖域以及变元的约束情况

１.$\forall$x(P(x)$\wedge$Q(x))

解：$\forall$x的辖域是P(x)$\wedge$Q(x),x为约束变元

2.$\forall$x(P(x)$\rightarrow$$\exists$yQ(x,y))

解：$\forall$x的辖域是P(x)$\rightarrow$$\exists$yQ(x,y)，$\exists$y的辖域为Q(x,y)，x，y均为约束变元

3.$\forall$x$\forall$y(P(x,y)$\wedge$Q(y,z))$\wedge$$\exists$xR(x,y)

解：$\forall$x的辖域是$\forall$y(P(x,y)$\wedge$Q(y,z))，$\forall$y的辖域是P(x,y)$\wedge$Q(y,z)，$\exists$x的辖域是R(x,y)，在$\forall$x$\forall$y(P(x,y)$\wedge$Q(y,z))中，x和y是约束变元，z是自由变元。在$\exists$xR(x,y)中，x是约束变元，y是自由变元

对谓词公式中约束出现的变元更改符号名称，称为约束变元换名

约束变元换名规则

将量词中的指导变元以及该量词辖域中该变元的所有出现更改为辖域中没有出现的变元名称，公式的其余部分不变

对谓词公式中自由出现的变元更改符号名称，称为自由变元代入

例题

对下列谓词公式中的变元更名，使每一变元只呈现一种出现形式

1.$\forall$x(P(x)$\rightarrow$Q(x,y))$\wedge$R(x,y)

解：利用约束变元换名规则，将$\forall$x(P(x)$\rightarrow$Q(x,y))中的约束变元x换成z，得到公式：$\forall$z(P(z)$\rightarrow$Q(z,y))$\wedge$R(x,y);或利用自由变元代入规则，将R(x,y)中的x用z代入，得到公式$\forall$x(P(x)$\rightarrow$Q(x,y))$\wedge$R(z,y)

2.$\forall$x(P(x,y)$\wedge$Q(y,z))$\wedge$$\exists$xR(x,y)$\wedge$$\forall$yS(y)

解：利用约束变元换名规则，将$\exists$xR(x,y)中的约束变元x换成u，利用自由变元代入规则，将自由出现的三处y用t代入，得到公式：$\forall$x(P(x,t)$\wedge$Q(t,z))$\wedge$$\exists$uR(u,t)$\wedge$$\forall$yS(y)

闭式

任一谓词公式A，若A中没有自由出现的个体变元，称A使封闭的谓词公式，简称闭式

例题

判断下列谓词公式是否是闭式

1.$\forall$x(P(x)$\rightarrow$Q(x))

解：公式中x都是约束出现的，没有任何自由出现的变元，所以是闭式。

2.3.1谓词公式的解释和分类

谓词公式

谓词逻辑中公式A的一个解释（或赋值）I由如下四部分组成：

1. 非空的个体域集合D
2. A中的每个常元符号，指定D中的某个特定的元素
3. A中的每个n元函数符号，指定Dⁿ到D的某个特定的函数
4. A中的每个n元谓词符号，指定到Dⁿ到{0,1}的某个特定的谓词

例题

给定解释I如下：

1. 个体域为自然数集合N
2. a=0
3. N中特定的函数f(x,y)=x+y,g(x,y)=xy
4. N中特定的谓词F(x,y)：x=y

求以下公式的真值

1.$\forall$xF(g(x,y),z)

解：$\forall$xF(g(x,y),z)$\Leftrightarrow$$\forall$x(xy=z)。不是命题，真值不确定

2.$\forall$xF(g(x,a),x)$\rightarrow$F(x,y)

解：$\forall$xF(g(x,a),x)$\rightarrow$F(x,y)$\Leftrightarrow$$\forall$x(xa=x)$\rightarrow$(x=y)$\Leftrightarrow$$\forall$x(0=x)$\rightarrow$(x=y)$\Leftrightarrow$1

最后化简出来是一个蕴含式，蕴含式的前件为假，所以无论后件是真是假，都为真，所以为1.

封闭的谓词公式（闭式）在任何解释下都变成命题

不是闭式的谓词公式在某些解释下也可能变成命题

谓词公式的分类

1. 设A是一个谓词公式，如A在任何解释下的真值恒为真，则称A为永真式（或逻辑有效式）
2. 如A在任何解释下的真值恒为假，则称该谓词公式为永假式（或矛盾式）
3. 如果至少存在一个解释使得A的真值为真，则称A为可满足式

例题

判定公式$\exists$x$\forall$yA(x,y)$\leftrightarrow$$\forall$y$\exists$xA(x,y)的类型

解：设个体域为自然数集合，令A(x,y)表示xy=y

则$\forall$y$\exists$xA(x,y)在该解释下的真值为1

那么$\exists$x$\forall$yA(x,y)的真值也为1

所以在这个解释下，该公式的真值为1

再设个体域为自然数集合，A(x,y)表示x＞y

则$\forall$y$\exists$xA(x,y)在该解释下的真值为1

那么$\exists$x$\forall$yA(x,y)的真值为0

所以在这个解释下，该公式的真值为0

所以总体上讲，它既不是永真，也不是永假，所以是一个可满足式

命题公式的代换实例

假设谓词p和n个个体变元，如a₁，a₂,…,a_n，表示成p(a₁，a₂,…,a_n)的形式，称为n元原子谓词公式，简称n元谓词公式

如：F(x)$\rightarrow$G(y),$\forall$xF(x)$\rightarrow$$\exists$xF(x)都是p$\rightarrow$q的代换实例

定理：命题公式中永真式的代换实例都是永真式，矛盾式的代换实例都是矛盾式

例题

判断下列公式是永真式还是矛盾式

1.$\forall$xF(x)$\rightarrow$$\exists$xF(x)

解：该公式为永真式，因为对所有的xF(x)都成立，则一定存在某个x使得对F(x)成立的，所以是永真式

2.$\forall$xF(x)$\rightarrow$($\exists$yG(y)$\rightarrow$$\forall$xF(x))

解：因为p$\rightarrow$(q$\rightarrow$p)$\Leftrightarrow$1，而$\forall$xF(x)$\rightarrow$($\exists$yG(y)$\rightarrow$$\forall$xF(x))是p$\rightarrow$(q$\rightarrow$p)的代换实例，所以$\forall$xF(x)$\rightarrow$($\exists$yG(y)$\rightarrow$$\forall$xF(x))是永真式

2.4.1谓词演算的关系式

设A和B是任意两个谓词公式，如果A$\rightarrow$B是永真式，则称谓词公式A和B等价，记为A$\Leftrightarrow$B

谓词逻辑的等价式

1. 命题逻辑中的等价式的代换实例是谓词逻辑中的等价式
2. 谓词逻辑中特有的等价式

谓词逻辑的等价式题

定理（量词否定转换律）设A(x)是任意谓词公式，则有

1.$\neg$$\forall$xA(x)$\Leftrightarrow$$\exists$x$\neg$A(x)

证明：$\neg$$\forall$xA(x)为真$\Leftrightarrow$$\forall$xA(x)为假$\Leftrightarrow$$\exists$a使得A(a)为假$\Leftrightarrow$$\exists$x$\neg$A(x)为真，所以公式成立

2.$\neg$x$\exists$A(x)$\Leftrightarrow$$\forall$x$\neg$A(x)

证明：同上，只是从右边开始证明，先假设右边为假。

定理（量词辖域扩张和收缩域）设A(x)是包含x为自由变元的公式，B是不包含x的公式，则有

1. $\forall$x(A(x)$\wedge$B)$\Leftrightarrow$$\forall$xA(x)$\wedge$B
2. $\forall$xA(x)$\rightarrow$B$\Leftrightarrow$$\exists$x(A(x)$\rightarrow$B)
3. $\forall$x(A(x)$\vee$B)$\Leftrightarrow$$\forall$xA(x)$\vee$B
4. $\exists$x(A(x)$\wedge$B)$\Leftrightarrow$$\forall$xA(x)$\wedge$B
5. $\exists$x(A(x)$\vee$B)$\Leftrightarrow$$\exists$xA(x)$\vee$B
6. $\exists$xA(x)$\rightarrow$B$\Leftrightarrow$$\forall$x(A(x)$\rightarrow$B)
7. B$\rightarrow$$\forall$xA(x)$\Leftrightarrow$$\forall$x(B$\rightarrow$A(x))
8. B$\rightarrow$$\exists$xA(x)$\Leftrightarrow$$\exists$x(B$\rightarrow$A(x))

定理（量词分配律）设A(x)，B(x)是包含自由变元x的公式，则有

1. $\forall$xA(x)$\wedge$$\forall$xB(x)$\Leftrightarrow$$\forall$x(A(x)$\wedge$B(x))
2. $\exists$xA(x)$\vee$$\exists$xB(x)$\Leftrightarrow$$\exists$x(A(x)$\vee$B(x))

定理 设A(x,y)是包含自由变元x,y的二元谓词公式，则有：

1. $\forall$x$\forall$yA(x,y)$\Leftrightarrow$$\forall$y$\forall$xA(x,y)
2. $\exists$x$\exists$yA(x,y)$\Leftrightarrow$$\exists$y$\exists$xA(x,y)

例题

证明下面的等价式成立

1.$\exists$x(A(x)$\rightarrow$B(x))$\Leftrightarrow$$\forall$xA(x)$\rightarrow$$\exists$xB(x)

证明：$\exists$x(A(x)$\rightarrow$B(x))$\Leftrightarrow$$\exists$x($\neg$A(x)$\vee$B(x))$\Leftrightarrow$$\exists$x$\neg$A(x)$\vee$$\exists$xB(x)$\Leftrightarrow$$\neg$$\forall$xA(x)$\vee$$\exists$xB(x)$\Leftrightarrow$$\forall$xA(x)$\rightarrow$$\exists$xB(x)

2.5.1前束范式

一个谓词公式A，若具有形式Q₁x₁Q₂x₂…Q_nx_nM，其中每个Q_i（1≤i≤n）为$\forall$或$\exists$，M为不含量词的谓词公式，则称谓词公式A为前束范式。【简单地说就是把一个公式里的所有量词全部提到公式的前面去】

例子

$\forall$x$\forall$y(A(x,y)$\rightarrow$B(x,y)),$\exists$x$\forall$y(A(x,y,z)$\wedge$C(x,y))等都是前束范式，而$\forall$xA(x)$\rightarrow$$\exists$xB(x),$\exists$xA(x)$\vee$$\exists$xB(x,y)等都不是前束范式。

定理：任一谓词公式都存在着与之等价的前束范式

证明：设A为任意一个谓词公式

1. 将公式化成只含有3个联结词$\neg$、$\wedge$、$\vee$的形式
2. 利用$\neg$($\neg$p)$\Leftrightarrow$p、德摩根律以及量词转换率等将公式中的所有$\neg$符号移到原子公式的前面。如果需要的话，将约束变元换名
3. 利用量词辖域收缩及扩张律、量词分配律等，将所有量词提到公式的最前面

按照上面的步骤，可以得到谓词公式A的前束范式。由于每一步变换都保持着等价的关系，所以得到的前束范式与原公式是等价的

求下列谓词公式的前束范式

1.$\forall$xA(x)$\rightarrow$$\exists$xB(x)

解：$\forall$xA(x)$\rightarrow$$\exists$xB(x)$\Leftrightarrow$$\neg$$\forall$xA(x)$\vee$$\exists$xB(x)【置换规则】

$\Leftrightarrow$$\exists$x$\neg$A(x)$\vee$$\exists$xB(x)

$\Leftrightarrow$$\exists$x($\neg$A(x)$\vee$$\exists$xB(x))

证明完毕

或者

$\forall$xA(x)$\rightarrow$$\exists$xB(x)$\Leftrightarrow$$\neg$$\forall$xA(x)$\vee$$\exists$xB(x)【置换规则】

$\Leftrightarrow$$\exists$x$\neg$A(x)$\vee$$\exists$xB(x)

$\Leftrightarrow$$\exists$x$\neg$A(x)$\vee$$\exists$yB(y)【换名规则】

$\Leftrightarrow$$\exists$x$\exists$y($\neg$A(x)$\vee$B(y))

由此可知，一个公式转换成前束范式，前束范式并不唯一

2.6.1谓词逻辑的推理规则

若（A₁$\wedge$A₂$\wedge$A₃$\wedge$…$\wedge$A_n)$\rightarrow$B是永真式，则称由前提A₁,A₂,A₃,….,A_n可推出结论B，可表示为（A₁$\wedge$A₂$\wedge$A₃$\wedge$…$\wedge$A_n)$\Rightarrow$B

在命题逻辑的推理中使用的等价关系、蕴含关系和推理规则在谓词逻辑的推理中同样适用，另外还有谓词演算特有的关于量词的规则

全称量词消去规则（UI）

$\forall$xA(x)$\Rightarrow$A(y)或$\forall$xA(x)$\Rightarrow$A(c)

成立的条件：

1. x是A(x)中自由出现的个体变元；【也就是说，A(x)这里面不能够对x在进行约束】
2. y是任意的不在A(x)中约束出现的个体变元；【也就是说消去全称量词后，所用的字母y不能选用在A(x)当中约束出现的个体变元】

例如：若A(x)$\Rightarrow$$\exists$yF(x,y),则$\forall$xA(x)$\Leftrightarrow$$\forall$x$\exists$yF(x,y)。利用UI规则后：$\forall$xA(x)$\Rightarrow$A(y)，于是$\forall$x$\exists$yF(x,y)$\Rightarrow$$\exists$yF(y,y)。这个蕴含是是不成立的，原因是使用UI规则时违背了条件2

存在量词消去规则（EI）

$\exists$xA(x)$\Rightarrow$A(c)

成立条件：

1. c是个体域中使A成立的特定的个体常元。【c是特定的】
2. c不曾出现在A(x)中出现过
3. A(x)中除x外还有其他自由出现的个体变元时，不能用此规则

注意：c是使A成立的特定的个体常元，不要和公式中或推理过程中前面步骤的其他常元和变元名称相同

例如，在实数集上F(x,y)：x＞y,若A(x)$\Leftrightarrow$F(x,c),c是实数集上的一个常数，则$\exists$xA(x)为真，利用EI规则，消去量词，用c取代x，得F(c,c)，这是假命题，因为违背了条件2.。【如果是选用b，变成F(b,c)这是真命题，成立的】

全称量词引入规则（UG）

A(y)$\Rightarrow$$\forall$xA(x)

成立条件：

1. y是A(y)中自由出现的个体变元，y取个体域中的任何值，A都为真
2. 取代y的x不能在A(x)中约束出现

例如，在实数集上F(x,y):x＞y。若A(y)$\Leftrightarrow$$\exists$xF(x,y)，则对任意的y，A(y)为真。用UG规则，用x取代y，得$\forall$x$\exists$xF(x,x)，显然这是一个假命题。因为违背了条件2

存在量词引入规则（EG）

A(y)$\Rightarrow$$\exists$xA(x)

成立条件：

1. c是特定的个体常元
2. 取代c的x不能在A(c)中出现过

例如在实数集上F(x,y)：x＞y。若A(2)$\Leftrightarrow$$\exists$xF(x,2)，则A(2)为真。若用EG规则，用x取代2，得$\exists$xF(x,x)，显然这是假命题，因为违背了条件2【如果用z，b等其他字母则是正确的，如$\exists$xF(x,b)】

谓词逻辑的应用

谓词逻辑是人工智能中最重要的一种知识表示方法，可用于表述各种描述性语句，并可有效地存储到计算机中进行处理；可用来建立自动定理证明系统、基于规则的演绎系统等。

2.6.2谓词逻辑推理证明举例

证明$\forall$x(P(x)$\rightarrow$$\neg$Q(x))是$\exists$x(P(x)$\wedge$Q(x))$\rightarrow$$\forall$y((R(y)$\rightarrow$S(y))，$\exists$y(R(y)$\wedge$$\neg$S(y))的结论

说明下面推理的错误，并指出错误的原因

错误在第五步用EI规则时，用c取代x，c在前面步骤已用于特指使p为真的个体，在这里不一定能使Q为真。

正确的步骤

注意：在前提中含有全称量词$\forall$x和存在量词$\exists$x的条件时，应先使用EI规则，后使用UI规则

3

3.1.1集合的基本概念和表示法

代数学研究的是数集（自然数集、整数集、有理数集、实数集等）

几何学研究的是点集、边集

集合的基本概念

集合是由一些对象聚集在一起构成的

例如

1. 全体整数
2. 全体中国人
3. 26个英文字母

构成集合的对象可以是各种类型的事物，集合中的对象叫集合的元素，或成员

集合的表示法

通常用大写的英文你字母来标记一些集合

例如

N:表示自然数集合（包括0）

Z:表示整数集合

Q：表示有理数集合

R：表示实数集合

C：表示复数集合

列举法

列举法是列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起来

例如A={1，2，3}

描述法

描述法不要求列出集合中的所有元素，只要把集合中的元素具有的性质或所满足的条件描述出来即可

可以用谓词公式描述集合中的元素具有的性质或所满足的条件

一般的，用B={x|P(x)}表示集合B是由具有性质P的元素x构成

例如B={x|x∈Z$\wedge$3＜x≤6}

注意：谓词P(x)的范围一定要明确清楚，否则集合无法构成，如A={x|P(x)},P(x)：x是公园里美丽的花【美丽无法进行判断，所以这个集合不明确】

归纳法

归纳法是通过归纳定义集合，主要由三部分组成：

1. 指出某些最基础的元素属于集合
2. 指出由基本元素构成新元素的方法
3. 指出该集合的界限

如：集合A按归纳法定义如下：

1. 0和1都是集合A的元素
2. 如果a、b是A的元素，则ab和ba也是A的元素
3. 有限次地使用1、2后得到的字符串都是A地元素

集合的元素

集合中的元素可以具有共同性质，也可以表面上看起来不相干

如：{2，Tom，广州，计算机}

在集合论中，规定元素之间是彼此相异的，并且是没有次序关系的

如：{3，4，5}，{3，4，4，5，5，}，{5，3，4}都是同一个集合

特殊集合

有限个元素构成的集合A，称为有限集，其中包含的元素个数称为该集合的元素数，记为|A|

无限个元素构成的集合称为无限集

不含任何元素的集合称为空集，记为$\varnothing$

所考虑的所有对象的集合，称为全集，记为E

3.2.1集合的关系

集合相等关系

设A、B为集合，当且仅当它们恰有完全相同的元素时，称A与B相等，记作A=B

符号化表示为：A=B$\Leftrightarrow$$\forall$x(x∈A$\leftrightarrow$x∈B)

例如A={1,2,3},B={1,2,3}，则A=B

集合包含关系

设A、B为两个集合，如果B中的每个元素都是A中的元素，则称B为A的子集合，简称子集。这时也称B被A包含，或A包含B。记作B$\subseteq$A或A$\supseteq$B

可符号化表示为：B$\subseteq$A$\Leftrightarrow$$\forall$x(x∈B$\rightarrow$x∈A)

如果B不被A包含，则记作B⊄A

例如A={1，2，3}，B={1，2}所以B$\subseteq$A

定义：设A，B为集合，如果B$\subseteq$A且B≠A（即集合B的每一个元素都属于A，但集合A中至少有一个元素不属于B），则称B是A的真子集。这时也称B被A真包含，或A真包含B，记作A$\supset$B，亦即B$\subset$A

可符号化表示为：B$\subset$A$\Leftrightarrow$$\forall$x(x∈B$\rightarrow$x∈A)$\wedge$$\exists$x(x∈A$\wedge$x∉B)

集合的性质

1. 对任何集合A都有A$\subseteq$A
2. 设A、B为集合，A$\subseteq$B$\wedge$B$\subseteq$A$\Leftrightarrow$A=B
3. 设A、B、C为集合，A$\subseteq$B$\wedge$B$\subseteq$C$\Leftrightarrow$A$\subseteq$C

空集上的集合关系

空集$\varnothing$是一切集合的子集

推论：空集是唯一的

幂集

设A为集合，把A的全体自己构成的集合叫做A的幂集，记作P(A)或2^A，符号化表示为P(A)={x|x$\subseteq$A}

若A是n元集，则P(A)有2ⁿ个元素

集合的运算

并、交、补（绝对补）、差（相对补）和对称差

集合的并运算

设A，B为集合，由A和B的所有元素组成的集合称为A与B的并集，可表示为：

A$\bigcup$B={x|x∈A$\vee$x∈B}

集合的交运算

设A，B为集合，由同时属于集合Ahead集合B的元素组成的集合，称为集合A与集合B的交集，可符号化表示为：Ａ$\bigcap$B={x|x∈A$\wedge$x∈B}

当两个集合的交集是空集时，称他们是不相交的。

B$\bigcap$C=$\varnothing$

集合运算的性质

设A，B为集合，则下列的交换律成立

1. A$\bigcup$B=B$\bigcup$A
2. Ａ$\bigcap$B=B$\bigcap$A

设A，B，C为任意三个集合，则下列结合律成立

1. (A$\bigcup$B)$\bigcup$C=A$\bigcup$(B$\bigcup$C)
2. (A$\bigcap$B)$\bigcap$C=A$\bigcap$(B$\bigcap$C)

设A，B为任意两个集合，则下列吸收率成立

1. A$\bigcup$(Ａ$\bigcap$B)=A
2. A$\bigcap$(Ａ$\bigcup$B)=A

设A，B，B为任意三个集合，则下列分配律成立

1. A$\bigcup$(B$\bigcap$C)=(A$\bigcup$B)$\bigcap$(A$\bigcup$C)
2. A$\bigcap$(B$\bigcup$C)=(A$\bigcap$B)$\bigcup$(A$\bigcap$C)

集合的差运算

设A，B为任意两个集合，由属于A但不属于B的元素构成的集合，称为A和B的差，又称为集合B对于A的补集或相对补集，记为A-B。可符号化表示为：

A-B={x|x∈A$\wedge$x∉B}

集合的补运算

设E为全集，A$\subseteq$E，则称E和Adequate差集为A的补集或绝对补集，记作～A，即：~A=E-A={x|x∉A}

一些性质：

~E=$\varnothing$

~$\varnothing$=E

~(~A)=A

A$\bigcap$~A=$\varnothing$

A$\bigcup$~A=E

集合的对称差运算

设A，B为集合，由属于A而不属于B的所有元素和属于B而不属于A的所有元素组成的集合，称为集合A与B的对称差，记为A$\bigoplus$B，可符号化表示为：

A$\bigoplus$B={x|(x∈A$\wedge$x∉B)$\vee$(x∈B$\wedge$x∉A)}

一些性质：

A$\bigoplus$B=(A-B)$\bigcup$(B-A)

A$\bigoplus$A=$\varnothing$

A$\bigoplus$$\varnothing$=A

A$\bigoplus$B=B$\bigoplus$A

(A$\bigoplus$B)$\bigoplus$C=A$\bigoplus$(B$\bigoplus$C)

集合恒等式

例题

1.证明A-(B$\bigcup$C)=(A-B)$\bigcap$(A-C)

证明：x∈A-(B$\bigcup$C)

$\Leftrightarrow$x∈A$\wedge$x∉B$\bigcup$C

$\Leftrightarrow$x∈A$\wedge$$\neg$(x∈B$\vee$x∈C)

$\Leftrightarrow$x∈A$\wedge$x∉B$\wedge$x∉C

$\Leftrightarrow$(x∈A$\wedge$x∉B)$\wedge$(x∈A$\wedge$x∉C)

$\Leftrightarrow$x∈A-B$\wedge$x∈A-C

$\Leftrightarrow$x∈(A-B)$\bigcap$(A-C)

另一个方法：

证明：

A-(B$\bigcup$C)

=A$\bigcap$~(B$\bigcup$C)

=A$\bigcap$(~B$\bigcap$~C)

=(A$\bigcap$~B)$\bigcap$(A$\bigcap$~C)

=(A-B)$\bigcap$(A-C)

3.4.1后继集和自然数

集合论的提出，其中一个重要的目的是研究无穷。因此数学家尝试构造出与特殊数集性质相似的集合，从而能够分析无穷数集的性质

后继集

设A是一集合，A的后继集A⁺为：

A⁺=A$\bigcup${A}

例：

1.已知集合A={1，2，3}求A的后继集A⁺

解：A的后继集A⁺=A$\bigcup${A}={1，2，3}$\bigcup$={1，2，3，{1，2，3}}

2.对于空集$\varnothing$，求(1)$\varnothing$⁺;(2)($\varnothing$⁺)⁺;(3)(($\varnothing$⁺)⁺)⁺

解：0=$\varnothing$

(1)$\varnothing$⁺=$\varnothing$$\bigcup${$\varnothing$}={$\varnothing$}

(2)($\varnothing$⁺)⁺={$\varnothing$}⁺={$\varnothing$}$\bigcup$={$\varnothing$,{$\varnothing$}}

(3)(($\varnothing$⁺)⁺)⁺={$\varnothing$,{$\varnothing$},{$\varnothing$,{$\varnothing$}}}

利用上述的后继集，我们可以用空集和后继集把所有自然数定义为集合

即：

0=$\varnothing$

1=$\varnothing$⁺={$\varnothing$}

2=($\varnothing$⁺)⁺={$\varnothing$,{$\varnothing$}}

3=(($\varnothing$⁺)⁺)⁺={$\varnothing$,{$\varnothing$},{$\varnothing$,{$\varnothing$}}}

……

任一个自然数都是一个集合的名称

4

4.1.1关系的概念和笛卡尔积

序偶

由两个元素a和b按一定的顺序排列称的二元族叫做一个有序对（也称序偶），记作(a,b)，其中a是它的第一元素，b是它的第二元素

一般说，有序偶具有以下特点：

1. 有序性：当a≠b时，则(a,b)≠(b,a).
2. 两个有序偶相等，即(a,b)=(c,d)的充分必要条件时a=c且b=d

注意：区别(a,b)和{a,b}。【（）是有序性的，而{}是没有顺序的，即前者ab≠ba，后者可以ab=ba】例如，当a≠b时，有{a,b}={b,a}

有序n元组

由n个元素a₁，a₂,…,a_n按一定的顺序排列成的一个序列(a₁，a₂,…,a_n)，称为有序n元组，其中a₁为第一元素，a₂为第二元素，a_n为第n元素

例如：n维空间中点的坐标或n维向量都是有序n元组。

(a₁，a₂,…,a_n)=(b₁，b₂,…,b_n)，当且仅当a_i=b_i,i=1,2,3,….,n

笛卡尔积（直积）

设A，B为集合，取A中的元素作为第一元素，取B中的元素做为第二元素构成有序对，所有这样的有序对组成的集合，称为A和B的笛卡尔积（直积），表示为A$\times$B。于是符号化为：

A$\times$B={(x,y)|x∈A$\wedge$y∈B}

例：A={a,b,c},B={1,3}。求A$\times$B，B$\times$A,A$\times$$\varnothing$,$\varnothing$$\times$B

解：

A$\times$B={(a,1),(a,3),(b,1),(b,3),(c,1),(c,3)}

B$\times$A={(1,a),(1,b),(1,c),(3,a),(3,b),(3,c)}

A$\times$$\varnothing$=$\varnothing$

$\varnothing$$\times$B=$\varnothing$

笛卡尔积

1. 当A，B为非空集合且A≠B时，笛卡尔积运算不满足交换律，即A$\times$B≠B$\times$A
2. A$\times$B=$\varnothing$，当且仅当A=$\varnothing$或者B=$\varnothing$
3. 当A，B，C均为非空集合时，笛卡尔积运算不满足结合律，即(A$\times$B)$\times$C≠A$\times$(B$\times$C)
4. 当集合AheadB都是有限集时，根据乘法原理，有｜A$\times$B｜＝|A|$\times$|B|

定理：设A，B，C为任意集合，则

1. A$\times$(B$\bigcup$C)=(A$\times$B)$\bigcup$(A$\times$C)
2. A$\times$(B$\bigcap$C)=(A$\times$B)$\bigcap$(A$\times$C)
3. (A$\bigcup$B)$\times$C=(A$\times$C)$\bigcup$(B$\times$C)
4. (A$\bigcap$B)$\times$C=(A$\times$C)$\bigcap$(B$\times$C)

n个集合的直积

设A₁，A₂,…,A_n为任意n个集合，它们的笛卡尔积（又称n阶直积）为

A₁$\times$A₂$\times$…$\times$A_n={(a₁，a₂,…,a_n)|a_i∈A_i,for i =1,2,3,…,n}

当A₁=A₂=…=A_n=A时，A₁$\times$A₂$\times$…$\times$A_n=Aⁿ

若|A₁|=n₁,|A₂|=n₂,…,|A_n|=n_n，则n个集合的笛卡尔积中的元素个数为

|A₁$\times$A₂$\times$…$\times$A_n|=|A₁|$\times$|A₂|$\times$…$\times$|A_n|=n₁$\times$n₂$\times$…$\times$n_n

二元关系

如果一个集合非空且它的元素都是有序对，或集合为空，则称该集合为一个二元关系，记作R。二元关系也可以简称为关系。对于二元关系R，如果有序对(a,b)∈R，则称a与b有R关系，记作aRb；当(a,b)∉R时，称a与b没有R关系，记作a$\cancel{R}$b

例如，R={(0,a),(0,b),(1,a),(2,b)}是一个二元关系

其中0Ra，1Ra，0Rb，2Rb，而1$\cancel{R}$b,2$\cancel{R}$a

R={(1,2),(1,3),2,3}不是一个二元关系。因为元素2，3并不是有序对

设A、B为集合，A$\times$B的任意一个子集是集合A到B的一个二元关系。当A=B时称为A上的二元关系

例如

A={0，1，2}，B={a,b}，则

R₁={(0,a),(1,b),(1,a),(2,b)}是从A到B的一个二元关系

R₂={(0,1),(1,2),(0,2)}是A上的一个二元关系

空关系

$\varnothing$$\subseteq$A$\times$A

全域关系

E_A=A$\times$A={(x,y)|x∈A$\wedge$y∈A}

恒等关系

I_A={(x,x)|x∈A}

对于集合A有n个元素，B有m个元素，那么集合A到集合B有2^nm个不同的二元关系(也就是A$\times$B的子集个数)

如果B=A，则|A$\times$A|=n²,则A上有2ⁿ²个不同的二元关系

例题

A={0，1}，B={a,b}，写出所有A到B的二元关系

解：

0元子集：$\varnothing$

1元子集：{(0,a),(0,b),(1,a),(1,b)}

2元子集：{(0,a),(0,b)},{(0,a),(1,a)},{(0,a),(1,b)},{(0,b),(1,a)},{(0,b),(1,b)},{(1,a),(1,b)}

3元子集：{(0,a),(0,b),(1,a)},{(0,a),(0,b),(1,b)},{(0,a),(1,a),(1,b)},{(0,b),(1,a),(1,b)}

4元子集：{(0,a),(0,b),(1,a),(1,b)}

定义域（前域）、值域（后域）

设A、B是两个集合，R是从A到B的二元关系，R的所有有序对的第一个元素构成的集合称为R的定义域（前域），记为domR；R的所有有序对的第二个元素构成的集合称为R的值域（后域），记为ranR；R的定义域和值域的并集称为R的域，记为fidR

n元关系

设设A₁，A₂,…,A_n是n个集合。A₁$\times$A₂$\times$…$\times$A_n的任一子集，称为A₁，A₂,…,A_n间的一个n元关系

4.2.1关系的表示法

用集合表示关系

根据关系的定义可知，关系是一个集合，因此可用列出集合的所有元素的列举法或描述集合元素的特性的描述法来表示关系

例如：

描述法：R={(a,b)|a,b是整数且0＜a＜b＜4}

列举法：R={(1,2),(1,3)}

用关系图表示关系

设集合A={a₁，a₂,…,a_n}，B={b₁，b₂,…,b_m}，R是从A到B上的一个二元关系。把集合A和B的每个元素表示成一个结点，关系R的每一个有序对表示成一条有向边，有向边的方向由有序对的第一元素指向第二元素。

A={a₁，a₂,…,a_n}

B={b₁，b₂,…,b_m}

这样得到的图就是表示关系R的关系图

在关系图中，结点a是有向边(a,b)的起点，结点b是终点，若aRa，则从a到自身有一条有向边，称为环

用矩阵表示关系

设A={a₁，a₂,…,a_n}，B={b₁，b₂,…,b_m}，R是从A到B上的一个二元关系。关系R可以用一个m行n列的矩阵M_R=[m_ij]来表示，称M_R为关系R的邻接矩阵，其中

$m_{ij}=\begin{cases}1,,,若(a_1,b_j)∈R\0,,,若(a_1,b_j)∉R\\end{cases}$

例

集合A＝｛１，２，３｝，B＝｛１，２｝。R是A到B上的大于关系，给出R的关系矩阵

$M_R=\begin{bmatrix}0&0\1&0\1&1\\end{bmatrix}$

4.3.1关系的运算

关系本身就是一种集合，因此可以在关系上进行集合运算

1. R$\bigcup$S
2. R$\bigcap$S
3. R-S
4. S$\oplus$R
5. ~R,~s

若R和S是集合A到B的两个二元关系，则上述运算结果，仍然是A到B的二元关系。

关系的逆运算

设R是从集合A到B的关系，R的所有有序对的元素顺序交换得到的有序对的集合是从B到A的关系，该关系称为R的逆关系。记为R^-1，即R^-1={(x,y)|yRx}

R={(1,a),(2,c),(3,d),(4,a),(4,b)}

R^-1={(a,1),(c,2),(d,3),(a,4),(b,4)}

结论

1. 将R的关系图中有向边的方向改变成相反方向即可获得R^-1的关系图，反之亦然。
2. R和R^-1的关系矩阵互为转置矩阵
3. dom R^-1=ran R,ran R^-1=dom R
4. |R|=|R<sup>-1</sup>|

逆关系的性质

设R和S是任意关系，则有

1. ($R^{-1}$)^-1=R
2. (R$\bigcup$S)$^{-1}$=R^-1$\bigcup$S^-1
3. (R$\bigcap$S)^-1=R$^{-1}$$\bigcap$S$^{-1}$
4. (~R)$^{-1}$=~(R$^{-1}$)
5. (R-S)$^{-1}$=R$^{-1}$-S$^{-1}$
6. 若R$\subseteq$S，则R$^{-1}$$\subseteq$S$^{-1}$

关系复合运算

设R是集合A到集合B上的一个二元关系，S是集合B到集合C上的一个二元关系，则R和S的复合关系S$\circ$R为集合A到集合C上的一个二元你关系，定义如下：

S$\circ$R＝｛（ｘ，ｚ）｝ｘ∈Ａ$\wedge$ｚ∈Ｃ$\wedge$$\exists$ｙ(ｙ∈Ｂ$\wedge$（ｘ，ｙ）∈Ｒ$\wedge$（ｙ，ｚ）∈Ｓ）}

从R和S求S$\circ$R的运算，称为关系的复合运算，又称关系的合成运算

有些书会写将R和S的复合关系写成Ｒ$\circ$Ｓ

例子

有集合A={a,b,c},B={a,c,d}

R={<a,b>,<c,d>},S={<c,b>,<a,d>,<b,c>}

那么R$\circ$S={<a,c>,<c,a>}

实际上就是R中的(x,y)在S中找到(y,z)，那么R$\circ$S就是（x，z)

关系复合运算的结合律

设R、P、S为任意二元关系，则P$\circ$(S$\circ$R)=(P$\circ$S)$\circ$R

关系复合运算的分配律

设R、P、S为任意二元关系，则有

1. R$\circ$(S$\bigcup$P)=R$\circ$S$\bigcup$R$\circ$P
2. (S$\bigcup$P)$\circ$R=(S$\circ$R)$\bigcup$(P$\circ$R)
3. R$\circ$(S$\bigcap$P)$\subseteq$R$\circ$S$\bigcap$R$\circ$P
4. (S$\bigcap$P)$\circ$R$\subseteq$S$\circ$R$\bigcap$P$\circ$R

注意：复合运算对并运算是可分配的，对交运算分配后是包含关系式

关系复合的逆运算性质

设R和S是任意关系，则有

(S$\circ$R)$^{-1}$=R$^{-1}$$\circ$S$^{-1}$

与恒等关系的复合

设R是A上的关系，则有

R$\circ$I$_A$=I$_A$$\circ$R=R

其中I$_A$表示<x,x>

R的n次幂

设R为A上的关系，ｎ为非负整数，则R的ｎ次幂定义如下

1. R$^0$={(x,x)|x∈A}=I$_A$
2. R$^n$=R$^{n-1}$$\circ$R,n≥1

这个定义说明R$^2$=R$\circ$R，R$^3$=R$^2$$\circ$R=(R$\circ$R)$\circ$R,…..等

关系的n次幂的性质

设R为A上的关系，m，n为非负整数，有

1. R$^m$$\circ$R$^n$=R$^{m+n}$
2. (R$^m$)$^n$=R$^{mn}$

实际上，对于有限集A和A上的关系R，R的不同的幂只有有限个

关系的幂的周期性

R为A上的关系，｜Ａ｜＝ｎ，则存在自然数ｓ、ｔ，使

1. R$^s$=R$^t$,(T=t-s为周期)
2. 对任何k∈N有R$^{s+k}$=R$^{t+k}$

用矩阵表示两个关系的复合

$M_R=\begin{bmatrix}r_{11}&r_{12}&…&r_{1n}\r_{21}&r_{22}&…&r_{2n}\…&…&…&…\r_{m1}&r_{m2}&…&r_{mn}\\end{bmatrix}$

$M_S=\begin{bmatrix}s_{11}&s_{12}&…&s_{1n}\s_{21}&s_{22}&…&s_{2n}\…&…&…&…\s_{m1}&s_{m2}&…&s_{mn}\\end{bmatrix}$

$M_{S{\circ}R}=M_R{\times}M_S\begin{bmatrix}t_{11}&t_{12}&…&t_{1n}\t_{21}&t_{22}&…&t_{2n}\…&…&…&…\t_{m1}&t_{m2}&…&t_{mn}\\end{bmatrix}$

$t_{ij}$=${\vee}{k=1}^n$($r{ik}{\wedge}s_{kj}$)

4.4.1关系的性质

1. 自反性
2. 反自反性
3. 对称性
4. 反对称性
5. 传递性

自反关系

设R使集合A上的一个关系，如果对A中的每一个元素x，均有(x,x)∈R，则称R使自反关系，即

R使自反的$\Leftrightarrow$$\forall$x(x∈A$\rightarrow$(x,x)∈R)

例如：正整数集合上的整除关系，相等关系等都是自反的关系；整数集合上的大于关系，小于关系等都不是自反关系

反自反关系

设R是集合A上的一个关系，如果对A中的每一个元素x，均有(x,x)∉R，则称R是反自反关系，即

R是反自反的$\Leftrightarrow$$\forall$x(x∈A$\rightarrow$(x,x)∉R)

例如：整数集合上的大于关系，小于关系等都是反自反的关系；而整数集合上的整除关系，大于等于关系等都不是反自反的关系

例题

A={1，2，3，4}上的关系R={(1,2),(1,4) ,(2,1),(2,3),(3,2),(4,1),(4,2)},S={(1,2),(1,3),(2,2),(3,1),(4,3)}，判断R和S是否反自反关系？是否自反关系？

解：R是反自反的关系，因为没有（２，２）这种环存在。而S虽然存在（２，２），但因为只有一个而不是全部元素（即１，２，３，４）都是，所以它不是反自反关系也不是自反关系。

自反性和反自反性的特征

1. 如果关系R是自反的，则关系R一定不是反自反的，反之亦然
2. 如果关系R不是自反的，则关系R不一定就是反自反的，反之亦然。也就是说存在既不是自反也不是反自反的关系
3. 如果关系R是自反的，当且仅当R的关系图中每个节点都有环；如果关系R是反自反的，当且仅当R的关系图中每个节点都没有环
4. 如果关系R是自反的，当且仅当R的关系矩阵中主对角线上都为1；如果关系R是反自反的，当且仅当R的关系关系矩阵中主对角线上都为0

对称关系

设R是A上的一个关系，如果对A中的元素x和y，如有(x,y)∈R，必有(y,x)∈R，则称R是对称关系

R是对称的$\Leftrightarrow$$\forall$x$\forall$y(x∈A$\wedge$y∈A$\wedge$(x,y)∈R$\rightarrow$(y,x)∈R)

例如：整数集合上的等于关系，任意集合上的全域关系，同学关系，朋友关系等都是对称的；而整数集合上的整除关系，大于关系等都是不对称的。

反对称关系

设R是A上的一个关系，如果对A中的元素ｘ和ｙ，若（ｘ，ｙ）∈R和（ｙ，ｘ）∈R，就必有ｘ＝ｙ，则称R是反对称关系

R是反对称的$\Leftrightarrow$$\forall$x$\forall$y(x∈A$\wedge$y∈A$\wedge$(x,y)∈R$\wedge$(y,x)∈R$\rightarrow$x=y)

若关系R是反对称的，则当x≠y时，（x，y）∈R，则（y，x）∉R

实数集合上的大于等于关系，大于关系，集合的幂集上的包含关系等都是反对称的

总结：

1. 对称性和反对称性的概念是不对立的，一个关系可以不具有对称性的同时也不具有反对称性，且存在既对称也反对称的关系
2. 关系R是对称的当且仅当在其关系图上，若两点之间有边，则必定是成对出现的方向相反的两条边；关系R是反对称关系当且仅当在其关系图上，若两点之间有边，只有一条边
3. 对称关系R的关系矩阵是对称矩阵，反对称关系R的关系矩阵中，不再主对角线上关于主对角线对称的元素不能同时为1

传递关系

设R是A上的一个关系，ｘ、ｙ、ｚ是A中的元素，若（ｘ，ｙ）∈Ｒ，（ｙ，ｚ）∈Ｒ，必有（ｘ，ｚ）∈Ｒ，则称R是传递关系

R是传递的$\Leftrightarrow$$\forall$x$\forall$y$\forall$z(x∈A$\wedge$y∈A$\wedge$z∈A$\wedge$(x,y)∈R$\wedge$(y,z)∈R$\rightarrow$(x,z)∈R)

例如：实数集上的大于关系、小于关系等是传递关系，而同学关系、朋友关系等不一定是传递的。

关系性质的充要条件

设R是集合A上的关系，则

关系性质的保持

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

可以用下表来看

4.5.1关系闭包

原本R是不具备自反等性质的，但我们为了让他有这些性质，添加最少的有序对，形成R’，这个R’就具备了自反等性质。而这个添加最少的有序对的操作就叫关系闭包的操作

闭包

设R是非空集合A上的二元关系，如果A上的关系R’满足

1. R’是自反的(对称的或传递的)【具备所需性质】
2. R’$\supseteq$R【包含R】
3. 对A上的任何包含R的自反(对称或传递)关系R’’,都有r’’$\supseteq$R’.【最小性】

称R’是R的自反（对称或传递）闭包

一般将R的自反闭包记作r(R),对称闭包记作s(R)，传递闭包记作t(R)

例题

集合A＝｛１，２，３｝上的关系Ｒ＝｛（１，１）｝，（１，２），（２，１），（３，２）｝，求R的对称闭包

s(R)={(1,1),(1,2),(2,1),(3,2),(2,3)}

充分必要条件

设R是非空集合A上的二元关系，则有

1. R是自反的，当且仅当r(R)＝Ｒ
2. R是对称的，当且仅当s(R)＝Ｒ
3. R是传递的，当且仅当t(R)＝Ｒ

闭包构造方法

设R为非空集合A上的关系，则有

1. r(R)=R$\bigcup$I$_A$
2. s(R)=R$\bigcup$R$^{-1}$
3. 

例题

设集合A＝｛ａ，ｂ，ｃ｝，R是A上的二元关系，Ｒ＝｛（ａ，ｂ），（ｂ，ｃ），（ｃ，ａ）｝，求r(R)、s(R)和t(R)

解：

闭包的定理

设R$_1$和R$_2$为非空集合A上的二元关系，且R$_1$$\subseteq$R$_2$，则有

1. r(R$_1$)$\subseteq$r(R$_2$)
2. s(R$_1$)$\subseteq$s(R$_2$)
3. t(R$_1$)$\subseteq$t(R$_2$)

设R是非空集合A上的二元关系，有

1. 若R是自反的，则s(R)和t(R)也是自反的
2. 若R是对称的，则r(R)和t(R)也是对称的
3. 若R是传递的，则r(R)也是传递的

令tsr(R)=t(s(r(R)))，则有下面的定理：

则tsr(R)是R的自反、对称、传递的闭包

4.6.1等价关系

设R是非空集合A上的关系，若R是自反的、对称的和传递的，则称R为A上的等价关系。若(x,y)∈R，称x等价于y，记作x~y

例如：集合上的恒等关系和全域关系都是等价关系

同余关系

设x和y为整数，n为正整数。如果x除以n的余数和y除以n的余数相等，则称x与y模n同余，用x$\equiv$y(mod n)表示

R={(x,y)|x$\equiv$y(mod n)}，称R为模n同余关系

PS：如果要证明是等价关系，只要证明它具有传递性、自反性和对称性即可。

等价类

设R是非空集合A上的等价关系，x是集合A中的一个元素，所有与x有R关系的元素组成的集合叫做x的等价类，记作[x]$_R$，则有

[x]$_R$={y|y∈A$\wedge$xRy}

例题

A={1,2,…,8},A上的模3同余关系R为A上的等价关系，它的关系图如图所示，A中各元素的等价类：

1. [1]$_R$=[4]$_R$=[7]$_R$={1,4,7}
2. [2]$_R$=[5]$_R$=[8]$_R$={2,5,8}
3. [3]$_R$=[6]$_R$={3,6}

等价类的性质

设R是非空集合A上的等价关系，对任意的x,y∈A，下面的结论成立

1. $\forall$x∈A，[x]$_R$≠$\varnothing$且[x]$_R$$\subseteq$A
2. $\forall$x，y∈A，若(x,y)∈R，则[x]$_R$=[y]$_R$
3. $\forall$x，y∈A，若(x,y)∉R,则[x]$_R$$\bigcap$[y]$_R$=$\varnothing$
4. $\bigcup$[x]=A

商集

设R为非空集合A上的等价关系，以R的所有等价类为元素构成的集合，叫做A在R下的商集，记作A/R，即

A/R={[x]$_R$|x∈A}

覆盖和划分

设A是非空集合，A的一簇子集$A_1,A_2,…,A_m$，满足以下条件

1. A$_i$≠$\varnothing$（i=1,2,3….)
2. 
3. $A_i{\bigcap}A_j=\varnothing$(i≠j)

若满足1，2的条件，则称{$A_1,A_2,…,A_m$}是A的覆盖

若满足１，２，３的条件，称{$A_1,A_2,…,A_m$}是A的一个划分，且称{$A_1,A_2,…,A_m$}中的任一元素为A的一个类或划分的一个块。

求解对应的等价关系

设A的划分{$A_1,A_2,…,A_m$}，求笛卡尔积Ａ$_i\times$A$_j$，和这些笛卡尔积的并集：(Ａ$_1{\times}$A$_1$)$\bigcup$(Ａ$_2{\times}$A$_2$)$\bigcup$….$\bigcup$(Ａ$_m{\times}$A$_m$)，即为由此划分确定的等价关系

4.7.1偏序关系

它用于研究一个集合中元素之间是否可以进行大小比较和排序

定义

设R为非空集合A上的关系，如果R是自反的、反对称的和传递的，则称R为A上的偏序关系，简称偏序，记作$\preceq$。集合A和A上的偏序关系R一起叫做偏序集，记作（Ａ，Ｒ）

如果R是集合A上的偏序关系，(a,b)∈R可以表示为a$\preceq$b

注意：这里并不是意义下的小于等于，而是说a排在b前面

可比与不可比

设(A,$\preceq$)为偏序集，对于任意的x,y∈A，如果x$\preceq$y或者y$\preceq$x成立，则称x与y是可比的；如果既没有x$\preceq$y成立，也没有y$\preceq$x成立，则称x与y是不可比的。如果x$\prec$y（即x$\preceq$y$\wedge$x≠y)，且不存在z∈A，使得x$\prec$z$\prec$y，则称y覆盖x

例题

设(A,$\preceq$)为偏序集，其中，$\preceq$是整除关系，A={1,2,3,4,5}则有：

4覆盖2，2覆盖1，3覆盖1

4不覆盖1【因为1$\prec$2$\prec$4，所以4不覆盖1】

哈斯图

对于一个偏序关系，如果按照以下规则画图：

集合A中的每个元素用一个结点表示。结点的位置按它们在偏序中的次序从底向上排序，如x$\preceq$y，则结点x在结点y的下面。若x和y是A中的元素，y覆盖x，则在x和y之间连一条线，省略连线的箭头。

这样得到的表示偏序关系的关系图称为哈斯图

例题

全序集

设(A,$\preceq$)为偏序集，若对任意的x，y∈A，x和y都可比，则称$\preceq$为A上的全序关系，且称(A,$\preceq$)为全序集

例如：{1，2，3，4，5}上的小于等于关系是全序关系，而整除关系就不是全序关系

全序集的哈斯图是一条直线，所以全序集也可以称为线序集

实数集R上的小于关系$\prec$不是全序关系，因为小于关系$\prec$不是自反的，不是偏序关系。而小于等于却是全序关系

最小（大）元和极小（大）元

设(A,$\preceq$)为偏序集，B$\subseteq$A

1. 若$\exists$y(y∈B)，使得$\forall$x(x∈B$\rightarrow$y$\preceq$x)成立，则称y是B的最小元【极小元之间可不可比，不可比则没有】
2. 若$\exists$y(y∈B)，使得$\forall$x(x∈B$\rightarrow$x$\preceq$y)成立，则称y是B的最大元【极大元之间可不可比，不可比则没有】
3. 若$\exists$y(y∈B)，使得$\neg$$\exists$x(x∈B$\wedge$x$\preceq$y)成立，则称y是B的极小元【就是哈斯图最下一层的那些结点就是极小元】
4. 若$\exists$y(y∈B)，使得$\neg$$\exists$x(x∈B$\wedge$y$\preceq$x)成立，则称y是B的极大元【哈斯图最上一层的结点就是极大元】

例题

结论

1. B的最大元和最小元可能存在，也可能不存在。如果存在，则是唯一的。
2. B中不一定存在着极大元和极小元，如果存在，可以是不唯一的
3. B的最大元也是极大元，B的最小元也是极小元
4. B的极大元不一定是最大元，B的极小元不一定是最小元

上界和下界

设(A,$\preceq$)为偏序集，B$\subseteq$A且B≠$\varnothing$

1. 若$\exists$a(a∈A)，使得$\forall$x(x∈B$\rightarrow$x$\preceq$a)成立，则称a是B的上界
2. 若$\exists$a(a∈A)，使得$\forall$x(x∈B$\rightarrow$a$\preceq$x)成立，则称a是B的下界
3. 若a是B的上界，且对B的任意上界b均有a$\preceq$b，则称a为B的最小上界或上确界
4. 若a是B的下界，且对B的任意下界b均有b$\preceq$a，则称a为B的最大下界或下确界

例题

结论

设(A,$\preceq$)为偏序集，B$\subseteq$A且B≠$\varnothing$

1. B的上、下界不一定存在，如果存在，可以不唯一
2. B的上、下确界不一定存在，如果存在，一定唯一

良序关系

设(A,$\preceq$)为偏序集，若A的每一个非空子集都存在最小元，则称(A,$\preceq$)为良序集，为良序关系

例如：自然数集合N={0，1，2，3，…}上的小于等于关系是良序关系，即(N,$\preceq$)是良序集

例题

结论

1. 每一个良序集，一定是全序集。每一个全序集，不一定是良序集
2. 每一个有限全序集，一定是良序集

4.8.1函数的定义

设f是从集合A到B的一个二元关系，且对于任一x∈A，都有唯一的y∈B，使得(x,y)∈f，则称f为从A到B的函数或映射，记作：f：A$\rightarrow$B

定义域和值域

如果f是从A到B的函数，则称A是f的定义域，B是f的陪域。如果(x,y)∈f，则可写成y=f(x)，称y为x的像，x为y的原像。A中元素的所有像元素构成的集合，称为f的值域。

可以用dom f表示f的定义域，ran f表示f的值域，所以有dom f=A，ran f$\subseteq$B

f是从A到B的函数需要满足以下条件：

1. 函数的定义域是A，不能是A的任一真子集
2. 对集合A的任一元素，对应集合B中唯一的元素ｙ

函数相等

设f、g均为集合A到集合B的函数。若对$\forall$x∈A，都有f(x)=g(x)，则称函数f和g相等，记作f=g

设A、B为集合，所有从A到B的函数构成B$^A$，读作B上A，即

B$^A$={f|f:A$\rightarrow$B}

映射

给定函数f:A$\rightarrow$B

若对于$\forall$x$_1$,x$_2$属于A，x$_1$≠x$_2$，都有f(x$_1$)≠f(x$_2$)，则称f是单射函数（或一对一映射）

若对于$\forall$y∈B，都有x∈A，使得f(x)=y，则称f是满射函数（或从A到B上的映射）

若f既是满射又是单射，则称f是双射函数（或一一对应映射）

常用的函数

设f：A$\rightarrow$B，如果存在b∈B使得对所有的x∈A都有f(x)=b，则称f：A$\rightarrow$B是常函数

设f：A$\rightarrow$A，如果对所有的x∈A都有f(x)=x，称f：A$\rightarrow$A为A上的恒等函数

设A为集合，对于任一的A’$\subseteq$A,A’的特征函数f$_A$’:A$\rightarrow${0,1}定义为

$f_{A’}=\begin{cases}1,,,若a∈A’\0,,,若a∉A’\\end{cases}$

设R是A上的等价关系，令g:A$rightarrow$A/R，g(a)=[a]$_R$，$\forall$a∈A，称g是从A到商集A/R的自然映射

对有理数x，f(x)为大于或等于x的最小整数，称f(x)为上取整函数，记为f(x)=$\lceil x \rceil$

对有理数x，f(x)为小于或等于x的最小整数，称f(x)为下取整函数，记为f(x)=$\lfloor x \rfloor$

4.8.2函数的复合和反函数

设f是从集合A到集合B的函数，g是从集合B到集合C的函数，f和g的复合用g$\circ$f表示为

g$\circ$f={(x,z)|x∈A$\wedge$z∈C$\wedge$$\exists$y(y∈B)$\wedge$(x,y)∈f$\wedge$(y,z)∈g}

g$\circ$f是从A到C的函数，称为f和g的复合函数

对任意x∈A都有g$\circ$f(x)=g(f(x))

注意：如果f的值域不是g的定义域的子集，就无法定义g$\circ$f

定理

设函数g:A$\rightarrow$B,f:B$\rightarrow$C，则：

1. f$\circ$g是A到C的函数
2. 对任意的x∈A，有f$\circ$g(x)=f(g(x))

设f和g是函数，g$\circ$f是f和g的复合函数，于是有：

1. 如果f和g都是满射函数，则g$\circ$f也是满射函数
2. 如果f和g都是单射函数，则g$\circ$f也是单射函数
3. 如果f和g都是双射函数，则g$\circ$f也是双射函数

设f和g是函数，g$\circ$f是f和g的复合函数，于是有：

1. 如果g$\circ$f是满射函数，则g必定是满射函数
2. 如果g$\circ$f是单射函数，则f必定是单射函数
3. 如果g$\circ$f是双射函数，则g必定是满射函数，f是单射函数

反函数

设集合A和B，函数f:A$\rightarrow$B是一个双射函数，则称f的逆关系叫做f的反函数（逆映射），记作f$^{-1}$,称f是可逆的

定理

如果函数f是从A到B的双射函数，则f$^{-1}$是从B到A的双射函数。

若$f$：A$\rightarrow$B是双射函数，则$(f^{-1})^{-1})=f$

若$f:A{\rightarrow}B$,$g:B{\rightarrow}C$均为双射函数，则$(g{\circ}f)^{-1}=f^{-1}{\circ}g^{-1}$

4.8.3集合的基数

等势

设A和B是两个集合，如果存在一个双射函数$f:A{\rightarrow}B$，则称A与B是等势的（或等基数），记作A~B。等基数的两个集合的基数相等，所以又记为|A|=|B|

基数

设A和B是两个集合，如果存在一个单射函数$f:A{\rightarrow}B$，则称A的基数小于或等于B的基数，记作|A|≤|B|。如果|A|≤|B|且|A|≠|B|，则称A的基数小于B的基数，记作|A|＜|B|

有限集合、无限集合

基数为自然数的集合称为有限基数集合（有限集合），非有限集合称为无限集合

有限集合：A={1,2,3,4} |A|=4(自然数)

无限集合:N，Z，R等

可数集合、可列集合

所有与自然数集合等势的集合都称为可数集合或可列集合。

可数集合的基数为ℵ₀（阿列夫零）

例题

定理

1.集合S可列的充分必要条件是它的全体元素可排成无穷序列形式。

2.任意一个无限集合必含有可数子集

这说明了可数集合是基数最小的一种无穷集合，因为任意无穷集合都包含了可数集合。

3.可列集的任意无穷子集是可列集

设A是可列集合，B是A的任意一个无穷子集。由于A可列，它的元素可以排成s={$a_0,a_1,a_2,…,a_n,…$}。从$a_0$开始，一次将不在B中的元素删去，剩下的元素s={$b_0,b_1,b_2,…,b_n,…$}仍然是一个可列集合

4.可数个的可数集的并集是可数集

$S_0$={$a_{00},a_{01},a_{02},…,a_{0n},…$}

$S_1$={$a_{10},a_{11},a_{12},…,a_{1n},…$}

…

$S_k$={$a_{k0},a_{k1},a_{k2},…,a_{kn},…$}

重新排列下标

S={$a_{00},a_{01},a_{10},a_{02},a_{11},a_{20},…$}

规则：按下标之和p=i+j从小到大排列，p相等时按i从小到大排列，删去其中重复的元素，得到的s仍然是可列的

5.开区间(0,1)不可列

6.实数集R也是不可列的，因为(0,1)不可列。

康托尔定理

设M是一个集合，P(M)是集合M的幂集，则|M|＜|P(M)|

这个定理的意思是没有最大的集合，只有更大的集合

那如何构造出一个更大的集合呢？

我们只需要构造出一个幂集，因为一个集合的幂集的基数大于等于该集合的基数

5.1.1图论

图论是以图为研究对象。图论中的图是由若干给定的结点及连接结点的边所构成的图形，用来描述某些事物之间的某种特定关系，结点代表事物，连接两个结点的边表示相应两个事物间具有这种关系

图论研究图的结点和边的关系及特性，是研究离散结构及其特性的重要方法

5.2.1图的基本概念

图论中的图由节点和连接节点的边的边组成，分为无向图和有向图。一般用G=(V,E)表示无向图，用D=(V,E)表示有向图。

无向图

在无向图中，如果一个结点是一条边的端点，则称这个结点和这条边关联；如果有边关联于一对结点，则称这对结点是邻接的；若两条边有公共端点，则称这两条边是相邻的

如果一条边的两个端点关联于同一个结点，则称为环，若点和任何边都不关联，则称为孤立点。如果关联一对结点的边多于一条，则称这些边为多重边或平行边

如图，e$_5$是环，v$_4$孤立点，e$_2$和e$_3$是平行边

有向图

在有向图中，如果两个结点间有一条有向边，则称这两个结点是邻接的；如果一条边的重点是另一条边的起点，则称这两条边是邻接的；如果关联一对结点的方向相同的有向边多于一条，则称这些有向边为多重有向边或平行边

e$_1$和e$_2$是平行边，e$_3$和e$_4$因为方向相反，所以不是平行边

阶

图G=(V,E)，称|V|为图的阶

n阶图：n个结点的图

零图：E=$\varnothing$的图【即使没有边的图】

平凡图：1阶零图

空图：结点集为空集的图，记为$\varnothing$

度

设G=<V,E>为无向图，v∈V，称所有边和v关联的次数之和为v的度数，简称度，记作d(v)

悬挂结点：度数为1的顶点

悬挂边：与悬挂结点关联的边

G的最大度：图中结点的最大值叫做最大度

G的最小度：图中结点的最小值叫做最小度

定义：设D=<V,E>为有向图，v∈V，称所有边的起点和v关联的次数之和为v的出度，记作$d^+$(v);称所有边的终点和v关联的次数之和为v的入读，记作$d^-$(v)

总度数：d(v)=$d^+$(v)+$d^-$(v)

例如：上图中a结点的入度是1，出度是4，所以总度数为5【注意，a是成环的，所以a出一次也入一次，所以入度1出度4】

定理

1.不管是有向图还是无向图，G中所有结点的度数之和等于边数的两倍。

推论：任何图中，度数为奇数的结点的个数为偶数

2.在有向图中，所有结点的入度之和与所有结点的出度之和相等，都等于有向边数。

度数列

把图的所有结点的度数排称一个数列，称为结点的度数列。有向图的所有结点的入度排成一个数列，称为入度列，所有结点的出度排成一个数列，称为出度列

5.2.2图的分类

图分为有向图和无向图，根据图是否有环或者平行边，又可以分成简单图和多重图

简单图和多重图

图中不含平行边不含环，就称为简单图

若图中含有平行边，则称图为多重图

无向完全图

一个无向图，如果有n个结点，每个结点跟其余n-1个结点有边，则称为n阶无向完全图。记作$K_n$(n≥1)

n阶无向完全图的边数m=n(n-1)/2

最大度和最小度=n-1

有向完全图

任意两个结点u和v既有边(u,v),又有边(v,u)，则称该图为n阶有向完全图

n阶有向完全图的出度和入度以及最大出度、最小出度、最小入度和最小出度都是n-1

每个结点的度为2（n-1）

n阶有向完全图的边数m=n(n-1)

定理

1.设G为任意n阶无向简单图，则$\Delta$(G)≤n-1

正则图

设G为n阶无向简单图，若$\forall$x∈V，均有d(v)=k，则称G为k-正则图

n阶k-正则图的边数m=nk/2

当k=0时，0-正则图就是n阶零图

环图

当结点数≥3时，用边将所有结点连成环的图叫环图，记作$C_n$

n阶环图的结点最大度数和最小度数都为2

边数m=n

轮图

给环图添加一个结点，并把这个结点和环图里每个结点逐个连接后的图叫轮图，记作$W_n$

轮图的结点数为n+1

结点最大度是n，最小度是3，所有度数和为n+3n=4n

边数m=2n

方体图

如果图有2$^n$个结点，每个结点表示一个长度为n的位串(01比特位串)，任何两个相邻的结点表示的位串只有一位不同，则称该图为n方体图，记作$Q_n$

结点数：2$^n$

最大度和最小度位n

边数：m=n2$^{n-1}$

对任意n∈N，$Q_n$是将两个$Q_{n-1}$图的对应结点连接起来的简单图

二分图

如果图的结点集V能划分为两个子集：$V_1$和$V_2$，使每条边有一个端点在$V_1$中，另一个端点在$V_2$中，则称该图为二分图（或二部图）

若二分图G的结点集V能划分为两个子集：$V_1$和$V_2$，若$V_1$中的每个结点和$V_2$中的每个结点均有边相连，则称G为完全二分图。若|$V_1$|=m,|$V_2$|=n，则可记为$K_{m,n}$

(左侧为$K_{2,3}$,右则为$K_{3,3}$)

带权图

每个结点或每条边都带有数值的图叫带权图

可以用有序三元组或有序四元组来表示带权图

5.2.3子图和补图

删除运算

图G=(V,E)，若e∈E，从G图中删去边e，称为删除边运算，得到的图表示为G-e;若边子集$E_1$$\subseteq$E，从G图中删去$E_1$的所有边，称为删除边子集运算，得到的图表示为$G-E_1$

设v∈V，从G图中删去结点v及v关联的所有边，称为删除结点运算，得到的图表示为G-v；设$V_1$$\subseteq$V，从G图中删去$V_1$中所有结点及它们关联的所有边，称为删除结点子集运算，得到的图表示为$G-V_1$

收缩

设e=(u,v)∈E，从G中删除边e，将e的两个端点u,v用一个新的结点w代替，将u,v关联的所有边都关联结点w，称为边e的收缩，记为G\e

加新边

设u,v∈V，在u,v之间加一条边(u,v)，称为加新边，表示为$G{\bigcup}(u,v)$(或G+(u,v))

子图和母图

定义：设G=(V,E)和$G_1=(V_1,E_1)$是两个图。若$V_1$$\subseteq$V，且$E_1$$\subseteq$E，则称$G_1$是G的子图，G是$G_1$的母图，记作$G_1$$\subseteq$G

若$G_1$$\subseteq$G且$G_1$≠G(即$V_1$≠V或$E_1$≠E)，则称G$_1$是G的真子图

若$G_1$$\subseteq$G且$V_1=V$,则称$G_1$是G的生成子图

定义：

• 对图G=(V,E)，设$V_1$$\subseteq$V且$V_1$≠$\varnothing$，以$V_1$为结点集，以两端点均在$V_1$中的全体边为边集的G的子图，称$G_1$为G的由结点集$V_1$导出的子图，记为G($V_1$)

• 对图G=(V,E),设$E_1$$\subseteq$E且$E_1$≠$\varnothing$，以$E_1$为边集，以$E_1$中边关联的结点的全体为结点集的G的子图$G_1$,称G的由边集$E_1$导出的子图，记为G($E_1$)

补图

设G=(V,E)是n阶无向简单图或有向简单图。以V为结点集，以所有能使G称为完全图需添加的边组成的集合为边集的图，称为G相对于完全图的补图，简称G的补图，记作

5.2.4图的同构

设两个图$G_1=(V_1,E_1)$和$G_2=(V_2,E_2)$，如果从$V_1$到$V_2$存在双射函数f，使得对于任意的u,v∈$V_1$,(u,v)∈$E_1$,当且仅当(f(u),f(v))∈$E_2$;如果在u，v间存在平行边，则关联于结点u,v的平行边数与关联于结点f(u),f(v)的平行边数相同，则称$G_1$与$G_2$是同构的，记作$G_1{\cong}G_2$

两个图同构的必要条件

1. 具有相同的结点数
2. 具有相同的边数
3. 度数相同的结点数相同
4. 相同长度的回路数相同

例题

如果一个图G和它的补图同构，即$G{\cong}{\backsim}G$，则称此图为自互补图

PS：一个图为自互补图，其对应的完全图的边必为偶数

• 图之间的同构关系构成全体图集合上的二元关系
• 同构关系是等价关系，具有自反性、对称性和传递性
• 同构关系的每个等价类中的图在同构意义下都可以看成一个图

以上三个图，在同构意义下都是同个图

5.3.1通路和回路

定义

给定图G=(V,E),称以$v_0$为起点，$v_n$为终点的由结点和边交替出线的序列$v_0e_1v_1e_2v_2…v_{n-1}e_nv_n$为从结点$v_0$到$v_n$的长度为n的通路。若一条通路的起点和重点是同一点，则称它是一条回路

• 若通路中的所有边互不相同，则称它为简单通路或迹。若回路中的所有边互不相同，则称它为简单回路或闭迹

• 若通路中的所有结点互不相同，所有边互不相同，则称它为基本通路或初级通路、路径
• 若回路中的所有结点互不相同，所有边互不相同，则称它为基本回路

PS：有向图的简单通路和回路跟无向图基本类似，但要注意它的方向

定理

• 在n阶图G中，若从结点u到v(u≠v)存在通路，则从u到v存在长度小于或等于n-1的通路

推论：在n阶图G中，若从结点u到v(u≠v)存在通路，则从u到v存在长度小于或等于n-1的基本通路

• 在n阶图G中，若从结点u到自身存在回路，则一定存在小于或等于n的回路

推论：在n阶图G中，若从结点u到自身存在回路，则一定存在小于或等于n的基本回路

距离

设u,v为无向图G中任意两个结点，u与v之间长度最短的通路（假设u与v之间有通路）的长度，称为u与v之间的巨鹿d(u,v)。若u和v之间不存在通路，则规定d(u,v)=$\infty$

性质

对图G中的任意的结点u,v,w,有：

1. d(u,v)≥0，d(u,v)=0$\Leftrightarrow$u=v
2. d(u,v)=d(v,u)（当G是无向图时）
3. d(u,v)+d(v,w)≥d(u,w)

5.3.2图的连通性

连通图和非连通图

若无向图G时平凡图或其中任意两节点间都有一条通路（长度≥1），则称G为连通图，否则称G是非连通图

• 在无向图G中，若从结点$v_i$到$v_j$存在通路，则称$v_i$和$v_j$有连同关系

连通关系R是对称的，自反的，传递的，所以连通关系R是等价关系

• 连通关系R可将结点集V划分称k（k≥1）个等价类:$V_1,V_2,…,V_k$，它们的导出子图G($V_1$),G($V_2$),…,G($V_k$)称为G的连通分支

定理

设简单图G=(V,E)有n个结点，e条边，w个连通分支，则n-w≤e

点割集和割点

设无向图G=(V,E)，V’$\subset$V,若W(G-V’)＞W(G)且$\forall$V’’$\subset$V‘,W(G-V’’)=W(G)，则称V’为G的点割集，若{v}为点割集，则称v为割点

简单的说，点割集就是一个图要删除n个点，它才会成为非连通图，若少删一个都不行，这些点就叫点割集。若只有一个点，则叫割点。

边割集

设E’$\subseteq$E,若W(G-E’)＞W(G)且$\forall$E’’$\subset$E‘,W(G-E’’)=W(G)，则称E’为G的边割集，若{e}为边割集，则称e为割边或桥

简单地说就是一个图删除n条边就可以多一个连通图，少删一条都不行，这些边就是边割集。若只有一条，则叫割边或桥

定义

设图G是无向连通图且不是完全图，为产生一个不连通图，需要从G中删去的最少结点数成为G的点连通度，记为k(G)，简称为G的连通度。规定完全图$K_n$(n≥1)的点连通度为n-1，非连通图的点连通度为0

设图G是无向连通图，为产生一个不连通图，需要从G中删去的最少边数成为G的边连通度，记为${\lambda}(G)$。规定非连通图的边连通度为0

定理

对任何无向图G，有点连通度≤边连通度≤图的最小度

若G的点连通度为k(G)，k是非负整数且K≤k(G)，则称G是K-连通图

若G的边连通度为${\lambda}(G)$，r是非负整数且r≤${\lambda}(G)$，则称G是r边-连通图

若G是k-连通图(k≥1)，则在G中删除任何k-1个结点后，所得图一定还是连通的。

若G是r边-连通图(r≥1)，则在G中删除任何r-1条边后，所得图一定还是连通的

相互可达

设G=(V,E)是一个有向图，对G中任意两个结点u和v，若从u到v存在通路，则称由u到v是可达的，否则称由u到v是不可达的。若从u到v存在通路，且从v到u存在通路，则称u和v是相互可达的。

规定一个结点到子集总是可达的。

有向图的结点之间的可达关系具有自反性和传递性，不具备对称性

单向连通和强连通

设G=(V,E)是有向图

• 如果图G的任意两个结点间至少从一个结点到另一个结点是可达的，则称G是单向连通的。
• 如果图G的任意两个结点间是相互可达的，则称G是强连通的。
• 图G在略去有向边的方向后得到的无向图是连通的，则称G是弱连通的。

有向图的强连通分支

• 利用相互可达关系R可将结点集V划分为$V_1,V_2,…,V_w$，$V_i$中的任两个结点都是相互可达的。
• 每个$V_i$ 导出的子图$G_i$是强连通的，称为G的一个强分图

定理

有向图G是强连通的当且仅当G中存在经过每个结点的回路

有向图G是单向连通的当且仅当G中存在经过每个结点的通路

5.4.1图的表示

图的表示有多种，如邻接矩阵、邻接表、集合、直接画图等

邻接表

列出图的每一个结点和它的所有邻接结点的表称为邻接表。用邻接表可以表示不带多重边的图

有向图的邻接矩阵

设图G=(V,E)是有向图，V={$v_1,v_2,…,v_n$}，G的邻接矩阵为A(G)=($a_{ij}^{(1)}$)${n{\times}n}$,$a{ij}^{(1)}$是以$v_i$为起点、$v_j$为终点的边的条数

性质

1. 邻接矩阵的每一行的元素之和是该行对应结点的出度数
2. 邻接矩阵的每一列的元素之和是该列对应结点的入度数
3. 邻接矩阵的所有元素之和是该图的总边数
4. 孤立店对应的行和列元素全为0
5. 主对角线的元素之和是图中的环的数目

定理

设A是有向图G=(V,E)的邻接矩阵，V={$v_1,v_2,…,v_n$},$A^k=(a_{ij}^{(k)}){n{\times}n}$，则 $a{ij}^{(k)}$表示G中从$v_i$到$v_j$的长度为k的所有有向路的数目，其中$a_{ij}^{(k)}$是从$v_i$到自身的长度为k的所有回路的数目

推论

设矩阵$B_l$=$A+A^2+…+A^;$

则$B_l$中的元素$b_{ij}^{(l)}=a_{ij}^{(1)}+a_{ij}^{(2)}+…+a_{ij}^{(l)}={\sum}{k=1}^la{ij}^{(k)}$

$b_{ij}^{(l)}$表示图G中从结点$v_i$到$v_j$的长度小于等于l的所有通路的总数。其中$b_{ij}^{(l)}$是从$v_i$到自身的长度小于等于l的所有回路的总数目

例题

无向图的邻接矩阵

跟有向图差不多，只是有向图中无法到达的边给的数目是∞，而无向图则是0

性质

• 无向图的邻接矩阵是关于主对角线对称的矩阵
• 主对角线的元素不为0表示对应的结点有环
• 第i行对应的结点$v_j$没有环时，该行的所有元素之和时结点$v_j$的度数
• 无向图的邻接矩阵A的k次幂$A^k$的元素$a_{ij}^{(k)}$等于从结点$v_i$到$v_j$的长度为k的所有通路的数目。

例题

判断是否可达，直接算$B_n=(b_{ij})_{n{\times}n}=A+A^2+…+A^n$

矩阵元素$v_{ij}$不为0时，则存在结点i到结点j可达，其中可达矩阵中的$p_{ij}$为1。若为0，则说明不存在通路，即不可达

例题

【$B_3$中不为零的元素在P中为1，P中的主对角线为1】

有向图的关联矩阵

设图G=(V,E)是无环的有向图，V={$v_1,v_2,…,v_n$},E={$e_1,e_2,…,e_m$}

$m_{ij}=\begin{cases}1,,,v_i为e_j的起点\0,,,v_i和e_j不关联\-1,,,v_i为e_j的终点\\end{cases}$

则称$(m_{ij})_{n{\times}m}$为G的关联矩阵，记为M(G)

性质

• 每列中只有一个“1”和一个“-1”
• 每行元素中“1”的个数为对应结点的出度，“-1”的个数为对应结点的入度
• 孤立点对应的行全为0
• 多重边对应的列相同

无向图的关联矩阵

设G为无向图，V={$v_1,v_2,…,v_n$},E={$e_1,e_2,…,e_m$}，则G的关联矩阵$M(G)=(m_{ij}){n{\times}m}$，其中$m{ij}$是$v_i$与边$e_j$的关联次数

性质

• 每行所有元素之和为该行对应结点的度数
• 每列的元素之和为2
• 孤立点对应的行全为0
• 多重边对应的列相同
• 同一个图当结点或边的边序不同时，其对应的M(G)有行序、列序的差别

例题

6.1.1欧拉图

设G=(V,E)时无向图或有向图，若G中一条包含所有边（有向边）的简单回路，称该回路为欧拉回路，称图G为欧拉图。若G中有一条包含G中所有边（有向边）的简单通路，称它为欧拉通路，称图G为半欧拉图。规定平凡图时欧拉图

简单地说，欧拉图就是有一条回路包含所有边。而半欧拉图就是有一条简单通路包含了所有边。

判断

定理1：无向连通图G是欧拉图，当且仅当G的所有结点的度数都是偶数

定理2：连通无向图G是半欧拉图，当且仅当G中只有两个奇度数的结点，其余结点的度数都是偶数

例题

欧拉有向图

如果连通有向图G中有一条包含G中所有有向边的有向回路，称它为欧拉有向回路，称图G为欧拉有向图

如果连通有向图G中有一条包含G中所有有向边的有向通路，称它为欧拉有向通路，称图G为半欧拉有向图

判断

定理3：连通有向图G是欧拉图，当且仅当G中每个结点v的入度等于它的出度

定理4：连通有向图G是半欧拉图，当且仅当G中有且仅有两个奇度数结点，其中一个结点的入度比出度大1，另一个结点的入度比出度小1.其余结点的出度和入度相等

定理5：图G是非平凡的欧拉图当且仅当G是连通的且是若干个边不重的回路的并

能够一笔画完的图，就是欧拉图或半欧拉图

6.2.1哈密顿图

设图G=(V,E)是无向图或有向图。若G中有一条包含G的素有结点（仅一次）的回路，称该回路为哈密顿回路，称图G为哈密顿图。若图G有一条包含G的所有结点的通路，称该通路为哈密顿通路，称图G为半哈密顿图。规定平凡图是哈密顿图

PS：哈密顿图是经过途中每个结点，而欧拉图是经过途中每一条边

判断

前提：目前还没有充分必要条件，只有充分条件或必要条件

定理1：设无向图G=(V,E)是哈密顿图，则对于结点集V的每一个真子集S均有：W(G-S)≤|S|,其中，W(G-S)是G-S的导出子图的连通分支数（必要条件）

定理2：如果G是有n个结点的简单无向图，对于每一对不邻接结点u和v，满足d(u)+d(v)≥n-1，那么G中存在哈密顿通路，图G是半哈密顿图。（充分条件）

推论1：如果图G是有n个结点的简单无向图，对于每一对不邻接结点u和v，满足d(u)+d(v)≥n，那么G中存在哈密顿回路，图G是哈密顿图

推论2：如果G是有n个结点的简单无向图，G中每个结点的度数都至少为n/2，那么图G是哈密顿图

6.3.1最短路劲问题

• 无向简单连通图的边或结点带有信息的图称为带权图
• 在一个无向简单连通边带权图G=(V,E,W)中，从u到v的一条通路中包含的各条边的权值之和称为这条通路的长度
• 从u到v的所有通路中长度最短的通路称为u到v的最短路径
• 求给定两结点之间的长度最短的通路问题称为最短路径问题

Dijkstra算法

Dijkstra算法是求最短路径算法，用于计算权值非负的图的一个姐弟啊拿到其他所有结点的最短路径

思想

1. 将图G的结点集合V分成两组，第一组是已求出最短路径的结点集合S，第二组为其他未确定最短路劲的结点集合T
2. 最初S中只有一个源结点，按最短路径长度的递增次序依次把集合T的结点加入集合S中
3. 每个结点对应一个距离，s中的结点的距离就是从u到此结点的最短路径长度；T中的结点的距离，是从u到此结点只包含S中的结点为中间结点的当前最短路径长度

实际上就是从源点开始，把源点附近的点加入到S，修改距离，然后再以这个点为新的源点，把它周围的点加入S并修改距离，依次类推。（所以S和T实际上就是一个矩阵，在算法实现上则是使用数组来存放距离）

Floyd算法

与Dijkstra算法类似

1. 从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大

2. 对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。

   把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则$G[i][j]=d$，d表示该路的长度；否则$G[i][j]=\infty$。定义一个矩阵D用来记录所插入点的信息，$D[i][j]$表示从Vi到Vj需要经过的点，初始化$D[i][j]=j$。把各个顶点插入图中，比较插点后的距离与原来的距离，$G[i][j] = min( G[i][j], G[i][k]+G[k][j] )$，如果$G[i][j]$的值变小，则$D[i][j]=k$。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。

比如：要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连

6.4.1中国邮路问题

一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局。如果它必须至少一次走过他负责范围内的每条街道，如何选择投递路线，邮递员可以走尽可能少的路程？这个就是中国邮路问题

简单翻译一下就是：在有奇度数结点的连通带权图中，在包含G中每条边至少一次的回路中找到一条总权值最小的回路

定理

1.设G(V,E,W)为一个连通的带权图，自使附加边子集$E_1$的权值$W(E_1)$为最小的充分必要条件是$G+E_1$中任意边至多重复一次，且$G+E_1$中的任意回路中重复边的权值之和不大于该回路总权值的一半

解决方法

1. 先找出奇结点
2. 对奇结点进行配对，找到每对结点间的最短通路，给每条通路所含的边加一条平行边
3. 当某条边添加的平行边大于等于2条时，将添加的平行边删除
4. 检查每一条回路，若一条回路中重复边的权值和大于该回路权值的一半，把该回路的重复边删去，每没有平行边的边上加上平行边
5. 若没有任何回路的重复边的权值之和大于该回路权值的一半，图中的任意一条欧拉回路就是最优邮路

6.5.1二分图

匹配

定义1：在图G(V,E)中，若M$\subseteq$E，且M中任意两条边都不相邻，称M为G的一个匹配

若在M中再加入任意其他的边e，M$\bigcup${e}有相邻的边，则称M为G的极大匹配。若G中不存在匹配$M_1$，使得$|M_1|＞|M|$，则称M为G的最大匹配

定义2：若M是G的一个匹配，M的边和结点v关联，则称v为M饱和点，否则称v为M非饱和点。若$G=(V,E)$的每个结点都是M饱和点，则称M为G的一个完美匹配

定义3：若M是G=(V,E)的一个匹配，从G中的一个结点到另一个结点存在一条由属于M的边和不属于M的边交替出线组成的简单路，称这条简单路为M交错路。若M交错路的两端点为M非饱和点时，称这条M交错路是M可扩充路

定理1：M是图G=(V,E)的最大匹配的充分必要条件是图G中不存在M可扩充路

定义4：如果图G=(V,E)的结点集V能划分称两个子集$V_1$和$V_2$，使得G中任何一条边的两个端点一个属于$V_1$，另一个属于$V_2$，称G为二分（部）图，$V_1$和$V_2$称为互补结点集，二分图通常记为$G=(V_1,V_2,E)$

定义5：若$V_1$中每一结点与$V_2$中每一个结点均有且仅有一条边相关联，则称二分图G为完全二分图。若$|V_1|=m$，$|V_2|=n$，则记完全二分图G为$K_{m,n}$

判断

如何判断一个图是不是二分图，主要用以下定理

定理2：一个无向简单图G=(V,E)是二分图，当且仅当G中无奇数长度的回路

例题

PS：图二回路为0

完美匹配和完备匹配

设G=(V,E)是二分图，$V_1$和$V_2$是G的互补结点集，若G的一个匹配M使得$|M|$=min{$|V_1|$,$|V_2|$}，称匹配M是G的完备匹配。这时，若$|V_1|≤|V_2|$，称M是从$V_1$到$V_2$的一个完备匹配如果$|V_1|=|V_2|$，称M是G的完美匹配

简单地说就是上面的结点数跟下面的结点数一样就是完美匹配，如果有一个多了或者少了，就是完备匹配

判断

(Hall定理)设二分图G=(V,E)，$V_1$和$V_2$是G的互补结点集，存在从$V_1$到$V_2$的完备匹配，当且仅当对于$V_1$中的任意k各结点（k=1，2，3，….，$|V_1|$)至少邻接$V_2$的k各结点

充分条件

设G=(V,E)是二分图，$V_1$和$V_2$是G的互补结点集。若存在正整数t，使

1. $V_1$中的每个结点至少关联t条边
2. $V_2$中的每个结点之多关联t条边

则图G中存在从$V_1$到$V_2$的完备匹配

PS：该定理的条件常称为t条件，是判断呢如粪土是否存在完备匹配的充分条件，不是必要条件

例题

6.6.1平面图

设G=(V,E)是一个无向图，如果能把G画在平面上，使得除结点处外，任意两条边都不相交，称图G为平面图

如果能把图G画在平面上，使得除结点外，边喝边都不相交，称图G是可平面图

将一个平面图G，画成除结点处外，任意两条边都不相交的和它同构的图，称这样的图为图G的平面嵌入

若非平面图G任意删除一条边后，所得之图都是平面图，则称G为极小非平面图

设G为简单平面图，若在G的任意不相邻的结点u、v之间加边(u,v)后，所的图是非平面图，则称G是极大平面图

设G是一个平面嵌入，G的边将G所在的平面划分成若干个区域，每个区域称为G的一个面。面积无限的区域称为无限面或外部面，记为$f_0$，面积有限的区域称为有限面或内部面，记为$f_1,f_2,…,f_k$

包围每个面的所有边所构成的回路称为该面的边界。一个面的边界包含的边数称为该面的次数，记为$deg(f)$

定理

1:一个连通平面图G的边数为m，G的边将G所在的平面划分成f个面，所有面的次数之和等于边数m的2倍，即

$\sum{_{i=0}^f}deg(f_i)=2m$

2:设图G是任意的连通平面图，G中有n个结点，m条边，f个面，则有公式n-m+f=2成立。该公式称为欧拉公式

例题

推论

1：设G是由n(n≥3)个结点，m条边，f个面的简单连通平面图，边数m≤3n-6

2：设G是由n(n≥3)个结点，m跳变，f个面的简单连通平面图，若每个面由4条或4条以上的边围成，则m≤2n-4

3:$K_5$和$K_{3,3}$都不是平面图

欧拉公式的推广

设为任意的平面图，G有k个连通分支，n个结点，m条边，f个面，则有公式$n-m+f=k+1$成立

设m=(u,v)是图G的一条边，在G中删去边m，增加新的结点w，使u,v均与w相邻，则称在图G中插入2度结点w

设w为G的一个度数为2的结点，w与u,v相邻，删去w及与w相关联的边(w,u),(w,v)，同时增加新边(u,v)，则称在图G中删去2度结点w

若两个图$G_1$和$G_2$同构或通过反复插入或删除2度结点后是同构的，则称$G_1$和$G_2$是同胚的

库拉托斯基定理

设G是无向图，则G是平面图的充分必要条件是图G不含和$K_5$或$K_{3,3}$同胚的子图

推论：设G是无向图，则G是平面图的充分必要条件是图G没有可收缩为$K_5$或$K_{3,3}$的子图

例题

6.6.2对偶图与图的着色

设G是平面图。在图G的每个面中指定一个新结点，对两个面公共的边，指定一条新边与其相交。由这些新结点和新边组成的图称为G的对偶图$G^*$

性质

1. 对偶图是平面图，而且是平面嵌入
2. 对偶图是连通图
3. G中的环对应对偶图$G^*$的桥，G中的桥对应对偶图的环
4. 多数情况下，对偶图为多重图
5. 同构的平面图（平面嵌入）的对偶图不一定是同构的

点着色

对一个简单图G进行结点着色，是指给它的每个结点指定一种颜色使得相邻结点都有不同的颜色。若采用了k中颜色给G的结点着色，称图G是k-可着色的

给图G的结点着色所用的最少的颜色数，称为图G的色数。最少用了k钟颜色，则称G是k色图。

定理

对于任意的无环图G，G的色数为k，则$k≤{\Delta}(G)+1$,${\Delta}(G)$是G的结点最大度数。

Brooks定理

对于无环图G，G的色数为k，若G不是完全图，也不是长度为奇数的基本回路，则$k≤{\Delta}(G)$

图着色

地图：连通无桥平面图的平面嵌入及其所有的面称为地图

国家：平面地图中的面

相邻：若两个面的边界至少有一条公共边，称这两个面是相邻的

地图的着色：是指给它的每个面指定一种颜色，使得相邻的面有不同的颜色

对平面图G的各个面着色与其对偶图$G^*$的结点着色相对应。

当且仅当对偶图$G^*$的结点时n-可着色时，平面图G才是n-面可着色的。

平面图的色数就是给平面地图着色，使得没有两个相邻的面的颜色相同所需要的最少的颜色数。

四色定理

对一个平面图的各个面进行着色，使得相邻的面有不同的颜色，所用的颜色可以不多于4色

对于无环图G的每条边指定一种颜色，使得相邻的边有不同的颜色，称为对图G的边着色。若能用k中颜色给图G的边着色，称图G是k-可边着色的。若对G的边着色用的最少颜色数为k，则称G的边色数为k

定理

设G是简单图，G的边色数是结点度数最大值${\Delta}(G)$或${\Delta}(G)+1$

设G是二分图，G的边色数位结点度数最大值${\Delta}(G)$

7.1.1树的定义

一个连通且无回路的无向图称为无向树。树中的边称为树枝。度数为1的结点称为树叶。度数大于1的结点称为分支点（内点）。平凡图称为平凡树

一个不连通的，但每个连通分支都是无向树的图称为森林

定理1：对于有n个结点，e条边的无向树T，下列的命题等价

1. T是无回路的连通图
2. T是连通的单删去任一边后，便不连通
3. T是连通的，且e=n-1
4. T中无回路且e=n-1
5. 在T的每一对结点之间有唯一的一条简单路
6. T中无回路，但在任意两个结点间增加一条边，得到一条且仅一条回路

定理2：设T是n阶非平凡的无向树，则T中至少有两片树叶

例题

【其中1+3+x是结点数，（1+3+x-1是边数）】（两倍的边数=总结点度数）

给定连通图G，如果它的生成子图$T_G$是树，则$T_G$为G的生成树。生成树$T_G$中的边称为树枝；G中的不再生成树$T_G$中的边称为弦；生成树$T_G$的所有弦的集合称为生成树$T_G$的余树。

图的生成树一般不是唯一的，只有图是一棵树的时候才是唯一

定理：图G有生成树，当且仅当G是连通的

最小生成树

设G是无向连通边带全图=(V,E,W)，T是G的一棵生成树，T个边带权之和称为T的权，G的所有生成树中带权最小的生成树称为最小生成树。

最小生成树一般有两种方法，一种是Kruskal算法（基于避圈法思想），另一种是prim算法

Kruskal算法

1. 在边集E中选一条具有最小权值的边e，加入生成树T中，并将e从边集E中删去
2. 在边集E中选一条具有最小权值的边e，若e和已在T中的边不构成回路，将e添加到T中，并从边集E中删去e；若e和已在T中的边构成回路，从边集E中删去e
3. 若T中的边数为n-1，算法结束，否则返回2.算法结束时，T就时G的最小生成树

【先选一条最小的边加入最小生成树，然后从剩下的边中找最小的边加入，该边不能成环，也不能跟最小生成树里的边形成回路，以此类推】

Prim算法

跟Kruskal很类似，只是Kruskal是从所有边中选最小的，而Prim是从这条边中选最小的。

1. 在一个加权连通图中，顶点集合V，边集合为E
2. 任意选出一个点作为初始顶点,标记为visit,计算所有与之相连接的点的距离，选择距离最短的，标记visit.
3. 重复以下操作，直到所有点都被标记为visit：在剩下的点钟，计算与已标记visit点距离最小的点，标记visit,证明加入了最小生成树。

7.2.1根树

一个有向图G，如果略去有向边的方向所得无向图为一棵无向树，则称G为有向树。

有向根树

一棵平凡的有向树，如果有一个结点的入度为0，其余结点入度均为1，则称此有向树为有向根树。称入度为0的结点为树根，称出度不为0的结点（含根）为分支点（内点），称出度为0的结点为树叶

在根树中，从树根到任意结点$v_i$只有唯一的一条简单路，这条路的长度称为$v_i$的级（层）数。级数最大的结点的级数称为树的高度

画根树时，根结点画在上方，其他分支点和叶结点画在下面，可以省去有向边的方向。

在根树T中

1. 若结点$v_i$到结点$v_j$可达，则称$v_i$时$v_j$的祖先，$v_j$是$v_i$的后代
2. 若结点$v_i$邻接到结点$v_j$，则称$v_i$是$v_j$的父亲，$v_j$是$v_i$的儿子
3. 若两个结点同为一个结点的儿子，则称这两个结点为兄弟

根子树

设T为一棵根树，$v_i$为T中一个结点，且$v_i$不是树根，称$v_i$及其后代的导出子图为T的以$v_i$为根的子树，简称根子树

m元树

在根树中，如果每个结点的出度小于或等于m，则称这棵树为m元树。m=2时称为二元树或二叉树。如果每个分支点的出度都等于m，则称这棵树为m元正则树。所有树叶级（层）数相同的m元正则树称为完全m元正则树。

定理1：有i个分支点的m元正则树有n=mi+1个结点

定理2：一个m元正则树T

1. 若T有n个结点，则有i=(n-1)/m个分支点和l=[(m-1)n+1]/m片叶子
2. 若T有i个分支点，则有n=mi+1个结点和l=(m-1)i+1片树叶
3. 若T有l片树叶，则有n=(ml-1)/(m-1)个结点和i=(l-1)/(m-1)个分支点

定理3：在高度为h的m元树立之多有$m^h$片树叶

有序根树

如果将根树每一层上的结点都规定次序，这样的根树称为有序根树。在有序根树中，每一层上的结点按从左到右的次序排序。如一个分支点有两个子结点，则从做到右称这两个子结点为左儿子和右儿子【一般我们都叫左孩子和右孩子，这里的左儿子和右儿子听得我很难受】。以这两个子结点为根所产生的根子树分别称为左子树和右子树。

有序根树的遍历

系统地访问有序根树地每个结点，使得每个结点恰好访问一次，进行数据存取地过程称为有序根树遍历算法。一般有三种遍历2元有序根树的算法：

先序遍历、中序遍历、后序遍历

先序遍历（这里也叫前序遍历算法）

先访问根结点，然后再访问左子树，最后访问右子树

1
2
3
4
5
6

//伪代码
void abc(tree *T){
visit(T->data);
abc(T->lchild);
abc(T->rchild);
}

中序遍历

先左后根最后右

1
2
3
4
5
6
7

//伪代码
void abc(tree *T){
abc(T->lchild);
visit(T->data);
abc(T->rchild);

}

后序遍历

先左后右最后根

1
2
3
4
5
6

//伪代码
void abc(tree *T){
abc(T->lchild);
abc(T->rchild);
visit(T->data);
}

例题

可以用二元有序根树来表达各种类型的表达式：

【运算符放在根上，变量放在树叶上】

例题

PS：中序遍历结果存在二义性，因为不同的元素去掉括号后可能是相同的

如：$(x-y)(2+z)$和$x-(y(2+z))$去掉括号后都是$x-y*2+z$

所以为了让这样的表达式无歧义，按中序遍历算法得到的表达式要包含括号，括号中的表达式是子树的表达式

7.3.1根树的应用

前缀码

前缀：设${\beta}=a_1a_2a_3…a_n$为长度为n的符号串，称$a_1,a_1a_2,a_1a_2a_3…a_{n-1}$分别为符号串$\beta$的长度为1,2,…,n-1的前缀

前缀码：设$B={\beta_1},{\beta_2},…,{\beta_m}$是一个字符串集合，若对任意的${\beta_i},{\beta_j}∈B$，i≠j，${\beta_i},{\beta_j}$互不为前缀，称B为前缀码；

二元前缀码：若${\beta_i}(i=1,2,…,m)$中只有0，1两个 符号，称B为二元前缀码

例如：{0，10，110，111}，{11，00，010，011}都是二元前缀码，而{1，01，010，110}不是前缀码

定理1：任何一棵二元树的树叶可对应一个前缀码

定理2：任何一个前缀码都对应一棵二元树

例题

定义2：给定一组权$w_1,w_2,…,w_n$，如果2元树T有n片树叶$v_1,v_2,…,v_n$树叶的权分别为$w_1,w_2,…,w_n$，称2元树T为带权$w_1,w_2,…,w_n$的二元树。称$W(T)={\sum}_i=1^nw_il(v_i)$为T的权，其中$l(v_i)$是$v_i$的层数。在所有带权为$w_1,w_2,…,w_t$的2元树中,称权最小的2元树为最优2元树。（实际上就是哈夫曼树）

哈夫曼（Huffman）算法

1. 画t个结点作为树叶，对应给定的t个权值。
2. 然后将这些结点中权值最小的两个放在一起，组成一棵树，这两个结点为左右孩子结点，根结点为他们加起来的权值。
3. 然后对树的权值和其他结点进行比较，把最小的两个作为子结点组成一棵新树，根结点为他们的总权值
4. 重复步骤3，直到所有结点均组成一棵树

例题

最优二元树也是带权路径长度最小的二元树

通过最优二元树（哈夫曼树）构造的编码称为哈夫曼编码。哈夫曼编码一般用于数据压缩

最佳前缀码：当要传输按一定比例出现的符号组成的符号串时，用最少的二进制数字传输它们的前缀码，称为最佳前缀码

哈夫曼编码是最佳前缀码

例题

解：以频率乘以100作为权值：

$w_1=5,w_2=5,w_3=6,w_4=10,w_5=10,w_6=14,w_7=20,w_8=30$

通过这些权值，可以得到一棵哈夫曼树，从而得到最佳前缀码

所以传输10000个按上述比例出现的八进制数字需要27600个二进制数字，而用等长的（长为3）的编码传输则需要30000个二进制数字

ps：最佳前缀码不唯一，因为给定权值的最优二元树不唯一。产生最优二元树时，每一步选择两个最小的权的选法可能不唯一，两个权对应结点所方的左右位置可以不同，画出的最优二元树可能不同

决策树

在根树中，每个分支点都对应一个决策，分支点的子树对应该决策的每种可能结果，称这样的根树为决策树

如下图是排序3个不同树的决策树，表示对3个不同数排序的比较判断过程

8

代数系统

代数系统是离散对象模型及其运算的共同特征和共同结构的抽象。集合是离散对象的一般模型，所以，代数系统就是具有特殊性质的集合及其运算的抽象。代数系统又称为代数结构

幂等元

在某集合 E 中定义了一个运算*，如果 E 中的元 a 满足a*a = a,则称 a 为 E 的幂等元

幺元

幺元也称作单位元、幺元，是集合里面一种特殊的元

当它和其他元素结合时，并不会改变那些元素

例子

若a*e=a，那么e称为右幺元

若e*a=a，那么e称为左幺元

若a*e=e*a=a，则称e为幺元

逆元

设*是Z中的二元运算，且Z中包含幺元e，令x∈Z

若存在$x_l$∈Z，能使$x_l$*x=e，则称$x_l$是x的左逆元，并且称x是左可逆的

若存在$x_r$∈Z，能使x*$x_r$=e，则称$x_r$是x的右逆元，并且称x是右可逆的

若元素x既是左可逆的，又是右可逆的，则称x是可逆的，且x的逆元用$x^{-1}$表示

零元

设*是对集合Z中的二元运算,e∈Z

若e*x=e,则称e为Z中对于*的左零元

若x*e=e，则称e为Z中对于*的右零元

PS：零元不存在逆元

同代

两个看起来相似不同的代数系统，往往具有共同的性质，或进一步还会有相同的结构，只是这两个代数系统里面的符号和名称不同而已。

如：

（该图来源于古天龙老师的《离散数学》一书第六章）

仔细一看可以发现，这两个代数系统，在本质上是一致的，只不过是用了不同的符号而已。

所以我们有一个定义

对于代数系统<S,$\ast$>和<T,$\circ$>。如果存在S到T的双射函数$f:S{\rightarrow}T$，使得对S中任何元素a和b满足$f(a{\ast}b)=f(a){\circ}f(b)$，则称函数$f$是代数系统<S,$\ast$>到<T,$\circ$>的同构映射，代数系统<T,$\circ$>是代数系统<S,$\ast$>的同构代数系统，或称代数系统<S,$\ast$>同构于代数系统<T,$\circ$>，代数系统<S,$\ast$>与代数系统<T,$\circ$>同构

PS:一般做题都是弄出f(x#y)=f(x)#f(y)

定理

1.代数系统的同构关系是等价关系

同态代数系统

两个不同的代数系统，不一定有完全相同的性质，但可能存在一些共同的性质。这类相互联系的代数系统用下属同态的概念来刻画。

定义：对于代数系统<S,$\ast$>和<T,$\circ$>，如果存在S到T的函数$f:S{\rightarrow}T$，使得对S中任何元素a和b满足$f(a{\ast}b)=f(a){\circ}f(b)$,则称函数$f$是代数系统<S,$\ast$>到<T,$\circ$>的同态映射，称代数系统<T,$\circ$>是代数系统<S,$\ast$>的同态代数系统，$f(S)$是同态像，或称代数系统<S,$\ast$>同态于代数系统<T,$\circ$>，代数系统<S,$\ast$>与代数系统<T,$\circ$>同态。如果同态映射$f$为单射函数，则称$f$为单一同态映射；如果同态映射$f$为满射函数，则称$f$为满同态映射;如果同态映射$f$为双射函数，则称$f$为同构映射。

自同态

对于代数系统<A,$\ast$>，如果存在<A,$\ast$>到<A,$\ast$>的同态映射$f$，则称函数$f$是代数系统<A,$\ast$>的自同态映射，称代数系统<A,$\ast$>是代数系统<A,$\ast$>的自同态代数系统或称代数系统<A,$\ast$>自同态

例子

构造代数系统$<N_5,{\bigoplus}_6>$的一个自同态映射

$f(x)=\begin{cases}0,,,x为偶数\3,,,x为奇数\\end{cases}$

定理

1. 如果运算”$\ast$”是可交换的、可结合的，则运算“$\circ$”在$f(S){\subseteq}T$中是可交换的、可结合的
2. 如果代数系统<S,$\ast$>中存在关于运算”$\ast$”的单位元e和零元θ，则$f(e)$和$f(θ)$分别是<$f(S)$,$\circ$>中关于运算$\circ$的单位元和零元
3. 对于$\forall$x∈S，如果$x^{-1}$是x的关于运算”$\ast$”的逆元，则$f(x^{-1})$是<$f(S)$,$\circ$>中$f(x)$关于运算”$\circ$”的逆元。
4. 如果代数系统<S,$\ast$>中存在关于运算“$\ast$”的等幂元a，则$f(a)$是<$f(S)$,$\circ$>中关于运算“$\circ$”的等幂元
5. 如果代数系统<S,$\ast$>中存在关于运算“$\ast$”的（左、右）可消去元a，则$f(a)$是<$f(S)$,$\circ$>中关于运算“$\circ$”的（左、右）可消去元

从这个定理可以看出如果代数系统<S,$\ast$>和<T,$\circ$>同态，则S所具有某些性质单向地对代数系统<$f(S)$,$\circ$>保持。这里$f(S)$是代数系统<S,$\ast$>在$f$下的同态像；如果代数系统<S,$\ast$>和<T,$\circ$>为满同态，则S所具有的性质单向地对T保持；如果两个代数系统<S,$\ast$>和<T,$\circ$>为同构，则S所具有地性质对T保持，反之亦然。

所以两个代数系统同态的实际意义是：代数系统的同态像集中体现了代数系统中的某些基本体征，特别是代数系统中的重要特征，如基本性质、特殊元素等

基本性质

不同的代数系统可能含有不同的代数运算，这些代数运算往往具有基本性质中的某些性质

• 对于集合A上的二元运算”$\ast$”，如果$\forall$x，y∈A，x$\ast$y=y$\ast$x，则称运算“$\ast$”满足交换律，或称运算“$\ast$”是可交换的，或具有可交换性
• 对于集合A上的二元运算”$\ast$”，如果$\forall$x，y∈A，(x$\ast$y)$\ast$z=x$\ast$(y$\ast$z)，则称运算“$\ast$”满足结合律，或称运算“$\ast$”是可结合的，或者具有可结合性。【实数集R上的加法和乘法都满足结合律，但减法不满足。幂集合P(A)上的并和交运算满足结合律，但差运算不满足】
• 对于集合A上的二元运算“$\ast$”和“$\Delta$”，如果$\forall$x，y，z∈A，都有x$\ast$(y$\Delta$z)=(x$\ast$y)$\Delta$(x$\ast$y)，则称运算”$\ast$“对运算$\Delta$”是左可分配的；如果$\forall$x，y，z∈A，都有(x$\Delta$y)$\ast$z=(x$\ast$z)$\Delta$(y$\ast$z)，则称运算“$\ast$”对运算“$\Delta$”是右可分配的。如果运算“$\ast$”对运算“$\Delta$”既是可左分配的又是右可分配的，则称运算“$\ast$”对运算“$\Delta$”是可分配的，或者称运算“$\ast$”对运算“$\Delta$”满足分配律或具有可分配性【乘法运算对于加法运算是可分配的，但是反过来加法运算对于乘法运算是不可分配的】
• 对于集合A上的二元运算“$\ast$”和“$\Delta$”，如果$\forall$x，y∈A，都有x$\ast$(x$\Delta$y)=x，则称运算“$\ast$”对运算“$\Delta$”是左可吸收的；如果$\forall$x，y∈A，都有(x$\Delta$y)$\ast$x=x，则称运算“$\ast$”对运算“$\Delta$”是右可吸收的。如果运算“$\ast$”对于运算“$\Delta$”是左可吸收同时也是右可吸收的，就称运算“$\ast$”对运算“$\Delta$”是可吸收的。如果运算“$\ast$”对于运算“$\Delta$”是可吸收的，且反过来也是（即运算“$\ast$”对于运算“$\Delta$”是可吸收的，$\forall$x,y∈A，满足x$\ast$(x$\Delta$y)=x,(x$\Delta$y)$\ast$x=x），则称运算“$\ast$”和运算“$\Delta$”满足吸收率或具有吸收性
• 对于集合A上的二元运算“$\ast$”，如果$\forall$x∈A，x$\ast$x=x，则称运算“$\ast$”是幂等的或等幂的，或称运算“$\ast$”满足幂等律或等幂律
• 对于集合A上的二元运算“$\ast$”，如果$\forall$x，y，z∈A，x$\ast$y=x$\ast$z必有y=z，则称运算“$\ast$”是左可消去的；如果$\forall$x，y，z∈A，y$\ast$z=z$\ast$x必有y=z，则称运算“$\ast$”是右可消去的。如果运算“$\ast$”既是左可消去的又是右可消去的，则称运算“$\ast$”是可消去的，或称运算“$\ast$”满足消去律【在实数集R上，加法运算、减法运算都满足这个消去律，但乘法运算和除法运算都不满足（主要原因是0）】

特殊元素

集合中的某些元素在代数运算的作用下会显示出与其他元素有不相同的特殊性质，这些具有特殊性质的元素称为代数运算的特殊元素，简称为特殊元

同态核

设$f$是代数系统<S,$\ast$>到代数系统<T,$\circ$>的一个同态映射，e是代数系统<T,$\circ$>中关于运算“$\circ$”的幺元，称集合{$x|x∈S,f(x)=e$}为同态映射$f$的核，简称为同态核，记作Ker($f$)

商代数系统

zhongwu