数理逻辑（讲义）

《数理逻辑》教案

许道云

(2011.8)

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

(陆钟万著)

出版社：科学出版社

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

绪言（课程介绍）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1

例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.

2

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

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

语法 形式语言

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

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

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

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

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

3

第一章 预备知识

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

内涵：元素具有的性质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如下：

4

(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

5

第二章 经典命题逻辑

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

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

（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关于命题公

6

式?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每一个赋值下取值均为假。

8

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，则公式为可满足式。

9

（逻辑）语义等价：若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公式。

10

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

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

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

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

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

11

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

所有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'。

12

语义证明方法

一、王浩算法

原理：将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,?

13

证明形式：

以一个起始串为树根，按规则消去联结词。当串为公理形式时，不再往下做。如果证明树的每个叶结点均为公理形式，则原公式为重言式（或矛盾式）。 证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(公理)

14

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]取假。

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

15

T.??

F.??

F.?

T.?

F.???

T.???

F.?

T.?

T.?

F.?

T.???

F.???

T.?

F.?

F.?

T.?

16

F.???

T.???

T.?

F.?T.?

F.?

T.???

F.???

T.?

F.?

T.? F.?

T.?

F.?

F.?

T.?

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

17

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

F.C

18

形式推理与证明

推理规则系统: (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) 使用其它规则.

19

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

?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

数据结构：

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

25

一阶语言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 (归纳基)

26

(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前提：有算法就能用程序实现。

27

存在求解问题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)

28

例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

29

语义解释系统(赋值)

在命题逻辑语言中，语义赋值是一个映射：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

30

。 赋值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)

31

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'-可满足。

32

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）补充规则：

33

(??)： 若?|?(?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)

34

本文来源：https://www.bwwdw.com/article/60p7.html