第三章谓词逻辑（第一部分）（Chapter3PredicateLogic）

第三章谓词逻辑

（第一部分）

(Chapter3PredicateLogic)

(PartA)徐从富浙江大学人工智能研究所2002年第一稿2004年9月修改

一阶谓词演算是一种形式语言，其根本目的在于把数学中的逻辑论证符号化，之所以有用是其给出了一种数学演绎方法：旧知识——数学演绎—新知识参考书：[1]俞瑞钊.数理逻辑.浙江大学出版社.[2]Chang,C.L.,Lee,R.C.T.SymbolicLogicandMechanicalTheoremProving.AcademicPress,1973.

最重要的三类谓词演算的相互关系：命题演算一阶谓词演算二阶谓词演算【注】：本课程对二阶谓词演算不予讨论。3.1谓词演算3.1.1命题逻辑及其局限性

命题：不带参数的谓词

谓词：带参数的命题

我们可以很容易地把客观世界的各种事实表示为逻辑命题，用命题逻辑把各种命题写成合适公式（WFF），也称“谓词公式”。例如： 晴天: 表示为SUNNY

雨天： 表示为RAINING

雾天： 表示为FOGGY “若为雨天，则非晴天” 表示为

RAININGSUNNY

“张三是工人” 表示为

ZHANG-SAN-IS-WORKER

“毛泽东生于1893年” 表示为MAO-TZETONG-IS-BORN-IN-EIGHTEEN-NINETY-THREE注：上述连字符，只是为了便于阅读，可有可无。由上述可知，表示知识的陈述性形式称为命题。

带有参数的命题叫谓词，比起命题来，谓词有更强的表达能力。谓词逻辑可以表达那些无法用命题逻辑表达的事实。因为：

（1）命题没有概括能力。为了表达：“XX是一个城市”，则有多少个城市就要用多少个命题来表示：P1:代表“杭州是一个城市”P2:代表“上海是一个城市”P3:代表“北京是一个城市”………

事实上，上述命题只要用一个谓词CITY(X)即可表示，其中X可以是杭州、上海、北京……，上述三个命题变为：P1:CITY(杭州)P2:CITY(上海)P3:CITY(北京)

（2）谓词可以代表变化着的情况，而命题只能代表某种固定的情况。对命题而言，其值非真即假，不可变化。例如：P：杭州是一个城市 P之值恒真Q：鸵鸟会飞 Q之值恒假但是，谓词值的真假却可因参数而异。例如：P1：CITY(杭州) P1之值为真P2：CITY(鸵鸟) P2之值为假（3）可以利用谓词在不同的知识之间建立联系。例如： HUMAN(X)X是人 LAWED(X)X受法律管制 COMMIT(X)X犯法 PUNISHED(X)X受法律制裁前两个知识单元可联成一个高一级的知识单元：第一判断：HUMAN(X)LAWED(X)

表示：人人都要受法律的管制。直译：由于X是人，则X这个人就要受法律管制。后两个知识单元也可联成一个高一级的知识单元：第二判断：

COMMIT(X)PUNISHED(X)

表示：只要X犯了罪，X就要受到惩罚。这里X不一定是人，可以是人，也可以是某种动物。进一步，还可把这两个高级知识单元联成更高级的知识单元：

{[HUMAN(X)LAWED(X)]

[COMMIT(X)PUNISHED(X)]}

错误的理解：“因为人人都受法律的管制，所以任何人犯了罪一定要受到惩罚。”

正确的意思：

“如果【由于某个X是人而受到法律管制】，则这个人犯了罪就一定要受到惩罚。”事实上，由第一判断推不出第二判断。例如：(1)晁盖劫了生辰纲，违犯了宋王朝的法律，受到官府的追究。

(2)

高俅强抢民女，同样违犯了宋王朝的法律，却可以横行无忌。从第二判断看，可以解释得通：(1)晁盖是人而受到法律管制。对晁盖来说，第二判断的前提成立，因此要治罪。

(2)

高俅同样是人而不受法律管制。而对高俅来说，第二判断的前提不成立，故可逍遥法外。更有甚者，第二判断还包括这样的意思：“如果X不是人，则X犯了罪就一定要受到惩罚。”

例如：兔子犯罪要受到惩罚。这是因为，如HUMAN(X)为假，则不论LAWED(X)如何，第二判断的前提自然为真，其结论又必然为真。需特别注意的是：谓词公式对于同名参数置换的一致性要求使得不同论断之间可以建立起内在联系。但是这样做的时候必须特别小心，否则很容易把意思搞错。3.1.2句法和语义

