【面向計算機的數理邏輯/軟體理論基礎筆記】命題邏輯系統的蘊含和自然演繹

基本定義

• 推理的定義：從一組前提合乎邏輯地推出結果的思維過程。
• 比如我們有一堆叫做 G 1 , G 2 . . . G n G_1,G_2...G_n G1​,G2​...Gn​的前提，在這些前提均成立的情況下，我們可以得到一個叫做 H H H的結論，這就叫做推理。類似于生活中的，提前：我課前預習，我上課做筆記，我下課及時複習，就可以推出我可以通過期末考試。
• 而在數學中，我們将 G 1 , G 2 . . . G n G_1,G_2...G_n G1​,G2​...Gn​和 H H H稱為公式，當且僅當對任意解釋 I I I，如果 I I I使得 G 1 ∧ G 2 ∧ . . . ∧ G n G_1 \wedge G_2 \wedge ... \wedge G_n G1​∧G2​∧...∧Gn​為真，則公式 H H H的結果也為真，這就叫做數學上的推理。
• 公式：
  1. 推理公式： G 1 , G 2 . . . G n ⇒ H G_1,G_2...G_n \Rightarrow H G1​,G2​...Gn​⇒H
  2. 通常，用集合 Γ \Gamma Γ來表示一組前提，記作 Γ = { G 1 , G 2 . . . G n } \Gamma=\{G_1,G_2...G_n \} Γ={G1​,G2​...Gn​}，此時，推理公式也可寫成： Γ ⇒ H \Gamma \Rightarrow H Γ⇒H

• 在這裡， ⇒ \Rightarrow ⇒也叫做蘊含，隻不過這個蘊含表示的是公式之間的關系，我們之前學的蘊含 → \to →是命題變元的運算符。
• 有時，我們使用 ⊢ \vdash ⊢代替 ⇒ \Rightarrow ⇒來表示公式之間的蘊含關系，如 Γ ⊢ H \Gamma \vdash H Γ⊢H
• 當 G 1 , G 2 . . . G n G_1,G_2...G_n G1​,G2​...Gn​能推出 H H H的時候，我們稱 G 1 , G 2 . . . G n ⇒ H G_1,G_2...G_n \Rightarrow H G1​,G2​...Gn​⇒H為有效的，否則稱為無效的。

• 定理：當且僅當 ( G 1 ∧ G 2 ∧ . . . ∧ G n ) → H (G_1 \wedge G_2 \wedge ... \wedge G_n) \to H (G1​∧G2​∧...∧Gn​)→H為永真公式時，前提集合 Γ = { G 1 , G 2 . . . G n } \Gamma=\{G_1,G_2...G_n \} Γ={G1​,G2​...Gn​}的邏輯結果為公式 H H H

永真公式也叫重言式，上述定理中，不管 G 1 , G 2 . . . G n G_1,G_2...G_n G1​,G2​...Gn​和 H H H如何取值， ( G 1 ∧ G 2 ∧ . . . ∧ G n ) → H (G_1 \wedge G_2 \wedge ... \wedge G_n) \to H (G1​∧G2​∧...∧Gn​)→H結果始終為1時，被稱為永真公式。

• 範例：判斷推理 P → Q , P ⇒ Q P \to Q,P \Rightarrow Q P→Q,P⇒Q是否有效

  \quad

  答案：題目中 P → Q P \to Q P→Q和 P P P是前提，Q是結論 ，詢問 P → Q , P ⇒ Q P \to Q,P \Rightarrow Q P→Q,P⇒Q是否有效是否有效，其實就是在詢問， P 、 Q P、Q P、Q取任意值時， ( ( P → Q ) ∧ P → Q ) ((P \to Q) \wedge P \to Q) ((P→Q)∧P→Q)的結果是否始終為真。有三種方法來驗證：

1. 畫真值表

