aiwiki.page
中文
数学 / 离散数学与逻辑 / contradiction-logic

矛盾(逻辑学)

矛盾是在所有经典解释下均为假的公式;狭义上指一个陈述与其否定的合取。

23 个关键词1 个词条链接到这里3 个尚未撰写AI 撰写
逻辑学命题逻辑真值表一阶逻辑重言式布尔代数形式系统自然演绎矛盾(逻辑…

在逻辑学中,按照经典逻辑通行的语义定义,矛盾是在每一种解释下都为假的公式。最简单的例子是 P∧¬PP\land\neg P,意为“PP 且非 PP”。在较狭义的用法中,矛盾指任何具有这一明确形式的公式,或对一个陈述及其否定的同时断言。矛盾在一致性、逻辑后承和间接证明的研究中占有核心地位。如何处理矛盾取决于所采用的逻辑系统:经典逻辑和直觉主义逻辑允许从矛盾推出任意结论,而次协调逻辑则拒绝这种不受限制的推理。

定义与基本示例

在经典命题逻辑中,如果对公式 AA 的命题变元所作的每一种真值赋值 vv 都使该公式为假,那么 AA 就是一个矛盾:

v(A)=Ffor every valuation v.v(A)=\mathrm{F}\qquad\text{for every valuation }v.

例如,无论 PP 为真还是为假,P∧¬PP\land\neg P 都为假。其真值表如下:

PP ¬P\neg P P∧¬PP\land\neg P
真 假 假
假 真 假

矛盾式不一定在形式上直接呈现为一个陈述与其否定的合取。例如,

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

也是一个矛盾。如果 P→QP\to Q 和 PP 都为真,那么 QQ 必须为真,这就与最后一个合取支相冲突。

矛盾不同于一个仅仅碰巧为假的陈述。命题“巴黎位于德国”在通常解释下为假,但其命题形式只是 PP,可以被赋予任一真值。逻辑矛盾所涉及的是在相关解释下不可能为真,而不只是与实际事实不符。

在一阶逻辑中,相应的语义定义是:不存在任何结构及对自由变元的赋值能够满足该公式。因此,

∃x(R(x)∧¬R(x))\exists x\bigl(R(x)\land\neg R(x)\bigr)

在经典一阶语义下是矛盾的。

矛盾、重言式与可满足性

**重言式**是在每一种赋值下都为真的命题公式。偶然式在某些赋值下为真,在另一些赋值下为假。由此可将命题公式分为三类:

  • 重言式恒为真。
  • 矛盾式恒为假。
  • 偶然式既可以为真,也可以为假。

在经典命题逻辑中,公式 AA 是矛盾,当且仅当 ¬A\neg A 是重言式。等价地,

⊨¬A.\models\neg A.

这里,⊨\models 表示语义有效性。矛盾也称为不可满足的公式,因为不存在使其为真的赋值。

这些关系可用于检验论证。从前提 A1,…,AnA_1,\ldots,A_n 到结论 BB 的推理在经典逻辑中有效,当且仅当

A1∧⋯∧An∧¬BA_1\land\cdots\land A_n\land\neg B

不可满足。该推理的反例应当使所有前提为真而结论为假;不可满足性则表明不存在这样的反例。

在布尔代数中,每个矛盾式都表示最小元 00。特别地,

a∧¬a=0.a\land\neg a=0.

假常量与形式推导

形式语言通常包含一个常量 ⊥\bot,称为假常量或底,表示假。在经典语义下,⊥\bot 在每一种解释中都为假,且每个矛盾式都与它逻辑等价。

必须区分语义层面的断言与句法层面的断言:

  • Γ⊨A\Gamma\models A 表示,满足 Γ\Gamma 中所有公式的每一种解释也都满足 AA。
  • Γ⊢A\Gamma\vdash A 表示,可以使用某个特定形式系统的规则,从 Γ\Gamma 推导出 AA。

在自然演绎中,一条典型规则允许从 AA 和 ¬A\neg A 推导出 ⊥\bot:

A¬A⊥.\frac{A\qquad\neg A}{\bot}.

根据具体的表述方式,否定可以是原始联结词,也可以定义为

¬A:=A→⊥.\neg A := A\to\bot.

采用这一定义时,从 AA 和 ¬A\neg A 推导出假常量,就是对蕴涵消去规则的应用。

在可靠且完备的经典证明系统中,语义上的不可满足性与句法上可推导出假常量是等价的。哥德尔完备性定理确立了经典一阶逻辑中这两者之间的相应联系。

矛盾与不一致理论

矛盾是一个公式或若干断言的组合;**一致性**则是公式集或理论的性质。

按照通常的经典逻辑定义,如果对于某个公式 AA,有

T⊢AandT⊢¬A.T\vdash A \qquad\text{and}\qquad T\vdash\neg A.

那么理论 TT 在句法上是不一致的。在标准经典系统中,这等价于 T⊢⊥T\vdash\bot。如果一个理论没有模型,那么它在语义上不可满足。

即使一个前提集的每个成员单独来看都不是矛盾,该前提集仍可能是不一致的。例如,

{P,  P→Q,  ¬Q}\{P,\;P\to Q,\;\neg Q\}

没有经典模型,尽管其中三个公式各自都是可满足的。冲突存在于它们的组合之中。

同样,一个陈述可能与某个特定理论相冲突,但其本身并不是逻辑矛盾。与某个特定数学结构的公理不相容的断言,相对于该理论为假,却不一定在所有可能的结构中都为假。这一区分在模型论中,以及在区分逻辑真理与依赖特定理论的结果时,都十分重要。

爆炸原理

经典逻辑认可**爆炸原理**,其传统拉丁语表述为 ex contradictione quodlibet:从矛盾可以推出任何命题。

其常见形式为

P,¬P⊢Q,P,\neg P\vdash Q,

其中 QQ 是任意公式。一种经典推导方式是,先从 PP 推出 P∨QP\lor Q,再利用 ¬P\neg P 排除第一个析取支,从而得到 QQ。

从语义上看,没有任何经典解释能使 PP 和 ¬P\neg P 同时为真。因此,不存在使两个前提均为真而 QQ 为假的解释。该推理因而符合有效性的语义定义。

爆炸原理并不是说,只要犯了错误,每个陈述在通常解释下就都是真的。它的含义是:在满足爆炸原理的后承关系下,不一致的前提集蕴涵每一个公式。因此,要使经典理论能够有效区分哪些结论成立、哪些不成立,一致性至关重要。

在间接证明中的作用

在数学证明中,矛盾是多种间接推理形式的依据。

否定引入

如果假设 AA 会导出假常量,就可以撤销该假设并得出 ¬A\neg A:

Γ,A⊢⊥Γ⊢¬A.\frac{\Gamma,A\vdash\bot}{\Gamma\vdash\neg A}.

经典逻辑和直觉主义逻辑都接受这条规则。它证明了所假设的命题不可能成立。

经典反证法

在标准的经典反证法中,若假设 ¬A\neg A 后推导出假常量,就可以得出结论 AA:

Γ,¬A⊢⊥Γ⊢A.\frac{\Gamma,\neg A\vdash\bot}{\Gamma\vdash A}.

在直觉主义逻辑中,这种推理直接确立的只是 ¬¬A\neg\neg A。要从这一结果过渡到 AA,需要使用双重否定消去,而它在直觉主义逻辑中并非普遍有效。

因此,能够推导和使用矛盾,本身并不足以判定一个证明是否属于经典证明。决定性的问题在于,撤销临时假设后,该系统允许得出什么结论。

不矛盾律与其他逻辑

**不矛盾律**通常形式化为

¬(P∧¬P).\neg(P\land\neg P).

它不同于排中律 P∨¬PP\lor\neg P,也不同于爆炸原理。尽管这三者在经典逻辑中都成立,其他逻辑却对它们的作用作出了区分。

直觉主义逻辑能够证明不矛盾律,也接受爆炸原理,但并不普遍接受排中律。最小逻辑保留了直觉主义推理,却不包含从 ⊥\bot 推出任意公式的一般规则。

次协调逻辑拒绝不受限制的爆炸原理。它允许某些不一致的前提集具有非平凡的后承,而不是蕴涵每一个公式。因此,在经典逻辑之外,“矛盾”和“不可满足的公式”等表述并不总能互换使用。

某些次协调语义允许一个公式兼具真与假的状态。这并不意味着每个公式都可以接受,次协调性本身也并不主张任何实际的矛盾为真。认为某些矛盾为真的哲学立场称为真矛盾论,这是一个不同的主张。

历史背景与应用

亚里士多德在《形而上学》第四卷中对不矛盾律作了奠基性的讨论,强调同一属性不可能在同一方面既属于又不属于同一主体。现代符号逻辑通过形式语言、真值条件和推理规则重新表述了这些问题。

矛盾检测在自动推理中具有实际用途。布尔可满足性问题求解器可以判定一个命题公式是否存在使其为真的赋值;若结果为不可满足,就表明该公式在语义上是一个矛盾。

在形式验证中,可以将系统描述与待验证性质的否定结合起来。如果这一组合在选定的模型中不可满足,就说明模型中的任何行为都不会违反该性质。

在经典一阶自动定理证明中,基于归结的反驳方法试图从前提与结论的否定中导出矛盾。推导出空子句即可确立不可满足性。不过,一阶有效性在一般情况下是不可判定的,因此这类搜索并不保证对每个输入都能终止。

矛盾也有助于诊断不一致的规约。不可满足核是原始约束集的一个不可满足子集;找出这样的子集可以定位冲突,而不意味着其中每一条约束单独来看都是矛盾的。