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

可靠性(逻辑学)

可靠性指证明系统只推导出语义上成立的结论;可靠的论证则既有效,前提又都为真。

22 个关键词2 个词条链接到这里1 个尚未撰写AI 撰写
逻辑学形式系统形式证明逻辑后承命题逻辑一阶逻辑逻辑有效性整数可靠性(逻…

在逻辑学中,可靠性是指形式推导保持语义正确性的性质:只要一个结论可以从给定前提证明出来,它就在所有使这些前提为真的解释中为真。可靠性将形式系统的句法规则与赋予其表达式的意义联系起来。在另一种相关但不同的用法中,一个论证如果在逻辑上有效,而且所有前提都为真,就称为可靠的论证。

形式定义

设 Γ\Gamma 为一个前提集合,φ\varphi 为一个公式。记号

Γ⊢φ\Gamma\vdash\varphi

表示在某个指定的演绎系统中,存在一个从 Γ\Gamma 出发证明 φ\varphi 的形式证明。记号

Γ⊨φ\Gamma\models\varphi

表示 φ\varphi 是 Γ\Gamma 的逻辑后承:每一个满足 Γ\Gamma 中所有公式的解释,也都满足 φ\varphi。

如果对于每一组适当的 Γ\Gamma 和 φ\varphi,都有

Γ⊢φ⟹Γ⊨φ.\Gamma\vdash\varphi \quad\Longrightarrow\quad \Gamma\models\varphi.

就称该演绎系统相对于其语义是可靠的。

因此,句法上的可推导性不会超出语义后承的范围。可靠的系统不可能推导出这样的结论:它在某个满足其前提的解释中为假。

对于命题逻辑,解释是对命题变元的真值赋值。对于一阶逻辑,解释是指定了论域以及非逻辑符号之解释的结构。当公式含有自由变元时,满足关系还取决于如何将论域中的元素赋给这些变元。

因此,可靠性始终是相对于某种指定语义而言的。不能脱离对公式和后承关系的解释,独立地判断一组推理规则是否可靠。

弱可靠性与强可靠性

上述将前提纳入考虑的条件通常称为强可靠性。弱可靠性只涉及定理,也就是不借助前提即可推导出的公式:

⊢φ⟹⊨φ.\vdash\varphi \quad\Longrightarrow\quad \models\varphi.

这里,⊨φ\models\varphi 表示 φ\varphi 在逻辑上有效,即它在该语义所允许的每一个解释中都为真。

令 Γ\Gamma 为空集,即可由强可靠性得到弱可靠性。对于任意证明系统,反过来则未必成立,不过标准系统往往提供了将二者联系起来的方法。术语用法并不统一,许多论述直接用“可靠性”指称将前提纳入考虑的结果。

可靠的论证与可靠的证明系统

必须区分一个论证的可靠性与整个演绎系统的可靠性。

如果不存在使一个论证的所有前提为真、结论却为假的解释,就称该论证具有逻辑有效性。如果它有效,而且其前提事实上都为真,就称它是可靠的。

例如:

  1. 每一个能被 44 整除的整数都是偶数。
  2. 1212 能被 44 整除。
  3. 因此,1212 是偶数。

按照对整数和整除关系的通常解释,这是一个可靠的论证。

相比之下:

  1. 每一个素数都是奇数。
  2. 33 是素数。
  3. 因此,33 是奇数。

第二个论证的形式是有效的,但它并不可靠,因为它的第一个前提是假的:22 是素数,却不是奇数。不过,它的结论碰巧为真。

可靠的演绎系统并不保证输入其中的任意前提事实上为真。它所保证的是:当前提为真时,其推导不会引入假的结论。因此,在一个其他方面都正确的证明中使用了假前提,并不能说明其所依据的证明系统不可靠。

如何证明可靠性

可靠性定理是在元理论中证明的;元理论是一种数学框架,可以将公式、推导和解释作为对象加以研究。可靠性定理是连接证明论与模型论的核心结果之一。

对于许多证明系统,证明包含两个主要部分:

  1. 证明每一条逻辑公理或公理实例都有效。
  2. 证明每一条推理规则都保持相应的语义后承关系。

然后,对推导的长度或结构运用数学归纳法,即可确立所有推导的可靠性。

示例:肯定前件式

肯定前件式规则为

AA→BB.\frac{A\qquad A\to B}{B}.

在经典语义下,如果 AA 和 A→BA\to B 在某个解释中都为真,那么 BB 在该解释中也必定为真。因此,如果两个前提都是 Γ\Gamma 的语义后承,那么 BB 也是。

所以,对于由有效的逻辑公理以及肯定前件式等可靠规则构成的证明系统,可以通过逐行检查证明来确立其可靠性。

假设、撤销与附加条件

在自然演绎中,有些规则会撤销假设。这些规则的可靠性必须根据未撤销假设与结论之间的关系来表述,而不能仅仅表述为所列公式之间的保真性。

例如,蕴涵引入规则允许从在附加假设 AA 下对 BB 的推导,转到对 A→BA\to B 的推导,并撤销该假设。

量词规则尤其需要谨慎处理。标准的全称量词引入规则只在 xx 不自由出现于 Γ\Gamma 中任何未撤销假设的情况下,才允许如下形式的推理:

Γ⊢A(x)Γ⊢∀x A(x)\frac{\Gamma\vdash A(x)} {\Gamma\vdash\forall x\,A(x)}

如果没有这一限制,就可能从前提 P(x)P(x) 不合法地推得 ∀x P(x)\forall x\,P(x):赋给变元的某个对象具有某种性质,并不意味着每一个对象都具有该性质。

相继式演算的相应可靠性证明则通过对推导树进行归纳来完成。具体细节取决于相继式的含义,以及系统中可用的结构规则和逻辑规则。

与完备性的关系

可靠性和完备性分别涉及证明与语义之间联系的两个相反方向:

性质 形式条件 含义
可靠性 Γ⊢φ⇒Γ⊨φ\Gamma\vdash\varphi\Rightarrow\Gamma\models\varphi 凡是可推导的结论,在语义上都成立。
完备性 Γ⊨φ⇒Γ⊢φ\Gamma\models\varphi\Rightarrow\Gamma\vdash\varphi 每一个语义后承都可推导。

当二者都成立时,

Γ⊢φ⟺Γ⊨φ.\Gamma\vdash\varphi \quad\Longleftrightarrow\quad \Gamma\models\varphi.

标准的经典命题演算对于真值语义既可靠又完备。标准的经典一阶演算对于通常的一阶语义也既可靠又完备;其中,完备性方向由哥德尔完备性定理确立,该定理于1929年首次得到证明,并于1930年发表。

一个系统可以可靠但不完备。例如,某个命题演算没有公理,除了允许使用前提之外也没有任何规则,那么它只能推导出已经包含在前提中的公式。这个系统是可靠的,但它甚至无法在不借助前提的情况下证明最基本的有效公式。

可靠性与完备性还取决于所选取的解释类。同一个演算,相对于不同语义进行考察时,可能具有不同的性质。

与一致性及可满足性的关系

按照经典逻辑中一种常见的表述,如果一个理论无法推导出矛盾,就称它在句法上具有一致性。如果它至少有一个模型,就称它是可满足的。

如果使用的是可靠的证明系统,而且理论 TT 有模型,那么 TT 就是一致的。否则,可靠性将要求该模型满足一个矛盾。

然而,证明系统的可靠性并不意味着每一个可能的前提集合都是一致的。在经典逻辑中,相互矛盾的前提集合没有模型。因此,当 Γ\Gamma 不可满足时,对于每一个 φ\varphi,都有

Γ⊨φ\Gamma\models\varphi

因为不存在满足 Γ\Gamma 的解释可充当反例。这就是为什么从矛盾前提推导出任意结论,本身并不违反经典逻辑的可靠性。

一致性也弱于在预期解释中为真。一个理论可能有模型,却包含在其原本意图描述的特定结构中为假的陈述。

理论在预期模型中的可靠性

当一个理论被称为可靠时,通常是指它的所有定理在某个特定的预期结构中都为真。

对于算术理论 TT,它在标准结构 N\mathbb N 中可靠,是指对于每一个语句 φ\varphi,都有

T⊢φ⟹N⊨φT\vdash\varphi \quad\Longrightarrow\quad \mathbb N\models\varphi

这一要求比一阶逻辑的可靠性更强。逻辑可靠性保证定理在 TT 的每一个模型中为真,却不能单凭自身确立标准自然数结构就是这样的模型。如果 TT 的公理在 N\mathbb N 中为真,那么逻辑可靠性就能保证其定理在那里也为真。

可靠性与不完备性

哥德尔不完备定理并不与一阶逻辑的可靠性或完备性相矛盾。这些结果涉及不同的区分:

  • 逻辑完备性涉及在一个前提集合的每一个模型中为真。
  • 算术完备性要求理论能够判定其语言中的每一个语句。
  • 标准算术中的可靠性涉及在某个特定结构 N\mathbb N 中为真。

一个一致的、可有效公理化且足以表达算术的理论,不可能判定每一个算术语句。因此,如果这样的理论在 N\mathbb N 中可靠,它就会留下一些关于 N\mathbb N 的真命题无法证明。这与一阶逻辑的完备性并不冲突:一个在 N\mathbb N 中为真的语句,未必在该理论的每一个模型中都为真。

可靠性证明也依赖于其元理论假设。对于满足第二不完备定理通常假设且足够强的算术理论,如果该理论是一致的,它就不能证明自身的标准一致性陈述。恰当表述的内部可靠性断言会蕴含一致性,因此也面临相应的限制。

其他逻辑与计算中的应用

可靠性并不限于经典真值语义。直觉主义逻辑对于适当的代数语义和关系语义也有可靠性结果。在经典语义下有效的规则,在这些语义下可能不再成立;例如,排中律在直觉主义逻辑中并非普遍有效。

在形式验证中,可靠性确立的是:由验证演算推导出的性质,在赋予程序或系统的数学语义下成立。这与数学模型是否准确反映物理实现,仍然是两个不同的问题。

对于自动定理证明器,可靠性意味着它所宣称的每一个定理都有相应逻辑的支持。完备性则是另一个问题:可靠的证明器可能无法找到某些证明。此外,可靠且完备的一阶演算,也并不提供一种能够对每一个一阶逻辑有效性问题都停机并给出正确答案的算法。可靠性约束的是结论的正确性,而不是终止性或计算成本。