P P P	Q Q Q	P → Q P \to Q P→Q	( P → Q ) ∧ P (P \to Q )\wedge P (P→Q)∧P	( ( P → Q ) ∧ P ) → Q ((P \to Q )\wedge P) \to Q ((P→Q)∧P)→Q
1	1
1	1	1
1	1
1	1	1	1	1

我們可以看到 ( ( P → Q ) ∧ P ) → Q ((P \to Q )\wedge P) \to Q ((P→Q)∧P)→Q的值始終為1，是以 P → Q , P ⇒ Q P \to Q,P \Rightarrow Q P→Q,P⇒Q有效。

1. 公式轉換

   ( ( P → Q ) ∧ P → Q ) ((P \to Q) \wedge P \to Q) ((P→Q)∧P→Q)

   = ¬ ( ( ¬ P ∨ Q ) ∧ P ) ∨ Q =\neg((\neg P \vee Q) \wedge P) \vee Q =¬((¬P∨Q)∧P)∨Q

   = ( ¬ ( ¬ P ∨ Q ) ∨ ¬ P ) ∨ Q =(\neg(\neg P \vee Q) \vee \neg P) \vee Q =(¬(¬P∨Q)∨¬P)∨Q

   = ¬ ( ¬ P ∨ Q ) ∨ ¬ P ∨ Q =\neg(\neg P \vee Q) \vee \neg P \vee Q =¬(¬P∨Q)∨¬P∨Q

   = ¬ ( ¬ P ∨ Q ) ∨ ( ¬ P ∨ Q ) =\neg(\neg P \vee Q) \vee (\neg P \vee Q) =¬(¬P∨Q)∨(¬P∨Q)

   = 1 =1 =1

   因為公式可以轉換為1，是以不管 P , Q P,Q P,Q取何值，公式始終為永真公式，也是以 P → Q , P ⇒ Q P \to Q,P \Rightarrow Q P→Q,P⇒Q有效。

2. 主析取範式

   ( ( P → Q ) ∧ P → Q ) ((P \to Q) \wedge P \to Q) ((P→Q)∧P→Q)

   = ¬ ( ( ¬ P ∨ Q ) ∧ P ) ∨ Q =\neg((\neg P \vee Q) \wedge P) \vee Q =¬((¬P∨Q)∧P)∨Q

   = ¬ ( ¬ P ∨ Q ) ∨ ¬ P ∨ Q =\neg(\neg P \vee Q) \vee \neg P \vee Q =¬(¬P∨Q)∨¬P∨Q

   = ( P ∨ ¬ Q ) ∨ ¬ P ∨ Q =(P \vee \neg Q)\vee \neg P \vee Q =(P∨¬Q)∨¬P∨Q

   = ( P ∨ ¬ Q ) ∨ ( ¬ P ) ∨ ( Q ) =(P \vee \neg Q)\vee (\neg P) \vee (Q) =(P∨¬Q)∨(¬P)∨(Q)

   = ( P ∨ ¬ Q ) ∨ ( ¬ P ∧ ( ¬ Q ∨ Q ) ) ∨ ( ( ¬ P ∨ P ) ∧ Q ) =(P \vee \neg Q) \vee (\neg P \wedge (\neg Q \vee Q)) \vee ((\neg P \vee P) \wedge Q) =(P∨¬Q)∨(¬P∧(¬Q∨Q))∨((¬P∨P)∧Q)

   = ( ¬ P ∧ ¬ Q ) ∨ ( ¬ P ∧ Q ) ∨ ( P ∧ ¬ Q ) ∨ ( P ∧ Q ) =(\neg P \wedge \neg Q) \vee (\neg P \wedge Q)\vee (P \wedge \neg Q)\vee (P \wedge Q) =(¬P∧¬Q)∨(¬P∧Q)∨(P∧¬Q)∨(P∧Q)

   此公式包含了所有的析取項，是以此公式為永真公式，是以 P → Q , P ⇒ Q P \to Q,P \Rightarrow Q P→Q,P⇒Q有效。

