数理逻辑-余俊伟（一） (5-4)

2.4.3 演绎规则

推广证明的定义，得到演绎。演绎比证明多一个条件，要求φi为给定公式集中的公式。

一步步推下来的序列可视为一个演绎规则。常见演绎规则如德摩根律等。

2.4.4 演绎定理‬

证内定理时不能用假设，演绎规则的假设必须是前面就得到的。因此还要一些能消去假设的原则如演绎定理，可以从有假设的演绎得到内定理。演绎定理有逆。演绎定理和逆揭示了内定理和有前提（假设）间的关系。

2.4.5 公理的独立性

公理系统的出发点是公理，公理是否冗余即公理独立性问题。演绎规则不变，一条公理不能由其他公理推出，则该公理为独立的。如果一公理系统的每条公理都独立则该公理系统独立。演绎规则不变，一公理模式不能由其他公理模式推出则该公理模式独立。公理系统中每个公理模式都独立则该公理系统独立。

如果想证“不能推出”，用语义赋值方法。想证“推出”，用形式证明方法。

2.5 可靠性和完全性

前面给出了语言和语义，定义了重言式和语义后承。然后给出了一个公理系统（公理、推理规则），讨论如何进行形式证明和演绎来获得内定理和演绎规则。接下来检查该公理系统是否是命题逻辑的形式化，即检查可靠性和完全性。如果该公理系统的内定理都是语义解释所肯定的公式则可靠，如果该公理系统在语义解释下的肯定公式都是内定理则完全。

2.5.1 可靠性证明

即证明命题演算的所有内定理都是重言式。

2.5.2 完全性证明

完全性有两种证法，一是亨金证明（用极大一致集），二是哥德尔证明。

公式集中某公式推出矛盾则该公式集是不一致的，反之则是一致的。极大一致集是该公式集本身为一致集，并上任意公式后仍然一致。可数语言的系统往往有不可数个极大一致集。不同系统的极大一致集不同。一个公理系统的极大一致集可以不是另一公理系统的一致集。极大一致集的重要引理即林登鲍姆引理，即每个一致集都能扩张成极大一致集。极大一致集不再有一致的真扩张。还有一个定理：φ是任意公式，演绎推出φ，当且仅当φ属于每个极大一致集。命题演算的内定理集恰好是所有命题殴极大一致集的公共部分。

亨金证明：φ不是内定理等值于φ不是重言式，用林登鲍姆引理和上面那个定理证。完全性定理：若φ不是内定理则其矛盾式~φ一致，再由林登鲍姆引理的存在极大一致集使得~φ属于极大一致集，存在赋值使得~φ为1则φ为0。

2.5.3 广义完全性定理

根据可靠性和完全性定理，对于命题逻辑，语法内定理和语义重言式对应。继续进一步考虑语法演绎与语义后承的对应性。

广义可靠性定理：如果极大一致集演绎推出φ，则极大一致集推出的是重言式φ。

广义完全性定理：如果极大一致集推出的是重言式φ，则极大一致集演绎推出φ。

2.5.4 证明公理的独立性

证明公理独立性与证明可靠性相似。证明思路：要证某公理模式有独立性，先选一性质使得其他公式有该性质，演绎规则保持该性质不变，但公理模式中能找出一个公式没有该性质，因此该公理模式不能从其他推理模式中推出，因此该公理模式有独立性。

2.5.5 紧致性和可判定性

紧致性定理：某公式集可满足当且仅当该公式集的每个有穷自己都是可满足的。

可判定性：如果存在一个算法告诉我们某公式是否是内定理，则该逻辑可判定。命题逻辑的真值表算法能判定重言式，因此命题逻辑可判定。而一阶逻辑不可判定。用此可区分命题逻辑和一阶逻辑。

除了公理系统还有自然演绎系统。

第3章 一阶逻辑

3.1 导言

3.1.1 问题引入

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。