自考离散数学(02324) 思维导图模板_ProcessOn思维导图、流程图

第1章命题与命题公式

命题与命题联结词

命题与命题的表示

具有唯一真值的陈述句称为命题，命题的真值一定是唯一的，或者为真，或者为假，不能既真又假

判断命题的两个条件

语句本身是陈述句

它有唯一真值

命题符号化

可用大写字母或者小写字母表示

复合命题与联结词

原子命题

不能再分解的命题称为原子命题或者简单命题

联结词

在自然语言中，常使用连词来表示两个句子之间的关系。在命题符号化时，这样的连词将表示为联结词，
联结词都有特定的符号

复合命题

由原子命题通过联结词联结而成的命题，称为复合命题

常用联结词

否定

设P为命题，P的否定是一个复合命题，记作┐P

合取

设P和Q为两个命题，P和Q的合取是一个复合命题，记作P∧Q，
当前仅当P和Q同时为T时，P∧Q为T，其余情况P∧Q为F

合取其根本含义是表示两个事件同时成立

自然语言中对应词语

并且

即···，又··

不但···，而且···

虽然···，但是···

合取具有对称性，两个原子命题可以互换位置

复合命题所含的多个原子命题之间可以没有逻辑关联性。
我们仅关心它的表示，而忽略其语义。所以它的真值只与原子命题的真值有关，与语义无关

析取

设P和Q为两个命题，P和Q的的析取是一个复合命题，记作P∨Q。
当且仅当P、Q同时为F时，P∨Q的真值为F，其余情况的真值为T

自然语言中对应词语

或

同或

或者

自然语言中有时会使用“或”来表示“相斥”的含义，
即用“或”连接的两者不能同时成立，这样的语句不能表示为析取

析取具有对称性，两个原子命题可以互换位置

条件

设P、Q为两个命题，P和Q组成的条件命题是一个复合命题，记作P→Q，
当且仅当P的真值为T，Q的真值为F时，P→Q的真值为F，其余情况真值为T

P称为前件或者前提，Q称为后件或结论

条件命题表示的是，当前件发生时后件是否发生。而当前件没有发生即P为F时，后件发生或不发生都没有关键

自然语言中对应词语

如果···，那么···

若···，则···

Q是P的必要条件

只有···，就···

因为···，所以···

只有···，才···

双条件

设P和Q未两个命题，P和Q组成的双条件命题是一个复合命题，记作P↔Q。
当P与Q的真值相同时，P↔Q的真值为T，否则P↔Q的真值为F

当P与Q的真值相同时，也可以看作P和Q是等价的，即P与Q互为充分必要条件

自然语言中对应词语

···当且仅当···

命题公式的等值演算

命题公式

命题常项

当符号P代表一个具体的命题时，此时P的真值是确定的，所以称为常项，符号P称为命题常项

命题变元

当符号P仅仅表示是一个命题，但并没有指明是哪个命题时，P为命题变远。一般地，命题变元不是命题

合式公式

命题用联结词和圆括号按一定的逻辑关系联结起来的符号称为合式公式

命题演算的合式公式定义如下(1.6)

单个命题变元和命题常项是合式公式，并成为原子命题公式

若A是合式公式，则（┐A）是合式公式

若A、B是合式公式，则（P∧Q），（P∨Q），（P→Q），（P↔Q）也是

有限次地应用1~3形式的符号串是合式公式

联结词优先顺序

┐、∧、∨、→、↔

约定

合式公式的最外层括号可以省略

不影响运算次序的括号也可以省略

两命题公式等价

给定两命题A和B，设P1，P2，Pn为所有出现于A和B中的原子边元，若给P1，P2，Pn任一组真值指派，
A和B的真值都相同，称A和B是等值或等价的，记作A⇔B。若至少存在一组真值指派，使得A与B的真值不相同，
称A和B不等值或者等价，记作A<≠>B

重言式或永真式（1.10）

设A为一命题公式，若A在她的各种指派情况下，其取值均为真，则称公式A为重言式或永真式

矛盾式或永假式（1.11）

设A为一命题公式，若A在她的各种指派情况下，其取值均为假，则称公式A为矛盾式或永假式

可满足式（1.12）

设A为一命题公式，若A在它的各种指派情况下至少存在一组成真指派，则称A是可满足式。
若可满足式A至少存在一个成假赋值，则称A为非重言式的可满足式

从1.10~1.12可知结论

合式公式P是可满足式，等价于P至少存在一个成真赋值

重言式一定是可满足式，但可满足式不一定是重言式

