数理逻辑4--一阶谓词逻辑形式系统.pdf

LI Wensheng, SCST, BUPT 李文生北京邮电大学计算机学院wenshli@010-62282929第4章 一阶谓词逻辑wenshli@2本章内容1 基本概念2 一阶谓词逻辑形式系统（ FSFC）3 一阶谓词逻辑形式演算4 一阶谓词逻辑形式系统语义5 前束范式6 一阶谓词逻辑形式系统元理论wenshli@31．基本概念„命题逻辑的局限性命题逻辑对现实世界的描述能力是有限的，因为在命题逻辑中，原子命题是最小的研究单元，对原子命题不再进行深入研究„例如：¾所有自然数都有大于它的素数 ( A ) 2100是自然数 ( B ) 2100有大于它的素数 ( C )¾推理正确但用命题逻辑无法描述¾在命题逻辑中无法进行推理¾N(x)：x是自然数； P(x,y)：x∈ƒwenshli@9变元和常元„常元：表示个体域中一个确定个体的符号如：5，lisi„变元：表示个体域上的任意个体，是不确定的„例如：在实数域上(1) x+y 表示任意两个实数的和，函词 ƒ(x,y)：x+y(2) x+y=0 表示一个二元谓词填式，可填入任意两个实数谓词 P(x,y)：x+y=0 (3) x+y=y+x二元谓词EQ(x,y)：x=y 二元函词 ƒ(x,y)：x+yEQ(ƒ(x,y), ƒ(y,x)) 二元谓词表示加法交换律(4) 对所有的x,y，有x+y=y+x。

nΣi=1(5) ƒ(i)wenshli@10„自由变元：真正的变元，可将个体域中的任意个体代入到自由变元中如上例(1) ∼(3)中的变元„约束变元：不是实际意义上的变元，而是表达某种思想的辅助符号如上例中(4),(5)中的变元„自由变元与约束变元的对比¾它们的使用场合、使用方式不同¾自由变元可代入，而约束变元不能代入如对于：x+y=0 和 x+y=y+x2/x,-3/y：2+(-3)=0, 2+(-3)=(-3)+2, ¾自由变元不能改名，但约束变元可改名x+y 不同于 x+znΣƒ(j)j=1nΣƒ(5)5=1变元和常元（续）wenshli@11量词„仅有谓词、函词、变元和常元的概念，还不能充分地描述现实中的命题例如：对任意x，如果P(x)真，则P(x+1)真„P(x)ÆP(x+1)与原意不同„P(x)恒真 ÆP(x+1)恒真这种表示形式不理想„全称性变元， “所有 ”变元；存在性变元， “存在 ”变元„Frege建议引入量词来表示谓词的成立范围全称量词： ∀，存在量词： ∃∀x表示所有x， ∃x表示存在x„∀x(P(x)ÆP(x+1))wenshli@12„全称量词： ∀xP(x)中的 ∀称为全称量词∀x中的x称为 ∀的指导变元；P(x)称为量词 ∀的辖域，其中的x为约束变元。

∀xP(x) 所有的x均满足P，P(x)真¬∀xP(x) 并非所有x都满足P∀x¬P(x) 所有x均不满足P„存在量词： ∃xP(x)中的 ∃称为存在量词∃x中的x称为 ∃的指导变元；P(x)称为量词 ∃的辖域，其中的x为约束变元∃xP(x) 存在x满足P，P(x)真¬∃xP(x) 不存在x满足P∃x¬P(x) 存在x不满足P，使P(x)假量词（续）wenshli@13命题符号化举例„所有的人都是要呼吸的M(x)：x是人，B(x)：x是要呼吸的∀x(M(x)ÆB(x))„所有实数的平方都是非负的R(x)：x是实数，NN(x)：x是非负的, sq(x)：x的平方∀x(R(x)ÆNN(sq(x)))„有些人早餐吃面包M(x)：x是人，E(x)：x早餐吃面包∃x(M(x)∧E(x))„对任何实数均有实数使得它们的和为零R(x)：x是实数，add(x,y)：x+y∀x(R(x)Æ∃y(R(y)∧add(x,y)=0))wenshli@14命题符号化举例（续）„ 人总是要死的，苏格拉底是人，所以苏格拉底是要死的M(x)：x是人，D(x)：x是要死的，a：苏格拉底∀x(M(x)ÆD(x)) ∧ M(a) Æ D(a)„ 练习：(1) 每个学生都要参加考试。