( ¬ P ∧ ¬ Q ) ∨ ( ¬ P ∧ Q ) ∨ ( P ∧ ¬ Q ) ∨ ( P ∧ Q ) (\neg P \wedge \neg Q) \vee (\neg P \wedge Q)\vee (P \wedge \neg Q)\vee (P \wedge Q) (¬P∧¬Q)∨(¬P∧Q)∨(P∧¬Q)∨(P∧Q)格式為： m 0 ∨ m 1 ∨ m 2 ∨ m 3 m_0\vee m_1\vee m_2\vee m_3 m0​∨m1​∨m2​∨m3​符合永真公式的條件。

基本公式

• 設 G , H , I G,H,I G,H,I為任意的命題公式
• 簡化規則：
  • I 1 : G ∧ H ⇒ G I_{1}:G \wedge H \Rightarrow G I1​:G∧H⇒G

  I 1 I_{1} I1​解釋：比如G是我不會飛，H是羊不會飛， G ∧ H G \wedge H G∧H表示我和羊都不會飛，那麼根據 G ∧ H G \wedge H G∧H可以知道，羊是不會飛的，是以 G ∧ H ⇒ G G \wedge H \Rightarrow G G∧H⇒G

  • I 2 : G ∧ H ⇒ H I_{2}:G \wedge H \Rightarrow H I2​:G∧H⇒H
• 添加規則
  • I 3 : G ⇒ G ∨ H I_{3}:G \Rightarrow G \vee H I3​:G⇒G∨H
  • I 4 : H ⇒ G ∨ H I_{4}:H\Rightarrow G \vee H I4​:H⇒G∨H
• 合取引入規則
  • I 5 : G , H ⇒ G ∧ H I_{5}:G,H \Rightarrow G \wedge H I5​:G,H⇒G∧H
• 選言三段論
  • I 6 : G ∨ H , ¬ G ⇒ H I_{6}:G \vee H,\neg G \Rightarrow H I6​:G∨H,¬G⇒H

  I 6 I_{6} I6​解釋：比如 G G G是我可以飛， H H H是鳥可以飛， G ∨ H G \vee H G∨H表示我可以飛或鳥可以飛或我和鳥都可以飛， ¬ G \neg G ¬G表示我不可以飛，在 G ∨ H , ¬ G G \vee H,\neg G G∨H,¬G公式中，因為必須有一個可以飛，而我不可以飛，可以得出，鳥是可以飛的，也就是 H H H，是以 G ∨ H , ¬ G ⇒ H G \vee H,\neg G \Rightarrow H G∨H,¬G⇒H

  • I 7 : G ∨ H , ¬ H ⇒ G I_{7}:G \vee H,\neg H \Rightarrow G I7​:G∨H,¬H⇒G
• 假言推理規則
  • I 8 : G → H , G ⇒ H I_{8}:G \to H,G \Rightarrow H I8​:G→H,G⇒H
• 否定後件式
  • I 9 : G → H , ¬ H ⇒ ¬ G I_{9}:G \to H, \neg H \Rightarrow \neg G I9​:G→H,¬H⇒¬G
• 假言三段論
  • I 10 : G → H , H → I ⇒ G → I I_{10}:G \to H,H \to I \Rightarrow G \to I I10​:G→H,H→I⇒G→I
• 二難推論
  • I 11 : G ∨ H , G → I , H → I ⇒ I I_{11}:G \vee H,G \to I ,H \to I \Rightarrow I I11​:G∨H,G→I,H→I⇒I

I 11 I_{11} I11​解釋： G ∨ H G \vee H G∨H表示 G G G或 H H H有一個成立， G → I G \to I G→I表示 G G G蘊含 I I I， G G G成立則 I I I也成立， H → I H \to I H→I表示 H H H蘊含 I I I， H H H成立則 I I I也成立。是以，可以通過 G ∨ H , G → I , H → I G \vee H,G \to I ,H \to I G∨H,G→I,H→I成立，得到 I I I也成立。