若两个命题公式P和Q等价，则P↔Q是重言式

命题定律

P28

德摩根律

蕴含等值式

等价等值式

吸收律

等值演算与蕴涵式

定理1.2

设A、B为两个命题公式，A⇔B，当且仅当A↔B为一个重言式

永真条件式

当且仅当P→Q是一个重言式时，我们称P蕴涵Q，并记作PQ。PQ称P蕴涵Q或蕴涵式，亦称作永真条件式

性质

对于任意公式A，有AA

对于任意公式A、B和C，若AB，BC，则AC

对于任意公式A、B和C，若AB，AC，则A(B∧C)

对于任意公式A、B和C，若AC，BC，则A∨BC

定理1.3

设A和B为任意两个命题公式，A⇔B的充分必要条件是AB且BA

推理定律

P32

联结词完备集

包含↔的公式等价变换为包含→和∧的公式

包含→的公式等价变换为包含￢和∨的公式

{￢,∨}和{￢,∧}称作命题公式的最小联结词完备集

联结词完备集几种

￢ ∧ ∨ → ↔

￢ ∧ ∨ →

￢ ∧

￢ ∨

￢ →

第2章命题逻辑的推理理论

范式

范式的概念

文字

命题变元及其否定统称为文字

简单析取式

仅由有限个文字构成的析取式称作简单析取式，简单析取式的联结词只有￢ ∨

简单合取式

仅由有限个文字构成的合取式称作简单合取式，简单合取式的联结词只有￢ ∧

简单析取式和简单合取式有以下性质

一个简单析取式是重言式，当且仅当它同时含某个命题变元及它的否定式

一个简单合取式是矛盾式，当且仅当它同时含某个命题变元及它的否定式

合取范式

当且仅当它具有形式：A1∧A2∧···∧An，其中A1，A2，An是简单析取式

合取范式都是由简单析取式构成的，根据合取联结词的定义可知，当且仅当每个简单析取式都是重言式时，合取范式是重言式

析取范式

当且仅当它具有形式：A1∨A2∨···∨An，其中A1，A2，An是简单合取式

析取范式都是由简单合取式构成的，根据析取联结词的定义可知，当且仅当每个简单合取式都是矛盾式时，析取范式是矛盾式

合取范式和析取范式等值

对任何一个命题公式，都存在与之对等的合取范式或析取范式

求等值析取范式和合取范式的步骤

P38

小项

定义

n个命题变元的简单合取式，称作布尔合取或极小项，简称为小项，其中每个命题变元与它的否定不能同时存在，
但该命题变元必须出现且仅出现一次，或以变元的形式，或以变元的否定形式

n个命题变元有2^n个小项，用字母m加上由编码构成的下标来表示每个小项，下标是个n位的二进制数。
命题变元Pi则对应小项编码的第i位为1，若是命题变元Pi的否定，则对应i位为0。n位二进制也可以使用对应十进制数i来表示小项的编码。
m011可以表示为m3

性质

每一个小项具有一个相应编码，且只在一种情况下真值为T，即按照其编码值进行指派时，其真值为T，其他情况下，真值都为F。
故每个小项有一个成真赋值，有2^n-1成假赋值。每个小项成真赋值均不相同。

任意两个小项的合取式为矛盾式

全体小项的析取式为重言式

大项

定义

n个命题变元的简单析取式，称作布尔析取或极大项，简称为大项，其中每个命题变元与它的否定不能同时存在，
但该命题变元必须出现且仅出现一次，或以变元的形式，或以变元的否定形式

与小项类似，字母M加上由编码构成的下标来表示每个大项，下标是一个n位的二进制数。若出现的是命题变元Pi，则对应该大项编码的第i位为0，
若出现命题变元Pi的否定,则对应i位为1。

主范式

主析取范式

定义

对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称为原式的主析取范式

定理

在公式的真值表中，所有真值为T的指派所对应的小项的析取，即构成该公式的主析取范式

定理

任何命题公式都存在与之等值的主析取范式，并且是唯一的

等值演算方法求解主析取范式

P42

主合取范式

定义

对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称为原式的主合取范式

定理

在公式的真值表中，所有真值为F的指派所对应的大项的合取，即构成该公式的主合取范式

定理

任意含有n个命题变元的公式A，都存在与之等值的主合取范式，并且是唯一的

等值演算方法求解主合取范式

P44

主析取范式求其主合取范式步骤

P45

根据主范式的定义和定理得出结论

若A可化为与其等价的含2^n个小项的主析取范式，则A为重言式

若A可化为与其等价的含2^n个大项的主合取范式，则A为矛盾式

