被使用的规则带有的假设条件已经在
?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