数理逻辑（讲义）

更新时间：2024-04-18 20:35:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

《数理逻辑》教案

许道云

(2011.8)

教材：《面向计算机科学的数理逻辑》(第二版)

(陆钟万著)

出版社：科学出版社

版本：2006年6月第8次印刷

绪言（课程介绍）

什么是逻辑？命题（判断）对象、以及对象间的（推理）关系。数理逻辑：用数学的方法研究逻辑。

数理逻辑研究分支：模型论、集合论、递归论、证明论。数理逻辑研究什么？

逻辑推理：当前提为真时，保证结论为真。

逻辑研究这样的可推理关系。即，前提和结论之间的推理关系是否正确。演绎推理---演绎逻辑。

它不同于归纳逻辑。归纳逻辑是从前提出发，使用归纳推理，得到的结论与自身协调，或与前提协调。

数理逻辑属于演绎逻辑范围。只研究推理及可推理关系，不关心前提与结论中各个命题的真假。

例1. 前提：所有大于2不被自身整除的自然数为素数。 7不被自身整除。结论：7不是素数。例2. 前提：所有中学生打网球。王君不打网球。结论：王君不是中学生。

命题有内容和形式：内容决定命题的真或假。决定前提和结论之间的可推导关系，是命题逻辑形式。如：

前提：集合S中的所有元素具有R性质。 a不具有R性质。

结论：a不是S中元素。命题的陈述需要语言。

元语言：描述对象的所用的最基本语言。如：自然语言（汉语）。

对象语言：描述“对象所用元语言”的语言。

如：形式语言（符号语言）。

自然语言中语言上的相似并不保证逻辑形式上的相同。

例1：X认识Y。（前提） Y是足球队长。（前提） X认识足球队长。（结论）例2：X认识A班某学生。（前提） A班某学生是足球队长。（前提） X认识足球队长。（结论）近代数理逻辑思想：

Leibniz力图建立一种精确的、普适的科学语言作为形式语言。直到1879年，Frege才建立了这样的语言。近代数理逻辑介绍的就是这种形式语言。所以，数理逻辑史从1879年算起。

在数理逻辑中要构造一种符号语言来代替自然语言，这种人工构造的符号语言称为形式语言。

对象的描述和对象间的推理关系全部用形式语言表示。数理逻辑研究的主要内容：

（1）引入一个形式语言，以表示非结构化对象。并且要求表示公式的语言是递归生成的。（2）引入一套形式化推理规则，基于这些规则进行符号化演算。引入形式证明的一般形式。

(?|?A)

（3）引入一套解释系统---语义(映射)函数，赋予形式符号在给定环境下的具体含义。（4）基于语义模型，引入逻辑推理概念。(?|?A) （5）研究形式推理与逻辑推理之间的关系。

（可靠性和完备性）。

形式推理系统的可靠性：?|?A??|?A。形式推理系统的完备性：?|?A??|?A。

一般，逻辑中的语言和推理是某类智能推理的抽象，语言解决表示问题(即，数据结构问题)。从某种意义上讲，应该是先有具体实例，想找一种一般描述，这就产生了形式语言和形式推理。实例数据对形式符号给出一种解释(或赋值)。两者之间的映射关系形成一个解释系统。

实例数据与形式符号有解释(或赋值)和被解释(或赋值)之分。如：a:=0. 可以理解为：将数字0赋给符号a. 也可理解为：a被解释为0.

其中，a是抽象的，而0是具体的。为什么会有各种逻辑？

由逻辑研究内容，我们可以观察下表：

语法形式语言

(表达方式和能力) 形式推理：?|?A 可靠性：?|?A??|?A 完备性：?|?A??|?A

在表中，形式语言、解释系统、推理规则是可变的。 (1) 当形式语言的表达能力不够用时，新的语言就会出现。

(2) 不同规则系统的引入，直接关系到形式推理的能力说、有效性、以及单调性等。 (3) 不同的解释系统，给出不同的语义模型。思考题：

1、逻辑研究的主要内容。 2、为什么会有各种逻辑？

语义解释系统语义(映谢)函数逻辑推理：?|?A

第一章预备知识

集合：某些对象全体。集合表述方式：

内涵：元素具有的性质P。外延：所含元素的全体。

自然数集合N上的二元关系 <（作为集合）：（内涵）m

二元关系的性质：自反，对称，等价，……。集合等势：S~T?|S|?|T| 可数无限集：与自然数集等势的集合。可数集：有限集或可数无限集。|S|?|N| 定理：（1）可数集的子集仍然可数。

（2）有限个可数集的并仍为可数集。（3）可数个可数集的并仍为可数集。自然数集合N的归纳定义：（1） 0?N.

（2）如果n?N，则（后继）n'?N 。

（3）N只含通过（1）（2）有限次使用得到的数。等价定义：自然数集合N是满足如下条件的最小集合S （1）0?S 。

（2）如果n?S，则（后继）n'?S 。设R是一个性质，R(x)表示x具有性质R。定理1（数学归纳法）如果（1）R(0)。