谓词逻辑的基本组成部分：

谓词符号、变量符号、函数符号、常量符号，并用（）、[]、{}和，隔开，以表示论域内的关系。例如：

INROOM(ROBOT,R1)

谓词符号常量符号表示：机器人ROBOT在1号房间（ROOM1）内。(1)原子公式：由若干谓词符号和项组成。

(2)

常量符号（项）：表示论域内的物体或实体，可以是物、人、概念或事情。

(3)

变量符号（项）：允许不必明确涉及是哪一个实体，如INROOM(X,Y),X,Y即为变量。(4)

函数符号：表示论域内的函数。例如函数符号MOTHER可表示某人与他或她母亲的映射。原子公式举例：“李的父亲与他的母亲结婚”MARRIED[father(LI),mother(LI)]

说明：

(1)一般可用大写字母串表示谓词符号，如INROOM,MARRIED。

(2)“大写字母＋数字短串”即可表示谓词符号，也可作为常量符号。如，P1,Q2,…

(3)常量符号与谓词符合的区别要通过上下文来区分。(4)

小写字母表示函数符号，如father,mother(5)原子公式的真、假。对已定义了某个解释的一个原子公式，只有当其对应的语句在定义域内为真时，才具有真值；反之，也成立。3.1.3连词和量词

原子公式是谓词演算的基本“积木块”，应用连词（与）、（或）、蕴涵（隐含）或(1)连词

表示“合取”，组成复合句子。例如：“我喜爱音乐和绘画”LIKE(I,MUSIC)LIKE(I,PAINTING)“李住在一幢黄色的房子里”LIVES(LI,HOUSE-1)COLOR(HOUSE-1,YELLOW)(2)连词

表示“析取”，表示可兼有的“或”。例如：“李明打篮球或踢足球”PLAYS(LIMING,BASKETBALL)PLAYS(LIMING,FOOTBALL)

(3)真值的确定

每个合取项都为真（T），则合取值为真。若析取项中至少又一个取真，则析取值为真（T），否则为假(F)。(4)连词

表示“如果…那么…”。例如：“如果兔子跑得最快，那么它取得冠军”RUNS(RABBIT,FASTEST)WINS(RABBIT,CHAMPION)

蕴涵：用“”连接两个公式所构成的公式，其中，蕴涵的左式称为“前项”，右式成为“后项”。

蕴涵真值的确定：a)若前项取值为假（F），不管其后项的真值如何(TorF)，则蕴涵取值为真(T)。

b)若后项取值为真（T），不管其前项的值为如何(TorF)，则蕴涵取值为真(T)。c)只有在前项为真，后项为假时，蕴涵为假。(5)“”（非）或“”用来否定一个公式的真值。INROOM(ROBOT,R2)

(6)命题演算是谓词演算的子集，不使用变量项，它缺乏用有效的方法来表达多个命题的能力。如：“所有的乌鸦都是黑的”(7)全称量词x：表示“所有的x或任一个x”

存在量词x：表示“存在一个x，至少有一个x”(x)[ROBOT(x)COLOR(x,GRAY)](x)INROOM(x,R1)(8)约束变量：经过量化的变量

自由变量：未经量化的变量我们一般关心的是受约束变量，由它构成的合适公式叫“句子”。注意：在讨论一阶谓词运算时，不允许对谓词符号或函数符号进行量化。如下面的表示是不允许的：(P)P(A) 错误！！3.2谓词公式3.2.1谓词公式的定义

原子公式（原子谓词公式）：P(x1,x2,…,xn)

分子谓词公式：用连词（,,等）把原子谓词公式组成的复合谓词公式。例如：“任何整数或者为正或者为负”(x)[I(x)(P(x)N(x))]

所有xx是整数x是整数x是负数SyntaxitemUsuallyusedOthersNegation(not)~P,PP（加上划线）Conjunction(and)PQP&QP·QPQP,QDisjunction(or)PQP|QP;QP+QImplication(if)PQPQPQEquivalence(iff)PQPQPQUniversal(all)(x)P(x)xP(x)xP(x)Existential(exists)(x)P(x)xP(x)xP(x)RelationR(x,y)(Rxy)Rxy

xRy常用的谓词公式表示方法对照表：3.2.2合适公式的性质

若P,Q是两个合适公式，则真值表为：PQPQPQTTTTFTTTTFFTFFTF(1)

否定之否定:(P)

