可靠性定理

维基百科,自由的百科全书

可靠性定理(或健全性)是数理逻辑的最基本结果。它们有关于某个形式逻辑语言与这个语言的形式演绎系统的特定语义理论。可靠性定理有两种主要变体:弱可靠性的和强可靠性的。“强”与“弱”的意义在于,强可靠性考虑句子的任意集合,而与弱可靠性有关的句子的空集是这种集合之一。大多数的演绎系统,强可靠性和弱可靠性都成立,但並非全部的演繹系統都如此。

論證可靠性[编辑]

邏輯論證可靠若且唯若

  • 論證有效
  • 所有前提皆已被證實為真。

弱可靠性定理[编辑]

演绎系统的弱可靠性定理声称,在这个演绎系统中任何可证明的句子,在所有释义或这个理论所基于的语言的语义理论的模型上为真。用符号表示,这里的S是演绎系统,而L是语言和一起的它的语义理论,而P是L的句子:若,则

强可靠性定理[编辑]

演绎系统的强可靠性定理声称,演绎系统所基于的语言的任何句子P,可以从这个语言的一个句子集合Γ推导出来,则它也是这个集合Γ的语义推论,在使Γ的所有成员为真的任何模型也使P为真的意义上。用符号表示,这里的Γ是L句子的一个集合:若,则

与完备性定理的联系[编辑]

可靠性定理的逆命题是语义完备性定理。在强形式下,它声称对于一个演绎系统和语义理论,是一个句子集合的语义推论的任何句子可以在这个演绎系统中从这个集合推导出来。(在一阶完备性定理的情况下常叫做哥德尔完备性定理。)用符号表示:若,则

非形式的,演绎系统的可靠性定理告诉我们用这个演绎系统可以推导或证明的任何东西都是你希望能够推导或证明的东西。因此,没有你不想推导出的东西可以被推导出来。所以,推导关于语义可以被信任。完备性告诉我们你希望能被推导或证明的所有东西都可以被推导出来。

哥德尔第一不完备定理保证对于有充分表达力的语言,可能没有演绎系统关于经典语义是完备的,在其中所有句子是要么为真要么为假。因此,不是所有可靠的演绎系统都是完备的。

而可靠性一般被认为是对有价值的演绎系统根本上的最小要求。这是因为如果演绎系统是不可靠的,在这个系统中可以被推导或证明的一个句子不告诉我们关于这个句子的语义性质的任何事情。

参见[编辑]

引用[编辑]