离散数学(命题逻辑)课后总结.doc

离散数学（课件上习题）
第一章
例1-1.1 判定下面这些句子哪些是命题。
⑴ 2是个素数。
⑵ 雪是黑色的。
⑶ 2013年人类将到达火星。
⑷ 如果 a>b且b>c，则a>c 。（其中a,b,c都是
确定的实数）
⑸ x+y<5
⑹ 请打开书！
⑺ 您去吗？
⑴⑵⑶⑷是命题
例1-2.1 P：2是素数。
ØP：2不是素数 。
例1-2.2 P：小王能唱歌。
Q：小王能跳舞。
P∧Q：小王能歌善舞。
例1-2.3. 灯泡或者 线路有故障。（析取“∨”）
例1-2.4. 第一节课上数学或者上英语。（异或 、排斥或 。即“⊽”）
注意：P ⊽ Q 与 (P∧ØQ)∨(Q∧ØP ) 是一样的。
归纳自然语言中的联结词，定义了六个逻辑联结词，分别是：（1）否定 “Ø ” (2) 合取 “∧ ” (3) 析取 “∨ ” (4) 异或 “⊽ ” (5) 蕴涵 “® ” (6) 等价 “« ”
例1-2.5： P表示：缺少水分。
Q表示：植物会死亡。
P®Q：如果缺少水分，植物就会死亡。
P®Q：也称之为蕴涵式，读成 “P蕴涵Q”， “如果P则Q”。
也说成P是P®Q 的前件，Q是P®Q的后件。
还可以说P是Q的充分条件，Q是P的必要条件。
以下是关于蕴含式的一个例子
P：天气好。 Q：我去公园。
1.如果天气好，我就去公园。
2.只要天气好，我就去公园。
3.天气好，我就去公园。
4.仅当天气好，我才去公园。
5.只有天气好，我才去公园。
6.我去公园，仅当天气好。
命题1.、2.、3.写成： P®Q
命题4.、5.、6.写成： Q®P
例1-2.6： P：△ABC 是等边三角形。 Q ：△ABC是等角三角形。
P«Q ：△ABC 是等边三角形 当且仅当它是等角三角形。

课后练习：填空
已知P∧Q为T，则P为( )，Q为( )。
已知P∨Q为F，则P为( )，Q为( )。
已知P为F，则P∧Q为( )。
已知P为T，则P∨Q为( )。
已知P∨Q为T，且P为F ，则Q为( )。
已知P®Q为F，则P为( )，Q为( )。
已知P为F，则P®Q为( )。
已知Q为T，则P®Q为( )。
已知 ØP®ØQ为F，则P为( )， Q为( )。
已知P为T， P®Q为T，则Q为( )。
已知ØQ为T, P®Q为T，则P为( )。
已知P«Q 为T ，P 为T , 则Q 为( ).
已知P«Q 为F ，P 为T , 则Q 为( ).
P«P 的真值为( ).
P®P 的真值为( )。

1—3节
例1.说离散数学无用且枯燥无味是不对的。
P：离散数学是有用的。
Q：离散数学是枯燥无味的。
该命题可写成： Ø (ØP∧Q)
例2. 如果小张与小王都不去，则小李去。
P ： 小张去。 Q ： 小王去。 R ： 小李去。
该命题可写成： (ØP∧ØQ)®R
如果小张与小王不都去，则小李去。
该命题可写成： Ø(P∧Q)®R
也可以写成： (ØP∨ØQ)®R
例3. 仅当天不下雨且我有时间，才上街。
P：天下雨。Q：我有时间。R：我上街。
分析：由于 “仅当 ”是表示 “必要条件 ”的，既 “天不下雨且我有时间 ”，是 “我上街 ”的必要条件。所以
该命题可写成： R®(ØP∧Q)
例4. 人不犯我，我不犯人；人若犯我，我必犯人。
P ： 人犯我。Q ： 我犯人。
该命题可写成：(ØP®ØQ)∧(P®Q)或写成： P«Q
例5 .若天不下雨，我就上街；否则在家。
P：天下雨。Q ：我上街。R：我在家。
该命题可写成： (ØP®Q)∧(P®R).
注意：中间的联结词一定是“∧”，而不是“∨”，也不是“⊽ ”。