若A的主析取范式中至少含有一个小项，或A的主合取范式中最多含有2^n-1大项,则A为可满足式

自然推理系统

有效结论

设H1,H2，···，Hn和C都是命题公式，若对于H1，H2，···，Hn
的命题变元的任意一组赋值，或者H1∧H2∧Hn为假，或者当H1∧H2∧Hn为真时
C也为真，则称有前提H1,H2,Hn的结论推出结论C的推理是有效的或正确的。

判断有效结论

CP规则推理

真值表法

主范式方法及等值演算

第3章谓词逻辑

谓词的表示与概念

x大于3

主语x是一个变量，称为个体词

谓语“大于3”表示主语的某一性质，称为谓词

P（x）表示句子"x大于3"，其中P表示的是性质，x表示的是变量

个体常项

个体词代表具体或特定的客体时

小写字母a,b,c表示

个体变项

个体词代表抽象或广泛的个体时

小写字母x,y,z表示

论域

个体变项的取值范围为个体域，或称论域。论域是个集合，即可以是又穷集合，也可以是无穷集合

谓词

指明个体与个体性质之间的关系，用大写英文字母表示

表示形式

P（x）,x的性质

B(x,y,z),y在x和z之间

G(x,y),x小于y

谓词变项

一个谓词、一些个体变量组成的表达式称为谓词变项或命题函数

命题函数不是命题，只有命题函数中的变元都取为特定具体的个体时，才是确定的命题

不带个体变项的谓词称为0元谓词

量词与合式公式

有些命题函数中，使用命题为真或为假的变量值并不是唯一的，即变量取不同的值时，得到命题真值是相同的

量词

命题函数中表示数量的词称为量词，可以使用量词来表示个体常项与变项之间的数量关系，即对命题函数进行量化。
量词分为两种，一是全称量词，二是存在量词。

全称量词

P(x)的全称量化是命题"P(x)对x在其论域的所有值均为真"。符号∀xP(x),∀称为全称量词

一切、任意、所有、凡是

存在量词

P(x)的存在量化是命题"论域中存在一个元素x使P(x)值为真"。符号∃∀xP(x),∃称为全称量词

存在着、有一个、至少有一个

特性谓词

有些命题中需要指明论域，称为特性谓词。特性谓词是条件式的前件，在存在量词中特性谓词后跟一个合取项。

复合公式的联结词

￢ ∧ ∨ → ↔

谓词演算的合式公式递归定义

原子谓词公式是合式公式

若A是合式公式，则￢A也是

若P、Q是合式公式，则（P∧Q），（P∨Q），（P→Q），（P↔Q）也是

若A是合式公式，x是A中出现的任何个体变元，则（∀x）A和（∃x）A也是

只有经过有限次应用规则1~4所得到的符号串才是合式公式

自由变元与约束变元

变元改名规则

约束变元改名规则

将量词辖域中，量词的指导变元及其辖域中该变元的所有约束均改为本辖域中未曾出现过的个体变元，其余不变

自由变元代入规则

把公式中的某一自由变元，用该公式中没有出现的个体变元符号替代，且要替换该自由变元在公式中的所有出现出

谓词演算的等价式与蕴含式

论域确定后，有此等价关系

∀xA(x)⇔A(a1)∧A(a2)∧···∧A(an)

∃xA(x)⇔A(a1)∨A(a2)∨···∨A(an)

量词和否定联结词之间的关系（定理3.1）

¬∀xA(x)⇔∃x¬A(x)

¬∃xA(x)⇔∀x¬A(x)

谓词等式与蕴含式

E27

E28

前束范式

一个公式，如果量词均在全式的开头，它们的作用域延伸到整个公式的末尾，则该公式称为前束范式

存在定理

任意一个谓词公式，均存在与之等值的前束范式

谓词公式转前束范式步骤

对不同辖域的同名变元进行换名（换名规则）

利用定理3.1，将否定联结词深入到命题变元和谓词公式前面（量词转换规则）

利用等值式∀x（A∨B(x))⇔A∨∀xB(x)和∃x（A∧B(x))⇔A∧∃xB(x)，将量词移到全式最前面（量词前提规则）

第4章集合

集合的基本概念

集合的表示法

空集

空集的子集只有一个，即它本身，但空集的真子集不是本身

空集是唯一的

对于任意集合A，必有一个子集是空子集（定理4.2）

幂集

设A为任意集合，以A的子集为元素所组成的集合，称为集合A的幂集

幂集有2^n个元素

集合的运算

补集

