1. 命题及其表示
1) 判断哪些是命题（悖论，真值不能确定的，非陈述句）
a) 我正在说假话！
b) X=2
c) 今天天气真好啊！
2) 分清简单命题与复合命题
a) 蓝色和黄色可以调配成绿色。
b) 蓝色和黄色是常用的颜色。
3) 区别相容或与排斥或
a) 李和平是山西人或陕西人。
b) 李冰选学英语或法语。
4) 蕴涵式的逻辑关系，准确地找出蕴涵式的前件与后件（只有??才，除非??否则
非??，除非??才??，??仅当??）
a) 除非4是奇数，否则5不是奇数。
b) 只有4是偶数，则5才是偶数。
c) 5是偶数仅当4是奇数。
2. 求复合公式的成真赋值，成假赋值，类型以及真值。（真值表法）
3. 等值式与基本等值式
4. 等值演算，置换规则
5. 重言式与矛盾式的判别法
A为重言式当且仅当A?1, A为矛盾式当且仅当A?0
6. 主析取范式与主合取范式
1) 求公式A的主析取范式的方法与步骤
a) 等值演算法
1）求公式A的析取范式A； '
（1）消去除?，?，?以外公式中出现的所有逻辑联结词。
（2）将否定联结词消去或内移到各命题变元之前。
如，
??A?B?A?B??A?B；
?(A?B)??A??B；
?(A?B)??A??B。
（3）利用分配律、结合律将公式转化为合取范式或析取范式。
如，
P?(Q?R)?(P?Q)?(P?R)；
P?(Q?R)?(P?Q)?(P?R)。
2）除去A中所有永假的析取项；
'3） 若A的某个简单合取式B中不含有某个命题变元p，也不含?p，则将'
B展成形式B?B?1?B?(p??p)?(B?p)?(B??p)
4）将重复出现的命题变元、矛盾式及重复出现的极小项都消去。
5）将极小项按顺序排列。
b) 真值表法
c) 由主合取范式求析取范式
主析取范式的用途
1. 求公式的成真赋值与成假赋值
2. 判断公式的类型
3. 判断公式A与B是否等值。
4. 解实际问题
7. 推理的形式结构（A1?A1?A1
8. 判断推理是否正确的方法
1) 真值表法
2) 等值演算法
3) 主析取范式法
9. 推理定律（9条）
10. 在自然推理系统P中构造证明
直接证明法
附加前提证明法
归谬法
11. 一阶逻辑命题的符号化
a) “D中所有x都有性质F”，符号化为?xF(x)
b) “D中有的x有性质F”，符号化为?xF(x)
c) “对D中所有x而言，如果有性质F，x就有性质G”，符号化为A1?B?1）
?x(F(x)?G(x))
d) “对D中有的x有性质F且有性质G”，符号化为?x(F(x)?G(x))
e) “对于D中所有x,y而言，若x有性质F，y有性质G，则x与y就有关系H”,
符号化为?x?y(F(x)?G(x)?H(x,y))
f) “对于D中所有x而言，若x有性质F，就存在y有性质G，使得x与y有关
系H”，符号化为?x(F(x)??y(G(x)?H(x,y))
g) “存在着D中x有性质F，并且对D中所有y而言，如果y有性质G，则x
与y就有关系H”，符号化为?x(F(x)??y(G(x)?H(x,y))
12. 一阶逻辑公式及解释
13. 一阶逻辑等值式与置换规则
1) 等值式
2) 基本的等值式
a) 命题逻辑中基本等值式的代换实例。
b) 一阶逻辑中重要的等值式
14. 求一阶逻辑前束范式
15. 约束变元与自由变元
16. 一阶逻辑的推理理论（A1?A1?A1A1?B?1）
17. 一阶逻辑中重要的推理定律
18. 自然推理系统F
第二部分
1. 集合的基本概念
2. 集合的基本运算
3. 有穷集合元素的计数（文氏图或包含排斥原理）
4. 鸽笼原理的应用
5. 集合恒等式（基本证明方法）
a) 命题演算法
b) 利用包含哦传递性
c) 反证法
命题演算证明法的书写规范 (以下的X和Y代表集合公式)
（1）证X?Y
任取x，
x?X ? … ? x?Y
（2）证X=Y
方法一 分别证明X?Y和Y?X
方法二
任取x，
x?X ? … ? x?Y
注意：在使用方法二的格式时，必须保证每步推理都是充分必要的
6. 有序对与笛卡尔积
7. 二元关系
8. 关系的表示（关系矩阵，关系图）
9. 关系的性质（自反，反自反，对称，反对称，传递）表格
（1） 若?x(x∈A→<x,x>?R), 则称R在A上是自反的
（2） 若?x(x∈A→<x,x>?R), 则称R在A上是反自反的.
（3） 若?x?y(x,y∈A<x,y>∈R→<y,x>∈R), 则称R为A上对称的关系.
（4） 若?x?y(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y), 则称R为A上的反对称关系.
（5） ?x?y?z(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R), 则称R是A上的传递关系.。 证明：R在A上自反
任取x，有
x∈A ? ………………… ?<x,x>?R
前提 推理过程 结论
R在A上对称
任取<x,y>，有
<x,y>?R ? ………………… ?<y,x>?R
R在A上反对称
任取<x,y>，有
<x,y>?R ∧<y,x>?R ? ………………… ? x=y
R在A上传递
任取<x,y>，<y,z>有
<x,y>?R ∧<y,z>?R ? ………………… ? <x,z>?R
10. 关系运算的定义（定义域，值域，域，逆，右复合，限制，像，幂，自反闭包，对称闭
包，传递闭包及其构造）
11. 关系运算的性质
12. 等价关系与划分（等价关系证明，等价类，等价类的性质，商集，集合A的划分，一
一对应）
13. 偏序关系与偏序集（哈斯图，特殊元素）
14. 函数（满射，单射，双射
*第三部分
1. 格的定义
1） 格的偏序集定义
2） 格的代数系统定义
2. 格的性质
对偶原理
格的运算性质
偏序与运算的关系
保序性质
2. 子格与子格的判别
子格判别：S非空，且S关于格L中的运算?和?封闭。
3. 分配格，有界格，有补格的概念
分配格的判别方法：
1) 根据定义判别：注意在证明L为分配格时，只须证明其中的一个等式即可
2) 设L是格，则L是分配个当且仅当L不含有与钻石格或五角格同构的子格。
3) 格L是分配格当且仅当?a,b,c?L,a?b?a?c且a?b?a?c?b?c
第四部分
1.
2.
3.
4.
5.
6.
7.
8. 图的定义（平凡图，零图，基图，完全图与竞赛图，子图，补图） 图的矩阵表示（关联矩阵，邻接矩阵，可达矩阵），通路与回路的计数 *无向图的边连通度，点连通度，边割集，点割集 二部图定义及判别 结点的度数及其相关性质（握手定理）； 树、非同构树、生成树、最小生成树 有关树的几个等价命题及其证明； 最小生成树的Kruscal算法
第二篇：离散数学复习题(请参考课件)
离散数学Part1_数理逻辑部分
1． 将下列命题符号化。P48
（1） 豆沙包是由面粉和红小豆做成的.
（2） 苹果树和梨树都是落叶乔木.
（3） 王小红或李大明是物理组成员.
（4） 王小红或李大明中的一人是物理组成员.
（5） 由于交通阻塞，他迟到了.
（6） 如果交通不阻塞，他就不会迟到.
（7） 他没迟到，所以交通没阻塞.
（8） 除非交通阻塞，否则他不会迟到.
（9） 他迟到当且仅当交通阻塞.
分清复合命题与简单命题
分清相容或与排斥或
分清必要与充分条件及必要充分条件
答案：（1）是简单命题 （2）是合取式
（3）是析取式（相容或） （4）是析取式（排斥或）
请分别写出（1）—（4）的符号化形式
设p: 交通阻塞，q: 他迟到
（5） p®q, （6）Øp®Øq或q®p
（7）Øq®Øp 或p®q, （8）q®p或Øp®Øq
（9）p«q 或Øp«Øq
可见（5）与（7），（6）与（8）相同（等值）
3． 用真值表判断下面公式的类型 P51
（1） pÙrÙØ(q®p)
（2） ((p®q) ®(Øq®Øp)) Úr
（3） (p®q) «(p®r)
按层次写真值表，由最后一列判类型
答案：（1）为矛盾式，（2）为重言式，（3）为可满足式
例 用等值演算法判断下列公式的类型 P59
（1）qÙØ(p®q)
（2）(p®q)«(Øq®Øp)
（3）((pÙq)Ú(pÙØq))Ùr)
解（1）qÙØ(p®q)
Û qÙØ(ØpÚq) （蕴涵等值式）
Û qÙ(pÙØq) （德摩根律）
Û pÙ(qÙØq) （交换律，结合律）
Û pÙ0 （矛盾律）
Û 0 （零律）
由最后一步可知，（1）为矛盾式.
（2）(p®q)«(Øq®Øp)
Û (ØpÚq)«(qÚØp) （蕴涵等值式）
Û (ØpÚq)«(ØpÚq) （交换律）
Û 1
由最后一步可知，（2）为重言式.
问：最后一步为什么等值于1？
说明：（2）的演算步骤可长可短，以上演算最省.
（3）((pÙq)Ú(pÙØq))Ùr)
Û (pÙ(qÚØq))Ùr （分配律）
Û pÙ1Ùr （排中律）
Û pÙr （同一律）
由最后一步可知，（3）不是矛盾式，也不是重言式，它是可满足式，其实101, 111是成真赋值，000, 010等是成假赋值.
总结：从此例可看出
A为矛盾式当且仅当A Û 0
A为重言式当且仅当A Û 1
例 求公式 A=(p®Øq)®r的主析取范式与主合取范式. P71
（1）求主析取范式
(p®Øq)®r
Û (pÙq)Úr （析取范式） ①
(pÙq)
Û (pÙq)Ù(ØrÚr)
Û (pÙqÙØr)Ú(pÙqÙr)
Û m6Úm7 ②
r
Û (ØpÚp)Ù(ØqÚq)Ùr
Û (ØpÙØqÙr)Ú(ØpÙqÙr)Ú(pÙØqÙr)Ú(pÙqÙr)
Û m1Úm3Úm5Úm7 ③
②, ③代入①并排序，得
(p®Øq)®r Û m1Úm3Úm5Ú m6Úm7 （主析取范式）
（2）求A的主合取范式
(p®Øq)®r
Û (pÚr)Ù(qÚr) （合取范式） ①
pÚr
Û pÚ(qÙØq)Úr
Û (pÚqÚr)Ù(pÚØqÚr)
Û M0ÙM2 ②
qÚr
Û (pÙØp)ÚqÚr
Û (pÚqÚr)Ù(ØpÚqÚr)
Û M0ÙM4 ③
②, ③代入①并排序，得
(p®Øq)®r Û M0ÙM2ÙM4 （主合取范式
1． 设A与B均为含n个命题变项的公式，判断下列命题是否为真？ P85
（1） AÛB当且仅当A与B有相同的主析取范式
（2） 若A为重言式，则A的主合取范式为0
（3） 若A为矛盾式，则A的主析取范式为1
（4） 任何公式都能等值地化成{Ù, Ú}中的公式
（5） 任何公式都能等值地化成{Ø, ®, Ù}中的公式
（1）为真，这是显然的
（2）为假. 注意, 任何公式与它的主范式是等值的，显然重言式不能与0等值。重言式的主合取范式不含极大项，因而主合取范式为1.
（3）的分析类似于（2），矛盾式的主合取范式为0.
（4）为假，因为{Ù, Ú}不是完备集，比如矛盾式Ø(p®q)Ùq不能化成{Ù, Ú}中的公式.
（5）为真，注意{Ø, ®, Ù}的子集{Ø, ®}为完备集.
2．通过求主范式判公式类型 P87
（1）(p®q)®(Øq®Øp)
（2）Ø(p®q)Ùq
（3）(p®q)ÙØp
（1）重言式，（2）矛盾式，（3）可满足式
解 用等值演算法求解
（1） (p®q)®(Øq®Øp)
Û Ø(ØpÚq)Ú(qÚØp) (消去®) ①
Û (pÙØq)Ú(qÚØp) (Ø内移) ②
Û (pÙØq)Ú(ØpÙq)Ú(pÙq)Ú(ØpÙØq) ③
Û m2 Ú m1 Ú m3 Ú m0 ④
Û m0 Ú m1 Ú m2 Ú m3 ⑤
Û 1 ⑥
问由②如何得③？
⑤为主析取范式，⑥为主合取范式
结论：（1）为重言式
（2） Ø(p®q)Ùq
Û Ø(ØpÚq)Ùq ①
Û pÙØqÙq ②
Û 0 ③
Û M0 Ù M1 Ù M2 Ù M3 ④
问：由②如何得③？
③为主析取范式，④为主合取范式
结论：（2）为矛盾式.
（3） (p®q)ÙØp
Û m0 Ú m1 ①
Û M2 Ù M3 ②
请自己等值演算得①与②
结论：（3）为可满足式
请用真值表再解此题
3．已知命题公式A中含3个命题变项p, q, r，并知道它的成真赋值为001, 010, 111, 求A的主析取范式和主合取范式，及A对应的真值函数. P90
答案A的主析取范式为m1 Ú m2Ú m7
A的主合取范式为M0 Ù M3 Ù M4 Ù M5 Ù M6
设A对应的真值函数为F，则
F(001)=F(010)=F(111)=1
F(000)=F(011)=F(100)=F(101)=F(110)=0
试说明以上得出答案的理由
5. 某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习. 选派必须满足以下条件：P94
（1） 若赵去，钱也去.
（2） 李、周两人中必至少有一人去
（3） 钱、孙两人中去仅去一人.
（4） 孙、李两人同去或同不去.
（5） 若周去，则赵、钱也去.
用等值演算法分析该公司如何选派他们出国？
解此类问题的步骤应为：
1 将简单命题符号化
2 写出各复合命题
3 写出由②中复合命题组成的合取式
4 将③中公式化成析取式（最好是主析取范式）
解 ① 设p：派赵去，q：派钱去，r：派孙去，s：派李去，u：派周去
② (1) (p®q)
(2) (sÚu)
(3) ((qÙØr)Ú(ØqÙr))
(4) ((rÙs)Ú(ØrÙØs))
(5) (u®(pÙq))
③ 设(1)—(5)构成的合取式为A
A = (p®q)Ù(sÚu)Ù((qÙØr)Ú(ØqÙr))Ù
((rÙs)Ú(ØrÙØs))Ù(u®(pÙq))
④ A Û (ØpÙØqÙrÙsÙØu)Ú(pÙqÙØrÙØsÙu)
结论：由④可知，A的成真赋值为00110与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）
例 用构造证明法构造下面推理的证明： P112
若明天是星期一或星期三，我就有课. 若有课，今天必备课. 我今天下午没备课. 所以，说明天是星期一或星期三是不对的.
构造证明
（1） 设p：明天是星期一，q：明天是星期三，r：我有课，s：我备课
（2） 形式结构
前提：(pÚq)®r, r®s, Øs
结论：ØpÙØq
（3） 证明
① r®s 前提引入
② Øs 前提引入
③ Ør ①②拒取式
④ (pÚq)®r 前提引入
⑤ Ø(pÚq) ③④拒取式
⑥ ØpÙØq ⑤置换
2. 附加前提证明法
（1） 欲证：
前提：A1, A2, …, Ak
结论：C®B
（2）等价地证明
前提：A1, A2, …, Ak, C
结论：B
（3）理由：
(A1ÙA2Ù…ÙAk)®(C®B)
Û Ø( A1ÙA2Ù…ÙAk)Ú(ØCÚB)
Û Ø( A1ÙA2Ù…ÙAkÙC)ÚB
Û (A1ÙA2Ù…ÙAkÙC)®B
例 构造下面推理的证明 P115
2是素数或合数. 若2是素数，则 是无理数. 若 是无理数，则4不是素数. 所以，如果4是素数，则2是合数.
用附加前提证明法构造证明
（1）设p：2是素数，q：2是合数，
r： 是无理数，s：4是素数
（2）形式结构
前提：pÚq, p®r, r®Øs
结论：s®q
（3）证明
① s 附加前提引入
② p®r 前提引入
③ r®Øs 前提引入
④ p®Øs ②③假言三段论
⑤ Øp ①④拒取式
⑥ pÚq 前提引入
⑦ q ⑤⑥析取三段论
请用直接证明法证明之
2． 在P系统中构造下面推理的证明： P125
如果今天是周六，我们就到颐和园或圆明园玩. 如果颐和园游人太多，就不去颐和园. 今天是周六，并且颐和园游人太多. 所以我们去圆明园或动物园玩.
（1） 设p：今天是周六，q：到颐和园玩，
r：到圆明园玩，s：颐和园游人太多
t：到动物园玩
（2）前提：p®(qÚr), s®Øq, p, s
结论：rÚt
（3）证明：
① p®(qÚr) 前提引入
② p 前提引入
③ qÚr ①②假言推理
④ s®Øq 前提引入
⑤ s 前提引入
⑥ Øq ④⑤假言推理
⑦ r ③⑥析取三段论
⑧ rÚt ⑦附加
2． 在一阶逻辑中将下列命题符号化 P150
（1） 大熊猫都可爱
（2） 有人爱发脾气
（3） 说所有人都爱吃面包是不对的
（4） 没有不爱吃糖的人
（5） 一切人都不一样高
（6） 并不是所有的汽车都比火车快
由于没指出个体域，故用全总个体域
（1）"x(F(x)®G(x))
其中，F(x): x为大熊猫，G(x): x可爱
（2）$x(F(x)ÙG(x))
其中，F(x): x是人，G(x): x爱发脾气
（3）Ø"x(F(x)®G(x)) 或 $x(F(x)ÙØG(x))
其中，F(x): x是人，G(x):x爱吃面包
（4）Ø$x(F(x)ÙØG(x)) 或 "x(F(x)®G(x))
其中，F(x): x是人，G(x): x爱吃糖
（5）"x(F(x)®"y(F(y)ÙØH(x,y)®ØL(x,y))),或
"x"y(F(x)ÙF(y)ÙØH(x,y)®ØL(x,y))
其中，F(x):x是人, H(x,y), x与y相同, L(x,y): x与y一样高
（6）Ø"x"y(F(x)ÙG(y)®H(x,y)) 或 $x$y(F(x)ÙG(y)ÙØH(x,y))
其中, F(x):x是汽车, G(y):y是火车, H(x,y):x比y快
几点说明
使用的是全总个体域
(1)与(2)是两个基本公式的使用
(3)与(4)是否定式
(5)与(6)使用了二元谓词
(3)-(6)的不同符号化形式是等值的
离散数学Part2_集合论部分
2．计数实例 P14
例 求1到1000之间（包含1和1000在内）既不能被5和6整除，也不能被8整除的数有多少个？
解 方法一
方法二
令S = {x | xÎZÙ1£x£1000}, A = {x | xÎSÙxº0(mod 5)}
B = {x | xÎSÙxº0(mod 6)}, C = {x | xÎSÙxº0(mod 8)}
则
|S| = 1000
|A| = ë1000/5û = 200, |B| = ë1000/6û = 166, |C| = ë1000/8û = 125
|AÇB| = ë1000/lcm(5,6)û = ë1000/33û = 33
|AÇC| = ë1000/lcm(5,8)û = ë1000/40û = 25
|BÇC| = ë1000/lcm(6,8)û = ë1000/24û = 41
| AÇ BÇ C| = ë1000/lcm(5,6,8)û = ë1000/120û = 8
= 1000-(200+166+125)+(33+25+41)-8 = 600
．设A = {1, 2, 3}, R = {<x,y> | x, yÎA且x+2y £ 6 }， P104
S = {<1,2>, <1,3>,<2,2>}, 求
（1）R的集合表达式
（2）R-1
（3）dom R, ran R, fld R
（4）RoS, R3
（5）r(R), s(R), t(R)
（1）R = {<1,1>, <1,2>, <2,1>, <2,2>, <3,1>}
（2）R-1 = {<1,1>, <2,1>, <1,2>, <2,2>, <1,3 >}
（3）domR = {1, 2, 3}, ranR = {1,2}, fldR = {1, 2, 3}
（4）RoS = {<1,2>, <1,3>, <2,2>, <2,3>, <3,2>, <3,3>}
R3 = {<1,1>, <1,2>, <2,1>, <2,2>, <3,1>, <3,2>}
（5）r(R) = {<1,1>, <1,2>, <2,1>, <2,2>, <3,1>, <3,3>}
s(R) = {<1,1>,<1,2>,<2,1>, <2,2>, <3,1>, <1,3>};
t(R) = {<1,1>, <1,2>, <2,1>, <2,2>, <3,1>, <3,2>}
2．设A={1,2,3,4}，在A´A上定义二元关系R：P106
<<x,y>,<u,v>>ÎR Û x+y = u+v，
求R导出的划分.
解
A´A={<1,1>, <1,2>, <1,3>, <1,4>, <2,1>, <2,2>, <2,3>, <2,4>,
<3,1>, <3,2>, <3,3>, <3,4>, <4,1>, <4,2>, <4,3>, <4,4>}
根据有序对<x,y>中的x+y=2,3,4,5,6,7,8将A划分成等价类：
A/R={{<1,1>}, {<1,2>,<2,1>}, {<1,3>, <2,2>, <3,1>},
{<1,4>, <2,3>, <3,2>, <4,1>}, {<2,4>, <3,3>, <4,2>},
{<3,4>, <4,3>}, {<4,4>}}
4．设偏序集 <A, R> 的哈斯图如图所示. P108
（1）写出A和R的集合表达式
（2）求该偏序集中的
极大元
极小元
最大元
最小元
解
（1）A = {a, b, c, d, e}
R = {<d,b>, <d,a>, <d,c>, <e,c>, <e,a>, <b,a>, <c,a>}ÈIA
（2）极大元和最大元是a, 极小元是d, e；没有最小元.
例 设 f：R→R, g：R→R P133
求fog, gof. 如果f和g存在反函数, 求出它们的反函数.
解
f：R→R不是双射的, 不存在反函数.
g：R→R是双射的, 它的反函数是
g-1：R→R, g-1(x)=x-2