1—4节
重言(永真)蕴涵式证明方法
方法1.列真值表。
方法2.假设前件为真，推出后件也为真。
例如求证：
((A∧B)®C)∧ØD∧(ØC∨D) Þ ØA∨ØB
证明:设前件((A∧B)®C)∧ØD∧(ØC∨D) 为真则((A∧B)®C)、ØD、(ØC∨D)均真，
ØD为T，则D为F
ØC∨D为T 得C为F
((A∧B)®C )为T 得A∧B为F
如果A为F，则ØA为T，所以ØA∨ØB为T。
如果B为F，则ØB为T，所以ØA∨ØB 为T。
\((A∧B)®C)∧ØD∧(ØC∨D) Þ ØA∨ØB
方法3.假设后件为假，推出前件也为假 。
例如求证： ((A∧B)®C)∧ØD∧(ØC∨D) Þ ØA∨ØB
证明: 假设后件ØA∨ØB 为F, 则A 与B 均为T 。
1. 如C 为F ，则(A∧B)®C为F，所以 前件((A∧B)®C)∧ØD∧(ØC∨D) 为F 。
2. 如C 为T ，则
⑴ 若D 为T ，则ØD 为F ， 所以前件((A∧B)®C)∧ØD∧(ØC∨D) 为假；
⑵若D为F，则ØC∨D 为F ， 所以 前件((A∧B)®C)∧ØD∧(ØC∨D) 为假。

\((A∧B)®C)∧ØD∧(ØC∨D) Þ ØA∨ØB
重要的重言蕴涵式( 如教材第43 页所示)（课件中出现过多次，可不用记忆）
I1. P∧QÞP I2. P∧QÞQ
I3. PÞP∨Q I4. QÞP∨Q
I5. ØPÞP®Q I6. QÞP®Q
I7. Ø(P®Q)ÞP I8. Ø(P®Q)ÞØQ
I9. P,Q ÞP∧Q I10. ØP∧(P∨Q)ÞQ
I11. P∧(P®Q)ÞQ I12. ØQ∧(P®Q)ÞØP
I13. (P®Q)∧(Q®R)ÞP®R
I14. (P∨Q)∧(P®R)∧(Q®R)ÞR
I15. A®B Þ(A∨C)®(B∨C)
I16. A®B Þ(A∧C)®(B∧C)
1—5节
重要的等价公式（课件中出现多次，可不用记忆）
⑴ 对合律 ØØP ÛP ⑵ 幂等律 P∨PÛP P∧PÛP
⑶ 结合律 P∨(Q∨R)Û(P∨Q)∨R P∧(Q∧R)Û(P∧Q)∧R
⑷ 交换律 P∨QÛQ∨P P∧QÛQ∧P
⑸分配律 P∨(Q∧R)Û(P∨Q)∧(P∨R) P∧(Q∨R)Û(P∧Q)∨(P∧R)
⑹ 吸收律 P∨(P∧Q)ÛP P∧(P∨Q)ÛP
⑺底-摩根定律 Ø(P∨Q)ÛØP∧ØQ Ø(P∧Q)ÛØP∨ØQ
⑻ 同一律 P∨FÛP P∧TÛP ⑼ 零律 P∨TÛT P∧FÛF
⑽ 互补律 P∨ØPÛT P∧ØPÛF ⑾ P®Q ÛØP∨Q
⑿ P®Q ÛØQ®ØP ⒀ P«Q Û(P®Q)∧(Q®P)
⒁ P«Q Û(ØP∨Q)∧(P∨ØQ) ⒂ P«Q Û(P∧Q)∨(ØP∧ØQ )
例题1. 求证吸收律 P∧(P∨Q)ÛP
证明 ： P∧(P∨Q)
Û (P∨F)∧(P∨Q) (同一律)
ÛP∨(F∧Q) (分配律)
ÛP∨F (零律)
ÛP (同一律)
例题2. 求证 (ØP∨Q)→(P∧Q) ÛP
证明 (ØP∨Q)→(P∧Q)
ÛØ(ØP∨Q)∨(P∧Q) ( 公式E16)
Û (ØØP∧ØQ)∨(P∧Q) ( 摩根定律)
Û (P∧ØQ)∨(P∧Q) ( 对合律)
ÛP∧(ØQ∨Q) ( 分配律)
ÛP∧T ( 互补律)
ÛP ( 同一律)
公式E16 ： P®QÛØP∨Q
例题3.化简Ø(P∧Q)→(ØP∨(ØP∨Q))
解 原公式ÛØØ(P∧Q)∨((ØP∨ØP)∨Q) (E16,结合)
Û(P∧Q)∨(ØP∨Q) (对合律，幂等律)
Û(P∧Q)∨(Q∨ØP) (交换律)
Û((P∧Q)∨Q)∨ØP (结合律)
ÛQ∨ØP (吸收律)
公式E16 ： P®QÛØP∨Q
1-6.范式(Paradigm)
例1. 求 P®Q 和P«Q的 主析取范式
T
T
T
T
F
F
F
T
F
T
T
F
T
T
F
F
PQ
PQ
Q
P
方法一：真值表

