重言式
重言式(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