2) 任何人违反交通规则都要被罚款，因此，如果没有罚款，则没有人违反交通规则M(x)：x是交通规则， P(x)：x是罚款S(x,y)：x违反y， R(x,y)：x被处罚y(3) 生命诚可贵，爱情价更高，若为自由故，两者皆可抛谓词：M(1)： …是人，P(1)： …是宝贵的，V(1)： …是有价值的F(2)： …为 …而斗争，G(2)： …愿意舍弃 …函词：life(1)： …的生命，love(1)： …的爱情常元：i：我，free：自由wenshli@15„当需要对变元施加限制，使它以论域的一个子集为变域时，可以使用限定谓词¾当x为全称变元，x的变域确定为U的子集{x ∈U|P(x)}时，只要将P(x)作为蕴涵前件引入，表示为： ∀x(P(x)Æ…)¾当x为存在变元，x的变域确定为U的子集{x ∈U|P(x)}时，只要将P(x)作为合取项引入，表示为： ∃x(P(x)∧…)¾限定谓词的这种使用方法是不能改变的，否则会造成逻辑上的错误„例如：¾所有实数的平方非负 ∀x(R(x)ÆNN(sq(x))) √∀x(R(x)∧NN(sq(x))) ×¾有人为自由而斗争 ∃x(M(x)∧F(x,free)) √∃x(M(x)ÆF(x,free)) ×量词的使用方法wenshli@16„量词可以嵌套使用，量词连续使用时遵从右结合。

1) ∀x∀y(x+y=y+x)(2) ∀x∃y(x+y=0)(3) ∃x∃y(x2+y2=0)„量词的位置不能随意互换，如上面的(2)„量词等价公式(1) ∀xA(x)┝┥ ¬∃x¬A(x)(2) ∃xP(x)┝┥ ¬∀x¬P(x)(3) ¬∀xP(x)┝┥ ∃x¬P(x)(4) ¬∃xP(x)┝┥ ∀x¬P(x)(5) ∀x∀yP┝┥ ∀y∀xP(6) ∃x∃yP┝┥ ∃y∃xP量词的使用方法（续）wenshli@172．一阶谓词逻辑形式系统（FSFC）„一阶谓词逻辑形式系统的构成：语言部分 和 推理部分„语言部分：(符号表、项集、公式集)¾符号表z 个体变元：x,y, …； 个体常元：a1,a2,…z 函词： ƒ1(1), ƒ2(1), ƒ3(1),… （一元函词）……ƒ1(n), ƒ2(n), ƒ3(n),… （n元函词）z 谓词： P1(1), P2(1), P3(1),… （一元谓词）……P1(n), P2(n), P3(n),… （n元谓词）z 联结词： ¬,Æ；量词： ∀； 技术符号：(, )wenshli@18¾项：谓词所讨论的对象项的定义如下：(1) 变元和常元是项。