设任意两个集合A和B，属于A不属于B的所有元素组成的集合S，称A与B的差集，也称为B对于A的补集，或相对补

设E为全集，对于任一集合A，关于E的补E-A，称为集合A的绝对补,记

设A、B为任意两个集合，有如下关系式成立

A - B = A∩~B

A - B = A-（A∩B）

集合运算的恒等式

德摩根律

对称差

设A、B为任意两个集合，A和B的对称差为集合S，其元素或属于A，或属于B，但不能既属于A又属于B，记作

有序对和笛卡尔积

有序对

由两个元素x和y按一定顺利排列成的二元组称为一个有序对或序偶，记作<x,y>或(x,y)，其中x该有序对的第一个元素，y是该有序对的第二个元素

两个有序对相等,<x,y> = <u,v>，当且仅当x= u 且 y = v

笛卡尔积

性质

不满足交换律

不满足结合律

任意集合X空集等于空集

定义

若集合A有m个元素，集合B有n个，AXB有m*n个元素

笛卡尔积公式

第5章关系和函数

关系及关系的性质

关系

定义

设A、B是任意两个集合，AXB的子集R称为从A到B的二元关系，简称为关系。特别地，当A = B时，称R为A上的关系。
如果<x,y>属于R，可记为xRy,称x与y有关系R，如果<x,y>不属于R，则记为，称X与Y没有关系R

特殊关系

空关系

全域关系

恒等关系

定义域

R中所有有序对的第一元素构成的集合称为R的定义域，记为domR

值域

R中所有有序对的第二个元素构成的集合称为R的值域，记为ranR

性质

集合A中所有的a都有aRa，关系R在A上是自反

关系中所有的<x,x>均存在

集合A中所有的a都有，关系R在A上是反自反

关系中所有的<x,y>均不存在，称为反自反；若存在部分既不是自反也不是反自反

集合A中所有的a,b，若aRb必有bRa，关系R在A上是对称的

关系中所有的<x,y>和<y,x>均存在，称关系为对称的

集合A中所有的a,b，若aRb且bRa必有a=b，关系R在A上是反对称的

关系中所有的<x,y>均存在且<y,x>均不存在，称关系为反对称的，若存在部分既不是反对称也不是对称

集合A中所有的a,b,c，若aRb且bRc必有aRc，关系R在A上是传递的

关系的运算

关系的常规运算

逆关系

设R是从X到Y的二元关系，如奖R中每一个二元组中的元素顺序互换，所得到的集合称为R的逆关系，简称为R的逆，记作

二元关系的公式

复合关系

定义

设R为A到B的关系，S为B到C的关系，则称为R和S的复合关系，表示为

结合律

设R是集合A上的关系,幂R^n(n=1,2,3,...)递归定义为

对任意的n≥4，均有R^n = R^3

关系矩阵的布尔运算

复合关系的矩阵运算

P90

关系的闭包

任意一个关系R，在R中添加新的二元组形成新的关系R'，仅添加必要的二元组，使得新关系具有我们想要的性质。得到的新关系称为原关系的闭包

定理

原关系和恒等关系进行并运算使得新关系有自反

原关系和该关系逆运算进行并运算使得新关系有对称

原关系和该关系逆运算进行并运算使得新关系有传递

等价关系与序关系

等价关系

相容关系

给定集合A上的关系ρ，若ρ是自反的、对称的，则称ρ是A上的相容关系

等价关系

设R为非空集合A上的关系，若R是自反的、对称的和传递的，则称R为A上的等价关系

若<x,y>∈R，称x等价y，记作x~y

等价类

划分

给定非空集合A，若有集合S = {S1,S2,...,Sm}，其中Si是A的子集，Si不是空集(1≤i≤m)，且Si和Sj的交集是空集(i≠j)，同时S1和S2和...和Sm的并运算等于A，称S是A的划分，每个Si称为一个分块

划分不唯一

集合A的任一等价关系的等价类都构成A的一个划分

序关系

偏序关系

设A是一个非空集合，如果A上的关系R满足自反性、反对称性及传递性，则称R是A上的一个偏序关系，记，集合A和A上的偏序关系一起称为偏序集

哈斯图P97

全序关系

设是非空集合A上的偏序关系，对于任意的a,b属于A，若必有或，则称是A上的全序关系(或线序关系)

极大元、极小元、最大元、最小元

最小元是B中最小的元素，它与B中所有元素都可比，即与B中所有元素都存在偏序关系

最大元与B中所有元素是可比的，且都大于等于这些元素，即它是B中最大元素

