序偶

i

离散数学笔记

第一章命题逻辑

合取

析取

定义1.1。3否定：当某个命题为真时，其否定为假，当某个命题为假时，其否定为真

定义1。1。4条件联结词，表示“如果……那么……"形式的语句

定义1.1。5双条件联结词，表示“当且仅当"形式的语句

定义1.2。1合式公式

（1）单个命题变元、命题常元为合式公式,称为原子公式。

（2)若某个字符串A是合式公式，则A、(A)也是合式公式。

(3)若A、B是合式公式，则AB、AB、A



B、AB是合式公式.

(4)有限次使用(2）～(3)形成的字符串均为合式公式。

1.3等值式

1.4析取范式与合取范式

ii

将一个普通公式转换为范式的基本步骤

iii

iv

1。6推理

定义1.6。1设A与C是两个命题公式，若A→C为永真式、重言式,则称C是A的有

效结论，或称A可以逻辑推出C，记为A=〉C。（用等值演算或真值表)

第二章谓词逻辑

2。1、基本概念

∀：全称量词∃：存在量词

一般情况下,如果个体变元的取值范围不做任何限制即为全总个体域时，带“全称量词"的谓词公式形如”∀x

（H(x)→B(x))，即量词的后面为条件式,带“存在量词”的谓词公式形如∃x(H（x)∨WL(x)），即量词的后面为

合取式

例题