P注：表示“等价与”

(2)PQ

PQ或 PQ

PQ

(3)狄•摩根(DeMorgan)定律

(PQ)

P

Q

(PQ)

P

Q

(4)

分配率 P(QR)(PQ)(PR) P(QR)(PQ)(PR)

(5)

交换率 PQ

QR PQ

QP

(6)结合率 (PQ)R

P(QR) (PQ)R

P(QR)

(7)逆否律 PQ

QP

(8)

(x)P(x)(x)[

P(x)] (x)P(x)(

x)[

P(x)]

(9)全称量词、局部量词的分配率(x)[P(x)Q(x)]

(x)P(x)(x)Q(x)(x)[P(x)Q(x)]

(x)P(x)(x)Q(x)

(10)约束变量的替换法则 (x)P(x)(y)P(y)

(

x)P(x)(

y)P(y)

关于上述性质（10）的说明：

在一个量化的表达式中的约束变量是一类“虚元”，它可用任何一个未在表达式中出现过的其它变量符号来代替。

P,Q两个合适公式的析取、合取、蕴涵、等价四种运算的形象化（集合）表示：谓词公式的表达方法举例：例1.试用谓词演算表示如下英文句子：“Foreverysetx,thereisasety,suchthatthecardinalityofyisgreaterthanthecardinalityofx.”步1.For(x)SET(x),then(y)SET(y),|y|>|x|步2.(x){SET(x)(y)[SET(y)(|y|>|x|)]}步3.(x){SET(x)(y)[SET(y)((u)CARD(y,u)>(v)CARD(x,v))]}步4.(x){SET(x)(y)[SET(y)((u)CARD(y,u)(v)CARD(x,v)G(u,v))]}步5.(x){SET(x)(y)(u)(v)[SET(y)CARD(y,u)CARD(x,v)G(u,v)]}说明：（1）SET(x)和SET(y)分别表示集合x，集合y；（2）CARD(x,v)表示集合x的“模”为v，同样 CARD(y,u)表示集合x的“模”为u；

（3）G(u,v)表示u的值大于v的值。例2.把论断“世上决没有无缘无故的爱，也没有无缘无故的恨。”表示成谓词公式的形式。解题思路：把论断的表示形式“分细”，即知识的模块化问题。在下列不同程度上予以细分：步1.P——表示整个论断（即命题）步2.分解为2个命题：

没有无缘无故的爱

没有无缘无故的恨步3.否定词分出来：存在无缘无故的爱

存在无缘无故的恨步4.存在量词分出来：x[无缘无故的爱(x)]

y[无缘无故的恨(y)]步5.把“爱”和“恨”的概念分出来：x[爱(x)无缘故(x)]

y[爱(y)无缘故(y)]步6.把“缘故”的否定词分出来：x[爱(x)有缘故(x)]

y[爱(y)有缘故(y)]步7.把“A是B的原因”这个概念中的A和B分解开来：x[爱(x)y缘故(x,y)]

t[爱(t)s缘故(t,s)]

注意：一般地，分得越细，所含的知识越丰富，但推理效率也越低，究竟分到什么程度，应视需要而定。3.2.3永真性

永真：一个公式如果它对所有的解释均取真值，则称作“永真”。

重言式：永真的基公式。例如：P(x)[P(x)P(y)]为永真。

P(x)P(y) P(x)P(y) 说明F F F TF T T TT F T TT T T T3.3与或句演绎系统3.3.1与或句的SKOLEM标准形

SKOLEM标准形：只有

,,谓词（原子），前有“非”符号（）的谓词（负原子），以及看不见的全称量词（）组成的合适公式称为“与或句”——SKOLEM标准形。【注】：正、负原子统称为“句节”。任何合适公式都可化成与或句的形式。分为两步：

第一步：化成前束范式，即所有量词都在合适公式的最前面，每个量词的辖域（适用范围）都是整个公式。进而将合适公式化成等值的合取范式。第二步：消去存在量词，只剩下全称量词。化为前束范式的步骤是：1.把“IfAthenBelseC”化成(AB)(AC)或 (AB)(AC)

2.把AB（或AB）化成(AB)(BA)或 (AB)(BA)

3.把AB（或AB）化成AB4.利用下列式子消去或移入“非”符号 (1)把A化成A

(2)把(AB)化成AB

(3)把(AB)化成AB

(4)把xA(x)化成x(A(x))

(5)把xA(x)化成x(A(x))

5.把所有的量词变量全部换成不同的名字例如： xA(x)xB(x)化成 xA(x)yB(y)