极小元不一定与B中所有元素均可比，但只要可比，就一定是小于等于其他元素

极大元是B中没有比它更大的元素

最大元、最小元不一定存在，如果存在一定是唯一

极大元、极小元可能存在多个，如果极大元只有一个，那就是最大元，极小元同理

上界和下界

设为一偏序集，对于B是A的子集，如果有a属于A，且对B中任意元素x都满足，则称a为子集B的上界，同样对于B中任意元素x，都满足，则称a为B的下界

最大上界和最小下界

设为偏序集，A有子集B，若a为B的任一上界，且对B的所有上界y，均有，则称a为B的最小上界，同样若b为B任一下界，若对B的所有下界z，均有，则称b为B的最大下界

函数

函数的概念

设F为二元关系，若都存在唯一的，使xFy成立，则称F为函数，也称为映射。从x到y的函数F记为

F:x→y或x→y

函数F和关系R的差异

函数F要对定义域中的所有元素都有定义，而不能只对某个真子集进行定义。关系R可能只对定义域中的若干元素有定义

对于domF全部的x，ranF只有唯一的y，满足<x,y>属于F。而关系R中，对同一个x可以存在多个y，均满足<x,y>属于R

Y上X

设X、Y为集合，所有从X到Y的函数构成的集合记作Y^X

若X = ∅且Y = ∅，则Y^X = {∅}

若X ＝ ∅且Y ≠ ∅，则Y^X = {∅}

若X ≠ ∅且Y ＝ ∅，则Y^X = ∅

若X和Y均不为空集，设|X| = m，|Y| = n，|Y^X| = n^m

单射

函数f称一对一，当且仅当对于f定义域中的所有x和y，f(x) = f(y)蕴含着x = y。一对一函数也被称为单射函数或入射函数

一个x有唯一的y与之对应，y允许没有x

满射

给定函数f:X→Y，当且仅当对Y中所有的y，都有X中的x使用f(x) = y，则函数f称为满射或映上

Y中的每一个y至少要有一个x对应

双射

给定函数f:X→Y，既满足单射又满足双射,称f是一一对应的，也称双射

反函数

设f是从X到Y的双射函数，定义函数：Y中任一元素y，对应于X中满足f(x) = y的唯一的元素x，f的反函数表示为f^-1。当f(x) = y时,f^-1(y) = x

当且仅当函数是双射函数时才存在反函数，所以双射函数也称为可逆的，它的反函数也称为逆函数

复合函数

如果f的值域不是g的定义域的子集，则无法定义

函数复合不满足交换律

定理

若f和g都是满射的，则复合函数f·g也是满射的

若f和g都是单射的，则复合函数f·g也是单射的

若f和g都是双射的，则复合函数f·g也是双射的

关系证明例题

等价关系证明P94

序关系证明

P96

P98

第6章代数系统的一般概念

代数系统

运算封闭

设A为任意集合，一个从A^n到B的映射，称为集合A上的一个n元运算。如果B是A的子集，则称该n元运算是封闭的

代数系统

一个非空集合A，连通若干定义在该集合上的运算f1,f2,...,fk所组成的系统，称为一个代数系统，简称代数，记作<Mr(R),+,->

运算表

运算重要性质

设A为任意非空集合，*和是集合A上的二元运算，对于任意的a,b,c属于A

a*b 属于A，*关于集合A是封闭的

a*(b*c)=(a*b)*c，是满足结合律的

a*b=b*a，是满足交换律的

a*a=a，在A上是满足幂等律的

a(b*c) = (ab)*(ac)和(b*c)a = (ba)*(ca)成立，则称运算对*是可分配的，或称运算对*满足分配律

若和*均满足交换律，而且有：a(a*b) = a和a*(a) = a，则称运算和*是可吸收的

幺元

设*为集合A上二元运算，若A存在el，使用A中任意的x都有el*x = x，则称el是A中关于*运算的左幺元

若A存在er，使用A中任意的x都有x*er = x，则称er是A中关于*运算的右幺元

若A存在e，e即是左幺元，又是右幺元，则称e是A中关于*运算的幺元，又称为单位元。e*x = x*e = x

幺元可能不存在，也可能不唯一

在A中存在关于运算*的左幺元和右幺元,则el=er = e，且A中的幺元是唯一的。el= el*er = er = e

零元

设*为集合A上二元运算，若A存在Ol，使用A中任意的x都有Ol*x = 0，则称Ol是A中关于*运算的左零元

若A存在Or，使用A中任意的x都有x*Or = 0，则称Or是A中关于*运算的右零元

