离散数学笔记

第一章 命题逻辑

合取

析取

定义 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析取范式与合取范式

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

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)、 函数常元(如表示

的 f(x,y))、 谓词常元(如表示人类的 H(x))。

定义 2.2.2、逻辑符号：个体变元、量词(∀∃)、联结词(﹁∨∧→↔)、逗号、括号。

定义 2.2.3、项的定义：个体常元、变元及其函数式的表达式称为项(item)。

定义 2.2.4、原子公式：设 R(

)是 n 元谓词，

是项，则 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 自由变元：谓词公式中与任何量词都无关的量词，称为自由变元，它的每次出现称为自由出现。一个公式的个体变元不是约束变元，就是自由变元。

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

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

从本例(已省)可知， 不同的公式在同一个解释下， 其真值可能存在， 也可能不存在， 但是对于没有自由变元的公式(闭公式)，不论做何种解释，其真值肯定存在

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

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

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

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

定义 2.2.13 代换实例 设

是命题公式

中的命题变元，

是 n 个谓

词公式，用

代替公式

中的

后得到公式 A，则称 A 为

的代换实例。

如 A(x)∨﹁A(x)，∀xA(x) ∨﹁∀ xA(x)可看成 p ∨﹁ p 的代换实例，A(x) ∧﹁A(x)，∀xA(x) ∧﹁ ∀x A(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={

}，则∀ xA(x) ó A(

)∧A(

)∧…∧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)∨B 2、∀/∃(A(x)∧B) ó ∀/∃A(x)∧B

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

六、置换规则

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

七、约束变元改名规则

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

例

证明步骤：

2.4、谓词公式的范式

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

(1)剔除不起作用的量词；

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

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

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

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

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

2.5、谓词推理

定义 2.5.1 若在各种解释下

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

可推出结论 B。

定义 2.5.2 在所有使

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

可推出结论 B。

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

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

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

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

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。

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 二个集合的包含排斥原理 |

| = |

| + |

| - |

|

3.4、序偶

定义 3.4.2 令<x,y>与<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的直积或笛卡尔积，记为 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 个集合，称n元组的集合{<

>|

}，为

的直积或笛卡尔积，记为

。

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>}， 因此关系的复合不满足交换律。

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

说明：

的第 i 行与

的第 j 列相乘时，乘法是合取

，加法是析取

，如 MF 的 1 行与 MG

的第 3 列相乘是：(1

1)

(1

0)

(0

0)，结果为 1。

定义 3.7.2 若关系 F

A

A，称集合{<y,x>|<x,y>

F }为 F 的逆，记为

例题 3.7.2 令 A={1,2,3}，F={<1,2>,<1,3>,<2,1>}，则

={ <2,1>,<3,1>,<1,2>}。

3.8、关系的分类

定义 3.8.1 若

都有<x,x>

R，则R是自反关系。(自己到自己的关系全属于R)

定义 3.8.2 若

都有<x,x>

R,则 R 是反自反的。(自己到自己的关系全不属于R)

定义 3.8.4 如果所有形如<x,x>的序偶都在关系 R 中， R 也只有这种形式的序偶， 则称 R为恒等关系，记为

。

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

定义 3.8.5 令关系R

A

A，如果当<x,y>

R 时<y,x>

R，则称 R 为对称关系。

定义 3.8.6 令关系R

A

A，如果当<x,y>

R 且x

y时<y,x>

R， 则称 R 为反对称关系。

定义 3.8.8 令关系R

A

A，若当<x,y>

R,<y,z>

R时有<x,z>

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

从R

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

，凡满足这个不等式的关系，肯定为可传递关系。

所以不可传递。

从R

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

阵都没出现，不满足

，不可传递关系。

3.9、关系的闭包

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

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

定义 3.10.1 设R

A

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

定义 3.10.2 设R

A

A，如果 R 是等价关系， B

A， B 中任意二个元素之间都有关系R，则 B 是一个等价类。

定义 3.10.3 设R

A

A，R是等价关系，

