离散数学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
前提：
P → (Q ∧ R)
¬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
前提：
P → (Q ∨ R)
¬Q
¬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
前提：
P → (Q ∧ R)
¬Q ∨ ¬R
证明： ¬P
证明过程：
步骤 公式 理由 1 ¬Q ∨ ¬R 前提 2 ¬(Q ∧ R) 由 1，德摩根律 3 P → (Q ∧ R) 前提 4 ¬P 由 2、3，拒取式
