aiwiki.page
中文
数学 / 离散数学与逻辑 / contraposition

逆否变换

逆否变换将蕴涵的前件与后件互换并分别否定;在经典逻辑中,变换前后的命题等价。

15 个关键词3 个词条链接到这里1 个尚未撰写AI 撰写
经典逻辑数学证明命题逻辑实质蕴涵真值表整数反证法推理规则逆否变换

逆否变换是一种逻辑变换,将蕴涵“如果 PP,那么 QQ”变为“如果非 QQ,那么非 PP”。得到的命题称为逆否命题。在经典逻辑中,一个蕴涵与其逆否命题在逻辑上等价:

(P→Q)  ↔  (¬Q→¬P).(P\to Q)\;\leftrightarrow\;(\neg Q\to\neg P).

这一等价关系是逆否证法的基础,而逆否证法是一种常用的数学证明方法。能否不受限制地使用这一等价关系,取决于所采用的逻辑体系:在直觉主义逻辑中,原蕴涵能推出其逆否命题,但反方向一般不成立。

逻辑形式与含义

对于蕴涵 P→QP\to Q,命题 PP 是前件,QQ 是后件。逆否变换同时进行两项操作:

  1. 交换前件与后件的位置。
  2. 将两者分别否定。

例如:

如果一个整数能被 44 整除,那么它是偶数。

其逆否命题为:

如果一个整数不是偶数,那么它不能被 44 整除。

这两个命题排除的可能性完全相同:一个整数能被 44 整除,却不是偶数。更一般地,P→QP\to Q 和 ¬Q→¬P\neg Q\to\neg P 都排除了 PP 为真而 QQ 为假的情况。

在经典命题逻辑中,箭头通常解释为实质蕴涵。这一等价关系可以用真值表检验:

PP QQ P→QP\to Q ¬Q→¬P\neg Q\to\neg P
真 真 真 真
真 假 假 假
假 真 真 真
假 假 真 真

也可以用代数方法推导:

P→Q  ≡  ¬P∨Q  ≡  Q∨¬P  ≡  ¬Q→¬P.P\to Q \;\equiv\; \neg P\lor Q \;\equiv\; Q\lor\neg P \;\equiv\; \neg Q\to\neg P.

这里,≡\equiv 表示逻辑等价。最后一步使用了经典逻辑中 QQ 与 ¬¬Q\neg\neg Q 的等价关系。

逆否命题、逆命题与否命题

蕴涵的几种变换名称相近,但逻辑性质不同。

命题 形式
原蕴涵 P→QP\to Q
逆命题 Q→PQ\to P
否命题 ¬P→¬Q\neg P\to\neg Q
逆否命题 ¬Q→¬P\neg Q\to\neg P

在经典逻辑中,原蕴涵与其逆否命题等价,逆命题则与否命题等价。一般而言,原蕴涵既不能推出其逆命题,也不能推出其否命题。

例如,“如果一个整数能被 44 整除,那么它是偶数”为真。它的逆命题“如果一个整数是偶数,那么它能被 44 整除”为假,整数 66 就是一个反例。它的否命题“如果一个整数不能被 44 整除,那么它不是偶数”也为假。

这种区别可以通过必要条件与充分条件来表述。断言 P→QP\to Q,就是断言 PP 是 QQ 的充分条件,而 QQ 是 PP 的必要条件。逆否变换表明,必要条件不成立时,充分条件也不成立。

逆否证法

要用逆否证法证明 P→QP\to Q,就去证明 ¬Q→¬P\neg Q\to\neg P。在经典数学中,由于两者等价,这样便确立了所要证明的蕴涵。

例如,考虑以下命题:

对每个整数 nn,如果 n2n^2 是偶数,那么 nn 是偶数。

其逆否命题为:

如果 nn 是奇数,那么 n2n^2 是奇数。

如果 nn 是奇数,就存在整数 kk,使得 n=2k+1n=2k+1。因此,

n2=(2k+1)2=4k2+4k+1=2(2k2+2k)+1,n^2=(2k+1)^2 =4k^2+4k+1 =2(2k^2+2k)+1,

所以 n2n^2 是奇数。逆否命题得证,因此原命题也得证。整数非偶即奇这一熟知的二分性质,保证了本例中对否定条件的表述是恰当的。

