离 散 数 学
Discrete Mathematics
曾庆田
Email:qtzeng@
山东科技大学 信息科学与工程学院 二零一零年三月
1
上次课内容回顾
析取范式 小项 主析取范式 合取范式 大项
主合取范式
2
第一章 第5讲 §1—8 推理理论
在数学和其它自然科学中，经常要考虑从某些前提A1， A2，…，An能够推导出什么结论。 例如： 从分子学说，原子学说，能够得到什么结论； 从光的波动学说，能得到什么结论。 我们一般地要对“假设”的内容作深入分析，并推究 其间的关系，从而得到结论。 但也有一些推理，只需分析假设中的真值和联结词， 便可获得结论。
设有一组前提H1，H2，…，Hn ，要推出结论C， 即证H1 ∧ H2 ∧ … ∧ Hn C，记作S C，即 ┐C→ ┐S为永真，或C∨┐S为永真，故┐C ∧S为永 假 。因此要证明H1 ∧ H2 ∧ … ∧ Hn C，只要证 明H1，H2，…，Hn与是┐C是不相容的。即假定┐C 为真，推出矛盾。
E10 P ∨ P P
E11 P∧P P
E21
E22
P Q (P∧Q) ∨(┐P∧ ┐Q)
┐(P Q) P ┐Q
例题1 证明 (P∨Q) ∧(P→R)∧(Q→S) S∨R 证法1 (1) P∨Q (2) ┐P→Q
P
T(1) E
(3) Q→S (4) ┐P→S
(5) ┐S→P (6) P→R (7) ┐S→R (8) S∨R
解 若设M：天晴。 Q：下雨。 S：我看电影。R：我看书。 故本题即证：M ∨Q，M→S，S→ ┐R，推出R→Q (8) ┐( M Q) (1) R (2) S → ┐R (3) R→ ┐ S P(附加前提) P T(2) E (9) M ┐ Q (11) ┐Q →M (12) ┐M →Q (13) Q (14) R→Q T(7) E T(8) E T(9) E T(10) I T(11) E T(6),(12) I CP
P T(2) ,(3) I
T(4) E P T(5),(6) I T(7) E
例题1 证明 (P∨Q) ∧(P→R)∧(Q→S) S∨R 证法2 (1) P→R P (2) P∨Q →R∨Q T(1) I (3) Q→S P (4) Q∨R →S∨R T(3) I (5) P∨Q →S∨R T(2),(4) I (6) P∨Q P (7) S∨R T(5),(6) I
P∧ (Q ∨ R) (P∧Q) ∨(P∧R) E17
E7
E8 E9
P ∨(Q∧R) (P ∨ Q) ∧(P∨ R) E18
┐(P∧Q) ┐P ∨ ┐Q ┐(P ∨ Q) ┐P ∧┐Q E19 E20
P→Q ┐Q →┐P
P→ (Q→R) (P∧Q) →R P Q (P→Q) ∧(Q→P)
例题5 证明 A→(B→C)，┐D∨A ，B 重言蕴含D→C 证明 (1) D P(附加前提) (2) ┐D∨A P
(3) A
(4) A→(B→C) (5) B→C (6) B (7) C (8) D→C
T(1),(2) I
P T(3),(4) I P T(5),(6) I CP
例题6 设有下列情况，结论是否有效？ (a)或者是天晴，或者是下雨。 (b)如果是天晴，我去看电影。. (c)如果我去看电影，我就不看书。 结论：如果我在看书则天在下雨。
H1，H2，…，Hn真值均为T的行，对于每一 个这样的行，若C也有真值T，则(A)式成立； 或者看C的真值为F的行，在每一个这样的行 中，H1，H2，…，Hn的真值至少有一个为F， 则(A)式也成立。


例题1 一份统计表格的错误或者是由于材料不可靠， 或者是由于计算有错误；这份统计表格的错误不是
从表上看到只有在第三行P∨Q和┐P的真值都为T， 这时Q的真值亦为T。故 (P∨Q)∧(┐P) Q 成立。 或者考察Q的真值为F的情况，在第二行和第四行， 其相应的P∨Q或┐P中至少有一真值为F，故亦说明 (P∨Q)∧(┐P) Q成立。

例题2 如果张老师来了，这个问题可以得到解答， 如果李老师来了，这个问题也可以得到解答，总之 张老师或李老师来了，这个问题就可得到解答。
T(4),(5) I
T(6) E P P T(8),(9) I T(7),(10) I
(12) ┐W ∧ ┐R (13) ┐W
T(11) E T(12) I
二、证明方法
1. 真值表法 2. 直接证法 3. 间接证法
21
3. 间接证法
(1)定义
定义1-8.2 假设公式H1，H2，…，Hn 中的命题变 元为P1，P2，…，Pn ，
一、有效结论
1. 定义 定义1-8.1 设A和C是两个命题公式，当且仅当A→C为一 重言式，即A C，称C是A的有效结论。或C可由A逻辑 地推出。 2. 推广 有效结论定义可以推广到有n个前提的情况。 设H1，H2，……，Hn，C是命题公式，当且仅当 H1∧H2∧…∧Hn C (A) 称C是一组前提H1，H2，……，Hn的有效结论。 3 . 论证过程 判别有效结论的过程就是论证过程。
(10) (M →┐Q) ∧(┐Q →M)
(4) ┐S
(5) M →S (6)┐M (7) M∨Q
T(1),(3) I
P T(4),(5) I P
命题推理方法
真值表法：