蘊含關系範例

• 如果 a 是偶數，則 a 能被 2 整除；a 是偶數。是以，a 能被 2 整除。

  可描述為： P → Q , P ⇒ Q P \to Q, P \Rightarrow Q P→Q,P⇒Q

  假言推理規則

• 如果一個人是單身漢，則他不幸福；如果一個人不幸福，則他死得早。是以，單身漢死得早。

  可描述為： P → Q , Q → R ⇒ P → R P \to Q, Q \to R \Rightarrow P \to R P→Q,Q→R⇒P→R

  假言三段論

• 若你發電子郵件告訴我密碼，則我将完成程式的編寫；我沒有完成程式的編寫。是以，你沒

  有發電子郵件告訴我密碼。

  可描述為： P → Q , ¬ Q ⇒ ¬ P P \to Q, \neg Q \Rightarrow \neg P P→Q,¬Q⇒¬P

  否定後件式

• 這個案件的兇手肯定是王某或陳某；經過調查，王某不是兇手。是以，陳某是兇手。

  可描述為： P ∨ Q , ¬ P ⇒ Q P \vee Q,\neg P \Rightarrow Q P∨Q,¬P⇒Q

  選言三段論

自然演繹法推理

• 推理規則：
  • 規則P：稱為前提引用規則，在推導過程中，可随時引入前提集合中的任意一個前提
  • 規則T：稱為邏輯結果引用規則，在推導的過程中，可以随時引入公式 S，該公式 S 是由其前的一個或多個公式推導出來的邏輯結果
  • 規則CP：(稱為附加前提規則)：如果能從給定的前提集合 Γ \Gamma Γ與公式P推導出S，則能從此前提集合 Γ \Gamma Γ推導出P → \to →S

• 演繹：從前提集合 Γ \Gamma Γ推出結論 H H H的一個演繹是構造命題公式的一個有限序列：

  H 1 , H 2 , H 3 . . . H n − 1 , H n H_1,H_2,H_3...H_{n-1},H_n H1​,H2​,H3​...Hn−1​,Hn​

  在序列中，總共分為三部分

  • 第一部分是題目中給出的公式，我們叫做前提，他們在題目中通常以 Γ = { P ∨ Q , ¬ S , P → S } \Gamma=\{P \vee Q , \neg S,P \to S\} Γ={P∨Q,¬S,P→S}等形式給出，這裡面總共由三個前提，可以用 H 1 = P ∨ Q , H 2 = ¬ S , H 3 = P → S H_1 = P \vee Q,H_2 = \neg S,H_3 = P \to S H1​=P∨Q,H2​=¬S,H3​=P→S表示。
  • 第二部分是有效結論，由題目中前提和上文中提到的一些列基本公式 ( I 1 , I 2 . . . I 11 ) (I_1,I_2...I_{11}) (I1​,I2​...I11​)推到出來的公式，比如我們可以通過 H 2 H_2 H2​和 H 3 H_3 H3​推導出 H 4 = ¬ P H_4 = \neg P H4​=¬P
  • 第三部分是結論，通常 H n H_n Hn​就是我們要推導出的結論，也寫作 H H H，