是基于 R 得到的等价类，则称集合{

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

定义 3.10.3 若

是 A 的子集，若

时

，并且

，则称

是A的一个划分。

定理 3.10.1 设R

A

A，R 是等价关系，

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

为集合 A 的划分。

定理 3.10.2 设

是A 的划分， R=

， 则 R 是等价关系。

3.11、偏序关系

定义 3.1 1.1 设R

A

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

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

定义 3.1 1.2 设R

A

A，R 偏序关系，x 与 y 是 A 中的元素，若序偶<x,y>与<y,x>至少有一个在 R 中，则称 x 与 y 可比。

定义 3.1 1.3 设R

A

A，R 偏序关系，若 A 中任意二个元素都可比，则称 A 为全序关系或线序关系。

定义 3.1 1.4 设R

A

A，R 偏序关系，将关系图绘制成所有箭头都朝上，然后去掉所有箭头、去掉自旋边、去掉复合边，得到关系图的简化形式，称为哈斯图。

定义 3.1 1.5 在哈斯图中，如果某个元素 y 在元素 x 的直接上方，则称 y 盖住了 x。记COVA={<x,y>}

定义 3.1 1.6 设R

A

A，R 偏序关系，将偏序关系与集合 A 一块称为偏序集，记为<A,R>，表示是 A 上的偏序关系。以后说偏序关系时，可简单地说偏序集<A,R>。

定义 3.1 1.7 在偏序集<A,R>中，B

A，y

B，若

都有<x,y>

R，则称 y 是最大元。即最大元与 B 中每个元素都可比，并且都比其大。

定义 3.1 1.8 在偏序集<A,R>中，B

A，y

B，若

都有<y,x>

R，则称 y 是最小元。即最小元与 B 中每个元素都可比，并且都比其小。

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

定义 3.1 1.9 在偏序集<A,R>中，B

A，y

B，若不存在 x

B 使得<y,x>

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

定义 3.1 1.10 在偏序集<A,R>中，B

A，y

B，若不存在x

B 都有<x,y>

R，则称 y是极小元，不存在比 y 小的元素。即极小元与 B中元素是否可比不做要求。

定义 3.1 1.1 1 在偏序集<A,R>中，B

A，y

B，若任意x

B都有<x,y>

R，则称y是B 的上界。与 B 中每个元素都可比，并且都 B 中的元素大。

3.12、其它关系

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

定义3.6.3 给定非空集合A，设有集合S={

}，其中

且

，i=1,2,…,m,且

，则称集合S称作A的覆盖。

定理3.6.1 给定集合A的覆盖，

，由它确定的关系：

是相容关系。

定义3.7.1 设R为定义在集合A上的一个关系，若R是自反的，对称的，传递的，则R称为等价关系。(显然等价关系一定是相容关系)。

定义3.7.2 设给定非空集合A，若有集合S={

}，其中

且

(i=1,2,…,m)，且有

，同时有

，则称S为A的一个划分。(所有子集的并为A，且子集的交为空，则这些子集组成的集合为A的一个划分，覆盖中，子集的交集可不为空)

等价类

商集

偏序关系(自反性，反对称性，传递性)

，哈斯图，可比的，元素y盖住元素x，全序关系，极大元，极小元，最大元，最小元

拟序关系(反自反的，传递的)

第四章 代数系统

定义 4.3.1 设°是集合 S 上的二元运算，若

都有 x°y=y°x，则称°在 S 上是可交换的，或者说运算°在 S 上满足交换律。

定义 4.3.2 设°是集合 S 上的二元运算，若

都有(x°y)°z=x°(y°z)，则称°在 S上是可结合的,或者说运算°在 S 上满足结合律。

定义 4.3.3 设°是集合 S 上的二元运算，若

都有 x°x=x， 则称°在 S 上是幂等的,或说运算°在 S 上满足幂等律。

定义 4.3.4 设°与*是集合 S 上的二种运算，若

都有 x*(y°z)=(x*y)°(x*z)与(y°z)*x=(y*x)°(z*x)，则称*对°是可分配的。

定义 4.3.5 设°与*是集合 S 上的二种可交换的二元运算，若

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

广群：

半群：

群：

子群：