若A存在O，O即是左零元，又是右零元，则称O是A中关于*运算的零元。O*x = x*O = 0

在A中存在关于运算*的左零元和右零元,则Ol=Or = O，且A中的零元是唯一的。Ol= Ol*Or = Or = O

逆元

设代数系统<A,*>中,e是关于运算*的幺元，若对A中某个元素a，存在A的一个元素b，使得b*a = e，则称b为a的左逆元

若对A中某个元素a，存在A的一个元素b，使得a*b = e，则称b为a的右逆元

若一个元素b，既是a的左逆元，又是a的右逆元。则称b是a的一个逆元，记作

幺元和零元和逆元

代数系统中存在幺元，则该幺元是所有元素的幺元。零元同理，故幺元和零元具有一般性

逆元具有个体性，有的元素可能存在逆元，有的元素可能不存在逆元。即使两个元素都有逆元存在，也不能保证两个逆元是相同的

左右逆元唯一定理

设代数系统<A,*>中，*是在A上的二元运算，A中存在幺元e，且每一个元素都有左逆元，如果*是可结合运算，
那么这个代数系统中任何一个元素的左逆元必定也是该元素的右逆元，且每个元素的逆元是唯一的

群与半群

半群和独异点

半群

设V = <S,*>是代数系统，*是集合S上的二元运算，若运算*是封闭且是可结合的，则称V为半群

独异点

若半群中存在一个幺元，则称该半群为独异点或含幺元半群

设<S,*>是独异点，对于S中任意的a,b，若a,b均有逆元,则

群

设<G,*>是一个独异点，其中G是非空集合，*是G上一个二元运算，对于G的任意 x都有逆元x^-1的存在，则称<G,*>是一个群

群满足独异点三个条件，封闭性、结合律、存在幺元，同时每个元素都有逆元

平凡群

设<G,*>是一个群，如果G是有限集，则称为有限群，G中元素个数称为该群的阶数，记为|G|，
若群G只含有一个元素，G = |e|，|G| = 1，则称G为平凡群

Abel群

设<G,*>是一个群，若运算*满足交换律，则称G为交换群

元素的阶

设<G,*>是一个群，e是幺元，对于a∈G，使得a^k = e成立的最小正整数k称为a的阶，记作|a|，a称为k阶元。|
若不存在这样的正整数k，则称a为无限阶元

幂等元

设<G,*>是一个群，对于a∈G，有a*a = a，称a为幂等元

设<G,*>是一个群，e是唯一的幂等元

设<G,*>是一个非平凡群，则不存在0元

循环群

设<G,*>为群，若在G中存在一个元素a，使用G中的任意元素都有a的幂组成，则称该群为循环群，元素a被称为循环群的生成元

G的阶有限时，称为有限循环群，生成元是a。否则称为无限循环群，生成元是a^-1

生成元可能不止一个，因此生成元也不唯一

整数环Z不是域，有理数环Q和实数环R是域

环和域

环

定义

设<A,+,*>是一个代数系统，+和*是二元运算，如果满足

<A,+>是Abel群

<A,*>是半群

运算*对于运算+是可分配的

则称<A,+,*>是一个环

为了表示上的方便，环的加法幺元记作0，乘法则记作1，换种任一元素啊，加法逆元称为负元，记为-a。若存在乘法逆元，称为逆元，记a^-1

性质

环的元素的加法和乘法一样满足交换律、结合律、分配率

P121

零因子

设<R,+,*>为环，对a,b∈R，a≠0，b≠0，但a*b = 0，则称a是R的左零因子，称b是R的右零因子，则称它是一个零因子。

交换环

设<A,+,*>是一个环，乘法*满足交换律，称为交换环

含幺元环

设<A,+,*>是一个环，乘法*存在幺元，即对任意a∈A，均有1*a = a*1 = a，则称为含幺元环，1称为环的幺元

无零因子环

设<A,+,*>是一个环，对于任意a,b∈B，若a*b = 0，必有a = 0或b = 0，则称是一个无零因子环

整环

环既是交换环、含幺元环、无零因子环，则称为整环

设R是一个无零因子环，当且仅当R中乘法适合消去律，即对任意a,b,c∈R,a≠0，若有a*b = a*c或b*a = c*a，则有b=c

第7章格和布尔代数

格的基本概念

格

定义

设<A,≤>是一个偏序集，对于任意a,b∈A，子集{a,b}在A中都有最大下界和最小上界，则称为格

全序集是格，偏序集不一定是

格的交运算和并运算

