第六讲 褂氆理系统(下) .pptVIP

逻辑、代数与集合 ——关联及形式化方法初步 主讲 计算机学院 网络工程系 刘冬宁 邮箱 liudn@gdut.edu.cn 电话 时间 逢周三下午7,8节 15:30 — 17:15 地点 教二 — 425 第六讲 公理系统（下） 可靠性 完全性 （注：本讲很难，请提前预习） 1 可靠性 定理6.3 （可靠性定理）L的每一个定理都是重言式。 证明：令A是L的一条定理，施归纳于A在L中的证明序列。 基础步骤：设A的证明只含一个公式，即A自身，则A为L的一条公理。平凡的，A为重言式。 现在假设：A的证明包含n个公式，n＞1，此时A或者是公理（平凡的），或者是通过MP规则从证明中两个此前的公式推得。这两个公式必为B和(B?A)的模式。 据归纳假设，B和(B?A)为重言式。假设A不为重言式，则存在v使得v(A) = 0。∵(B?A)为重言式，所以对于v，v(B?A) = 1，则v(B) = 0，与B是重言式矛盾。所以假设不成立，A为重言式。 2 完全性 定义6.6 L的一个扩充是一个形式系统，它通过修改或扩大公理组使得所有原来的定理仍是定理（也可能引入新的定理）而得到。 定义6.7 L的一个扩充是一致的，如果不存在L的公式A，使得A和?A都是这个扩充的定理。 定理6.4 （一致性定理）L是一致的。 证明：假设L不一致。则存在A，使得=LA且=L?A，据可靠性定理，A和?A均为重言式，对于任意v，v(A) = v(?A)，故矛盾。 定理6.5 L的扩充L*是一致的，当且仅当存在一公式，它不是L*的定理。 定理6.6 令L*是L的一致的扩充，并且令A是L的公式且不是L*的定理。那么L**也是一致的。这里L**是L的扩充，它由L*补充?A为公理而得到。 定义6.8 L的一个扩充是极大的（完全的），如果对每个公式A，或者A或者?A是该扩充的一条定理。 定理6.7 （林登堡姆引理）令L*是L的一致扩充，那么存在L*的一个极大一致扩充。 定理6.8 如果L*是L的一个一致的扩充，则存在一种赋值，使得L*的每个定理取值为1。 定理6.9 （完全性定理）如果A是一个公式且是一重言式，则=LA。 定理6.10 （判定性定理）L是可判定的，即存在着一种能行的方法判定给定的L的公式是否为L的定理。 路漫漫其修远兮，吾将上下而求索