• 演繹-直接證明法範例：
  • 例題一：設前提集合 Γ = P ∨ Q , Q → R , P → S , ¬ S \Gamma = {P \vee Q, Q \to R, P \to S, \neg S} Γ=P∨Q,Q→R,P→S,¬S，結論 H = R ∧ ( P ∨ Q ) H = R \wedge (P \vee Q) H=R∧(P∨Q)。證明： Γ ⇒ H \Gamma \Rightarrow H Γ⇒H

    • 答案：

      ( 1 ) P → S P ( 2 ) ¬ S P ( 3 ) ¬ P T , ( 1 ) , ( 2 ) ( 4 ) P ∨ Q T , ( 1 ) , ( 2 ) ( 5 ) Q T , ( 3 ) , ( 4 ) , I ( 6 ) Q → R P ( 7 ) R T , ( 5 ) , ( 6 ) , I ( 8 ) R ∧ ( P ∨ Q ) T , ( 4 ) , ( 7 ) , I \begin{aligned} &(1)P \to S & P \\ &(2)\neg S& P \\ &(3)\neg P & T,(1),(2) \\ &(4)P \vee Q & T,(1),(2) \\ &(5)Q & T,(3),(4),I \\ &(6)Q \to R & P \\ &(7) R & T,(5),(6),I \\ &(8)R \wedge (P \vee Q) & T,(4),(7),I \\ \end{aligned} ​(1)P→S(2)¬S(3)¬P(4)P∨Q(5)Q(6)Q→R(7)R(8)R∧(P∨Q)​PPT,(1),(2)T,(1),(2)T,(3),(4),IPT,(5),(6),IT,(4),(7),I​

• 公式右邊标記符号解釋：
  • P P P指推理規則 P P P，标記上 P P P的公式，表示該公式都是題目中給定的前提；
  • T T T指推理規則 T T T，标記上 T , ( 1 ) , ( 2 ) T,(1),(2) T,(1),(2)的公式，表示左邊的公式是根據第1和第2條公式推出的有效結論， T , ( 1 ) , ( 2 ) T,(1),(2) T,(1),(2)有時也寫作 T 1 , 2 T_{1,2} T1,2​；
  • I I I指基本公式，标記上 I I I的公式，表示左邊的公式是根據上文提到的 ( I 1 , I 2 . . . I 11 ) (I_1,I_2...I_{11}) (I1​,I2​...I11​)中的一條或多條公式推出的有效結論。
• 每一個公式前面依次有一個序号，最後的序号表示這個證明的推演長度。

• 例題二：設前提集合 Γ = P → ( Q → S ) , ¬ R ∨ P , Q \Gamma = {P \to( Q \to S), \neg R \vee P,Q} Γ=P→(Q→S),¬R∨P,Q，結論 H = R → S H = R \to S H=R→S。證明： Γ ⇒ H \Gamma \Rightarrow H Γ⇒H
  • 答案：

( 1 ) R P ( 附 加 前 提 ) ( 2 ) ¬ R ∨ P P ( 3 ) P T , ( 1 ) , ( 2 ) , I ( 4 ) P → ( Q → S ) P ( 5 ) Q → S T , ( 3 ) , ( 4 ) , I ( 6 ) Q P ( 7 ) S T , ( 5 ) , ( 6 ) , I ( 8 ) R → S C P , ( 1 ) , ( 7 ) \begin{aligned} &(1) R & P(附加前提) \\ &(2) \neg R \vee P & P \\ &(3) P & T,(1),(2), I \\ &(4) P \to (Q \to S) & P \\ &(5) Q \to S & T,(3),(4), I \\ &(6) Q & P \\ &(7) S & T,(5),(6), I \\ &(8) R \to S & CP,(1),(7) \\ \end{aligned} ​(1)R(2)¬R∨P(3)P(4)P→(Q→S)(5)Q→S(6)Q(7)S(8)R→S​P(附加前提)PT,(1),(2),IPT,(3),(4),IPT,(5),(6),ICP,(1),(7)​

第一個公式後面标記為“ P P P(附加前提)”，是因為我們想要證明 Γ ⇒ H \Gamma \Rightarrow H Γ⇒H，雖然 R R R不在 Γ \Gamma Γ中，但當結論 H = R → S H = R \to S H=R→S成立時， R R R必須也要成立，是以假設 R R R是前提，這就叫做附加前提。使用附加前提的公式，要标記上 C P CP CP和引用的公式序号。

命題演繹舉例

