离散数学基础
2017-11-17
•推理的形式结构
−例：
»前提1: 如果今天是周五，那么我们有数理逻辑课。»前提2: 今天是周五。
»结论: 今天我们有数理逻辑课。
»形式化：P：今天是周五。Q：今天我们有数理逻辑课。»前提1：P→Q»前提2：P»结论：Q
•定义：条件式推理结构
−将例子中的两个前提记为 (P→Q)∧P，结论记为 Q，上述推理过程可表述为：
(P→Q)∧P|→ Q 或 (P→Q)∧P├ Q
称为条件式推理结构。−记号 ”├” 读成 ”推出”
−(P→Q)∧P├ Q 经常写成 (P→Q), P├ Q•定义：推理结构的有效性
−设命题公式 H、C，若当 H 为真时，C 必为真，则称推理结构 H├ C 是有效的（或是正确的） 推理形式。否则，称推理结构 H├ C 不是有效的（或是无效的）推理形式。
»H├ C 有效，即在 H 上的任何令 H 的真值为 T 的解释下，C 的真值均为 T。
»H├ C 无效，即至少存在一个令 H 的真值为 T 而 C的真值为 F 的解释。 »推广到有 n 个前提 H1, H2, …, Hn 的情形，可令
H= H1∧H2∧ …∧Hn
将推理的形式结构写成 H├ C；
如果定义 Γ = {H1, H2, …, Hn}，可写成 Γ├ C。−例： P, (P→Q)├ Q 是有效的推理结构。
»由下面的真值表可见，穷尽所有的解释，只有第4行令 P∧(P→Q)=T。而对
应此解释，Q=T。
P F F T T
QP→QP∧(P→Q)FT F TT F FF F TT T
− 例： ¬Q, (P→Q)├ ¬P 是有效的推理结构。
» 由真值表可见，只有第1行解释令 ¬Q∧(P→Q)=T。而对应此解释， ¬P =T 。
P
F F T T
Q ¬QP→Q¬Q ∧(P→Q)F TT T T FT F F TF F T FT F ¬P
TTFF
− 例： ¬P, (P→Q)├¬Q 不是有效的推理结构。
» 由其真值表可见，存在第2行解释令 ¬P∧(P→Q)=T。而对应此解释，¬Q =F 。
P
FFTT
Q¬QP→Q¬PFTT TTFT TFTF FTFT F
• 定义：逻辑推出/重言蕴涵
− 当 H├ C 有效时，可写成 H ⇒C，称 H 逻辑推出 C，或说 C 是 H 的逻辑推论（有效结论），或 H 重言蕴涵 C。
− 注意到 H ⇒C 描述了公式 H 和 C 之间的一种真值联系，但 ”⇒” 不是连接词，”H ⇒C” 也不是合式公式。
• 重言蕴涵的若干性质：
− 若 A ⇒B，且 A 为重言式，则 B 也为重言式。 − 若 A ⇒B，且 B ⇒A，则 A⇔B。 − 若 A ⇒B，且 B ⇒C，则 A ⇒C。 − 若 A ⇒B，且 A ⇒C，则 A ⇒B∧C。 − 若 A ⇒C，且 B ⇒C，则 A∨B ⇒C。
− 性质的证明：从重言蕴涵的定义可以直接对上述性质进行验证。
• 定理：演绎定理
− 设有命题公式 H1, H2, …,Hn, C，则推理形式 H1, H2, …, Hn├ C 是有效的当且仅当命题形式 H1∧H2 ∧ …∧Hn→ C 是重言式。 − 演绎定理的证明：
⇒ 对于那些令 H1∧H2 ∧ …∧Hn=1 的解释，由于 H1, H2, …, Hn├ C 是有效的，必须 C=1，此时 H1∧H2 ∧ …∧Hn→ C = 1；对于那些令 H1∧H2 ∧ …∧Hn=0 的解释， H1∧H2 ∧ …∧Hn→ C=1。故 H1∧H2∧ …∧Hn→ C 是重言式。
由于 H1∧H2∧ …∧Hn→ C 是重言式，⇐ 对于那些令 H1∧H2 ∧ …∧Hn=1 的解释，
必须 C=1，所以 H1, H2, …, Hn├ C 是有效的。
• 定理：演绎定理
− 推论：上述 H1, H2, …, Hn├ C 有效当且仅当 H1∧H2 ∧ …∧Hn∧¬C 为矛盾式。 − 推论的证明：只需证明命题形式 H1∧H2 ∧ …∧Hn→ C 是重言式当且仅当 H1∧H2 ∧ …∧Hn∧¬C 为矛盾式。
⇒ 若 H1∧H2 ∧ …∧Hn→ C 是重言式：对于那些令 H1∧H2 ∧ …∧Hn=1 的解释，C=1，即 ¬C=0，此时 H1∧H2 ∧ …∧Hn∧¬C=0；对于那些令 H1∧H2 ∧ …∧Hn=0 的解释，H1∧H2 ∧ …∧Hn∧¬C=0。故 H1∧H2 ∧ …∧Hn∧¬C 为矛盾式。
⇐ 若 H1∧H2 ∧ …∧Hn∧¬C 为矛盾式：对于那些令 H1∧H2 ∧ …∧Hn=1 的解释，必须 ¬C=0，即 C=1，此时 H1∧H2 ∧ …∧Hn→ C=1；对于那些令 H1∧H2 ∧ …∧Hn=0 的解释， H1∧H2 ∧ …∧Hn→ C=1。故H1∧H2 ∧ …∧Hn→ C 是重言式。
• 常用的推理公式/推理定律
− 下面是常用的14条有效的推理结构，也称推理定律或推理公式。其正确性可以利用真值表加以验证。 (1) P∧Q ⇒ P 化简 (2) ¬(P→Q) ⇒ P (3) ¬(P→Q) ⇒ ¬Q (4) P ⇒ P∨Q 附加 (5) ¬P ⇒ P→Q (6) Q ⇒ P→Q (7) ¬P∧(P∨Q) ⇒ Q 析取三段论
假言推理/分离规则 (8) P∧(P→Q) ⇒ Q
(9) ¬Q∧(P→Q) ⇒ ¬P 拒取式 (10) (P→Q)∧(Q→R) ⇒ (P→R) 假言三段论 (11) (P↔Q)∧(Q↔R) ⇒ (P↔R) 等价三段论 (12) (P→R)∧(Q→R) ⇒ ((P∨Q)→R) 二难推论 (13) (P→Q)∧(R→S)∧(P∨R) ⇒ (Q∨S) 构造性二难推论 (14) (P→Q)∧(R→S)∧(¬Q∨¬S) ⇒ ¬P∨¬R 破坏性二难推论
• 证明 A ⇒B 的方法
− 真值表法：列出真值表，证明 A→B 是重言式，再利用演绎定理得证 ；
− 解释法：设 A=1，对使得 A=1 的所有解释，论证 B 在这些解释下只能取真值1；
− 反证法1：设 B=0，论证 A=0； − 反证法2：论证 A∧¬B 是矛盾式；
− 公式演算法：利用命题定律和推理公式进行演算，得到结果。
• 定义：相容公式
− 设公式 H1, H2, …, Hn，若至少存在一个解释，使得 H1∧H2∧…∧Hn=1，则称 H1, H2, …, Hn 是相容的或一致的，否则称之为不相容的。 − H1, H2, …, Hn 相容即 H1∧H2 ∧ … ∧ Hn 是可满足的； − H1, H2, …, Hn不相容意味着 H1 ∧ H2 ∧ … ∧Hn 是矛盾的。
• 定义：推理规则
− 推理规则是从前提导出结论的推导过程中所依据的合理约定。包括： (1) P 规则（前提引入规则）：前提可视需要引入使用。
(2) T 规则（结论引入规则）：前面已经导出的有效结论都可以作为后续推导的前提引入。
(3) CP 规则（条件证明引入规则）：形如 H├ R→C 的有效性证明等价于形如 H∧R├ C 的有效性证明。
(4) 代入规则：对重言式的命题变量可以适当地使用重言代入规则。 (5) 置换规则：对公式的子式可以适当地使用等值置换规则。 (6) 分离规则：即推理定律(8)中的假言推理定律。
• 定理：CP 规则：H ⇒R→C 当且仅当 H∧R ⇒C
− 证明： H→(R→C) ⇔ H→(¬R∨C) ⇔ ¬H∨(¬R∨C) ⇔ (¬H∨¬R)∨C ⇔ ¬(H∧R)∨C ⇔ (H∧R)→C
− 即 H→(R→C) 是重言式当且仅当 (H∧R)→C 是重言式。 − 由演绎定理得：H ⇒R→C 当且仅当 H∧R ⇒C
• 定理：反证法
− 若 H1, H2, …, Hn 相容，则 H1, H2, … , Hn, ¬C 不相容当且仅当 H1, H2, …, Hn ⇒ C − 证明：
» 演绎定理推论：上述 H1, H2, …, Hn├ C 有效当且仅当 H1∧H2 ∧ …∧Hn∧¬C 为矛盾式。
» 利用演绎定理的推论容易得证。
• 推理规则总结：
− 前提引入（P）
− 结论引用（T） − 条件证明（CP） − 重言代入（{A/p}）
− 等价置换（E）（灵活应用命题定律） − 分离规则（I8） − 其他推理定律（Ik）
• 定义：演绎证明
− 从前提 H1, H2, …, Hn 推出结论 C 的一个演绎证明是构造命题公式的一个有限序列 A1, A2, …, A m ，其中： (1) A1= Hi (1≤ i ≤ n)
(2) 对任一 j ≥ 2，Aj 的形成为：
① 存在 k (1 ≤ k ≤ n) ，使得 Aj= Hk ；或
② 存在 1 ≤ j1< j2<…< js< j，使得 Aj1, Aj2, …, Ajs ├ Aj 有效 (3) Am = C
− 此时称 C 为该演绎的有效结论，或称从 H1, H2, …, Hn 演绎出 C。
• 例：证明 P→Q, Q→R, P ⇒ R
− 证： (1) P 前提引入 P (2) P→Q 前提引入 P (3) Q 引用(1)(2)分离 T(1)(2),I (4) Q→R 前提引入 P (5) R 引用(3)(4)分离 T(3)(4),I
• 例：证明 (P→Q)∧(R→S)∧(P∨R) ⇒ Q∨S − 证： (1) P∨R P (2) ¬P→R T(1),E (3) R→S P (4) ¬P→S T(2)(3),I (5) ¬S→P T(4),E (6) P→Q P (7) ¬S→Q T(5)(6),I (8) S∨Q T(7),E (9) Q∨S T(8),E
• 例：应用反证法，证明 P→Q, ¬(Q∨R) ⇒ ¬P
− 证：应用反证法，只需证明 P→Q, ¬(Q∨R), P ⇒ 0 (1) P P (2) P→Q P
(3) Q (4) ¬(Q∨R) (5) ¬Q∧¬R (6) ¬Q (7) Q∧¬Q (8) 0
T(1)(2),I P T(4),E T(5),I T(3)(6),I T(7),E
• 例：应用CP规则，证明 P→(Q→S), ¬R∨P, Q ⇒ R→S
− 应用CP规则，只需证明 P→(Q→S), ¬R∨P, Q, R ⇒ S (1) ¬R∨P P (2) R→P T(1),E (3) R P (4) P T(2)(3),I (5) P→(Q→S) P (6) Q→S T(4)(5),I (7) Q P
T(6)(7),I (8) S
• 例：证明 ¬(P→Q)→¬(R∨S), (Q→P)∨¬R, R ⇒ P↔Q
− 只需证明 ¬(P→Q)→¬(R∨S), (Q →P)∨¬R, R, ¬(P↔Q)⇒ 0 (1) ¬(P↔Q) P (2) ¬((P→Q)∧(Q→P) T(1),E (3) ¬(P→Q)∨¬(Q→P) T(2),E (4) (Q→P)→¬(P→Q) T(3),E (5) ¬(P→Q)→¬(R∨S) P
(6) (Q→P)→¬(R∨S) T(4)(5),I (7) (Q→P)∨¬R P (8) R→(Q→P) T(7),E (9) R→¬(R∨S) T(7)(8),I (10) R P (11) ¬(R∨S) T(9)(10),E (12) ¬R∧¬S T(11),E (13) ¬R T(12),I (14) ¬R∧R T(10)(13),I (15) 0 T(14),E
下一单元内容提示
− 命题逻辑公式的自然演绎系统