基於上一篇部落格 【數理邏輯】命題邏輯 ( 命題與聯結詞回顧 | 命題公式 | 聯結詞優先順序 | 真值表 可滿足式 矛盾式 重言式 ) ;

一、等值演算

---

等值演算 :

• 等值式
• 基本等值式
• 等值演算置換規則

二、等值式

---

等值式概念 : $A,B$ 是兩個命題公式 , 如果 $A\leftrightarrow B$ 是永真式 , 那麼 $A,B$ 兩個命題公式是等值的 , 記做 $A\iff B$ ;

等值式特點 : $A$ 和 $B$ 兩個命題公式 , 可以 互相代替 , 凡是出現 $A$ 的地方都可以替換成 $B$ , 凡是出現 $B$ 的地方都可以替換成 $A$ ;

證明 $p\to q$ 與 $\neg p\vee q$ 是等值式 ;

$p$	$q$	$p\to q$	$\neg p\vee q$	$(p\to q)\leftrightarrow (\neg p\vee q)$
$0$	$0$	$1$	$1$	$1$
$0$	$1$	$1$	$1$	$1$
$1$	$0$	$0$	$0$	$1$
$1$	$1$	$1$	$1$	$1$

寫出兩個命題公式的真值表 , 從而 計算 $(p\to q)\leftrightarrow (\neg p\vee q)$ 的真值表 , 計算完成後發現其是 永真式 , 根據定義 , 這兩個命題公式是等價的 , $(p\to q)\iff (\neg p\vee q)$ ;

三、基本等值式

---

基本運算規律 :

• 冪等律 : $A\iff A\vee A$ , $A\vee A\iff A$
• 交換律 : $A\vee B\iff B\vee A$ , $A\wedge B\iff B\wedge A$
• 結合律 : $(A\vee B)\vee C\iff A\vee (B\vee C)$ , $(A\wedge B)\wedge C\iff A\wedge (B\wedge C)$
• 分配律 : $A\vee (B\wedge C)\iff (A\vee B)\wedge (A\vee C)$ , $A\wedge (B\vee C)\iff (A\wedge B)\vee (A\wedge C)$

新運算規律 :

• 德摩根律 : $\neg (A\vee B)\iff \neg A\wedge \neg B$ , $\neg (A\wedge B)\iff \neg A\vee \neg B$
  • 有了 與 ( $\wedge$ ) 非 ( $\neg$ ) , 就可以表示 或 ( $\vee$ )
  • 有了 或 ( $\vee$ ) 非 ( $\neg$ ) , 就可以表示 與 ( $\wedge$ )
• 吸收率 :
  • 前者將後者吸收了 : $A\vee (A\wedge B)\iff A$
  • 後者將前者吸收了 : $A\wedge (A\vee B)\iff A$ ;

$0,1$ 相關的運算律 :

• 零律 : $A\vee 1\iff 1$ , $A\wedge 0\iff 0$
  • $1$ 是或運算的 零元 , $0$ 是與運算的 零元 ;
  • 與零元進行運算還是零元 ;
• 同一律 : $A\vee 0\iff A$ , $A\wedge 1\iff A$
  • $0$ 是或運算的 單位元 , $1$ 是 與運算的 單位元
  • 與單位元進行運算還是單位元
• 排中律 : $A\vee \neg A\iff 1$
• 矛盾律 : $A\wedge \neg A\iff 0$

對偶原理適用於上述運算律 , 將兩邊的 $\wedge ,\vee$ 互換 , 同時 $0,1$ 互換 , 等價仍然成立 ;

等價蘊含運算規律 :

• 雙重否定率 : $\neg \neg A\iff A$
• 蘊涵等值式 : $A\to B\iff \neg A\vee B$
  • 替換蘊含聯結詞 : 蘊含聯結詞 $\to$ 不是必要的 , 使用 $\neg ,\vee$ 兩個聯結詞可以替換 蘊含聯結詞 ;
• 等價等值式 : $A\leftrightarrow B\iff (A\to B)\vee (B\to A)$
  • 雙箭頭 ( 等價聯結詞 ) 可以理解成重分必要條件
  • $A\to B$ ( 蘊含聯結詞 ) 理解成 $A$ 是 $B$ 的充分條件 , $B$ 是 $A$ 的必要條件
  • $B\to A$ ( 蘊含聯結詞 ) 理解成 $B$ 是 $A$ 的充分條件 , $A$ 是 $B$ 的必要條件
  • 替換等價聯結詞 : 等價聯結詞 $\leftrightarrow$ 不是必要的 , 使用 $\to ,\vee$ 兩個聯結詞可以替換 等價聯結詞 ;
• 等價否定等值式 : $A\leftrightarrow B\iff \neg A\leftrightarrow \neg B$
• 假言易位 ( 逆否命題 ) : $A\to B\iff \neg B\to \neg A$
  • $A$ 稱為 前件 , $B$ 稱為 後件 ( 結論 ) ;
• 歸謬論 ( 反證法 ) : $(A\to B)\wedge (A\to \neg B)\iff \neg A$
  • 這是反證法的原理 , 由 $A$ 推匯出 $B$ 和 $\neg B$ , $B$ 和 $\neg B$ 是矛盾的 , 則 $A$ 是錯的 , $\neg A$ 是對的 ;

四、基本運算

---

基本運算 :

等價等值式 : 等價聯結詞 $\leftrightarrow$ 不是必要的 , 使用 $\to ,\vee$ 兩個聯結詞可以替換 等價聯結詞 ;

蘊含等值式 : 蘊含聯結詞 $\to$ 不是必要的 , 使用 $\neg ,\vee$ 兩個聯結詞可以替換 蘊含聯結詞 ;

德摩根律 :

• 有了 與 ( $\wedge$ ) 非 ( $\neg$ ) , 就可以表示 或 ( $\vee$ )
• 有了 或 ( $\vee$ ) 非 ( $\neg$ ) , 就可以表示 與 ( $\wedge$ )

因此得出結論 , 與非 或者 或非 ( 二選一 ) , 可以表示所有的命題 ;

五、等值演算

---

證明 $p\to (q\to r)$ 與 $(p\wedge q)\to r$ 是等價的 ;

證明上述兩個命題是等價的 , 有兩種方法 :

• 一個是列出 真值表
• 另外一個就是進行 等值演算

$p\to (q\to r)$

使用 蘊含等值式 , 進行置換 : 將 $q\to r$ 置換為 $\neg q\vee r$

$\iff p\to (\neg q\vee r)$

繼續使用 蘊含等值式 , 將外層的蘊含符號置換 :

$\iff \neg p\vee (\neg q\vee r)$

使用 結合律 , 將 $p,q$ 結合在一起 :

$\iff (\neg p\vee \neg q)\vee r$

使用 德摩根律 , 將 $\neg$ 提取到外面 :

$\iff \neg (p\wedge q)\vee r$

使用 蘊含等值式 , 進行置換 ;

$\iff (p\wedge q)\to r$