上一页

ⓘ 恆真式




                                     

ⓘ 恆真式

恆真式 (tautology)又称为 套套邏輯 、 恆真句 、 恆真式 或 重言式 等。

恆真式 是指在任何解釋下皆為真的命題,例如 P ∨ ¬ P {\displaystyle P\vee \neg P} 、 P → P {\displaystyle P\to P} 、 P ∧ Q ∨ R ↔ P ∨ R ∧ Q ∨ R {\displaystyle P\wedge Q\vee R\leftrightarrow P\vee R\wedge Q\vee R} 或" A=B,B=C,则A=C”。

                                     

1. 命題邏輯的恆真式

命題邏輯上,如某式為一連串命題變項的組合,將每個命題變項分別代入真、假,運算結果總是為真,則該式為一恆真式。

恆真式有無限多種,以下為常見例子:

  • ¬ A ∧ B ⇔ ¬ A ∨ ¬ B {\displaystyle \lnot A\land B\Leftrightarrow \lnot A\lor \lnot B} (若非 A 且 B 皆為真,則非 A 或非 B 為真,反之亦然):此即德摩根定律
  • A ∨ ¬ A {\displaystyle A\lor \lnot A} ( A 或非 A ):此即排中律,此式只有一個命題變項 A ,根據定義,無論將A代入「真」或代入「假」,運算結果都會是「真」
  • ¬ A → B ∧ ¬ A → ¬ B) → A {\displaystyle \lnot A\to B\land \lnot A\to \lnot B)\to A} (若非 A 蘊涵 B 且非 A 蘊涵非 B ,則非 A 恆為假,則 A 恆為真):此即歸謬法的原理
  • A → B ⇔ ¬ B → ¬ A {\displaystyle A\to B\Leftrightarrow \lnot B\to \lnot A} (若 A 蘊涵 B 則非 B 蘊涵非 A ,反之亦然):此即換質換位律
  • A → B ∧ B → C) → A → C {\displaystyle A\to B\land B\to C)\to A\to C} (若 A 蘊涵 B 且 B 蘊涵 C ,則 A 蘊涵 C ):此即三段論的原理
  • A ∨ B ∧ A → C ∧ B → C) → C {\displaystyle A\lor B\land A\to C\land B\to C)\to C} (若 A 或 B 其中之一為真,且兩者皆蘊涵 C ,則 C 為真):此即枚舉法之原理
                                     

2. 恆真式的證明

命題邏輯上證明恆真式的方式之一是代入真值表,對於有 n 個變項的式子,總共會有2 n 種組合。因此有時會非常複雜。

例如以下式子:

A ∧ B → C) ⇔ A → B → C) {\displaystyle A\land B\to C)\Leftrightarrow A\to B\to C)} 。

可將 A {\displaystyle A} 、 B {\displaystyle B} 、 C {\displaystyle C} 分別以真或假代入,然後根據規則算出各子式的真假值,最後算出整個式子真假值:

由於每一列的最後運算結果皆為「真」( T ),故此式為恆真式。

另外一些方式是用語法方式如自然演繹法等從空集合中證明出恆真句。

                                     

3. 恆真蘊涵

如果所有讓 R {\displaystyle R} 為真的命題賦值情況下 S {\displaystyle S} 也都會為真,則稱 R {\displaystyle R} 恆真蘊涵 ( 恆蘊涵 ) S {\displaystyle S} ,可記為 R ⊨ S {\displaystyle R\models S} ,這相當於恆真式 R → S {\displaystyle R\to S} 。

假設 S {\displaystyle S} 為 A ∧ B ∨ ¬ B {\displaystyle A\land B\lor \lnot B} ,而 R {\displaystyle R} 是 A ∧ C {\displaystyle A\land C} 。此時 S {\displaystyle S} 不是恆真式,因為 A {\displaystyle A} 為假時 S {\displaystyle S} 為假;但 R ⊨ S {\displaystyle R\models S} ,因為一切使 R {\displaystyle R} 為真的情況都會使 A {\displaystyle A} 為真,而一切使 A {\displaystyle A} 為真的情況都會使 S {\displaystyle S} 為真。

根據定義,如果 R {\displaystyle R} 為矛盾(恆假)命題,則 R {\displaystyle R} 恆蘊涵 S {\displaystyle S} ,因為沒有任何情況可使 R {\displaystyle R} 為真,而當 R {\displaystyle R} 為假時條件式 R → S {\displaystyle R\to S} 總是為真。

                                     

4. 参考

左孝凌,李为鉴,刘永才.离散数学:上海科学技术文献出版社,1982年

王礼萍, 张树功. 重言式和矛盾式的代数化证明. 山东大学, 2014.