# 离散数学3-命题逻辑推理理论
本质是"逻辑推导游戏"，给定几个前提，用固定规则一步步推出结论。**套路固定**，背下规则就能拿分。
## 一、核心推理规则公式：
假言推理(MP) | A→B, A ⇒ B | 肯定前件→肯定后件 |
拒取式(MT) | A→B, ¬B ⇒ ¬A | 否定后件→否定前件 |
假言三段论(HS) | A→B, B→C ⇒ A→C | 蕴含传递 |
析取三段论(DS) | A∨B, ¬A ⇒ B | 否定一边得另一边 |
附加律 | A ⇒ A∨B | 或上一个随便什么 |
化简律 | A∧B ⇒ A (或 ⇒ B) | 拆开且 |
合取引入 | A, B ⇒ A∧B | 两个真拼一起 |
构造性二难 | A∨B, A→C, B→C ⇒ C | 分情况讨论 |
一句话理解每条规则
> 假言推理 (MP)：A→B, A ⇒ B
>
> ▎ "如果下雨地就湿" + "下雨了" → 地湿了
>
> 就是你有了蕴含关系，现在前件真的发生了，后件必然发生。最自然的推理方式。
>
> * * *
>
> 拒取式 (MT)：A→B, ¬B ⇒ ¬A
>
> ▎ "如果下雨地就湿" + "地没湿" → 没下雨
>
> 后件没发生，说明前件不可能发生。反过来说"地湿了→下雨了"是错的（可能洒水），但"地没湿→没下雨"一定对。
>
> * * *
>
> 假言三段论 (HS)：A→B, B→C ⇒ A→C
>
> ▎ "下雨→地湿" + "地湿→路滑" → "下雨→路滑"
>
> 蕴含关系的传递。两个箭头首尾相连，可以把中间项消掉。
>
> * * *
>
> 析取三段论 (DS)：A∨B, ¬A ⇒ B
>
> ▎ "要么喝茶要么喝咖啡" + "不喝茶" → 喝咖啡
>
> 二选一，否定了一个，只能选另一个。排除法。
>
> * * *
>
> 附加律：A ⇒ A∨B
>
> ▎ "今天下雨" → "今天下雨或者中彩票"
>
> 一个真命题，或上任何东西都还是真。因为析取只要有一个为真就为真。
>
> * * *
>
> 化简律：A∧B ⇒ A
>
> ▎ "下雨且刮风" → "下雨"
>
> 合取为真意味着两边都真，单独拆出一个当然真。
>
> * * *
>
> 合取引入：A, B ⇒ A∧B
>
> ▎ "下雨"是真的 + "刮风"是真的 → "下雨且刮风"是真的
>
> 化简律的反向操作。两个分别成立的命题，可以拼成合取。
>
> * * *
>
> 构造性二难：A∨B, A→C, B→C ⇒ C
>
> ▎ "要么坐公交要么打车" + "坐公交会迟到" + "打车也会迟到" → 反正迟到
>
> 两个选项都导致同一个结果，那不管你选哪个，结果都跑不掉。分情况讨论的最终结论。
* * *
核心就两条
80%的题只用 MP 和 MT：
MP: 有蕴含 + 前件发生 → 推出后件 MT: 有蕴含 + 后件没发生 → 推出前件没发生
其他六条是辅助。做题的时候就问自己：
▎ 我现在手里有哪些"已知为真"的命题？我能用哪条规则从它们"合法地"产生一个新的真命题？
每次只推一步，推到最后一行恰好是你想证的结论，就完成了。
## 二、例题练习：
tips：前提：首先先给题目翻译，变成符号化再进行下一步的推理
> ### 例题1
>
> 前提：
>
> 1. P → (Q ∧ R)
>
> 2. ¬Q
>
>
> 证明： ¬P
> 证明过程：
>
> 1 | P → (Q ∧ R) | 前提 |
2 | Q ∧ R → Q | 重言式（简化律） |
3 | P → Q | 1, 2 假言三段论 |
4 | ¬Q | 前提 |
5 | ¬P | 3, 4 拒取式 |
在进行第二个例题之前，我们先了解一个概念：合取引入
在进行一些特殊题型的时候，为了后面的推导，我们需要在对于以下
`Q ∨ R，¬Q， ¬R` 这种情况的时候需要使用到合取引入的操作
具体为把`Q ∨ R` 转换成`¬Q ∧ ¬R`，一般这步之后会跟摩根律的使用，接下来我们来看看例题
> 例题2
>
> 前提：
>
> 1. P → (Q ∨ R)
>
> 2. ¬Q
>
> 3. ¬R
> 证明：¬P
>
> 证明过程：
>
> | **步骤** | **公式** | **理由** | **这一步到底在说什么** |
> | --- | --- | --- | --- |
> | 1 | ¬Q | 前提 | Q 是假的 |
> | 2 | ¬R | 前提 | R 也是假的 |
> | 3 | ¬Q ∧ ¬R | 由 1、2，合取引入 | 既然 Q 假而且 R 假，那“Q假 **且** R假”就是真的 |
> | 4 | ¬(Q ∨ R) | 由 3，德摩根律 | “Q假且R假” 这句话换个说法就是“并非(Q真或R真)”。换句话说，**Q ∨ R 整个是假的** |
> | 5 | P → (Q ∨ R) | 前提 | 如果 P 真，那么 Q ∨ R 必须真 |
> | 6 | ¬P | 由 4、5，拒取式 | 现在 Q ∨ R 是假的，所以 P 不能真（否则会推出假的 Q ∨ R）。所以 P 是假的 |
我们再来看一道相反的镜像题，巩固一下
> 例题3
>
> **前提：**
>
> 1. P → (Q ∧ R)
>
> 2. ¬Q ∨ ¬R
>
>
> **证明：** ¬P
> 证明过程：
>
> | **步骤** | **公式** | **理由** |
> | --- | --- | --- |
> | 1 | ¬Q ∨ ¬R | 前提 |
> | 2 | ¬(Q ∧ R) | 由 1，德摩根律 |
> | 3 | P → (Q ∧ R) | 前提 |
> | 4 | ¬P | 由 2、3，拒取式 |