命题逻辑的推理规则

推理


推理过程

$def:$ 设 $A$ 和 $B$ 是两个命题公式,当且仅当 $A\rightarrow B$ 是 重言式 时称由 $A$ 可推出 $B$ ,或 $B$ 是前提 $A$ 的结论,记为:$A\Rightarrow B$,读作如果 $A$ 为真那么 $B$ 为真。

推理方法

证明前提 $A$ 推出结论 $B$ 的方法有三种:

  • 真值表法
  • 等值演算法(利用等值式)
  • 在自然推理系统 $P$ 中用推理规则证明(重点)

推理规则:

以下规则虚熟记于心,下述逗号可以理解成 并且

  • 化简律:$p\wedge q\Rightarrow p, p\wedge q\Rightarrow q$;
  • 附加律:$p\Rightarrow p\vee q,q\Rightarrow p\vee q$
  • 假言推理:$p, p\rightarrow q \Rightarrow q$
  • 拒取式:$p\rightarrow q,\neg q\Rightarrow \neg p$
  • 析取三段论:$p\vee q,\neg p\Rightarrow q$
  • 合取式:$p,q\Rightarrow p\wedge q$
  • 假言三段论:$p\rightarrow q,q\rightarrow r\Rightarrow p\rightarrow r$ (传递性)
  • 等价三段论:$p\leftrightarrow q,q\leftrightarrow r\Rightarrow p\leftrightarrow r$(传递性)
  • 构造性二难:$p\rightarrow q,r\rightarrow s,p\vee r \Rightarrow q\vee s$
  • 归结式:$p\vee q,\neg p\vee s \Rightarrow q\vee s$

推理证明的一般步骤:

例1:证明下述式子:
$$
(p\vee q)\wedge(p\leftrightarrow r)\wedge(q\rightarrow s)\Rightarrow s\vee r
$$
$proof:$ 下表置换规则值得就是利用等值式进行等值演算得到的结论

步骤 公式 理由
1 $p\vee q$ 前提引入
2 $\neg p\rightarrow q$ 1,置换规则
3 $q\rightarrow s$ 前提引入
4 $\neg p\rightarrow s$ 2,3,假言三段论
5 $\neg s\rightarrow p$ 4,置换规则
6 $p\leftrightarrow r$ 前提引入
7 $(p\rightarrow r)\wedge(r\rightarrow p)$ 6,置换规则
8 $p\rightarrow r$ 7,化简律
9 $\neg s\rightarrow r$ 5,8,假言三段论
10 $\color{green}{s\vee r}$ 9,置换规则

例2: 给出下述推论的形式化证明

  • 若马会飞或羊吃草,则母鸡就会变飞鸟;
  • 如果母鸡变飞鸟,那么烤熟的鸭子还会跑;
  • 烤熟的鸭子不会跑,所以羊儿不吃草。

$proof:$
命题符号化:找到原子命题
令:

  • $p$:马会飞
  • $q$:羊吃草
  • $r$:母鸡变飞鸟
  • $s$:烤熟的鸭子还会跑

故上述命题符号化为:
前提:$(p\vee q)\rightarrow r,r\rightarrow s,\neg s$
结论:$\neg q$

一般证明法:

步骤 公式 理由
1 $\neg s$ 前提引入
2 $r\rightarrow s$ 前提引入
3 $\neg r$ 1,2 拒取式
4 $p\vee q\rightarrow r$ 前提引入
5 $\neg(p\vee q)$ 3,4 拒取式
6 $\neg p\wedge \neg q$ 5,置换规则
7 $\neg q$ ✅ 6,化简律

⚡️用归谬法(反证法)证明:
🔅思想:将结论否定,在由此推出矛盾

步骤 公式 理由
1 $\neg\neg q$ 附加前提引入,假设羊儿吃草
2 $q$ 1,置换规则
3 $p\vee q$ 2,附加律
4 $p\vee q\rightarrow r$ 前提引入
5 $r$ 3,4 假言推理
6 $r\rightarrow s$ 前提引入
7 $s$ 5,6 假言推理
8 $\neg s$ 前提引入
9 $\color{red}{s \wedge \neg s}$ 7,8 合取(❌出现矛盾,假设不成立)

例3: 🌞用附加前提法证明下述命题:

  • 如果小张和小王去看电影,则小李也去看电影;
  • 小赵不去看电影或小张不去看电影,小王去看电影;
  • 所以当小赵去看电影时,小李也去看电影。

$proof:$
命题符号化:找到原子命题
令:

  • $p$:小张去看电影
  • $q$:小王去看电影
  • $r$:小李去看电影
  • $s$:小赵去看电影

前提:$p\wedge q\rightarrow r,\neg s\vee p,q$
结论:$s\rightarrow r$

⭐️附加前提法:
若结论为 $s\rightarrow r$ ,可以把 $s$ 放到前提中,推证 $r$ 成立即可。

步骤 公式 理由
1 $s$ 附加前提引入
2 $\neg s \vee p$ 前提引入
3 $p$ 1,2,析取三段论
4 $q$ 前提引入
5 $p\wedge q$ 3,4 合取
6 $p\wedge q\rightarrow r$ 前提引入
7 $r$ 5,6 假言推理
# Math

温馨提示,此处可能会出现广告

评论


Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×

😏

📷

✍️