恒真式

恒真式(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.