设<A,≤>是一个格，如果在A上定义两个二元运算符∧和∨，使得对任意a,b∈A，a∧b等于a和b的最大下界，a∨b等于a和b的最小上界。
称<A,∧,∨>为由格<A,≤>所诱导的代数系统。

对偶

设<S,≤>是一个格，P是由格中元素及≤，=、≥、∧和∨等符号所表示的命题，
如果将P中的≤，=，≥，∧和∨分别替换称≥、=、≤、∨和∧，得到命题P'称为P的对偶命题，简称对偶

性质

设<A,≤>是一个格，对任意a,b∈A，都有a ≤ a∨b，b≤ a∨b，a∧b≤a，a∧b≤a

设<A,≤>是一个格，由格<A,≤>所诱导的代数系统为<A,∧,∨>。对于任意a,b,c∈A，有

交换律

结合律

幂等律:a∨a = a，a∧a = a

吸收律

设<A,*,>是一个代数系统，其中*和都是二元运算，且满足交换律、结合律和吸收律，则A上存在偏序关系≤，使<A,≤>是一个格，
且任何a,b∈A，有a∨b = ab，a∧b = a*b

设<L,∧,∨>是一个代数系统，其中∧,∨是二元运算，若∧和∨运算满足交换律、结合律、吸收律，则称为一个格

设<L,∧,∨>是格，S是L的非空子集，若S关于运算∧和∨封闭的，则称<S,∧,∨>是格L的子格

分配格与有补格

分配格

格的运算满足交换律、幂等律、结合律、吸收律，但不是所有格都满足分配律，满足分配律的格是一种特殊的格，对于补元素也是一样，并不是所有格元素都存在补元素

设<A,≤>是一个格，若对于任意a,b,c属于A，若满足分配律，则称格是分配格

钻石格和五角格不是分配格

小于五元的格或者任意一条链都是分配格

有补格

全上界和全下界

设<A,≤>是一个格，如果存在元素a,b∈A，对于任意x∈A

都有a≤x，则称a为格的全下界

都有x≤b，则称b为格的全上界

全下界就是偏序集的最小元，记为0

全上界就是偏序集的最大元，记为1

有界格

格存在全上界和全下界，则称A为有界格，记作<L,∧,∨,0,1>

补元

设<A,≤>是有界格，a∈A，若存在b∈A，使得a∨b = 1且a∧b = 0，称b是a的补元

若b是a的补元，则a也是b的补元，a和b互为补元，简称互补

任何有界格中，全上界1和全下界0总是互补的。其他元素可能存在补元，也可能不存在补元。如果存在补元，可能不唯一也可能多个。

设A是<L,∧,∨,0,1>是有界分配格，若a∈A，且对于a存在补元B，b是a唯一的补元

有补格

设<A,≤>是有界格，若对于任意a∈A，在A中都有a补元存在，则称A为有补格

布尔代数

布尔格

如果一个格是有补分配格，则称它为布尔格或布尔代数

在分配格中，若一个元素存在补元，则补元是唯一的。故在布尔代数中，每个补元都存在唯一的补元

设有代数系统<B,∧,∨,',0,1>，其中B至少包含两个元素，∧和∨为B上的两个二元运算，’为B上一元运算，对任意a,b,c∈B满足

交换律

分配律

同一律：a∧0 = 0,a∨1 = a,a∧1 = 1,a∨1 = 1

补元律:a'∈B，a∧a' = 0,a∨a' = 1

第8章图

图的基本概念

图的表示

G=(V,E)，|V|代表顶点数，|E|代表边数

零图

一条边也没有的图

平凡图

只有一个顶点的图叫平凡图，平凡图必是零图

n阶图

若|V| = n(n > 0)，称为n阶图

度

无向图

设G=(V,E)，顶点v（v∈V）关联的边数称作该顶点的度数，简称为度，记作deg(v)

deg(v) = 0称孤立点

deg(v) = 1称悬挂点

若v有环，计算deg(v)增加2

顶点度数总和等于边数的两倍

对任意的图G，奇顶点必有偶数个

有向图

设G=(V,E)是一个有向图

以顶点v为起点的有向边的个数称为v的出度，记为dev^+(v)

以顶点v为终点的有向边的个数称为v的入度，记为dev^-(v)

顶点的出度和入度之和就是该顶点的度数，即deg(v) = deg(v)^+(v)+deg^-(v)

在有向图中，所有顶点的入度之和等于出度

图最大的度记

图最小的度记

边

有向图

n阶有向完全图有n(n-1)条边

无向图

n阶无向完全图有边

生成子图