P®QÛ m0∨m1∨m3
Û(ØP∧ØQ)∨(ØP∧Q)∨(P∧Q)
P«QÛm0∨m3
Û (ØP∧ØQ)∨(P∧Q)
方法Ⅱ ：用公式的等价变换

⑴ 先写出给定公式的析取范式 A1∨A2∨...∨An 。
⑵ 为使每个Ai 都变成小项，对缺少变元的Ai
补全变元，比如缺变元R ， 就用∧ 联结永真式(R∨ØR) 形式补R 。
⑶ 用分配律等公式加以整理。
P®QÛØP∨Q
Û(ØP∧(Q∨ØQ))∨((P∨Ø P)∧ Q)
Û(ØP∧Q)∨(ØP∧ØQ)∨(P∧Q)∨(ØP∧Q)
Û(ØP∧Q)∨(ØP∧ØQ)∨(P∧Q)

思考题: 永真式的主析取范式是什么样 ？（包含所有小项）
例2.求 P®Q 和P«Q的 主合取范式
T
T
T
T
F
F
F
T
F
T
T
F
T
T
F
F
PQ
PQ
Q
P

P®Q Û M2 Û ØP∨Q
P«Q Û M1∧M2
Û (P∨ØQ )∧(ØP∨Q)
方法Ⅱ：用公式的等价变换
⑴ 先写出给定公式的合取范式 A1∧A2∧...∧An 。
⑵ 为使每个Ai 变成大项，对缺少变元的析取式Ai 补全变元，比如缺变元R ， 就用∨联
结永假式(R∧ØR) 形式补R 。
⑶ 用分配律等公式加以整理。
例如，求(P®Q)®R 的主合取范式
(P®Q)®R
Û Ø(ØP∨Q)∨R
Û (P∧ØQ)∨R
Û (P∨R)∧(ØQ∨R)
Û (P∨(Q∧ØQ)∨R)∧((P∧ØP)∨ØQ∨R)
Û (P∨Q∨R)∧ (P∨ØQ∨R)∧
(P∨ØQ∨R)∧(ØP∨ØQ∨R)
Û (P∨Q∨R)∧(P∨ØQ∨R)∧ (ØP∨ØQ∨R)
例3. 安排课表，教语言课的教师希望将课程安排在第一或第三节；教数学课的教师
希望将课程安排在第二或第三节；教原理课的教师希望将课程安排在第一或第二节。
如何安排课表，使得三位教师都满意。令L1 、L2 、L3 分别表示语言课排在第一、第二、第三节。
M1 、M2 、M3 分别表示数学课排在第一、第二、第三节。 P1 、P2 、P3 分别表示原理课排在第一、
第二、第三节。
三位教师都满意的条件是：
(L1∨L3)∧(M2∨M3)∧(P1∨P2 ) 为真。
将上式写成析取范式( 用分配律) 得：
((L1∧M2)∨(L1∧M3)∨(L3∧M2)∨
(L3∧M3))∧(P1∨P2)
Û(L1∧M2∧P1)∨(L1∧M3∧P1)∨
(L3∧M2∧P1)∨(L3∧M3∧P1)∨
(L1∧M2∧P2)∨(L1∧M3∧P2)∨
(L3∧M2∧P2)∨(L3∧M3∧P2)
可以取(L3 ∧M2∧P1)、(L1∧M3∧P2) 为T ， 得到两种排法。
T
T
T
T
T
F
T
T
F
T
F
T
T
F
F
T
T
T
T
F
F
F
T
F
F
T
F
F
T
F
F
F
A(P,Q,R)
R
Q
P
课堂练习：
1.已知A(P,Q,R)的真值表如图：
求它的主析取和主合取范式。
2. 已知A(P,Q,R)的主析取范式中
含有下面小项m1, m3, m5, m7
求它的主合取范式.
3. 已知A(P1,P2,…,Pn)的主合取范式中
含有k个大项，问它的主析取范式
中有多少个小项？