前真：看后真；
后假：前至少有一个假。
直接证法：由一组前提，利用一些公认的推理规则，
根据已知的等价或蕴含公式，推演得到有效的结论。 间接证法
真值表法是把所给前提一起使用，而直接证法则是不 断使用前提和前面推出的结论，构成推导序列，是把 前提一步一步拿来使用。
常用的蕴含式（43页表1-8.3） I1 P∧Q P I2 P∧Q Q I3 P P∨Q I4 Q P∨Q I9 P,Q P∧Q
I10 ┐P,P∨Q Q I11 P,P→Q Q I12 ┐Q,P→Q ┐P
例题2 证明 (W∨R) →V ,V→C∨S,S→U, ┐C∧ ┐U ┐W 证明
(1) ┐C∧ ┐U
(2) ┐U (3) S→U (4) ┐S (5) ┐ C
P
T(1) I P T(2) ,(3) I T(1) I
(6) ┐C ∧ ┐S
(7) ┐(C∨S) (8) (W∨R) →V (9) V→C∨S (10) (W∨R) →C∨S (11) ┐(W∨R)
由于材料不可靠，所以这份统计表格是由于计算有
错误。 解 设各命题变元为 P：统计表格的错误是由于材料不可靠。 Q：统计表格的错误是由于计算有错误。 本例可译为：Q是前提P∨Q，┐P的有效结论， 即 ┐P∧(P∨Q) Q

我们列出真值表1-8.1如下 P T T F F Q T F T F P∨Q T T T F ┐P F F T T
二、证明方法
1. 真值表法 2. 直接证法 3. 间接证法
二、证明方法
1. 真值表法 2. 直接证法 3. 间接证法
7
1. 真值表法
设P1，P2，…，Pn是出现于前提H1，H2，…，Hn和 结论C中的全部命题变元，假定对P1，P2，…，Pn作 了全部的真值指派，这样就能对应地确定H1，H2，…， Hn和C的所有真值，列出这个真值表，即可看出(A)式 是否成立。

对于P1，P2，…，Pn的一些真值指派，如果能使 H1 ∧ H2 ∧ … ∧ Hn的真值为T，则称公式H1， H2，…，Hn 是相容的。 如果对于P1，P2，…，Pn的每一组真值指派使得 H1 ∧ H2 ∧ … ∧ Hn的真值均为F，则称公式H1， H2，…，Hn是不相容的。

(2)证法 可以把不相容的概念应用于命题公式的证明。
Q→R T F T T T F T T
P∨Q T T T T T T F F
从真值表看到，P→R，Q→R，P∨Q的真值都为T的 情况为第一行、第三行和第五行，而在这三行中R的真值 均为T。故 (P→R)∧(Q→R)∧(P∨Q) R
真值表法证明
前真：看后真； 后假：前至少有一个假。

13
二、证明方法
(12) ┐(P ∧ ┐R) T(11) E (13) (P ∧ ┐R) ∧ ┐(P ∧ ┐R)(矛盾) T(9),(12) I
(3) CP规则（ 结论为R → C时使用）
间接证法的另一种情况是：若要证H1 ∧ H2 ∧ … ∧ Hn (R → C)。 设H1 ∧ H2 ∧ … ∧ Hn 为S ，即证 S (R → C) 或S ( ┐ R∨C)，故S →( ┐ R∨C)为 永真式。因为S →( ┐R∨C) ┐S∨( ┐R∨C) (┐S∨ ┐R)∨C ┐(S ∧R)∨C (S ∧R) →C，所 以若将R作附加前提，如有(S ∧R) C，即证得S (R→C)。 由(S ∧R) C，证得S (R→C)称为CP规则。
I5 ┐P P→Q
I6 Q P→Q
I13 P→Q, Q→R P→R
I14 P∨Q,P→R,Q→R R
I7 ┐(P→Q) P
I8 ┐(P→Q) ┐Q
I15 A→B (A∨C)→(B∨C)
I16 A→B (A∧C)→(B∧C)
常用的等价式(43页表1-8.4)
E1
E2 E3
例题3 证明 A→B， ┐(B∨C)可逻辑推出┐A
证明
(1) A→B
(2) A (3) B (4) ┐(B∨C) (5) ┐B ∧ ┐C (6) ┐B (7) B ∧ ┐B(矛盾)
P
P(附加前提) T(1),(2) I P T(4) E T(5) I T(3),(6) I
例题4 证明 证明
(P∨Q) ∧(P→R)∧(Q→S) S∨R (1) ┐(S∨R) (2) ┐S ∧ ┐R (3) P∨Q (4) ┐P →Q (5) Q →S (6) ┐P → S (7) ┐S → P (8) (┐S ∧ ┐R ) →(P ∧ ┐R ) (9) P ∧ ┐R (10) P →R (11) ┐P∨R P(附加前提) T(1) E P T(3) E P T(4),(5) I T(6) E T(7) I T(2),(8) I P T(10) E