2) 对任意正整数n和函词 ƒ(n)，如果t1,t2,…,tn为项，则 ƒ(t1,t2,…,tn)也为项3) 除有限次使用(1)(2)得到的符号串是项外，没有别的东西是项z 项集是递归定义的，项是可判定的FSFC—语言部分（续1）wenshli@19¾公式：公式的定义如下：(1) 对任意正整数n，如果t1,t2,…,tn为项，那么P(t1,t2,…,tn)为公式，并称之为原子公式；(2) 如果A，B为公式，那么，( ¬A),(AÆB)均为公式3) 如果A(u)是公式，并且x不在A(u)中出现，则 ∀xA(x)为公式4) 除有限次使用(1) ∼(3)得到的符号串是公式外，无其他东西是公式z 公式集是递归定义的，公式是可判定的„对于项和公式的性质，可以用归纳法证明„约定： ∀x/∃x的优先级与 ¬的优先级相同，高于所有二元真值联结词的优先级FSFC—语言部分（续2）wenshli@20一阶语言性质„闭项：不含自由变元的项，如a， ƒ(a1,a2)„闭公式：不含自由变元的公式，如P(a,b), ∀x(P(a,x)ÆB(x)), ∃x∀yF(x,y)„辖域：公式A称为量词 ∀x/∃x的辖域，如果 ∀x/∃x与A相邻，且A的任何真截段w(即当A为符号串ww ′,且w ′不是空串)不是公式。

„辖域可简单地定义为 ∀x/∃x的作用范围如，∀x(AÆB) 中， ∀x的辖域是A ÆB∀xAÆB中， ∀x的辖域是A∃x∀y∃zF(x,y,z) ∃x的辖域？ ∀y的辖域？ ∃z的辖域？wenshli@21一阶语言性质（续1）„约束出现：在公式A中，变元x的某个出现叫做约束出现，如果x为 ∀/∃的指导变元，或出现在 ∀x/∃x的辖域内；否则x的出现为自由出现„A中约束出现的变元称为A的约束变元，A中自由出现的变元称为A的自由变元如∀xP(x)ƬQ(y)x为约束出现(约束变元)，y为自由出现(自由变元)∀xP(x)ƬQ(x)x既是约束变元，又是自由变元wenshli@22„可代入性：称项t是对A中自由变元x可代入的，如果A中x的任何自由出现都不在 ∀y/∃y的辖域内，这里y是t中的任一自由变元„可代入性保证了代入过程中变元的约束关系不发生改变，即原来约束的代入后仍旧是约束的；原来自由的代入后仍旧是自由的„如：对于 ∀xP(x,y)若项t中含有自由变元x，则t对y不是可代入的若项t中不含有自由变元x，比如项 ƒ(y),g(u,v)等对y都是可代入的一阶语言性质 （续2）wenshli@23„如，对于 ∀yP(x,z)5/x,6/z： P(5,6)t=y+1 可代入x？ t=x+z 可代入x？∀yP(y+1,z) （ ×） ∀yP(x+z,z) （ √）„再如，对于： ∀xP(x,y)ÆQ(y)t=x+a 可代入y？ t=z+a 可代入y？∀xP(x,x+a)ÆQ(x+a) (×) ∀xP(x,z+a)ÆQ(z+a) (√)一阶语言性质 （续3）xtxt„代入：将公式A中变元x的所有自由出现都代换为项t的过程称为代入（前提：t对A中的x是可代入的）。

代换后所得公式称为A的代入实例，记为A 若A中没有x的自由出现，则 A 即为Awenshli@24„对于：P(x,y,z) ÆQ(x)首先：(y+1)/x 得到：P(y+1,y,z) ÆQ(y+1) 继续：(z+1)/y 得到：P(z+2,z+1,z) ÆQ(z+2)若同时：(y+1)/x,(z+1)/y 得到：P(y+1,z+1,z) ÆQ(y+1)nntttAxxx)))(((2211LL„用记号 表示逐步代入x1, x2, …, xnt1, t2, …, tn„用记号 A 表示对A中的变元同时作代入，x1代换为项t1,…,xn代换为项tn一阶语言性质 （续4）„例：设公式A=P(x1,x2)，那么逐步代换：((A ) ) 得到：P(x3,x3)同时代换： A 得到：P(x2,x3)x1 x2x2 x3x1 , x2x2 ,x3wenshli@25„子公式：称公式B为A的子公式，如果A为形如 ωBω′的符号串，其中 ω,ω′为符号串，B为公式当 ω,ω′有一个非空时，B称为A的真子公式„改名：任何约束变元均可改名若公式A中变元x为约束出现，将x改为其它变元(如y，要求y在A中不出现)是合理的。