数理逻辑（讲义）(5)

被使用的规则带有的假设条件已经在

?1|?A1,?2|?A2,........,?k?1|?Ak?1中出现。

n称为证明长度。

定理1 (有限化) 设?|?A，则存在?的一个有限子集?，使得：?0|?A。 证明： 对证明长度n进行归纳。在归纳过程中，对每一条规则进行讨论。

如：(??):如果?|?A,?|?A?B,则?|?B。

对?|?A,?|?A?B分别使用归纳假设。

存在有限子集?1??,?2??:?1|?A?B,?2|?A。

000,?0由单调规则：?12|?A?B,?1,?2|?A。

00000由规则(??)：?1,?2|?B,?1??2|?B。

0000从而存在有限集：?1??2??,?1??2|?B。

0000其它规则类似讨论。 ■

定理2 (可传性) 设?|??',?'|?A ，则?|?A。

证明： (1) 对?'|?A使用有限化定理，得到一个有限子集：

{A1,A2,......,An}??',A1,A2,......,An|?A。

每一个1?k?n，有?|?Ak。

对A1,A2,......,An|?A重复应用(??)得到： |?(A1?(A2?(......(An?A)......)。 (4) ?|?(A1?(A2?(......(An?A)......)。 (5) 重复应用(??)得到：?|?A。■ 例．?A?B|??B?A。

证明：(1) ?A?B,?B,?A|??A (?) (2) ?A?B,?B,?A|??B (?) (3) ?A?B,?B,?A|??A?B (?)

20

(4) ?A?B,?B,?A|?B (??,(1)(3)) (5) ?A?B,?B|?A (??,(2)(4))

(6) ?A?B|??B?A (??,(5))

21

一些常用定律： 幂等律：A|?|???A。

??A|?A(1)??A,?A|??A(?)

(2)??A,?A|???A(?)(3)??A|?AA|???A(1)A,?A|?A(?)(2)A,?A|??A(?)(??,(1)(2))

(??,(1)(2))(3)A|???A可传律：如果?|??',?'|?A。则?|?A。

(1)?'|?A(己知)(2)B1,......,Bk|?A(B1,......,Bk??)(3)?|?B1,......,Bk(4)B1,......,Bk?1|?Bk?A(??,2) (5)|?B?(B?......(B?A).....)(??,*)

12k(5)?|?B1?(B2?......(Bk?A).....)(6)?,B1|?B2?......(Bk?A).....)(??,5)(7)?|?A(??,*)归谬律：如果?,A|?B,?,A|??B，则?|??A。

(1)??A|?A(2)?,??A|?A(单调,(1))(3)?,A|?B(己知)(4)?,??A|?B(可传,(2,3)) (5)?,??A|??B(类似(1??4))(6)?|??A逆反律：如果A?B|??B??A。

(1)A?B,?B,A|?B(2)A?B,?B,A|??B

(3)A?B,?B|??A(3)A?B|??B??A(??)交换律：A?B|?|B?A,A?B|?|B?A。

22

分配律：

A?(B?C)|?|(A?B)?(A?C)。

A?(B?C)|?|(A?B)?(A?C)练习：

排中律：?|?|A??A。 De Morgen律：

不矛盾律：

?(A?B)|?|?A??B?(A?B)|?|?A??B。

|?|?(A??A) 23

?

第三章 经典一阶逻辑

命题语言的表达能力：最小对象为命题（具有明确真假判断的陈述） 如下推理在命题语言中无法表达： 例1.苏格拉底论断。

前提：所有的人要死。（范围界定,全称量化） 苏格拉底是人。

结论：苏格拉底要死。

例2. 前提：有人在教室看书则灯亮。（范围界定，存在量化）

张三在教室看书。

结论：教室灯亮。

例3. 前提：相互认识的人是朋友。（关系）

张三和李四相互认识。 结论：张三和李四是朋友。 论域：讨论对象构成的集合。 量词：论域中对象的范围界定。

“所有的对象……”、“有的对象……”。 谓词：论域中对象之间的关系。

一元关系：可以在论域中区别出一个子集。

如：x是男同学。（可判断）

x具有某性质特征。（可判断）

二元关系：论域中对象之间的相互关系。 如：张三和李四相互认识。（可判断） 一般描述：

设D为一个论域，R?Dn是D上的一个n元关系。 R(x1,......,xn)表示x1,......,xn具有R-关系。

等价表示：(x1,......,xn)?R（可判断，是命题形式） 例. 一元关系（代表性质）。P(x)：x具有性质P。

24