（2）对于任意的n?N，如果R(n) 则 R(n')。则对于任意的n?N 有R(n)。

设h,g为两个N上的己知函数。递归定义N上一个函数f如下：

(1) f(0)?g(0). (2) f(n')?h(f(n)).

定理2（递归原理）对于给定的函数g和h，能唯一定义N上一个函数f满足上述递归条件。一般集合S的归纳定义：

(1) 指定一个集合M。（基元，生成元）

(2) 指定k个函数g1,g2,.....,gk为生成函数.分别为n1,n2,.....,nk元函数。归纳生成集合S：S:??M,{g1,g2,.....,gk}?。归纳定义. 集合S是满足如下条件的最小集合T：（1）M?T 。

（2）对于每个1?i?k，

如果x1,.....xn?T，则gi(x1,.....xn)?T。

ii设h,h1,......,hk为k+1个己知基函数：

h:M?Shi:Sni?S(i?1,2,...,k).

递归原理定义S上的一个函数f:

f(x):?h(x)(x?M)f(gi(x1,.....xn)):?hi(f(x1),.....,f(xn))(i?1,2,...,k)

ii定理3（递归原理）对于给定的函数h,h1,......,hk，能唯一定义S上一个函数f满足上述递归条件。

归纳集生成系统：S:??M,{g1,g2,.....,gk}?。递归函数生成系统：S:??S,{h,h1,h2,.....,hk}?。

S:??M,{g1,g2,.....,gk};{h,h1,h2,.....,hk}?

例：自然数（算术）系统

N:??{0},{s};{c0,?,*}?.x'?s(x)?x?1,c0(x)?0

第二章经典命题逻辑

命题定义：具有明确真假值的（对象）陈述。

简单命题：最小命题。（最简单，不可分解，原子，……）复杂命题：借助联结词组合后命题小命题。组合方式：

（1）一元：否定、不、非。（2）二元：

或；且；如果…,则…；除非；当…,才有…; 仅当…,才有…。等等。

描述缺陷：自然语言。（非通用标准语言）形式语言：命题语言LP。（通用）字母表：0，1，p,q,r,……。运算符：?,?,?,?,?。

真---1；假---0。

命题公式的生成：（归纳定义命题公式集Form(LP)）

PP（1）（归纳基）：Atom(L)?{p,q,r,......}?Form(L)。

（原子命题公式集）

P（2）（归纳定义）：如果A,B?Form(L)，则

?A,(A*B)?Form(LP)。其中，*?{?,?,?,?}。（3）Form(LP)只含通过有限次使用（1）（2）得到的符号串。结构归纳法：将Form(LP)类比自然数集N。设P为一个性质，P(x)对表示x具有性质P。

类似于数学归纳法，引入关于Form(LP)上的某个性质（结论）P是否成立（真）的结构归纳法。

（1）（归纳基） P关于原子命题公式成立。（归纳基）

（2）（归纳步）对A,B?Form(LP)，假定P关于命题公式A、B成立。验证：P关于命题公

式?A,(A*B)成立。其中，*?{?,?,?,?}。语义解释：命题公式的解释(赋值)。

对原子命题公式的解释：（形式上是一个映射）

v:Atom(LP)?{0,1}。称为一个赋值。

理解为：p在v下被解释为pv?{0,1}。pv?v(p) 0表示“假”。1表示“真”。

基于这样的解释系统，命题逻辑只研究具有明确真、假区分的对象。这就是命题限制到具有明确真、假意义的陈述语句的根本原因。对联结词运算符号的解释：

p 0 1 p 0 0 1 1 q 0 1 0 1 ?p 1 0

p?q 0 1 1 1 p?q 0 0 0 1 p?q 1 1 0 1 p?q 1 0 0 1

对命题公式的解释：对于一个公式A，在一个赋值v下总可以计算出它的真值：Av?{0,1}。（归纳计算）

(1)pv?{0,1}.?1ifpv?0(2)(?p)??. v0ifp?1??0ifAv?Bv?0v(3)(A?B)??.o.w.?1v 7

?1ifAv?Bv?1(4)(A?B)??.o.w.?0v?0ifAv?1andBv?0(5)(A?B)??.

o.w.?1v?1ifAv?Bv(6)(A?B)??.o.w.?0v命题公式A的真值表：在所有可能的赋值v下，将取值结果列入表中。如： (┐p∧q)→┐r的真值表

可满足性：公式A是可满足，如果至少存在一个赋值v使A取真。

如果公式A含有n个变元，验证公式A的可满足性需要对2个赋值逐一验证。直观上需要指数验证时间。

可满足性判定问题（SAT问题）：实例：一个命题公式A。

询问：是否存在一个赋值v使A取真（满足A）？验证算法存在！

重言式：A每一个赋值下取值均为真。矛盾式：A每一个赋值下取值均为假。

n SAT问题的在计算机科学中的地位：

SAT问题是计算机科学中的核心问题。曾被著名美籍华人数理逻辑学家王浩称为“当代数理逻辑和理论计算机的第一问题”。

计算机科学家们一直都在寻求各种快速策略和方法改进求解SAT问题。现已证明：工程技术、军事、人工智能、并发控制、交通运输等领域中的诸多重要问题（如程控电话的自动交换，大型数据库的维护，大规模集成电路的自动布线，软件自动开发，机器人动作规划等）都涉及到SAT问题。

SAT问题是NP完全问题。从理论上说，SAT问题不能在多项式时间内解决，直观上它超出了现代计算机的能力。所以，SAT问题是计算机科学技术发展中的“瓶颈”问题。

从理论上讲，可满足性判定问题是NP完全的，然而在实际应用中，并非每一个CNF公式的可满足性问题的判定都需要指数时间。根据统计分析，对于3-CNF公式而言，出现在公式中的子句数与变元数之比是一个重要的参数，当公式的这个参数在4.25附近时，公式的可满足性的判定的确难。但是，当公式的这个参数远离4.25时，公式的可满足性的判定有可能在多项式时间内就可以完成。

约束满足性问题（CSP问题）：q?CSPW n 个变元：u1,......,un。

m 个q元函数：?i(ui1,......,uiq):Wq?{0,1}。

可满足性：(?v?(a1,......,an)?Wn)(?i)[?iv(ai1,......,aiq)?1]。（CSP问题）：q?CSPW

实例：一个约束??{?1,......,?m}。

询问：是否存在一个赋值(a1,......,an)?Wn使得(?i)[?iv(ai,......,ai)?1]？

1q（回到命题公式讨论）

重言式一定是可满足式，但反之不真。因而，若公式A是可满足式，且它至少存在一个成假赋值，则称A为非重言式的可满足式。

(1) 若真值表最后一列全为1，则公式为重言式。 (2) 若真值表最后一列全为0，则公式为矛盾式。

(3) 若真值表最后一列中至少有一个1，则公式为可满足式。

（逻辑）语义等价：若A,B构成的等价式A?B为重言式，则称A与B是等值的，或语义等价。记作A?B。

用真值表判断公式的等值（在所有赋值下验证）例： ?(p?q)?(?p??q)

（逻辑）语义蕴含：若公式A?B为重言式，则称A蕴含B。记作A?B。表示：若A为真命题，则B为真命题。

逻辑的主要任务是研究逻辑推理。命题公式的规范表示：

合取范式： CNF公式。析取范式： DNF公式。

文字：变元或变元的否定统称为文字。x,?x 子句：文字的析取称为子句。C?L1?L2?......?Ln。子句C中所含文字的个数n 称为子句长度。

CNF公式：子句的合取称为CNF公式。F?C1?C2?......?Cm。公式F的(大小)规模定义为。|F|?|C1|?|C2?......?|Cm|。 k-CNF公式: 公式F中每个子句的长度?k。

Horn子句：出现在C?L1?L2?......?Ln中的正文字个数至多为1。

DNF公式：

(1) 项：文字的合取称为项。C?L1?L2?......?Ln。 (2) DNF公式：项的析取称为DNF公式。

定理.设F为一个命题公式，则存在公式F1和F2，使得F?F1， F?F2. 其中，F1为CNF公式，F2为DNF公式。

范式的唯一性——主范式 p,q形成的极小项与极大项

p,q,r形成的极小项与极大项

联结词的完备集: 能表示任意布尔函数的联结词集合。

设S是一个联结词集合，如果任何n(n≥1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集。定理. S={┐,∧,∨}是联结词完备集。例：{?,?,?},

{?,?},{?,?}。

所有2元真值函数

逻辑推理：?|?A

设A?Form(LP)，??Form(LP)。若对于任一赋值v, 如果?v?1，则Av?1，称由?逻辑可推A。记为： ?|?A。

若A|?B且B|?A，称A与B逻辑等价。记为：A|?|B。注意：若?不可满足，则对任意的A，均有?|?A。证明方法：证?|?A。

v证明：假定任意赋值v, 使得??1，验证A?1。

v反证法：假定?|?A，由存在一个赋值v, 使得?v?1，但A?0。然后导出矛盾。

定理1.(1) A1,......,Anv|?A?(A1?A2?......?An)|?A

(2) A1,......,An|?A?|?(A1?(A2?(......(An?A)......)

定理2. (等值替换定理)

设F为一个命题公式，A是出现在F中的一个子公式，A|?|B。F'是将B替换F中的部份A得到的公式，则 F|?|F'。

语义证明方法

一、王浩算法

原理：将A1,......,An|?B的证明转换为证明(A1?......?An)?B为重言式。子句格式：

(a?b?c??d??e)(a?b?c)??(d?e)(d?e)?(a?b?c)

串格式：d,e?sa,b,c

重言子句的串格式：d,a?sa,b,c，对应a?b?c??d??a 公理格式：A,??A,?。前项规则：

??: 若?,?A??，则??A,? ??: 若?,A?B??，则?,A,B?? ??: 若?,A?B??，则?,A??或?,B?? ??: 若?,A?B??，则??A,?或?,B?? ??: 若?,A?B??，则?,A,B??或??A,B,?

后项规则：

??: 若???,?A，则A,??? ??: 若???,A?B，则???,A或???,B ??: 若???,A?B，则???,A,B ??: 若???,A?B，则?,A?B,? ??: 若???,A?B，则?,A?B,? 或B,??A,?

证明形式：

以一个起始串为树根，按规则消去联结词。当串为公理形式时，不再往下做。如果证明树的每个叶结点均为公理形式，则原公式为重言式（或矛盾式）。证F为重言式：起始串为 ?F 要证： A1,......,An|?B。

即证： F:?(A1?......?An)?B为重言式。证明起始串取为： A1,......,An?B。例：证明A?(B?C),A?B|?A?C （1）A?(B?C),A?B?A?C （2）（1-1）A?(B?C),A?B,A?C （3）（2-1）A?(B?C),A?C,A (公理) （4）（2-2）A?(B?C),A,B?C（待分解）（5）（4-1）A,B?C,A (公理)

（6）（4-2）A,B,(B?C)?C(待分解) （7）（6-1）A,B?C,B(公理) （8）（6-2）A,B,C?C(公理)

A?(B?C),A?B?A?C

A?(B?C),A?B,A?CA?(B?C),A?C,A

A?(B?C),A,B?C

A,B?A,C

A,B,(B?C)?C

A,B?C,B

A,B,C?C

二、表方法

原理：将A1?......?An)?B]为重言式。 1,......,An|?B的证明转换为证明[(A标记公式：F.?（指：公式?取假） T.?（指：公式?取真）根结点：F.[(A1?......?An)?B]

指：假定公式[(A1?......?An)?B]取假。

分解规则：（逐步取消联结词。如果己出现矛盾路径，则不再分解）

T.??

F.??

F.?

T.?

F.???

T.???

F.?

T.?

F.?

T.???

F.???

T.?

F.?

T.?

F.???

T.???

T.?

F.?T.?

F.?

T.???

F.???

T.?

F.?

T.? F.?

T.?

F.?

T.?

矛盾路径：从根到叶结点的路径上出现矛盾对T.A, F.A。终结树：每一叶结点路径上或出现矛盾，或不可再分解。矛盾树：每条路径均为矛盾路径。

F.[((A?(B?C))?(A?B))?(A?C)] 待递归分解 T.[(A?(B?C))?(A?B)] F.(A?C) T.A

F.C

形式推理与证明

推理规则系统: (Ref)： A|?A.

(单调)：若 ?|?A，???'，则?'|?A。

(??)：若 ?,?A|?B，?,?A|??B，则?|?A。 (??)：若 ?|?A?B,?|?A，，则?|?B。 (??)：若 ?,A|?B，则?|?A?B。 (??)：若 ?|?A?B，则?|?A,?|?B。 (??)：若 ?|?A,?|?B，则?|?A?B。 (??)：若 ?,A|?C,?,B|?C,则?,A?B|?C。 (??)：若 ?|?A，则?|?A?B,?|?B?A。 (??)：若 ?|?A?B,?|?A,则?|?B。若 ?|?A?B,?|?B,则?|?A。 (??)：若 ?,A|?B,?,B|?A，则?|?A?B。

补：(12) (?) ：若A??，则?|?A。(可由Ref和单调性证明) 形式化推理：?|?A

设A?Form(LP)，??Form(LP)。称A可由?形式化可推理。如果存在一个序列：

?1|?A1,?2|?A2,........,?n|?An满足如下条件： (1) ?1|?A1 (使用 (?) 或(Ref)引入)； (2) ???n,A?An；

(3) 对每一个1?k?n，?k|?Ak由下列情形之一引入： (3.1) 使用 (?)，

(3.2) 使用(Ref)， (3.3) 使用其它规则.

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

?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。

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

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

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

一些常用定律：幂等律：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。

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。

分配律：

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。

数据结构：

?D,{R1,......,Rn},{O1,......,Om}?D:数据集R1,......,Rn:数据集上的关系.

O1,......,Om:数据集上的操作(运算).极限描述：limn??xn?a

对于任意的??0,存在自然数N?0,当n?N时, |xn-a|

二元：大于、小于；函数：求绝对值。函数极限描述：limx?af(x)?A

对于任意的??0,存在??0,对任何x,当|x-a|

一阶语言L的构造

符号系统：

个体：常元：a,b,c,…;

自由变元：u,v,w,…; 约束变元：x,y,z,…; 函数符号：f, g, h,…; 关系符号：P, Q，R,…; 联结词：?,?,?,?,?

量词：?,?。辅助符号： (，)，[ ，]，{ ，}（用于区分）例：自然数系统：?N,0,s,{?,*},??

生成元：0

生成函数：后继函数s(x)=x+1, 生成自然数集。

(Peano公理)

运算：+，* 为两个二元运算。关系：= 为一个二元关系。

项集合Term(L)的归纳定义：（其中的元素称为项） (1) 个体常元a?Term(L)

个体自由变元u?Term(L)

(2) 若t1,......,tn?Term(L)，f是一个n元函数，则

f(t1,......,tn)?Term(L)；

(3) 对任何t?Term(L)，可以经由(1)、(2)有限步递归生成。

项集合Term(L)中的项元素被解释成论域中的元素。是基本数据的抽象。函数对应数据操作运算。

等价定义(项集合Term(L))：满足如下条件的最小集合S称为项集合。记为Term(L) (1) a,u?S (归纳基)

(2) 对任何t1,......,tn?S，及任意的n元函数f，有f(t1,......,tn)?S。(归纳步)

原子谓词公式集Atom(L)：

对任何t1,....t.,Term，L(及)任意的n元关系R，R(t1,......,tn)?Atom(L)。n.?（R(t1,......,tn)可判断）

在命题语言中，原子命题是最小单位，用一个命题符号表示。一阶语言中，原子命题不是最小单位，它刻画基础对象之间的某种关系（或性质）。对象之间有这种关系（或性质）就取真，否则就假。

谓词公式集Form(L)的归纳定义：

(1) 原子公式集Atom(L)?Form(L)。

(2) 若A,B?Form(L)，则(?A),(A*B)?Form(L) 。其中*?{?,?,?,?}

(2) 若A(u)?Form(L)，x不在A(u)中出现，则

(?x)A(x),(?x)A(x)?Form(L)。

在一阶语言中，变元只对个体，函数符号和谓词符号视为常元符号。量词只作用在个体变元上。

谓词语言的表达能力仍然有限！如下推理一阶语言不能表达：（1）

前提：自然数集的任何子集都有最小元。

A是自然数集的一个子集。结论：A有最小元。

子集的描述可用一元谓词。“任何子集”的表达需要将谓词作为变元，用全称量词才能表达！

需要引入关系变元（二阶语言）：（2）

(?A)?(x)A[x?()?y(A)y(?( ?x)y前提：有算法就能用程序实现。

存在求解问题A的算法。结论：存在求解问题A的程序。

算法和程序可用函数表达。“存在算法”的表达需要将函数作为变元，用存在量词才能表达！例1. 公式(?x)[F(x)?(?y)[(?z)G(y,z)?H(u,x,y)]的归纳生成过程。（1）F(u1),G(u2,u3),H(u,u1,u2)

（2）(?z)G(u2,z)

（3）(?z)G(u2,z)?H(u,u1,u2)] （4）(?y)[(?z)G(y,z)?H(u,u1,y)] （5）F(u1)?(?y)[(?z)G(y,z)?H(u,u1,y)] （6）(?x)[F(x)?(?y)[(?z)G(y,z)?H(u,x,y)] 例2.自然语言陈述表达公式表达（1）苏格拉底论断。

前提：所有的人要死。（(?x)[M(x)?D(x)]）苏格拉底是人。（a：苏格拉底，M(a)）

结论：苏格拉底要死。D(a)

（2）前提：有人在教室看书则灯亮。（(?x)[R(x)?Q]）

张三在教室看书。（a：张三，R(a)）结论：教室灯亮。（Q）

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

(?x)(?x)[K(x,y)?F(x,y)] 张三和李四相互认识。

（a：张三，b：李四。K(a,b)）

结论：张三和李四是朋友。F(a,b)

例4. 每一个自然数都存在唯一后继。

存在性：N(u)?(?y)(N(y)?(y?s(u)))]

唯一性：(?z)(?w){([N(z)?(z?s(u))]?[N(w)?(w?s(u))])?(z?w)} 最后公式：

(?x){N(x)?[(?y)(N(y)?(y?s(x)))]? (?z)(?w){([N(z)?(z?s(x))]?[N(w)?(w?s(x))])?(z?w)}一元谓词N(x)作为特称（限定）谓词可以省去。

(?x){[(?y)(y?s(x))]?(?z)(?w){([(z?s(x))?(w?s(x))]?(z?w)}}

(?x){[(?y)(N(y)?(y?s(x)))]?(?z)(?w){([N(z)?(z?s(x))]

?[N(w)?(w?s(x))])?(z?w)}例5.三人行，必有我师。

含义：任意三个人中，有一位是我的老师。

(?x)(?y)(?z)[T(x,a)?T(y,a)?T(z,a)]

论域：人构成的集合。特称（限定）谓词M(x)。

习题：

P92：3.2.2, 3.2.4

语义解释系统(赋值)

在命题逻辑语言中，语义赋值是一个映射：v:Atom(LP)?{0,1}

在一阶语言中，解释系统v?(D,C,F,R)是一个复杂映射。（仍称为赋值），要求对公式中的每一个符号进行分类解释。

个体符号、函数符号、谓词（关系）符号 D作为实际个体数据对象集，称为论域。符号含义：

D：论域---- 个体对象的取值范围。

C：对常元符号的解释：C:Const(L)?{av|av?D}。 F：对函数符号的解释：F:Func(L)?{fv:Dn?D|n?1}R：对关系符号的解释：R:Rel(L)?{Pv?Dn|n?1}。赋值v?(D,C,F,R) 下项取值的归纳定义： (1) av,uv?D。

(2) [f(tvvvv1,......,tn)]?f(t1,......,tn)。其中，fv?F(f):Dn?D

赋值v?(D,C,F,R)下原子公式的取值：

[P(tvv(tvvn1,......,tn)]?P1,......,tn)?D，其中(Pv?Dn)，[P(tv?1(tvvv1,......,tn)?P1,......,tn)]???0(tvvv

1,......,tn)?P[tv???1tv1?tvvv2,t1,t2?D1?t2)]?0tv1?tv（二元等值谓词）2

。赋值v?(D,C,F,R)下公式取值的归纳定义：（1）原子公式赋值定义（见上）

（2）?P,P?Q,P?Q,P?Q,P?Q的取值与命题公式中的定义一致。（略）（3）含量词的公式取值

v[u/a]?1若存在a?D，[A(u)]?1v[(?x)A(x)]??

0否则??1若对任意的a?D，[A(uv[)u]/a]?1[(?x)A(x)?] ?否则?0v其中，x不在 A(u)中出现。这里，wv[u/a]?a??v?ww?u。 w?u可满足、有效：设A?Form(L)，若存在一个赋值v, 使得A若对任一个赋值v, 使得A

注意：含有n个变元的命题公式的所有赋值只有2n。而任一个带有谓词和函数的谓词公式的所有赋值不止有限个。例1.

考虑公式(?x)P(x)的赋值。

v?1。称A可满足。

v?1。称A有效。

（1）D?{1,2,3,4,5}

1,3,5} P?{ v?(D,C,R,F)是一个赋值。公式在此赋值下取假。（2）D?{1,2,3,4,5}

v' P?{1,2,3,4,5}

vv'?(D,C,R,F)是一个赋值。公式在此赋值下取真。

例2．考虑公式(?x)(?y)[P(x,y)?(y?f(x))]的赋值。（1）v?(D,C,R,F)

D?N?{0,1,2,3,.....}

Pv(x,y):x?y,fv(x)?x?5，

v?(D,C,R,F)是一个赋值。公式在此赋值下取真。（2）v?(D,C,R,F)

D?N?{0,1,2,3,.....}

vv P(x,y):x?y,f(x)?x，

v?(D,C,R,F)是一个赋值。公式在此赋值下取假。

例3．构造一个公式，它在不超过3个个体的论域中是有效的，但更大的论域中不是有效的。如：(?x)(?y)[(F(x,y)??F(y,x)?(F(x,x)?F(y,y))]

相对满足性、相对有效性：论域D固定下的相对满足性、相对有效性。简称D-可满足、D-有效。

若存在以D为论域的赋值v, 使得A?1 。称A为D-可满足。若对任意以D为论域赋值v, 使得A?1 。称A为D-有效。定理1. 设 A?Form(L),D?D'，则

A为D-可满足 A为D'-可满足。 A为D'-有效 A为D-有效。证明：固定c?D. 作映射*:D'?D。

vvb?D?bb*:??

cb?D'?D? 以D为论域且满足A的任何赋值v 均可扩充为一个以D' 为论域的赋值v*，使其满足A。■ 定理2. 设A?Form(L),|D|?|D'|，则

A为D-可满足? A为D'-可满足。证明：作双射*:D'?D。定理3. 设A?Form(L),|D|?|D'|，则

A为D-可满足 A为D'-可满足。

A为D'-有效 A为D-有效。背景：(1) 实际应用中只用到D-可满足。 (2) 解释系统之间的转换。

逻辑推理

v逻辑推理: 设A?Form(L)，??Form(L)。若对于任一赋值v, 如果?v?1，则A?1，称由

?逻辑可推A。记为： ?|?A。

例1. (1) (?x)?A(x)|?|?(?x)A(x)。

v证明：（a）设有赋值v使得((?x)?A(x))?1，则存在a?D,使得(?A(u))v[u/a]?1，从而存在

a?D，(A(u))v[u/a]?0。

v如果(?(?x)A(x))?0，则((?x)A(x))?1。由定义，对于任意b?D，(A(u))v[u/b]?1。矛

v盾。

v（b）设有赋值v使得(?(?x)A(x)),则((?x)A(x))?0。由定义，存在a?D,使得?1vv[u/a](A(u))?0。从而，存在a?D,使得(?A(u))v[u/a]?1。即((?x)?A(x))v?1。■

(2) (?x)A(x)?(?x)B(x)|?(?x)[A(x)?B(x)]。证明：构造一个赋值v，使得

[(?x)A(x)?(?x)B(x)]v?1,[(?x)[A(x)?B(x)]]v?0。

取D?{a,b}(a?b)，Av?{a},Bv?{b}。则[(?x)A(x)]v?0。

v所以[(?x)A(x)?(?x)B(x)]?1。从而[(?x)[A(x)?B(x)]]?0。

vv[u/a][A(u)?B(u)]]?0。■ 因为

形式化推理： ?|?A 规则系统：

（1）命题逻辑中的规则。（2）补充规则：

(??)：若?|?(?x)A(x)，则?|?A(t)。 (??)：若?|?A(u)，则?|?(?x)A(x) 其中，u不在 ?中出现。

(??)：若?,A(u)|?B，则?,(?x)A(x)|?B 其中，u不在B和?中出现。 (??)：若?|?A(t)，则?|?(?x)A(x)

其中，A(x)是在A(t)是将部分t换为x。

(??)：若?|?A(t1),?|?t1?t2，则?|?A(t)

2其中，A(t2)是在A(t1)是将部分t1换为t2.

(??)： |?u?u。

上述规则可以推广到n元情形。

例. (1) (?x)?A(x)|?|?(?x)A(x)。

(2) (?x)?A(x)|?|?(?x)A(x)。(习题) 证明： (a) (?x)?A(x)|??(?x)A(x) (1) (?x)A(x)|?A(u)

（2） ?A(u)|??(?x)A(x)

(3) (?x)?A(x)|??A(u) （??， (2)）

(4) (?x)?A(x)|??(?x)A(x) （可传(2，3）)

(b) ?(?x)A(x)|?(?x)?A(x) (1) ?A(u)|?(?x)?A(x) (??)

(2) ?A(u),?(?x)?A(x)|?(?x)?A(x) (单调性， (1)) (3) ?A(u),?(?x)?A(x)|??(?x)?A(x) (?) (4) ?(?x)?A(x)|?A(u) (

??)，(2)(3)

(5) A(u)|?(?x)A(x) (??)，(4)

(6) ?(?x)?A(x)|?(?x)A(x) （可传，(4，5))

(7) ?(?x)A(x),?(?x)?A(x)|?(?x)A(x) (单调性， (6)) (8) ?(?x)A(x),?(?x)?A(x)|??(?x)A(x) (?) (9) ?(?x)A(x)|?(?x)?A(x) (

??)，(8，9)

前束范式：Q1x1......QnxnB。其中，Q1,......,Qn?{?,?}，B中不含量词，称为公式的母式。

定理. 每一个谓词公式A都可以划为与之语义等价的前束范式A’.即， A|?|A'，其中A’具有形式Q1x1......QnxnB。

进一步，可以要求母式具有合取范式（或析取范式）形式。证明方法：基于如下语义等价关系：（1）等价替换

如果A|?|A',B|?|B',C(u)|?|C'(u)，则（1.1）?A|?|?A' （1.2）A?B|?|A'?B' （1.3）A?B|?|A'?B' （1.4）A?B|?|A'?B' （1.5）A?B|?|A'?B' (1.6) (?x)C(x)|?|(?x)C'(x) (1.7) (?x)C(x)|?|(?x)C'(x)

(保证母式部分可以仿命题公式代范式方法) （2）（量词向前移动）

(2.1)?(?x)A(x)|?|(?x)?A(x)。（2.2）?(?x)A(x)|?|(?x)?A(x) （3）分配律仍然成立

(3.1) A?(B?C)|?|(A?B)?(A?C) (3.2) A?(B?C)|?|(A?B)?(A?C)

前束范式与公式分层：

量词合并：(?x1)(?x2)B(x1,x2)|?|(?x)B(x),x??x1,x2?

(?x1)(?x2)B(x1,x2)|?|(?x)B(x)

标准前束范式：Q1x1......QnxnB前束词Q1x1......Qnxn要求具有如下交替形式：

(?x1)(?x1)......(?xn)(n为奇数),(?x1)(?x1)......(?xn)(n为偶数) (?x1)(?x1)......(?xn)(n为奇数),(?x1)(?x1)......(?xn)(n为偶数)

公式分层：

（1）?0??0:不含量词的公式类。（2）?1:?{(?x)B:B??0}?1:?{(?x)B:B??0}。

（3）?n?1:?{(?x)B:B??n}?n?1:?{(?x)B:B??n}。习题：P108: 3.4.3(2,4,6) P119: 3.5.4.

第四章可靠性和完备性

可靠性：指形式推理的可靠性。

形式推理的结论在逻辑推理下是否仍然成立？

可靠性保证：应作系统中形式推理（纯符号演算）结论的正确性、安全性、…..。

一个智能专家系统中，形式推理完全由程序完成。如果没有可靠性保证，专家系统推理的结论不一定可靠、不一定正确。命题逻辑和谓词逻辑中的可靠性定理都成立。可靠性定理：设A?Form(L),??Form(L)，?|?A??|?A。

完备性：指形式推理的完备性。推理系统的能力。逻辑推理的结论能否在形式推理下完成？完备性体现：形式推理系统的推理能力。逻辑推理正确性推理结论，在形式系统中一定能做

到！

一个智能专家系统中，如果形式推理具有完备性，则表示它的能力己经足够。然而，通常的专家系统（如：医疗诊断系统）不具备完全性。所以，是用准确率刻划系统的功能。

命题逻辑和谓词逻辑中的完备性定理都成立。

完备性定理：设A?Form(L),??Form(L)，?|?A??|?A。从证明的难易程度上看：?|?A的证明比?|?A难。

如果完备性定理成立，则只需证明?|?A，就能保证?|?A成立。

命题逻辑和谓词逻辑中的可靠性定理和完备性定理都成立。 ◆可靠性定理的证明比较容易。直接可以证明。 ◆

完备性定理的证明比较难容易。采用间接证明。证明它的一个等价定理。并将命题逻辑和谓词逻辑中的完备性定理分别证明。借助于协调性概念，两个定理有如下等价形式：对于任意的A?Form(L),?,?'?Form(L) 原始定理1 等价定理2

可靠性定理完备性定理 ?|?A??|?A ?|?A??|?A ?'可满足??'协调 ?'协调??'可满足协调：设??Form(L)，称?不协调，如果存在B?Form(L)，使得?|?B,?|??B。?不是不

协调，称?协调。

可靠性定理

可满足性与有效性：

定理1. 设A?Form(L)，则A可满足??A不是有效。A有效??A 不可满足。证明：由定义。

定理2. 设A?Form(L)，则

A(u) 可满足? (?x)A(x)可满足。 A(u)有效 ? (?x)A(x)有效。

1?A(u)?A(u)证明：(1) (==>) 设A(u) 可满足。则存在赋值v满足A。令a?uv?D。

即，[(?x)A(u)]v?1。

vv[u/a]，

(<==) 设(?x)A(x) 可满足。则存在赋值v满足(?x)A(x)： [(?x)A(x)]v?1。由定义，存在

a?D，A(u)v[u/a]?1。

此表明：vua满足A(u).

（2）类似证明。或由定理1及(1)证明。 A(u)有效 ??A(u)为不可满足 ?(?x)A(x有效。■)定理3. (可靠性定理1) 设A?Form(L)，??Form(L)。

如果?|?A，则?|?A。如果|?A，则|?A。

证明：对规则的使用归纳法：如：(??)：

?为不可满足??(?x)A(x)为不可满足(?x)?A(x) 38

?,?A|?B,?,?A|??B?????????????

?|?A归纳假设：?,?A|?B,?,?A|??B，证明：?|?A。

v设赋值v使得??1。如果Av?0，则(?A)v?1。

于是，(???A)v?1，则归纳假设：?,?A|?B,?,?A|??B。我们有：(?B)v?1,Bv?1。矛盾。如：(??)：(u不在?,B中出现)

?,A(u)|?B ?????????????

?,(?x)A(x)|?B归纳假设：?,A(u)|?B，证明：?,(?x)A(x)|?B。

注意：由于u不在?,B中出现，?v[u/a]??v?1，Bv[u/a]?Bv。

vv?v[u/a]??v?1。设??[(?x)A(x)]?1，?a?D，A(u)v[u/a]?1，由于u不在?,B中出现，

由归纳假设：?,A(u)|?B。因此，Bv[u/a]?1。从而，Bv?Bv[u/a]?1。所以，?,(?x)A(x)|?B。■

定理4. (可靠性定理2) 设??Form(L)，A?Form(L)。

（1）如果?可满足，则?协调。（2）如果A可满足，则A协调。

证明：?可满足，证明：?协调。若?不协调，则存在B?Form(L)，使得?|?B,?|??B.由(可靠性定理1)，?|?B,?|??B，则?不可满足。否则，存在赋值v, 使得?v?1。从而，

Bv?1,(?B)v?1。矛盾。

从(可靠性定理2)证明 (可靠性定理1)[如果?|?A，则?|?A]。

设?|?A，若?|?A，则??{?A}可满足。由(可靠性定理2)，??{?A}协调。但是，??{?A}|?A,??{?A}|??A。表明：??{?A}不协调。矛盾。■

完备性定理

定理1. (完备性定理1) 设??Form(L)，A?Form(L)。

（1）如果?|?A，则?|?A。（2）如果|?A，则|?A。定理2. (完备性定理2) 设??Form(L)，A?Form(L)。

（1）如果?协调，则?可满足。（2）如果A协调，则A可满足。

由定理1证明定理2：

（1）假定A协调，证明A可满足。

假设A不可满足，则对于任意赋值v, Av?0.从而?A有效。即，|??A。由定理1，|??A。于是，A|?A(Ref),A|??A(单调性)。所以，A不协调。与假设矛盾。（2）假定?协调，证明?可满足。

假定?不可满足，则对于任意赋值v,有?v?0。从而必有一个公式A??，对于任意赋值v，如果(??{A})v?1，必有Av?0。此即，对于任意赋值v，(??{A})v?1，必有(?A)v?1。由定义，(??{A})|??A。

由定理1，(??{A})|??A。从而，(??{A}),A|?A，(??{A}),A|??A。即，?不协调。与假设矛盾。■ 由定理2证明定理1：（1）假定?|?A，证明?|?A。

由?|?A，则??{?A}不可满足。由定理2，??{?A}不协调。从而存在公式B，

??{?A}|?B,??{?A}|??B。

使用规则(??)，有?|?A。

（2）假定|?A，证明|?A。在（1）的证明中取???。

完备性定理的一般性证明是证明它的等价定理：协调一定可满足。在命题逻辑中，当?为有限命题公式集时，可以直接证明。

命题逻辑中完备性定理的有限形式：设A?Form(LP)，??Form(LP)为一个有限命题公式集合，则(1) 如果 |?A，则 |?A。(2) 如果?|?A，则?|?A。引理. 设A?Form(LP)含有变元p1,......,pn，v为一个赋值。令

?piAi????pipiv?1 i?1,....,n，则 piv?0 (1) 如果Av?1，则A1,......,An|?A。 (2) 如果Av?0，则A1,......,An|??A。证明：对命题公式A的结构进行归纳。（1）原子命题情形A?p。pv?1，p|?p。（2）A??A'。

v 如果A?1，则A'v?0，则归纳假设，A1,......,An|??A'。

如果Av?0，则A'v?1，则归纳假设，A1,......,An|?A'。

由于??A'|?A'，有A1,......,An|???A'，从而A1,......,An|??A。（3）A?B?C。

C含有命题变元pk',......,pn(k'?k)。假定B含有命题变元p1,......,pk，重复部份为：pk',......,pk。

如果Av?1，则Bv?Cv?1。由归纳假设：

A1,......,Ak|?B,A1,......,Ak,Ak?1,......,An|?BAk',......,An|?C,A1,......,Ak'?1,Ak',......,An|?C

从而，A1,......,An|?B?C。

(1) 设|?A，则A为重言式。从而，任意一个赋值v使得A?1。由引理，任一组A1,......,An，均有A1,......,An|?A。

由A1,......,An?1的任意性，重复上述过程 n-1次，|?A。注：若?|?A?B,?|??A?B，则?|?B。

?|?A?B,?|??B??A,?,?B|??A ?|??A?B,?|??B???A,?,?B|???A

?|?B(2) 设?|?A。由?有限，令??{B1,......,Bm}，B1,......,Bm|?A。从而，B1,......,Bm?1|?Bm?A，……, |?B1?(B2?......(Bm?A)...)。

由(1) |?B1?(B2?......(Bm?A)...)

B1|?B1?(B2?......(Bm?A)...)B1|?B1B1|?B2?(B3?......(Bm?A)...)

B1,B2|?B3?(B4?......(Bm?A)...) ……

B1,B2,......,Bm|?A。

即，?|?A。■

命题逻辑和谓词逻辑的完备性性定理

等价形式：协调公式集必可满足。

（如果?协调，则?可满足）

证明方法：将协调公式集?扩充为一个极大协调集?，利用极大协调集?的临界性质，构

造一个赋值满足?。

由于命题逻辑和谓词逻辑中赋值形式上不相同，所以我们分开讨论。极大协调集：设??Form(LP)，称?极大协调。如果

(1) ?协调。

(2) 任何命题公式A??，??{A}不协调。

极大协调集的（临界）性质：

设??Form(L)，?极大协调，公式A,B?Form(L)。有： (1) A????|?A。（边界性质） (2) A????A??。（边界性质） (3) A?B???A??且B??。 (4) A?B???A??或B??。 (5) A?B???如果A??，则B??。 (6) A?B???“A??当且仅当B??”。证明：（1.1）A????|?A( 显然)

（1.2）设?|?A，假定A??，则由极大协调性，??{A} 不协调。

从而有公式B，??{A}|?B,??{A}|??B。由归谬律：?|??A。于是，?|?A,?|??A。得到：?不协调。矛盾。■

（2.1）设A??，如果?A??，则?不协调。

（2.2）设?A??，则??{?A}不协调。从而有公式B，??{?A}|?B,??{?A}|??B，则规

**则(??)，?|?A。

其它性质由（1）（2）证明。

极大协调集性质的特征：

◆A????|?A：形式可推导与集合包含元素一致。

◆A????A??：每一个公式A，A,?A恰有一个在?中。特别，每一个命题变元p,

p,?p恰有一个在?中.这可以保证从?定义一个赋值：

p?? p???1v?(p):???0可见：v?(p)?1? ◆

p??。

性质（2）--（6）：处理联结词与（语义）赋值定义一致。从而可以保证：使用归纳法可以证明：对于命题A公式，有v?(A)?1?A??。

最终，v?可以满足?。从而可以满足?的子公式集?0

对于一个协调命题公式集?，设法将?扩充为一个极大协调集?，则?构造下个赋值

**v?*满足?。

命题逻辑中完备性定理

定理1.设A?Form(LP)，??Form(LP)。 (1) 如果?协调，则?可满足。 (2) 如果A协调，则A可满足。

证明：(1) 对?进行极大协调扩充为：极大协调?。 Form(LP):?{A0,A1,...........}（可数集） ?0??， ?n?1????n?n?{An}不协调?n?{An}协调*??n?{An}

?*??n?0?n。

注意：???0??1??2......。验证：?*极大协调。 (1.1) ?*协调

如果不协调，?*|?Ak,?*|??Ak，则存在?*的一个有限子集?'??*，使?'|?Ak,?'|??Ak，从而必有一个n, ?'??n。于是，?n|?Ak,?n|??Ak，此即，?n不协调。矛盾。 (1.2) ?*极大协调。

P反证法。如果?*不是极大协调。则必有公式B?Form(L)，使得：B??*，{B}??*协调。

注意：Form(LP):?{A0,A1,...........}。故B必为某个An。由?n??*及{B}??*协调，必有{B}??n协调。由构造过程：B??n?1??*。与B??*矛盾。

(2) ?*由构造一个赋值v满足?。 pv?1?p??*

由?*极大协调，则极大协调的性质（2）保证定义的合理性。

归纳证明：对每一个命题公式A,Av?1?A??*。从而，v满足?. 证明中充分使用了?*是极大协调集的性质。

（2.1）A=p为原子公式。由定义。

（2.2）A??B。?B??*?B??*。由归纳假：Bv?0，故Av?1?A??*。

Bv?1?B??*,Cv?1?C??*。B?C??*?B??*且C??*。（2.3）A?B?C。由归纳假：

v?1。所以，B?C??*?(B?C)

（2.4）A?B?C,B?C,B?C类以证明。最终由归纳法：Av?1?A??*。而???*，所以?v?1。■

谓词逻辑完备性定理

假设条件：语言L中不含等词?。对于含等词情形，引入等价关系，作论域的商集，化为不含等词情形。

语言扩充：将一阶语言L扩充成一个新的语言L0。

在L之外引入可数无穷多个新的自由变元： u0,u1,.......。其目的是为了量词引入时保证不出现重复符号。对相应的项集合，公式集作扩充。

Term(L)?Term(L0),Atom(L)?Atom(L0),Form(L)?Form(L0)

存在性质：设??Form(L0)，称?具有存在性质。如果(?x)A(x)??，存在新增自由变元

d?{u0,u1,.......}，使A(d)??。

存在性质的引入和条件要求，其主要目的是处理公式(?x)A(x)??时，从(?x)A(x)到A(d)保证封闭。

引理. (带存在性质的扩充) 设??Form(L)，?协调，则?可以扩充为一个具有存在性质的极大协调集?**?Form(L0)。 (???**)

证明：(1) Form(L)中的所有形如(?x)A(x) 的公式可数： (?x0)A0(x0),(?x1)A1(x1),..........,(?xn)An(xn),........... 扩充过程：第0步：?0??。

第1步：取公式(?x0)A(x0)，以及从{u0,u1,.......}中取在未用过的最前面的新变元ui0。作

i0。 ?1??0?{(?x0)A0(x0)?A0(u)}第n+1步：取公式(?xn)An(xn)，以及从{u,u,.......}中取在未用过的最前面的新变元uin。

作?n?1??n?{(?xn)An(xn)?An(un)}。(0?i0?i1?.......?in)

验证?n协调：对n归纳.

i01n=0 : 显然。

n=k+1 : 假设?k协调，?k?1协调。

若?k?1??k?{(?xk)Ak(xk)?Ak(uik)}不协调，则

(??)?k|?(?x)Ak(x)?k|??(?y)Ak(y)?k|??(?x)Ak(x)从而?k不协调。矛盾。

作?*??n?0?n，则?*??n?0?n协调。

***（2）第二次扩充： ???(为\存在性质\作准备)??(极大协调,有\存在性质\)。

验证：?**有“存在性质”。

设有(?x)A(x)??**，则?n的定义，存在n, 使得(?x)A(x)?A(d)??n。从而，

?**|?A(d)，由极大协调性：A(d)??**。■

定理2. 设A?Form(L)，??Form(L)。 (1) 如果?协调，则?可满足。 (2) 如果A协调，则A可满足。

证明：分两次扩充：?可以扩充为一个具有存在性质的极大协调集?**。构造一个赋值v如下：论域：D?{ct|t?Term(L0)} 项：在L中，av?ca,uv?cu,

v在L0中，dv?cd，tv?ct，[f(t1,......,tn)]v?fv(t1v,......,tn)?cf(t1,......,tn)

原子公式：f(t1,......,tn)?P?P(t1,......,tn)?? 验证v满足具有性质：Av?1?A??** 对A的结构进行归纳。

vvvv**（1）原子公式：显然。

（2）?A,A?B,A?B,A?B,A?B。（由极大协调性，仿命题逻辑中完备性定理的证明部分）

（3）(?x)A(x)：

(?) 设(?x)A(x)??**。证：[(?x)A(x)]v?1。

由存在性质。 (?x)A(x)??**?A(d)??**。由归纳假设：A(d)v?1。所以，[(?x)A(x)]v?1。

(?) 反之，设[(?x)A(x)]v?1，证：(?x)A(x)??**。

由[(?x)A(x)]v?1，存在a?ct，[A(u)]v[u/a]?1。

vv[u/t]tv?[A(u)]v[u/c]?1。注意：c?t。A(t)?[A(u)]vt由归纳假设，A(t)??**。

所以，?**|?A(t)。 ?**|?(?x)A(x)。由极大协调性：(?x)A(x)??**。■

P138：4.3.1 P141: 4.4.4, 4.4.5 P150: 4.5.1

第五章紧致性定理、L-S定理、Herbrand定理

可靠性与完备性定理保证了如下关系：

?|?A??|?A

这表明：形式可推导和（语义）逻辑推导是一致的。从而可以考虑纯粹语义下的一些性质和结论。

紧致性定理：刻画无穷公式集可满足性与其有限子集可满足性之间的关系。

Lowenheim-Skolem定理：公式集的可满足性测试，可以只在模型论域大小为可数集上测试。 Herbrand定理：人工知能中自动定理证明的重要理论基础。它告诉了模型构造方法。公式的不可满足性测试只在Herbrand赋值上进行。形如(?x)B(x)不可满足当且仅当存在A的母式的有限个例式B(t1),......,B(tk)不可满足。

定理1. (紧致性定理) 设??Form(L)，?可满足当且仅当?的任何有限子集可满足。证明： (?)显然。

(?) 设?不可满足，由完备性定理，?不协调。所以，存在A?Form(L)，使得

?|?A，?|??A。从而，存在?的一个有限子集?'，使得：?'|?A,?'|??A。此表明：?'不

协调。则可靠性定理：?不可满足。矛盾。■

应用：如果找到?的一个有限子集不可满足，则?不可满足。定理2.(L-S定理) 设??Form(L)，A?Form(L)。

(1)不含等词的?可满足当且仅当?在可数无穷论域D上，?是D?可满足。 (2)含等词的?可满足当且仅当?在可数无穷或有限论域D上，?是D?可满足。证明：由可靠性和完备性定理。■

推论(L-S定理) 设??Form(L)，A?Form(L)。

（1）不含等词的A有效当且仅当A在可数无穷论域D上，?是D?有效。（2）含等词的A有效当且仅当 ?在可数无穷或有限论域D上，?是D?有效。

本文来源：https://www.bwwdw.com/article/2vdp.html

相关文章：