恆真式(tautology)又稱為套套邏輯恆真句恆真式重言式等。

恆真式是指在任何解釋下皆為真的命題,例如經典邏輯中的或「A=B,B=C,則A=C」。

命題邏輯的恆真式

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

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

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

恆真式的證明

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

例如以下式子:

 

可將   分別以真或假代入,然後根據規則算出各子式的真假值,最後算出整個式子真假值:

               
T T T T T T T T
T T F T F F F T
T F T F T T T T
T F F F T T T T
F T T F T T T T
F T F F T F T T
F F T F T T T T
F F F F T T T T

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

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

恆真蘊涵

如果所有讓 為真的命題賦值情況下 也都會為真,則稱  恆真蘊涵恆蘊涵 ,可記為 ,這相當於恆真式 [1]

假設  ,而  。此時 不是恆真式,因為 為假時 為假;但 ,因為一切使 為真的情況都會使 為真,而一切使 為真的情況都會使 為真。

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

參考資料

引用

  1. ^ Kleene 1967 p.27

來源

  • 左孝凌,李為鑑,劉永才.離散數學:上海科學技術文獻出版社,1982年
  • 王禮萍, 張樹功. 重言式和矛盾式的代數化證明[J]. 計算機與數字工程, 2009, 37(8):17-21.
  • 耿素雲 屈婉玲 張立昂 .離散數學:清華大學出版社,2008:7
  • 張鳳霞. 基於一元算子的模糊蘊涵和余蘊涵及其廣義重言式研究[D]. 山東大學, 2014.