6.把所有的量词按原来次序移至最前边。

7.消去存在量词。假定此时的前束范式中不存在自由变量，因此，范式中的每个变量必定属于某个量词管辖的范围。假设共有n个量词，前束形式是：

Qixi

i=1,2,...,n其中，每个Qi或是，或是，从Q1始，到Qn止。

消去存在量词的算法如下：

(1)若Qi是，则移向下一个i，原Qixi不变动。(2)若Qi是，则消去Qixi

，并且

a)若Qi前没有全称量词，则把后面公式中的所有同名xi换成一个从未出现过的常数名；b)若Qi前有m个全称量词，则把后面公式中的所有同名xi换成fi(xi,1,...,xi,m)，其中，fi是从未出现过的函数名，xi,1,...,xi,m是这m个全称量词管辖的变量名；

c)做完第n个（最后一个）量词后算法停止。此时，实际上把所有的存在量词都去掉了，剩下的变量都有全称量词在管着它，这时得到的公式称作合适公式的SKOLEM标准形。3.3.2SKOLEM标准形的作用

在定理的机械化证明（一种机械化的、在计算机上实现的推理）过程中，我们面临的首要问题是如何建立推理规则。例如：假设由命题逻辑描述的命题A1,A2,A3和B，要求证明在A1A2A3成立的条件下B成立。或者说要证明A1A2A3B是定理（重言式）事实上，我们经常采用反演推理方法（即反证法）来证明。要证明A1A2A3B是重言式，就等价于证明A1A2A3B是矛盾式（永假式）。然而，要证明A1A2A3B是矛盾式（永假式），就要遇到量词（包括存在量词和全称量词）的问题，为此，需要将A1A2A3B化成SKOLEM标准形，进而建立“子句集”，方可使用Herbrand（海伯伦）定理和归结（Resolution）原理来证明A1A2A3B

是不可满足的。因此，SKOLEM标准形是利用Herbrand定理和归结（Resolution）原理等进行定理机械化证明的基础，具有非常重要的地位和作用。3.3.3合适公式转换成SKOLEM标准形举例例1.试将G=(x)(y)(z)((P(x,y)Q(x,z))R(x,y,z))化成SKOLEM标准形（即“与或式”）。解：令M(x,y,z)=(P(x,y)Q(x,z))R(x,y,z)则 G=(x)(y)(z)M(x,y,z)可知，G已是前束形了，需将M(x,y,z)化成合取范式。得M(x,y,z)=(P(x,y)R(x,y,z))(Q(x,z))R(x,y,z))于是G=(x)(y)(z)((P(x,y)R(x,y,z))(Q(x,z))R(x,y,z)))先消去(y)，令y=f(x)，有G=(x)(z)((P(x,f(x))R(x,f(x),z))(Q(x,z))R(x,f(x),z)))再消去(z)，令z=g(x)，有G=(x)((P(x,f(x))R(x,f(x),g(x)))(Q(x,g(x)))R(x,f(x),g(x))))上式即为G的SKOLEM标准形。其中，f(x),g(x)称作SKOLEM函数。例2.试将G=(x)(y)(z)(u)P(x,y,z,u)化成SKOLEM标准形。解：令x=a（某个常量）则 G=(y)(z)(u)P(a,y,z,u)再令u=f(y,z)，得G的SKOLEM标准形为：G=(y)(z)P(a,y,z,f(y,z))【注意】：G的SKOLEM标准形同G并不等值。3.3.4有目标的与或句演绎系统与或句演绎系统可用于求证某个目标的推理。例1.假设有下列事实和规则：1.喜欢《三国演义》者必读《水浒》2.某书与《儒林外史》同类，则一定不与《水浒》同类3.没有人喜欢的书不会和《三国演义》同类4.俞平伯只读与《红楼梦》同类的书求证：若《红楼梦》与《儒林外史》同类，则俞平伯一定不喜欢《三国演义》。证明：第一步，先将上述事实、规则和求证目标写成一阶谓词形式：

规则1.(x)(like(x,三国)read(x,水浒))规则2.(x)(samesort(x,儒林外史)

samesort(x,水浒))规则3.(x)like(x,y)

samesort(y,三国))规则4.read(俞平伯,y)samesort(y,红楼梦)辅助规则：samesort(x,y)

samesort(y,x)

求证目标：samesort(红楼梦,儒林外史)like(俞平伯,三国)第二步，将规则1化成SKOLEM标准形：