• 1.摘要
  • 2.基本信息
  • 3.定义
  • 4.相关定理
  • 5.离散数学领域
  • 5.1.重言式判定
  • 5.2.代入规则
  • 5.3.重言式示例
  • 5.4.离散例题
  • 6.计算机领域
  • 7.参考资料

重言式

重言式(Tautology )又称为永真式,它的汉语拼音为:[Chóng yán shì],是逻辑学的名词。命题公式中有一类重言式。如果一个公式,对于它的任一解释下其真值都为真,就称为重言式(永真式)。数理逻辑旨在利用有限的公理推出尽可能多的重言式,除此之外,重言式在计算机词法分析领域也具有重要应用。

基本信息

  • 中文名

    重言式

  • 外文名

    Tautology

  • 类别

    命题公式

  • 拼音

    Chóng yán shì

  • 别名

    永真式

  • 所属学科

    离散数学逻辑学

定义

给定一命题公式,若无论对分量作怎样的指派,其对应的真值永为T(True),则称该命题公式为重言式或永真公式。1

显然由联结词∨、∧、→和联结的重言式仍是重言式。

一个公式,如有某个解释I0, 在I0下该公式真值为真, 则称这公式是可满足的。P∨Q当取I0 = (T, F)即P = T, Q = F时便有P∨Q = T, 所以是可满足的。重言式当然是可满足的。

另一类公式是矛盾式(永假式或不可满足的)。如果一个公式,对于它的任一解释I下真值都是假,便称是矛盾式。如P∧P就是矛盾式。

不难看出这两类公式间有如下关系:

1. 公式A永真, 当且仅当永假。

2. 公式A可满足, 当且仅当非永真。

3. 不是可满足的公式必永假。

4. 不是永假的公式必可满足。

永真式与永假式互为否定式

相关定理

定理1: 任何两个重言式的合取或析取,仍然是一个重言式。1

定理2:一个重言式,对同一分量都用任何公式置换,其结果仍为一重言式。

定理3:设A,B为两个命题公式,A和B逻辑等价当且仅当双条件命题“A当且仅当B”成立。1

定理4:设A,B,C为合式公式,若A蕴含B且A是重言式,则B也是重言式。

定理5:若A蕴含B,B蕴含C,则A蕴含C,即蕴含关系是传递的。1

离散数学领域

重言式判定