1
离散数学
2
主要内容
? 数理逻辑
? 集合论
? 代数结构
? 图论
? 组合分析初步
? 形式语言和自动机初步
3
教材与教学参考书
? 教材,
?耿素云、屈婉玲、张立昂，离散数学（第三
版），清华大学出版社,2004,
? 教学参考书,
?屈婉玲、耿素云、张立昂，离散数学题解（修
订版），清华大学出版社,2004,
4
数理逻辑部分
?第 1章 命题逻辑
?第 2章 一阶逻辑
5
第 1章 命题逻辑
1.1 命题符号化及联结词
1.2 命题公式及分类
1.3 等值演算
1.4 对偶与范试
1.5 推理理论
6
1.1 命题符号化及联结词
? 命题与真值
? 原子命题
? 复合命题
? 命题常项
? 命题变项
? 联结词
7
命题与真值
命题, 判断结果惟一的陈述句
命题的真值, 判断的结果
真值的取值, 真与假
真命题, 真值为真的命题
假命题, 真值为假的命题
注意, 感叹句, 祈使句, 疑问句都不是命题
陈述句中的悖论以及判断结果不惟一确定的也不是
命题
8
例 下列句子中那些是命题？
(1) 是无理数,
(2) 2 + 5 ＝ 8,
(3) x + 5 ＞ 3,
(4) 你有铅笔吗？
(5) 这只兔子跑得真快呀 ！
(6) 请不要讲话 ！
(7) 我正在说谎话,
真命题
假命题
真值不确定
疑问句
感叹句
祈使句
悖论
(3)~(7)都不是命题
2
9
命题的分类
简单命题 (原子命题 ),
简单陈述句构成的命题
复合命题,
由简单命题与联结词按一定规则复合
而成的命题
10
简单命题符号化
2
用小写英文字母 p,q,r,…,pi,qi,ri (i≥ 1）表示
简单命题
用, 1”表示真, 用, 0”表示假
例如, 令
p,是有理数, 则 p 的真值为 0
q,2 + 5 = 7，则 q 的真值为 1
11
联结词与复合命题
1.否定式与否定联结词, ?”
定义 设 p为命题, 复合命题, 非 p”（ 或, p的否定, ）
称
为 p的 否定式, 记作 ?p,符号 ?称作 否定联结词, 并规
定 ?p 为真当且仅当 p为假
2.合取式与合取联结词, ∧,
定义 设 p,q为二命题,复合命题, p并且 q”(或, p与 q”)称
为 p与 q的 合取式, 记作 p∧ q,∧ 称作 合取联结词, 并规
定 p∧ q为真当且仅当 p与 q同时为真
注意：描述合取式的灵活性与多样性
分清简单命题与复合命题
12
例 将下列命题符号化,
(1) 王晓既用功又聪明,
(2) 王晓不仅聪明, 而且用功,
(3) 王晓虽然聪明, 但不用功,
(4) 张辉与王丽都是三好生,
(5) 张辉与王丽是同学,
解 令 p：王晓用功, q：王晓聪明, 则
(1) p∧ q
(2) p∧ q
(3) p∧ ?q,
13
例 (续 )
令 r, 张辉是三好学生, s,王丽是三好学生
(4) r∧ s,
(5) 令 t, 张辉与王丽是同学, t 是简单命题,
说明,
(1)~(4)说明描述合取式的灵活性与多样性,
(5) 中, 与, 联结的是句子的主语成分, 因而 (5)
中句子是简单命题,
14
联结词与复合命题 (续 )
定义 设 p,q为二命题, 复合命题, p或 q”称作 p与 q
的 析取式, 记作 p∨ q,∨ 称作 析取联结词, 并规
定 p∨ q为假当且仅当 p与 q同时为假,
例 将下列命题符号化
(1) 2或 4是素数,
(2) 2或 3是素数,
(3) 4或 6是素数,
(4) 小元元只能拿一个苹果或一个梨,
(5) 王晓红生于 1975年或 1976年,
3.析取式与析取联结词,∨,
15
解 令 p:2是素数,q:3是素数,r:4是素数,s:6是素数,
则 (1),(2),(3) 均为相容或,
分别符号化为, p∨ r,p∨ q,r∨ s,
它们的真值分别为 1,1,0,
而 (4),(5) 为排斥或,
令 t,小元元拿一个苹果,u:小元元拿一个梨,
则 (4) 符号化为 (t∧ ?u) ∨ (?t∧ u),
令 v,王晓红生于 1975年,w:王晓红生于 1976年,
则 (5) 既可符号化为 (v∧ ?w)∨ (?v∧ w),又可
符号化为 v∨ w,为什么?
16
联结词与复合命题 (续 )
定义 设 p,q为二命题, 复合命题, 如果 p,则 q” 称
作 p与 q的 蕴涵式, 记作 p?q,并称 p是蕴涵式的
前件, q为蕴涵式的 后件, ?称作 蕴涵联结词, 并
规定, p?q为假当且仅当 p 为真 q 为假,
4.蕴涵式与蕴涵联结词,?”
17
p?q 的逻辑关系,q 为 p 的必要条件
,如果 p,则 q, 的不同表述法很多,
若 p,就 q
只要 p,就 q
p 仅当 q
只有 q 才 p
除非 q,才 p 或 除非 q,否则非 p,
当 p 为假时, p?q 为真
常出现的错误：不分充分与必要条件
联结词与复合命题 (续 )
18
例 设 p:天冷, q:小王穿羽绒服,
将下列命题符号化
(1) 只要天冷, 小王就穿羽绒服,
(2) 因为天冷, 所以小王穿羽绒服,
(3) 若小王不穿羽绒服, 则天不冷,
(4) 只有天冷, 小王才穿羽绒服,
(5) 除非天冷, 小王才穿羽绒服,
(6) 除非小王穿羽绒服, 否则天不冷,
(7) 如果天不冷, 则小王不穿羽绒服,
(8) 小王穿羽绒服仅当天冷的时候,
注意,p?q 与 ?p??q 等值（真值相同）
p?q
p?q
p?q
p?q
q?p
q?p
q?p
q?p
19
联结词与复合命题 (续 )
定义 设 p,q为二命题, 复合命题, p当且仅当 q”称
作 p与 q的 等价式, 记作 p?q,?称作 等价联结词,
并 p?q规为真当且仅当 p与 q同时为真或同时为假,
说明,
(1) p?q 的逻辑关系,p与 q互为充分必要条件
(2) p?q为真当且仅当 p与 q同真或同假
5.等价式与等价联结词,?”
20
例 求下列复合命题的真值
(1) 2 + 2 ＝ 4 当且仅当 3 + 3 ＝ 6,
(2) 2 + 2 ＝ 4 当且仅当 3 是偶数,
(3) 2 + 2 ＝ 4 当且仅当 太阳从东方升起,
(4) 2 + 2 ＝ 4 当且仅当 美国位于非洲,
(5) 函数 f (x) 在 x0 可导的充要条件是它在 x0
连续,
它们的真值分别为 1,0,1,0,0,
21
联结词与复合命题 (续 )
以上给出了 5个联结词,?,?,?,?,?，组成
一个联结词集合 {?,?,?,?,?},
联结词的优先顺序为,?,?,?,?,?; 如果出
现的联结词同级，又无括号时，则按从左到右
的顺序运算 ; 若遇有括号时，应该先进行括号
中的运算,
注意, 本书中使用的 括号全为园括号,
22
1.2 命题公式及分类
?命题变项与合式公式
?公式的赋值
?真值表
?命题的分类
重言式
矛盾式
可满足式
23
命题变项与合式公式
命题常项,简单命题
命题变项,真值不确定的陈述句
定义 合式公式 (命题公式,公式 ) 递归定义如下,
(1) 单个命题常项或变项 p,q,r,…,pi,qi,ri,…,0,1
是 合式公式
(2) 若 A是合式公式, 则 (?A)也是合式公式
(3) 若 A,B是合式公式, 则 (A?B),(A?B),(A?B),
(A?B)也是合式公式
(4) 只有有限次地应用 (1)~(3)形成的符号串才是
合式公式
说明, 元语言与对象语言,外层括号可以省去
24
合式公式的层次
定义
(1) 若公式 A是单个的命题变项,则称 A为 0层公式,
(2) 称 A是 n+1(n≥0)层公式是指下面情况之一,
(a) A=?B,B是 n层公式；
(b) A=B?C,其中 B,C分别为 i层和 j层公式, 且
n=max(i,j)；
(c) A=B?C,其中 B,C的层次及 n同 (b)；
(d) A=B?C,其中 B,C的层次及 n同 (b)；
(e) A=B?C,其中 B,C的层次及 n同 (b),
25
合式公式的层次 (续 )
例如 公式
p 0层
?p 1层
?p?q 2层
?(p?q)?r 3层
((?p?q) ?r)?(?r?s) 4层
26
公式的赋值
定义 给公式 A中的命题变项 p1,p2,…,pn指定
一组真值称为对 A的一个 赋值 或 解释
成真赋值, 使公式为真的赋值
成假赋值, 使公式为假的赋值
说明,
赋值 ?=?1?2… ?n之间不加标点符号, ?i=0或 1,
A中仅出现 p1,p2,…,pn,给 A赋值 ?1?2… ?n是
指 p1=?1,p2=?2,…,pn=?n
A中仅出现 p,q,r,…,给 A赋值 ?1?2?3… 是指
p=?1,q=?2,r=?3 …
含 n个变项的公式有 2n个赋值,
27
真值表
真值表, 公式 A在所有赋值下的取值情况列成的表
例 给出公式的真值表
A= (q?p) ?q?p 的 真值表
p q q?p (q?p) ?q (q?p) ?q?p
0 0
0 1
1 0
1 1
1
0
1
1
0
0
0
1
1
1
1
1
28
例 B = ? (?p?q) ?q 的 真值表
p q ?p ?p?q ? (?p?q) ? (?p?q) ?q
0 0
0 1
1 0
1 1
1
1
0
0
1
1
0
1
0
0
1
0
0
0
0
0
实例
29
例 C= (p?q) ??r 的 真值表
p q r p?q ?r (p?q)??r
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0
0
1
1
1
1
1
1
1
0
1
0
1
0
1
0
1
1
1
0
1
0
1
0
30
公式的类型
定义 设 A为一个命题公式
(1) 若 A无成假赋值, 则称 A为 重言式 (也称 永真式 )
(2) 若 A无成真赋值, 则称 A为 矛盾式 (也称 永假式 )
(3) 若 A不是矛盾式, 则称 A为 可满足式
注意：重言式是可满足式, 但反之不真,
上例中 A为重言式,B为矛盾式,C为可满足式
A= (q?p)?q?p,B =?(?p?q)?q,C= (p?q)??r
离散数学
2
主要内容
? 数理逻辑
? 集合论
? 代数结构
? 图论
? 组合分析初步
? 形式语言和自动机初步
3
教材与教学参考书
? 教材,
?耿素云、屈婉玲、张立昂，离散数学（第三
版），清华大学出版社,2004,
? 教学参考书,
?屈婉玲、耿素云、张立昂，离散数学题解（修
订版），清华大学出版社,2004,
4
数理逻辑部分
?第 1章 命题逻辑
?第 2章 一阶逻辑
5
第 1章 命题逻辑
1.1 命题符号化及联结词
1.2 命题公式及分类
1.3 等值演算
1.4 对偶与范试
1.5 推理理论
6
1.1 命题符号化及联结词
? 命题与真值
? 原子命题
? 复合命题
? 命题常项
? 命题变项
? 联结词
7
命题与真值
命题, 判断结果惟一的陈述句
命题的真值, 判断的结果
真值的取值, 真与假
真命题, 真值为真的命题
假命题, 真值为假的命题
注意, 感叹句, 祈使句, 疑问句都不是命题
陈述句中的悖论以及判断结果不惟一确定的也不是
命题
8
例 下列句子中那些是命题？
(1) 是无理数,
(2) 2 + 5 ＝ 8,
(3) x + 5 ＞ 3,
(4) 你有铅笔吗？
(5) 这只兔子跑得真快呀 ！
(6) 请不要讲话 ！
(7) 我正在说谎话,
真命题
假命题
真值不确定
疑问句
感叹句
祈使句
悖论
(3)~(7)都不是命题
2
9
命题的分类
简单命题 (原子命题 ),
简单陈述句构成的命题
复合命题,
由简单命题与联结词按一定规则复合
而成的命题
10
简单命题符号化
2
用小写英文字母 p,q,r,…,pi,qi,ri (i≥ 1）表示
简单命题
用, 1”表示真, 用, 0”表示假
例如, 令
p,是有理数, 则 p 的真值为 0
q,2 + 5 = 7，则 q 的真值为 1
11
联结词与复合命题
1.否定式与否定联结词, ?”
定义 设 p为命题, 复合命题, 非 p”（ 或, p的否定, ）
称
为 p的 否定式, 记作 ?p,符号 ?称作 否定联结词, 并规
定 ?p 为真当且仅当 p为假
2.合取式与合取联结词, ∧,
定义 设 p,q为二命题,复合命题, p并且 q”(或, p与 q”)称
为 p与 q的 合取式, 记作 p∧ q,∧ 称作 合取联结词, 并规
定 p∧ q为真当且仅当 p与 q同时为真
注意：描述合取式的灵活性与多样性
分清简单命题与复合命题
12
例 将下列命题符号化,
(1) 王晓既用功又聪明,
(2) 王晓不仅聪明, 而且用功,
(3) 王晓虽然聪明, 但不用功,
(4) 张辉与王丽都是三好生,
(5) 张辉与王丽是同学,
解 令 p：王晓用功, q：王晓聪明, 则
(1) p∧ q
(2) p∧ q
(3) p∧ ?q,
13
例 (续 )
令 r, 张辉是三好学生, s,王丽是三好学生
(4) r∧ s,
(5) 令 t, 张辉与王丽是同学, t 是简单命题,
说明,
(1)~(4)说明描述合取式的灵活性与多样性,
(5) 中, 与, 联结的是句子的主语成分, 因而 (5)
中句子是简单命题,
14
联结词与复合命题 (续 )
定义 设 p,q为二命题, 复合命题, p或 q”称作 p与 q
的 析取式, 记作 p∨ q,∨ 称作 析取联结词, 并规
定 p∨ q为假当且仅当 p与 q同时为假,
例 将下列命题符号化
(1) 2或 4是素数,
(2) 2或 3是素数,
(3) 4或 6是素数,
(4) 小元元只能拿一个苹果或一个梨,
(5) 王晓红生于 1975年或 1976年,
3.析取式与析取联结词,∨,
15
解 令 p:2是素数,q:3是素数,r:4是素数,s:6是素数,
则 (1),(2),(3) 均为相容或,
分别符号化为, p∨ r,p∨ q,r∨ s,
它们的真值分别为 1,1,0,
而 (4),(5) 为排斥或,
令 t,小元元拿一个苹果,u:小元元拿一个梨,
则 (4) 符号化为 (t∧ ?u) ∨ (?t∧ u),
令 v,王晓红生于 1975年,w:王晓红生于 1976年,
则 (5) 既可符号化为 (v∧ ?w)∨ (?v∧ w),又可
符号化为 v∨ w,为什么?
16
联结词与复合命题 (续 )
定义 设 p,q为二命题, 复合命题, 如果 p,则 q” 称
作 p与 q的 蕴涵式, 记作 p?q,并称 p是蕴涵式的
前件, q为蕴涵式的 后件, ?称作 蕴涵联结词, 并
规定, p?q为假当且仅当 p 为真 q 为假,
4.蕴涵式与蕴涵联结词,?”
17
p?q 的逻辑关系,q 为 p 的必要条件
,如果 p,则 q, 的不同表述法很多,
若 p,就 q
只要 p,就 q
p 仅当 q
只有 q 才 p
除非 q,才 p 或 除非 q,否则非 p,
当 p 为假时, p?q 为真
常出现的错误：不分充分与必要条件
联结词与复合命题 (续 )
18
例 设 p:天冷, q:小王穿羽绒服,
将下列命题符号化
(1) 只要天冷, 小王就穿羽绒服,
(2) 因为天冷, 所以小王穿羽绒服,
(3) 若小王不穿羽绒服, 则天不冷,
(4) 只有天冷, 小王才穿羽绒服,
(5) 除非天冷, 小王才穿羽绒服,
(6) 除非小王穿羽绒服, 否则天不冷,
(7) 如果天不冷, 则小王不穿羽绒服,
(8) 小王穿羽绒服仅当天冷的时候,
注意,p?q 与 ?p??q 等值（真值相同）
p?q
p?q
p?q
p?q
q?p
q?p
q?p
q?p
19
联结词与复合命题 (续 )
定义 设 p,q为二命题, 复合命题, p当且仅当 q”称
作 p与 q的 等价式, 记作 p?q,?称作 等价联结词,
并 p?q规为真当且仅当 p与 q同时为真或同时为假,
说明,
(1) p?q 的逻辑关系,p与 q互为充分必要条件
(2) p?q为真当且仅当 p与 q同真或同假
5.等价式与等价联结词,?”
20
例 求下列复合命题的真值
(1) 2 + 2 ＝ 4 当且仅当 3 + 3 ＝ 6,
(2) 2 + 2 ＝ 4 当且仅当 3 是偶数,
(3) 2 + 2 ＝ 4 当且仅当 太阳从东方升起,
(4) 2 + 2 ＝ 4 当且仅当 美国位于非洲,
(5) 函数 f (x) 在 x0 可导的充要条件是它在 x0
连续,
它们的真值分别为 1,0,1,0,0,
21
联结词与复合命题 (续 )
以上给出了 5个联结词,?,?,?,?,?，组成
一个联结词集合 {?,?,?,?,?},
联结词的优先顺序为,?,?,?,?,?; 如果出
现的联结词同级，又无括号时，则按从左到右
的顺序运算 ; 若遇有括号时，应该先进行括号
中的运算,
注意, 本书中使用的 括号全为园括号,
22
1.2 命题公式及分类
?命题变项与合式公式
?公式的赋值
?真值表
?命题的分类
重言式
矛盾式
可满足式
23
命题变项与合式公式
命题常项,简单命题
命题变项,真值不确定的陈述句
定义 合式公式 (命题公式,公式 ) 递归定义如下,
(1) 单个命题常项或变项 p,q,r,…,pi,qi,ri,…,0,1
是 合式公式
(2) 若 A是合式公式, 则 (?A)也是合式公式
(3) 若 A,B是合式公式, 则 (A?B),(A?B),(A?B),
(A?B)也是合式公式
(4) 只有有限次地应用 (1)~(3)形成的符号串才是
合式公式
说明, 元语言与对象语言,外层括号可以省去
24
合式公式的层次
定义
(1) 若公式 A是单个的命题变项,则称 A为 0层公式,
(2) 称 A是 n+1(n≥0)层公式是指下面情况之一,
(a) A=?B,B是 n层公式；
(b) A=B?C,其中 B,C分别为 i层和 j层公式, 且
n=max(i,j)；
(c) A=B?C,其中 B,C的层次及 n同 (b)；
(d) A=B?C,其中 B,C的层次及 n同 (b)；
(e) A=B?C,其中 B,C的层次及 n同 (b),
25
合式公式的层次 (续 )
例如 公式
p 0层
?p 1层
?p?q 2层
?(p?q)?r 3层
((?p?q) ?r)?(?r?s) 4层
26
公式的赋值
定义 给公式 A中的命题变项 p1,p2,…,pn指定
一组真值称为对 A的一个 赋值 或 解释
成真赋值, 使公式为真的赋值
成假赋值, 使公式为假的赋值
说明,
赋值 ?=?1?2… ?n之间不加标点符号, ?i=0或 1,
A中仅出现 p1,p2,…,pn,给 A赋值 ?1?2… ?n是
指 p1=?1,p2=?2,…,pn=?n
A中仅出现 p,q,r,…,给 A赋值 ?1?2?3… 是指
p=?1,q=?2,r=?3 …
含 n个变项的公式有 2n个赋值,
27
真值表
真值表, 公式 A在所有赋值下的取值情况列成的表
例 给出公式的真值表
A= (q?p) ?q?p 的 真值表
p q q?p (q?p) ?q (q?p) ?q?p
0 0
0 1
1 0
1 1
1
0
1
1
0
0
0
1
1
1
1
1
28
例 B = ? (?p?q) ?q 的 真值表
p q ?p ?p?q ? (?p?q) ? (?p?q) ?q
0 0
0 1
1 0
1 1
1
1
0
0
1
1
0
1
0
0
1
0
0
0
0
0
实例
29
例 C= (p?q) ??r 的 真值表
p q r p?q ?r (p?q)??r
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0
0
1
1
1
1
1
1
1
0
1
0
1
0
1
0
1
1
1
0
1
0
1
0
30
公式的类型
定义 设 A为一个命题公式
(1) 若 A无成假赋值, 则称 A为 重言式 (也称 永真式 )
(2) 若 A无成真赋值, 则称 A为 矛盾式 (也称 永假式 )
(3) 若 A不是矛盾式, 则称 A为 可满足式
注意：重言式是可满足式, 但反之不真,
上例中 A为重言式,B为矛盾式,C为可满足式
A= (q?p)?q?p,B =?(?p?q)?q,C= (p?q)??r
