发布时间 : 星期六 文章江苏科技大学 数理逻辑2010试题、数理逻辑2011试题更新完毕开始阅读4cbd52eaec3a87c24128c425
命题1.8 可数个可数集的并集是可数集. 证明：设可数个可数集分别为A0,A1,A2,令A??i?0, 其中Ai?{a0,a1,a2,}(i?0,1,2,). 我们
Ai. 把A的元素按照如下次序排成阵列
a00,a01,a02,a03,a10,a11,a12,a13,
a20,a21,a22,a23,a30,a31,a32,a33, (0.1)
并依据箭头指示的方向顺序对集合A的元素进行枚举. 不难看出该枚举算法可以保证A的每个元素在有限步里被枚举到, 由此说明A是可数的. ■
命题1.2.2. 实数集R是不可数集.
证明: 根据上述分析知, 只要证明所有形如(1.2.2)的2小数的全体是不可数的. 运用反证法: 如果全体形如(1.1.2)的2小数是可数的, 则这些数的全体可枚举如下：
##0.x00x01x02x030.x10x11x12x13
0.x20x21x22x230.x30x31x32x33 (0.2)
其中每个xij是0或1. 我们利用枚举(2.3)构造一2#小数y?0.y0y1yn满足: yi?1如果
xii?0; yi?0如果xii?1, 则y不同于(2.3)所枚举出的全体2#小数中的任意一个, 由此产
生矛盾. 此矛盾说明全体2#小数是不能枚举的, 因此它们是不可数的, 所以R也是不可数的. ■
例3-1. 证明自然数加法f(x,y)?x?y是原始递归函数.
证明: 首先我们注意到自然数集上的恒等函数I(x)?x是原始递归函数，因为
1I(x)?P(. )于是f(x,y)?x?y可以通过递归模式f(x,0)?I(x)，f(x,y?1)?S(f(x,y))1x定义. 所以f(x,y)?x?y是原始递归函数. ■
例3-2. 证明自然数乘法g(x,y)?x?y是原始递归函数.
证明: 我们已经证明了x?y是原始递归的，在此基础上g(x,y)?x?y可以通过递归模式g(x,0)?O(x)，g(x,y?1)?g(x,y)?x定义. 所以g(x,y)?x?y是原始递归函数. ■
命题6.1（可靠性定理）. 每个L的定理都是L的重言式. 证明：设A是L的定理，则存在L的证明，即公式序列A1,A2,,An满足：每个Ai
或是L的公理，或是由某两个前面的公式Aj和Ak经MP得到. 现在我们施归纳于公式序列
A1,A2,,An的长度n来证明.
奠基步：当n?1时，上述序列中只有一个公式A，那么A必为L的公理L1，L2或L3，由例6-2知A一定是重言式.
归纳推证步：假设命题对小于n的证明序列成立. 在证明序列A1,A2,,An中公式
An是A，可分两种情况考虑：
情况1. An是公理，那么由奠基步的证明即得A是重言式.
情况2. An是由公式Aj,Ak(j?k?n)经MP得到，此时不妨设Ak为Aj?An的形式. 由于Aj和Ak是出现在An之前L的定理，故根据归纳假定知Aj和Ak均为重言式，即对任意赋值v，均有v(Aj)?T和v(Ak)?v(Aj?An)?T. 如果v(An)?F，那么根据赋值的定义就有v(Aj)?F，此和v(Aj)?T矛盾. 此矛盾说明对任意的赋值v必有v(An)?T，故An是L的重言式. 根据归纳法原理命题得证.
命题6.2. 形式系统L是协调的.
证明：如果L不是协调的，则存在L的公式A使得|??LA并且|??LA. 由可靠性
定理知A和A都是重言式，即对任意L的赋值v，v(A)和v(~A)均为T，由此而产生矛盾. ■
**命题6.3. L的扩充L是协调的充要条件为存在一个合式公式不是L的定理.
证明：如果L*协调，则对任意公式A，A和一公式不是L*的定理.
A不能同时为L*的定理，故至少有
??L*B并且|??L*B. 由于L*是L的扩反之，假定L*不协调，那么就有公式B使得|充，那么L的定理也是L的定理，由例2-2（b）知B?(B?A)是L的定理, 于是运
*??L*A, 其中A为任意公式，这样任意公式A都成为了L*的用推理规则MP就可得到|定理. 换句话说，如果有公式不是L*的定理，那么L*必是协调的. ■
在我们通过对L的公理集添加公式得到扩充L*时，必须保证L*是协调的. 下面命题为我们提供了一个途径.
命题6.4. 设L*是L的协调扩充，A是L的公式并且A不是L*的定理. 则我们把
A加到L*的公理中得到L*的扩充L**是协调的. 证明：设A是L的公式且不是L*的定理. 现将A加入L*的公理集得到L*的扩充L**.
如果L**不协调，则有某公式B使得|??L**B并且|??L**B，由此可得|??L**A. 由于L**
与L*的区别在于L**只比L*多一条公理A，所以在L*中，若假设A则可推出A，即
A|??L*A，运用演绎定理就得到|??L*A?A. 注意到(A?A)?A是L的
定理因而也是L*的定理，于是运用MP可得|??L*A，这和A不是L*的定理矛盾.
命题6.5. 设L*是L的协调扩充，则存在L*的协调完备扩充.
证明：首先注意到L的全部公式是可数的，因而我们可用某种方法将之排列出来. 设
A0,A1,A2,?
是L的全部公式的一个枚举. 我们构造L*的扩充序列J0,J1,,Jn,如下：
首先令J0?L*，构造J1：如果|??J0A0，则令J1?J0；如果没有|??J0A0，即A0不是J0的定理，则把A0加入J0的公理集得到J1. 根据命题6.4知J1是协调的.
假定已有Jn?1且Jn?1是协调的，我们构造Jn: 如果|??Jn?1An-1，则令Jn?Jn?1，如果没有|??Jn?1An-1，则把An-1加入Jn?1的公理集得到Jn. 同样Jn是协调的.
按照这样的方法依次构造下去，我们得到了一个扩充序列J0?J1??Jn?，其中
J0?L*而每个Jn(n?0,1,)都是协调的.
构造形式系统J，它的公理集是由所有J0,J1,J是L*的协调完全扩充.
,Jn,的公理集的并集组成. 我们证明
首先J是协调的：如果J不协调，那么有公式A使得|??JA并且|??J中能证明A和
A，即在JA都是J的定理. 但由于证明的序列是有穷的，因而最多只用到J的有
穷条公理，因此必有某个Jn，Jn的公理包含这些公理，于是在Jn中就可证明A和A都是Jn的定理，这和Jn协调矛盾.
其次J是完全的：设A是任一L的公式，不妨设A为Ak. 如果Ak是Jk的定理，那么Ak也是J的定理; 否则Ak将成为Jk?1的定理，当然也是J的定理.
命题5 在解释I中，赋值v满足公式(?xi)A的充要条件是在I中至少存在一个与v i?等价的赋值v'，v'满足A。
证明：设v满足(?xi)A，则v满足~(?xi)A，故v不满足(?xi)(~A)，于是有一个与v
i?等价的赋值v'不满足~A，故此v'满足A。
反之，若与v i?等价的v满足A，那么v'不满足~A，故v不满足(?xi)A，可得..v满足~(?xi)A，即v满足(?xi)A。
命题7 设I是L的解释，A是L的公式，v和w是I中的赋值，且对A中的每个自由变元xi均有v(xi)?w(xi)，则v满足A当且仅当w满足A。
证明：施归纳于A中联结词的数目
奠基步：A是原子公式，如Ain(t1,t2,?,tn)，对任意出现在ti中的自由变元和常元，均有 v和w的值相同，因而v(ti)?w(ti)(i?1,2,?n)，故v满足A的充要条件为w满足A。归纳推导：情形1，A是~B；
情形2，A是B?C；
这两种情形可以直接证明，只要用到有关的定义以及归纳假定即可，因而留作习题。 情形3 ，A是(?xi)B，假定v满足A，设w'是任意与w i?等价的赋值，由于xi在。我们(?xi)B中不自由出现，则对A中出现的任意自由变元y，w'(y)?w(y)?v(y)。定义v'如下：
v'(xi)?w'(xi)
v'(xj)?v(xj)(j?i)
则v'是与v i?等价的赋值，由v满足(?xi)B知，v'满足B知v'满足B，注意到对B中的任意自由变元y(y?xi)，均有v'(y)?v(y)?w'(y)，又有v'(xi)?w'(xi)，根据归纳假定知w'满足B，而w'是任意与w i?等价的赋值，故有w满足(?xi)B，即w满足公式A。
反之，类似可证明若w满足(?xi)B，则v满足(?xi)B。根据归纳法原理，命题得证。□
命题3.2. L 的任意公式A都与一个L 的前束范式B等价.
该命题可施归纳于A的长度来进行证明,证明的思路可归结为求某公式前束范式的一般方法：
步骤1. 对给定的公式A，改变A中的约束变元，使它们都不同于A中的自由变元,
??A1?A； 而且不同的约束变元取不同的名，这样得到A1. 根据变元替换定理知|步骤2. 如果A是原子公式，那么它已是前束范式;
步骤3. （1）如果A是~C的情形：设C的前束范式为?1xi1?2xi2的前束范式为?1xi1?2xi2?kxikD，那么A?kxik(~D),其中
?j?????如果?j是?,
?如果?是?.?j?（2）如果A是C?B的形式：设C的前束范式为?c1xi1?c2xi2束范式为?b1xi1?b2xi2?ckxikC*，B的前
?blxilB*，则A的前束范式为
(?c1xi1)(?ckxik)(?b1xj2)(?blxjl)(C*?B*).
（3）如果A是C?(B?D)，则先求B?D的前束范式F，再求C?F的前束范式.
C?B)?D，则先求C?B的前束范式F，再求F?D的（4）如果A是(前束范式. ■
数理逻辑和计算机科学有着十分密切的关系，无论是数字电子计算机雏形的图灵机，还是数字电路的布尔代数，以及作为程序设计工具的语言、程序设计方法学、关系数据库、知识库、编译方法、人工智能等领域均离不开数理逻辑。同时，由于两者的相互渗透推动了数理逻辑的发展。因此学好数理逻辑对于计算机科学理论的研究有重要的作用。数理逻辑的研究内容概括的讲是两个演算加上四论[1]，两个演算为命题演算和谓词演算；四论为递归论、证明论、模型论、公理集合论。其中命题演算和谓词演算是四论的共同基础。命题演算的一个具体模型就是逻辑代数。逻辑代数也叫做开关代数，它的基本运算是逻辑加、逻辑乘和逻辑非，也就是命题演算中的“或”、“与”、“非”，运算对象只有两个数 0和 1，相当于命题演算中的“真”和“假”。
利用电子元件组成相当于逻辑加、逻辑乘和逻辑非的门电路（就是逻辑元件）。还能把简单的逻辑元件组成各种逻辑网络，这样任何复杂的逻辑关系都可以有逻辑元件经过适当的组合来实现，从而使电子元件具有逻辑判断的功能。因此，在自动控制或智能控制方面有重要的应用。其应用可参考文献[5，6]。本文主要介绍数理逻辑在计算机科学中的应用。