课堂练习答案
1.A(P,Q,R)的主析取范式:
A(P,Q,R)Û m0∨m3∨m4∨m6∨m7
Û(ØP∧ØQ∧ØR)∨(ØP∧Q∧R)∨
(P∧ØQ∧ØR)∨(P∧Q∧ØR)∨(P∧Q ∧R)
A(P,Q,R)的主合取范式：
A(P,Q,R)Û M1∧M2∧M5 Û(P∨Q∨ØR)∧(P∨ØQ∨R)∧(ØP∨Q∨ØR)
2. A(P,Q,R)Û M0∧M2∧M4 ∧M6
Û(P∨Q∨R)∧(P∨ØQ∨R)∧(ØP∨Q∨R) ∧(ØP∨ØQ∨R)
3. A(P1,P2,…,Pn)的主析取范式中含有2n-k个小项.
1-7. 命题逻辑推理
例题１求证 P→Q，Q→R，P Þ R
证明
序号 前提或结论 所用规则 从哪几步得到 所用公式
(1) P P
(2) P®Q P
(3) Q T (1)(2) I11
(4) Q→R P
(5) R T (3)(4) I11
例题２求证
Ø(P∧Q)∧(Q∨R)∧ØR Þ ØP
(1) Q∨R P
(2) ØR P
(3) Q T (1)(2) I10
(4) Ø(P∧Q) P
(5) ØP∨ØQ T (4) E8
(6) ØP T (3)(5) I10
注公式I10为： Ø P,P∨Q Þ Q
公式E8为： Ø(P∧Q) Û ØP∨ØQ
例题３ 用命题逻辑推理方法证明下面推理的有效性：
如果我学习，那么我数学不会不及格。如果我不热衷于玩朴克，那么我将学习。但是我数学不及格。因此，我热衷于玩朴克。
解:设 P：我学习。
Q：我数学及格。
R：我热衷于玩朴克。
于是符号化为：
P→Q，ØR→P，ØQ Þ R
P→Q，ØR→P，ØQ Þ R
(1) P→Q P
(2) ØQ P
(3) ØP T (1)(2) I12
(4) ØR→P P
(5) ØØR T (3)(4) I12
(6) R T (5) E1
注：公式I12为： ØQ，P→Q Þ ØP
公式E1 为： ØØRÛR
例题４求证P→(Q→S),ØR∨P,Q ÞR→S
证明(1) P→(Q→S) P
(2) ØP∨(ØQ∨S) T (1) E16
(3) ØP∨(S∨ØQ) T (2) E3
(4) (ØP∨S)∨ØQ T (3) E5
(5) Q P
(6) ØP∨S T (4)(5) I10
(7) P→S T (6) E16
(8) ØR∨P P
(9) R→P T (8) E16
(10) R→S T (7)(9) I13
例题５ 用条件论证，证明例题４
P→(Q→S),ØR∨P,Q Þ R→S
证明 (1) R P(附加前提)
(2) ØR∨P P
(3) P T (1)(2) I10
(4) P→(Q→S) P
(5) Q→S T (3)(4) I11
(6) Q P
(7) S T (5)(6) I11
(8) R→S CP
例题６ 用命题逻辑推理方法证明下面推理的有效性：
如果体育馆有球赛，青年大街交通就拥挤。在这种情况下，如果小王不提前出发，就会迟到。因此，小王没有提前出发也未迟到，则体育馆没有球赛。
证明 先将命题符号化。
设 P：体育馆有球赛。
Q：青年大街交通拥挤。
R：小王提前出发。
S：小王迟到。
P→Q，(Q∧ØR)→S Þ(ØR∧ØS)→ØP
P→Q，(Q∧ØR)→S Þ(ØR∧ØS)→ØP