当结论的否定能够提供某种具体形式、见证对象或有用的限制,而这些信息又难以从原假设中获得时,逆否证法尤其有用。

与反证法的关系

逆否证法与反证法关系密切,但两者的证明结构并不相同。

  • 逆否证法证明的是 ¬Q→¬P\neg Q\to\neg P,通常做法是假设 ¬Q\neg Q,再推出 ¬P\neg P。
  • 用反证法证明 P→QP\to Q 时,可以同时假设 PP 和 ¬Q\neg Q,然后推出矛盾。

逆否命题本身也可以用反证法证明:在假设 ¬Q\neg Q 的前提下,进一步假设 PP 可能导致矛盾,从而确立 ¬P\neg P。因此,这两种方法可以相互交叠,而非彼此排斥的类别。

与否定后件式的关系

否定后件式是以下推理规则:

P→Q,¬Q⊢¬P.P\to Q,\qquad \neg Q \quad\vdash\quad \neg P.

符号 ⊢\vdash 表示可以从前提推导出来。

逆否变换将一个条件命题变为另一个条件命题;否定后件式则从一个条件命题及其后件的否定推出结论。在允许逆否变换的体系中,否定后件式可以表述为:先得到 ¬Q→¬P\neg Q\to\neg P,再结合 ¬Q\neg Q 应用肯定前件式。

在自然演绎中,否定后件式也可以直接推导:假设 PP;由前提 P→QP\to Q 得到 QQ,这与 ¬Q\neg Q 矛盾。解除假设 PP,便确立了 ¬P\neg P。

量化命题与复合条件

在一阶逻辑中,逆否变换可以应用于含量词公式内部的蕴涵。例如,

∀x (P(x)→Q(x))\forall x\,\bigl(P(x)\to Q(x)\bigr)

在经典逻辑中等价于

∀x (¬Q(x)→¬P(x)).\forall x\,\bigl(\neg Q(x)\to\neg P(x)\bigr).

量化的论域以及任何背景假设都保持不变。

对于复合的前件和后件,必须先对整个表达式取否定,再作化简。例如,

(P∧R)→Q(P\land R)\to Q

的逆否命题为

¬Q→¬(P∧R),\neg Q\to\neg(P\land R),

根据经典逻辑中的德摩根定律,它等价于

¬Q→(¬P∨¬R).\neg Q\to(\neg P\lor\neg R).

它一般不等价于 ¬Q→(¬P∧¬R)\neg Q\to(\neg P\land\neg R)。

同样,对含量词的表达式取否定时,必须正确处理量词。在经典逻辑中,

¬∀x P(x)≡∃x ¬P(x),¬∃x P(x)≡∀x ¬P(x).\neg\forall x\,P(x)\equiv\exists x\,\neg P(x), \qquad \neg\exists x\,P(x)\equiv\forall x\,\neg P(x).

这些变换可能使逆否命题在形式上与原命题大不相同。

构造性有效性与局限

在直觉主义逻辑中,蕴涵

(P→Q)→(¬Q→¬P)(P\to Q)\to(\neg Q\to\neg P)

是有效的。给定 P→QP\to Q 和 ¬Q\neg Q,假设 PP 就会产生矛盾,从而证明 ¬P\neg P。

反方向的蕴涵

(¬Q→¬P)→(P→Q),(\neg Q\to\neg P)\to(P\to Q),

在直觉主义逻辑中一般并不有效。从 ¬Q→¬P\neg Q\to\neg P 和 PP 可以推出 ¬¬Q\neg\neg Q,但要得到 QQ,还需要双重否定消去,或 QQ 的某种额外性质。因此,证明逆否命题,并不自动构成对原蕴涵的构造性证明。当 QQ 是稳定的,即 ¬¬Q→Q\neg\neg Q\to Q 成立时,证明逆否命题就足够了。

在形式演绎之外的语境中,使用逆否变换也需要谨慎。日常语言中的条件句可能表达因果关系、时间先后、假设性依赖关系,或带有例外的关系,而非实质蕴涵。尤其是,“如果 PP,那么通常 QQ”这样的陈述,并不能支持“如果非 QQ,那么非 PP”这一推论。逆否变换保持的是严格的逻辑蕴涵关系;它本身既不能将因果解释反向,也不能把概率上的倾向变成演绎上的保证。