R(x)表示对象x是兔子，T（x)表示对象x是乌龟,H(x，y)表示x比y跑得快,L(x，y）表示x与y一样快，

则兔子比乌龟跑得快表示为:∀x∀y(R（x）∧T(y)→H(x,y))

有的兔子比所有的乌龟跑得快表示为：∃x∀y（R(x）∧T(y）→H（x，y)）

2.2、谓词公式及其解释

定义2.2.1、非逻辑符号：个体常元(如a，b，c）、函数常元(如表示22yx

的f（x,y)）、谓词常元（如

表示人类的H（x）)。

定义2。2。2、逻辑符号:个体变元、量词(∀∃）、联结词（﹁∨∧→↔）、逗号、括号。

定义2。2。3、项的定义：个体常元、变元及其函数式的表达式称为项（item）。

定义2。2.4、原子公式:设R（

n

xx...

1

）是n元谓词，

n

tt...

1

是项,则R（t）是原子公式.原子公式中的个

体变元，可以换成个体变元的表达式(项），但不能出现任何联结词与量词，只能为单个的谓词公式。

定义2。2。5合式公式：(1）原子公式是合式公式;（2）若A是合式公式，则(﹁A）也是合式公式；(3）若A，

B合式，则A∨B,A∧B,A→B，A↔B合式(4)若A合式，则∀xA、∃xA合式(5）有限次使用（2)~(4)得

到的式子是合式。

定义2。2.6量词辖域：∀xA和∃xA中的量词∀x/∃x的作用范围，A就是作用范围。

定义2。2。7约束变元:在∀x和∃x的辖域A中出现的个体变元x，称为约束变元，这是与量词相关的变元，

约束变元的所有出现都称为约束出现.

定义2。2。8自由变元：谓词公式中与任何量词都无关的量词，称为自由变元,它的每次出现称为自由出现。

一个公式的个体变元不是约束变元，就是自由变元。

注意：为了避免约束变元和自由变元同名出现，一般要对“约束变元"改名，而不对自由变元改名.

v

定义2.2。9闭公式是指不含自由变元的谓词公式

从本例（已省)可知，不同的公式在同一个解释下,其真值可能存在，也可能不存在，但是对于没有自由变

元的公式(闭公式），不论做何种解释，其真值肯定存在

谓词公式的类型：重言式(永真式）、矛盾式（永假式)、可满足公式三种类型

定义2.2.10在任何解释下，公式的真值总存在并为真，则为重言式或永真式。

定义2。2。11在任何解释下，公式的真值总存在并为假，则为矛盾式或永假式。

定义2.2.12存在个体域并存在一个解释使得公式的真值存在并为真，则为可满足式。

定义2。2。13代换实例设

n

ppp,...,,

21

是命题公式

0

A中的命题变元，

n

AAA,...,,

10

是n个谓

词公式，用

i

A代替公式

0

A中的

i

p后得到公式A，则称A为

0

A的代换实例.

如A（x）∨﹁A(x），∀xA(x)∨﹁∀xA（x)可看成p∨﹁p的代换实例，A(x)∧﹁A（x）,∀xA（x)∧﹁

∀xA(x）可看成p∧﹁p的代换实例。

定理2.2.1命题逻辑的永真公式之代换实例是谓词逻辑的永真公式，命题逻辑的永假公式之代换实例是谓词

逻辑的永假式。（代换前后是同类型的公式）

2.3、谓词公式的等值演算

定义2.3.1设A、B是两个合法的谓词公式，如果在任何解释下，这两个公式的真值都相等,则称A与B等

值，记为AB。

当AB时，根据定义可知,在任何解释下,公式A与公式B的真值都相同,故A↔B为永真式，故得到如下

的定义。

定义2。3。2设A、B是两个合法谓词公式，如果在任何解释下，A↔B为永真式,则A与B等值,记为

AB。

一、利用代换实例可证明的等值式(p↔﹁﹁p永真，代换实例∀xF(x)↔﹁﹁∀xF(x）永真)

二、个体域有限时，带全称量词、存在量词公式的等值式

如：若D=｛

n

aaa,...,,

21

｝，则∀xA(x)A（

1

a）∧A(

2

a)∧…∧A(

n

a）

三、量词的德摩律

1、﹁∀xA（x)∃x﹁A(x）2、﹁∃xA（x)∀x﹁A（x)

四、量词分配律

1、∀x（A（x）∧B(x)）∀xA（x)∧∀xB(x）2、∃x（A（x)∨B（x)）∃xA（x）∨∃xB(x）

记忆方法：∀与∧，一个尖角朝下、一个尖角朝上,相反可才分配。2式可看成1式的对偶式

五、量词作用域的收缩与扩张律

A(x)含自由出现的个体变元x，B不含有自由出现的x，则有：

1、∀/∃(A(x）∨B)∀/∃A(x)∨B2、∀/∃(A（x）∧B）∀/∃A(x)∧B

对于条件式A(x）↔B，利用“基本等值一"将其转换为析取式,再使用德摩律进行演算

六、置换规则

若B是公式A的子公式，且BC，将B在A中的每次出现,都换成C得到的公式记为D，则AD

七、约束变元改名规则

vi

将公式A中某量词的指导变元及辖域中约束变元每次约束出现,全部换成公式中未出现的字母,所得到的公式

记为B，则AB

例

证明步骤:

2。4、谓词公式的范式

从定理证明过程,可得到获取前束范式的步骤:

（1）剔除不起作用的量词；

（2）如果约束变元与自由变元同名，则约束变元改名；

（3）如果后面的约束变元与前面的约束变元同名，则后的约束变元改名；

(4)利用代换实例,将→、↔转换﹁∨∧表示；

(5)利用德摩律，将否定﹁深入到原子公式或命题的前面；

(6）利用量词辖域的扩张与收缩规律或利用量词的分配律，将量词移到最左边

2.5、谓词推理

定义2.5.1若在各种解释下BAAA

n

...

21

只能为真即为永真,则称为前提

n

AAA...

21

可推出

结论B。

定义2。5.2在所有使

n

AAA...

21

为真的解释下,B为真，则称为前提

n

AAA...

21

可推出结论B。

vii

谓词逻辑的推理方法分为以下几类：

一、谓词逻辑的等值演算原则、规律：代换实例、量词的德摩律、量词的分配律、量词

辖域的扩张与收缩、约束变元改名。

二、命题逻辑的推理规则的代换实例，如假言推理规则、传递律、合取与析取的性质律、

CP规则、反证法等。

三、谓词逻辑的推理公理

第三章集合与关系

3.1、基本概念

在离散数学称“不产生歧义的对象的汇集一块”便构成集合。常用大写字母表示集合,如R表示实数，N表

示自然数,Z表示整数，Q表示有理数，C表示复数。描述一个集合一般有“枚举法"与“描述法"，“枚

举法”。元素与集合之间有“属于”或“不属于”二种关系。

定义3.1.1设A，B是两个集合,如果A中的任何元素都是B中的元素，则称A是B

的子集，也称B包含于A，记为BA，也称A包含B，记为AB。

viii

3。2集合运算性质

定义3。2。1设A、B为集合，A与B的并集AB、A与B的的交集AB、A—B的定

义：AB=｛x｜xAxB}，AB=｛x|xAxB}，A—B={x｜xAxB}

定义3。2.2设A、B为集合，A与B的对称差，记为AB=｛x|(xAxB）（x

AxB）}=AB-AB。

定义3。2。3设A、B是两个集合，若AB、BA则A=B，即两个集合相等.

幂等律AA=A、AA=A

结合律ABC=A(BC)=(AB)C

ABC=A(BC）=（AB)C

交换律AB=BA、AB=BA

分配律A（BC）=（AB)（AC）

A（BC）=(AB）（AC)

同一/零律AØ=A、AØ=Ø

排中/矛盾律AA=E、AA=Ø

吸收律（大吃小）A(BA)=A、A（BA）=A

德摩律(AB)=AB、（AB)=AB

双重否定A=A

3。3、有穷集的计数

定理3.3。1二个集合的包含排斥原理|

21

AA

｜=|

1

A｜+｜

2

A｜-|

21

AA

｜

3。4、序偶

定义3.4.2令与〈u,v〉是二个序偶，如果x=u、y=v，那么〈x,y>=〈u，v〉即二个序偶相等。

定义3。4.3如果〈x，y〉是序偶，且〈〈x，y>，z〉也是一个序偶，则称〈x，y，z>为三元组。

3。5、直积或笛卡尔积

定义3。5。1令A、B是两个集合，称序偶的集合｛〈x，y〉｜xA，yB｝为A与B的直积或笛卡尔积，

ix

记为AB.

如：A={1,2，3｝，B=｛a,b,c｝则AB={1，2,3}｛a，b,c｝={<1,a〉，<1,b〉，<1,c>，〈2，a>,<2，b〉,<2,c>,〈3，

a〉，〈3,b>,<3,c〉}

直积的性质

1、A（BC）=ABAC

2、A（BC)=ABAC

3、（BC）A=BACA

4、(BC)A=BACA

5、ABACBCCACB

6、AB，CDACBD

定义3.5。2令

n

AAA,...,

21

是n个集合，称n元组的集合｛<

n

xxx,...,,

21

〉|

nn

AxAxAx,...,,

2211

}，为

n

AAA,...,

21

的直积或笛卡尔积,记为

n

AAA...

21

。

3。6、关系

定义3.6。1称直积中部分感兴趣的序偶所组成的集合为“关系",记为R。

如在直积{1，2，3，4,5，6，7，8}{1,2,3，4，5,6,7，8}中,只对第1个元素是第2个元素的因数的序偶感

兴趣，即只对R=｛<1，1>，〈1，2>，<1，3〉,<1，4>,<1，5>,〈1，6〉，〈1，7>，<1,8>，〈2,2〉，<2,4〉，〈2,6〉,

<2,8〉，〈3，3>,〈3，6〉，<4，4>，<4,8〉，<5，5〉,

〈6，6〉,〈7，7〉,<8,8>｝,RAA(A=｛1,2,3，4,5，6,7，8})

定义3.6。2如果序偶或元组属于某个关系R,则称序偶或元组具有关系R。

关系图，关系矩阵

3.7、关系的复合

定义3。7。1若关系FAA，关系GAA,称集合{〈x,y>|t使得〈x,t>F,〈t，y〉G}

为F与G的复合，记为FG.

例题3.7。1令A={1,2,3}，F=｛〈1,1>,〈1,2>}G={〈2,2>，〈1，3>,〈1,1〉}则

解：FG=｛〈1,3〉,〈1,1〉，<1,2>｝,GF={<1,2〉,<1,1>｝，因此关系的复合不满足交换律。

采用复合的定义去计算,只适合于人工计算，为了编程实现，故采用矩阵表示关系。

x

说明:

F

M的第i行与

G

M的第j列相乘时，乘法是合取，加法是析取，如MF的1行与MG

的第3列相乘是：（11）（10)(00),结果为1.

定义3。7。2若关系FAA，称集合{｜

例题3。7.2令A=｛1,2,3},F=｛<1,2〉,<1,3〉，〈2，1〉｝，则1F=｛<2,1〉，<3，1>,〈1,2〉}。

3.8、关系的分类

定义3。8。1若Ax都有〈x,x>R，则R是自反关系。（自己到自己的关系全属于R）

定义3。8。2若Ax都有〈x，x>R,则R是反自反的。（自己到自己的关系全不属于R）

定义3.8。4如果所有形如

记为

A

I。

对于恒等关系而言，其关系矩阵是单位矩阵，即其主对角线全是1，其他位置全是0，对关系图是每个点都有

自旋,仅只有自旋，没有其他边。

定义3.8。5令关系RAA，如果当

定义3.8.6令关系RA



A，如果当〈x，y〉



R且x



y时R，则称R为反对称关系。

定义3.8.8令关系RA



A，若当〈x,y>



R，〈y,z>



R时有〈x,z〉



R，则称R为可传递关系.

从RR的关系矩阵可知，其非0元素在R的关系矩阵都出现，即

RRR

MM



，凡满足这个不等式的关系，

肯定为可传递关系。

xi

所以不可传递。

从RR的关系矩阵可知，其非0元素出现在(1,1），(1,3）,(2,2)，(2，4），在R的关系矩

阵都没出现,不满足

RRR

MM



，不可传递关系.

3.9、关系的闭包

将关系矩阵的主角线上全部变成1，即得到其自反闭包的关系矩阵，从而可得到其自反闭包。

3.10、等价关系与集合的划分

定义3。10。1设RA



A，如果R是自反、对称、可传递的关系则称为等价关系。

xii

定义3。10。2设RAA,如果R是等价关系,BA,B中任意二个元素之间都有关系R，则B是一个等

价类。

定义3.10。3设RAA，R是等价关系，

k

AAA,...,,

10

是基于R得到的等价类,则称集合｛

k

AAA,...,,

10

}

为A关于R的商集，记为A/R。

定义3.10.3若

110

,...,,

k

AAA是A的子集，若ji时



ji

AA

,并且

110

...





k

AAAA,

则称

k

AAA,...,,

10

是A的一个划分。

定理3。10。1设RAA，R是等价关系,

110

,...,,

k

AAA是利用R得到的k个不同的等价类,则

110

,...,,

k

AAA为集合A的划分。

定理3。10。2设

110

,...,,

k

AAA是A的划分,R=

111100

...





kk

AAAAAA，则R是等价

关系.

3.11、偏序关系

定义3.11.1设RAA，如果R是自反、反对称、可传递的关系则称为偏序关系.

如：R是实数中小于等于关系,则R是偏序关系。

定义3。11。2设RAA，R偏序关系，x与y是A中的元素，若序偶〈x，y〉与至少有一个

在R中,则称x与y可比.

定义3。11.3设RAA，R偏序关系，若A中任意二个元素都可比，则称A为全序关系或线序关系.

定义3。11。4设RAA，R偏序关系，将关系图绘制成所有箭头都朝上，然后去掉所有箭头、去掉自旋

边、去掉复合边，得到关系图的简化形式，称为哈斯图.

定义3。11.5在哈斯图中，如果某个元素y在元素x的直接上方,则称y盖住了x。记COVA=｛〈x,y〉｝

定义3.11.6设RAA，R偏序关系，将偏序关系与集合A一块称为偏序集，记为〈A，R〉，表示是A上

的偏序关系。以后说偏序关系时，可简单地说偏序集。

定义3。11.7在偏序集中，BA，yB，若Bx都有

B中每个元素都可比，并且都比其大。

定义3。11.8在偏序集〈A,R〉中,BA，yB，若Bx都有

中每个元素都可比，并且都比其小。

一个子集中没有最大元或最小元时,可能存在极大元或极小元.

定义3。11。9在偏序集

B中不存在比y“大"的元素。即极大元与B中有些元素是否可比不做要求。

定义3.11.10在偏序集〈A,R>中，BA，y



B，若不存在x



B都有



R，则称y是极小元，不存在

比y小的元素。即极小元与B中元素是否可比不做要求。

定义3.11.11在偏序集〈A，R>中,BA，y



B，若任意x



B都有〈x，y〉



R,则称y是B的上界.与B中

每个元素都可比，并且都B中的元素大。

3。12、其它关系

定义3。6。1给定集合A上的关系ρ，若ρ是自反的、对称的,则称ρ是A上的相容关系。

xiii

定义3。6.3给定非空集合A,设有集合S={

n

SSS,...,,

21

},其中AS

i

且

i

S，i=1，2,…，m，且

)(jiSS

ji

,则称集合S称作A的覆盖。

定理3。6.1给定集合A的覆盖，

n

SSS,...,,

21

，由它确定的关系:

nn

SSSS...

11

是相容关系.

定义3。7。1设R为定义在集合A上的一个关系，若R是自反的，对称的，传递的，则R称为等价关系。（显

然等价关系一定是相容关系)。

定义3。7.2设给定非空集合A,若有集合S={

n

SSS,...,,

21

｝，其中AS

i

且

i

S（i=1,2，…,m)，且有

)(jiSS

ji

,同时有

AS

i

m

i



1

，则称S为A的一个划分.（所有子集的并为A,且子集的交为空，

则这些子集组成的集合为A的一个划分，覆盖中,子集的交集可不为空）

等价类

商集

偏序关系（自反性，反对称性，传递性),A，哈斯图，可比的，元素y盖住元素x,全序关系，极大元,极

小元，最大元，最小元

拟序关系（反自反的，传递的),A

第四章代数系统

定义4。3.1设°是集合S上的二元运算，若Syx,都有x°y=y°x，则称°在S上是可交换的,或者

说运算°在S上满足交换律。

定义4.3。2设°是集合S上的二元运算,若Syx,都有(x°y）°z=x°(y°z），则称°在S上是可结合

的，或者说运算°在S上满足结合律。

定义4.3.3设°是集合S上的二元运算，若Sx都有x°x=x，则称°在S上是幂等的,或说运算°在S

上满足幂等律。

定义4。3.4设°与*是集合S上的二种运算，若Syx,都有x*(y°z）=(x＊y)°(x*z)与（y°z)＊x=

（y*x)°（z*x)，则称＊对°是可分配的。

定义4。3.5设°与*是集合S上的二种可交换的二元运算,若Syx,都有x＊（x°y)=x与x°（x＊y）

=x则称*与°是满足吸收律，内外二种运算不一样，运算符内外各出现一次，以多吃少.

广群：

半群:

xiv

群:

子群：