• 符号化下面的語句，并使用演繹法證明
• 例題一：若數 a 是實數，則它不是有理數就是無理數。若 a 不能表示成分數，則它不是有理數。a 是實數且它不能表示成分數。是以，a 是無理數。
  • 答案：

    • 設命題

      P : a P : a P:a 是實數；

      Q : a Q : a Q:a 是有理數；

      R : a R : a R:a 是無理數；

      S : a S : a S:a 能表示成分數。

    • 推理符号化成：

      P → ( Q ∨ R ) , ¬ S → ¬ Q , P ∧ ¬ S ⇒ R P \to (Q \vee R), \neg S \to \neg Q, P \wedge \neg S \Rightarrow R P→(Q∨R),¬S→¬Q,P∧¬S⇒R

    • 推理過程：

      ( 1 ) R P ( 附 加 前 提 ) ( 2 ) ¬ R ∨ P P ( 3 ) P T , ( 1 ) , ( 2 ) , I ( 4 ) P → ( Q → S ) P ( 5 ) Q → S T , ( 3 ) , ( 4 ) , I ( 6 ) Q P ( 7 ) S T , ( 5 ) , ( 6 ) , I ( 8 ) R → S C P , ( 1 ) , ( 7 ) \begin{aligned} &(1) R & P(附加前提) \\ &(2) \neg R \vee P & P \\ &(3) P & T,(1),(2), I \\ &(4) P \to (Q \to S) & P \\ &(5) Q \to S & T,(3),(4), I \\ &(6) Q & P \\ &(7) S & T,(5),(6), I \\ &(8) R \to S & CP,(1),(7) \\ \end{aligned} ​(1)R(2)¬R∨P(3)P(4)P→(Q→S)(5)Q→S(6)Q(7)S(8)R→S​P(附加前提)PT,(1),(2),IPT,(3),(4),IPT,(5),(6),ICP,(1),(7)​

• 例題二：如果馬會飛或羊吃草，則母雞就會是飛鳥；如果母雞是飛鳥，那麼烤熟的鴨子還會跑；烤熟的鴨子不會跑。是以羊不吃草。

這段語句的前提和結論與我們日常生活中的認識有所不同，但不影響我們進行推理。

• 答案：

  • 設命題

    P : P : P: 馬會飛；

    Q : Q : Q: 羊吃草；

    R : R : R: 母雞是飛鳥；

    S : S : S: 烤熟的鴨子會跑。

  • 推理符号化成：

    ( P ∨ Q ) → R , R → S , ¬ S ⇒ ¬ Q (P \vee Q) \to R, R \to S, \neg S \Rightarrow \neg Q (P∨Q)→R,R→S,¬S⇒¬Q

  • 推理過程：

    ( 1 ) ¬ S P ( 2 ) R → S P ( 3 ) ¬ R T , ( 1 ) , ( 2 ) , I ( 4 ) ( P ∨ Q ) → R P ( 5 ) ¬ ( P ∨ Q ) T , ( 3 ) , ( 4 ) , I ( 6 ) ¬ P ∧ ¬ Q T , ( 5 ) , E ( 7 ) ¬ Q T , ( 6 ) , I \begin{aligned} &(1) \neg S & P \\ &(2)R \to S & P \\ &(3)\neg R &T,(1),(2), I \\ &(4) (P \vee Q) \to R & P \\ &(5)\neg (P \vee Q) & T,(3),(4), I \\ &(6) \neg P \wedge \neg Q & T,(5), E \\ &(7) \neg Q & T,(6), I \\ \end{aligned} ​(1)¬S(2)R→S(3)¬R(4)(P∨Q)→R(5)¬(P∨Q)(6)¬P∧¬Q(7)¬Q​PPT,(1),(2),IPT,(3),(4),IT,(5),ET,(6),I​

• E E E指等價公式，标記上 E E E的公式，表示公式是根據等價公式轉換過來的。
• 等價公式有幂等律、交換律等。