恒真式
恒真式(tautology)又称为套套逻辑、恒真句、恒真式或重言式等。
恒真式是指在任何解释下皆为真的命题,例如经典逻辑中的、、或“A=B,B=C,则A=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]。
假设 为 ,而 是 。此时 不是恒真式,因为 为假时 为假;但 ,因为一切使 为真的情况都会使 为真,而一切使 为真的情况都会使 为真。
根据定义,如果 为矛盾(恒假)命题,则 恒蕴涵 ,因为没有任何情况可使 为真,而当 为假时条件式 总是为真。
参考资料
引用
- ^ Kleene 1967 p.27
来源
- 左孝凌,李为鉴,刘永才.离散数学:上海科学技术文献出版社,1982年
- 王礼萍, 张树功. 重言式和矛盾式的代数化证明[J]. 计算机与数字工程, 2009, 37(8):17-21.
- 耿素云 屈婉玲 张立昂 .离散数学:清华大学出版社,2008:7
- 张凤霞. 基于一元算子的模糊蕴涵和余蕴涵及其广义重言式研究[D]. 山东大学, 2014.