设图G = <V,E>，如果有图G' = <V',E'>，且E'是E的子集，V'是V的子集，则称G是G的子图。
如果G的子图包含G的所有顶点，即E'是E的子集，V' = V，则称G'称为G的生成子图

图的连通性

若无向图中每个顶点的度数至少为2，这图G包含一条初级回路

连通图

在无向图中，顶点u和v之间若存在通路，则称顶点u和v是连通的。
若图G中任何两个不同顶点都是连通的，则称G为连通图，否则称G为不连通图

对于连通图，它极大连通子图即是图的本身

单测连通

在简单有向图G中，任何一对顶点间至少有一个顶点到另一个订单是可达的，则称这个图是单侧连通的

强连通

如果对于图G中任何一对顶点，两者之间是相互可达，则称这个图是强连通的

弱连通

在图G中，略去边的方向，将它看成无向图后，图是连通的，则该图称为弱连通

割点

设无向连通图 G=(V,E)中，对于任意的顶点w∈V，若删除w以及所有与w关联的边之后，图G不在连通，则称w为G的割点。

割点集

设无向图 G=<V,E>为连通图，若有点集V1⊂V，使图G删除了V1的所有结点后（将结点与其关联的边都删除）得到的子图是不连通的，而删除了V1的任何真子集中顶点以及相关的边后所得到的子图仍然是连通图，则称V1为G的一个点割集。

割边

设无向连通图 G=(V,E)中，对于任意的边e∈E，若删除e之后，图G不在连通，则称e为G的割边，也称为桥

割边集

设无向图 G=<V,E>为连通图，若有边集E1⊂E，使图G删除了E1的所有边后得到的子图是不连通的，而删除了E1的任何真子集后所得到的子图仍然是连通图，则称E1为G的一个边割集。

无向连通图的点割集V1和边割集E1，则子图G-E1所含得连通分量个数必须为2，子图G-V1所含的连通分量个数不确定

图的表示

邻接矩阵

无向图的邻接矩阵是对称矩阵，有向图这个结论不成立

无向图中，非0元素即顶点的度

有向图中，行中非零元素为顶点的出度，列中非零的元素为顶点的入度

通路数目

M^k是简单图邻接矩阵顶点之间长度为k的的通路数目

可达性矩阵

第9章图的应用

欧拉图与哈密顿图

欧拉图

图G中每条边一次且仅一次的通路，称为欧拉通路或欧拉路。
若欧拉通路为回路，则称为欧拉回路，具有欧拉回路的图叫欧拉图

无向连通图G是欧拉图的充分必要条件是G是连通的且无奇点

无向连通图G是欧拉通路充分必要条件是连通且恰有两个奇点，从一个奇点出发到另一个奇点结束

哈密顿图

无向图G中，若存在一条路L，经过图的每一个顶点一次且仅一次，这称L为哈密顿路，简称H-路；
若存在一条回路G，经过图中每个顶点一次且仅一次，C称作哈密顿回路，简称H-回路。
具有哈密顿回路的图称作哈密顿图，简称H-图

含有度为1的顶点的图比不是哈密顿图

G是有n个顶点的简单图，如果G中每一对顶点度数之和大于等于n-1，则G中存在一条哈密顿路

G是有n个顶点的简单图，如果G中每一对顶点度数之和大于等于n，则在G中存在哈密顿回路

上述是哈密顿图的充分条件，但不是必要条件，即使不满足，图也有可能是哈密顿图

平面图

若一个图G能画在平面S上，且使G的边仅在端点处相交，则称图G可嵌入平面S，G称为可平面图，简称平面图

设G是一个连通平面图，G的边将G所在平面划分成了若干个区域，每个区域称为G的一个面，其中面积无限的区域称为无限面或外部面。
面积有限的区域称为有限面或内部面。包围每个面的所有边组成的回路称为该面的边界，边界的长度称为该面的次数。若该区域记为R，则次数可记为deg(R)

设连通平面图G，面的次数之和等于其边数的两倍

欧拉公式

连通平面图G有n个顶点，m条边，r个面。有欧拉公式

n-m+r = 2

设连通平面图G，有v个顶点m条边，若v≥3，则m≤3v-6，可以用于判定某些图是非平面图

设连通平面图G，有v个顶点m条边，若v≥3且没有长度为3的回路，则m≤2v-4

树及其遍历

树的节点数是n，则树的边是n-1

度为1的节点是叶子节点

破圈法求生成树

树的层从0开始，根结点是位于第0层

树的高从1开始算

二叉树

设T是有n个节点的完全二叉树，则T有（n+1）/2个叶子结点