证明
(1) ØR∧ØS P(附加前提)
(2) ØR T (1) I1
(3) ØS T (1) I2
(4) (Q∧ØR)→S P
(5) Ø(Q∧ØＲ) T (3)(4) I12
(6) ØQ∨R T (5) E8
(7) ØQ T (2)(6) I10
(8) P→Q P
(9) ØP T (7)(8) I12
(10)(ØR∧ØS)→ØP CP
例７ P→Q,(ØQ∨R)∧ØR, Ø(ØP∧S)ÞØS
证明
(1) ØØS P(假设前提)
(2) S T (1) E1
(3) Ø(ØP∧S) P
(4) P∨ØS T (3) E8
(5) P T (2)(4) I10
(6) P→Q P
(7) Q T (5)(6) I11
(8) (ØQ∨R)∧ØR P
(9) ØQ∨R T (8) I1
(10) ØR T (8) I2
(11) R T (7)(9) I10
(12) R∧ØR T (10)(11) I9
第一章 习题课
1.有工具箱A、B、C、D，各个箱内装的工具如下表所示。试问如何携带数量最少工具箱，而所包含的工具种类齐全。

工具箱
改锥
扳 手
钳 子
锤 子
A
有
有

B

有
有
有
C
有

有

D

有

有

解：设A、B、C、D分别表示带A、B、C、D箱。
则总的条件为：
(A∨C)∧(A∨B∨D)∧(B∨C)∧(B∨D) 为真。
改锥 扳手 钳子 锤子
将(A∨C)∧(A∨B∨D)∧(B∨C)∧(B∨D)写成析取范式，上式Û((A∨C)∧(B∨C))∧((A∨(B∨D))∧(B∨D)) (交换 )
Û((A∧B)∨C))∧(B∨D)
(分配(提取C)、吸收)
Û(A∧B∧B )∨(C∧B )∨(A∧B∧D)∨(C∧D) (分配)
Û(A∧B)∨(C∧B )∨(A∧B∧D)∨(C∧D)
分别可以取(A∧B)、(C∧B )、(C∧D)为真。
于是可以得到三种携带方法：
带A和B箱， 带B和C箱，带C和D箱。
请根据下面事实，找出凶手：
1. 清洁工或者秘书谋害了经理。
2. 如果清洁工谋害了经理，则谋害不会发生在午夜前。
3.如果秘书的证词是正确的，则谋害发生在午夜前。
4.如果秘书的证词不正确，则午夜时屋里灯光未灭。
5. 如果清洁工富裕，则他不会谋害经理。
6.经理有钱且清洁工不富裕。
7.午夜时屋里灯灭了。
令A:清洁工谋害了经理。 B:秘书谋害了经理。
C:谋害发生在午夜前。 D:秘书的证词是正确的.
E:午夜时屋里灯光灭了。H:清洁工富裕.
G:经理有钱.
命题符号为：
A∨B,AØ®C,D®C,ØDØ®E,HØ®A,G∧ØH,E Þ?
A∨B,AØ®C,B®C, D®C ØDØ®E,HØ®A,G∧ØH,E Þ?
⑴ E P
⑵ ØDØ®E P
⑶ ØØD T ⑴⑵ I
⑷ D T ⑶ E
⑸ D®C P
⑹ C T ⑷⑸ I
⑺ AØ®C P
⑻ ØA T ⑹⑺ I
⑼ A∨B P
⑽ B T ⑻⑼ I

结果是秘书谋害了经理。

第一章 小结
本章的重点内容、及要求：
１.逻辑联结词，要熟练掌握联结词的真值表定义以及它们在自然语言中的含义。其中特别要注意“∨”和“→”的用法。
２.会命题符号化。
３.掌握永真式的证明方法：
(1).真值表。
(2).等价变换，化简成Ｔ。
(3).主析取范式。
４.掌握永真蕴含式的证明方法，熟练记忆并会应用
43页中表1-8.3中的永真蕴含式。
５.掌握等价公式的证明方法，熟练记忆并会应用
43页表1-8.4中的等价公式。
６.熟练掌握范式的写法及其应用。
７.熟练掌握三种推理方法。
以上自己是不是都已经熟练掌握了呢？？

10