人工智能及专家系统第4章-逻辑的知识表示和推理课件.ppt

1、 41 命题与逻辑命题与逻辑 411 命题与命题定律命题与命题定律 412 谓词逻辑谓词逻辑 42 谓词逻辑知识表示谓词逻辑知识表示 421 谓词逻辑知识表示方法谓词逻辑知识表示方法 422 谓词逻辑表示的优缺点谓词逻辑表示的优缺点 43 逻辑推理的技术与算法逻辑推理的技术与算法 431 子句集及其化简子句集及其化简 432 置换与合一置换与合一 433 鲁滨逊消解鲁滨逊消解(归结归结)原理原理 41 命题与逻辑命题与逻辑 4.1.1 命题与命题定律命题与命题定律 1.1.概念概念 命题命题、真命题、假命题、原子命题、不是命题。真命题、假命题、原子命题、不是命题。命题的表示命题的表示大写大写A

2、 A、B B、C PC P、Q Q、R R。2.2.联结词（联结词（ConnectivesConnectives）否定或补的联结词用否定或补的联结词用“”表示表示 合取用合取用“”“”表示，表示，析取用析取用“”“”表示，表示，单条件联结词用单条件联结词用“”“”双条件联结词双条件联结词“”“”联结词运算的先后次序为、联结词运算的先后次序为、，同级联结，同级联结词先出现先运算词先出现先运算 3.定义真值指派：真值指派：设一个由设一个由n个变元个变元P1，P2，Pn组成的命题组成的命题表达式表达式A，则，则A的取值由这的取值由这n个变元唯一确定。把变元的个变元唯一确定。把变元的一组取值一组取值(

3、T或或F)叫做该表达式的一个真值指派。叫做该表达式的一个真值指派。真值表：真值表：真值表是由命题表达式所有的真值指派和对应真值表是由命题表达式所有的真值指派和对应的表达式真值所组成的一张表。的表达式真值所组成的一张表。永真式永真式永假式永假式等价式：等价式：设设P与与Q是是D上的两个谓词公式，若对上的两个谓词公式，若对D上的任上的任意解释，意解释，P与与Q都有相同的真值，则称都有相同的真值，则称P与与Q在在D 上是等上是等价的。如果价的。如果D是任意非空个体域，则称是任意非空个体域，则称P与与Q是等价的，是等价的，记作记作PQ。永真蕴含式：永真蕴含式：对谓词公式对谓词公式P和和Q，如果，如果P

4、Q永真，则称永真，则称P 永真蕴含永真蕴含Q，且称，且称Q为为P的逻辑结论，的逻辑结论，P为为Q的前提，记的前提，记作作P Q。4.真值表 PQPPQPQPQP QFFTFFTTFTTFTTFTFFFTFFTTFTTTT5.常用的等价命题定律 双重否定律双重否定律 P P 交换律交换律 PQ QP PQ QP 结合律结合律 （PQ）R P（QR）（PQ）R P（QR）5.常用的等价命题定律 分配律分配律 P（QR）（PQ）（PR）P（QR）（PQ）（PR）P（QR）（PQ）（PR）狄狄摩根定律摩根定律 （PQ）PQ （PQ）PQ 吸收律吸收律 P（PQ）P P（PQ）P 联结词化规律联结词化规

5、律 PQ PQ P Q （PQ）（QP）P Q （PQ）（PQ）变换等价式变换等价式 P （PQ）（PQ）5.常用的等价命题定律6.永真蕴含式永真蕴含式常用的永真蕴含式如下：常用的永真蕴含式如下：(1)化简式化简式 PQ P，PQ Q (2)附加式附加式 P PQ，Q PQ (3)析取三段论析取三段论 P,PQ Q (4)假言推理假言推理 P,PQ Q (5)拒取式拒取式 Q,PQ P (6)假言三段论假言三段论 PQ,QR PR (7)二难推理二难推理 PQ,PR,QR R (8)全称固化全称固化 (x)P(x)P(y)其中，其中，y是个体域中任一个体，依此可消去谓词公式中的全称量词是个体域

6、中任一个体，依此可消去谓词公式中的全称量词 (9)存在固化存在固化 (x)P(x)P(y)其中，其中，y是个体域中某一个可以使是个体域中某一个可以使P(y)为真的个体，依此可消去谓为真的个体，依此可消去谓词公式中的存在量词。词公式中的存在量词。7.利用命题定律证明等价式逻辑推理的步骤：逻辑推理的步骤：利 用 联 结 词 化 规 律 化 掉利 用 联 结 词 化 规 律 化 掉、；利用狄利用狄摩根定律将深入到摩根定律将深入到变元；变元；利用分配律进行变换。利用分配律进行变换。8.示例 例例4-1 试证明：试证明：（P（PQ）Q （PQ）（PQ）例例4-2 证明等价式：（证明等价式：（PQ）（RQ

7、）（PR）Q12 谓词逻辑谓词逻辑 1.1.谓词和个体谓词和个体 个体是指可以独立存在的事物，如花（桃花，个体是指可以独立存在的事物，如花（桃花，玫瑰，犁花）、计算机、智能等等。谓词是用来刻玫瑰，犁花）、计算机、智能等等。谓词是用来刻划个体的性质或关系的。例如张三和李四是工人。划个体的性质或关系的。例如张三和李四是工人。通常用大写英文字母表示谓词，用小写英文字通常用大写英文字母表示谓词，用小写英文字母表示个体。如果母表示个体。如果x x的集合为的集合为a a1 1，a a2 2，a an n，则则STUDENTSTUDENT（a an n）为真（为真（T T）。）。与一个个体相联的谓词叫一元谓

8、词，与多个个与一个个体相联的谓词叫一元谓词，与多个个体相联的谓词叫多元谓词。一个体相联的谓词叫多元谓词。一个n元的谓词常可表元的谓词常可表示为示为P（x1 1，x2 2，xn n），），一般来说，在多元谓词一般来说，在多元谓词中，个体间的次序不可随意交换。中，个体间的次序不可随意交换。2.2.量词量词 首先来考察两个谓词首先来考察两个谓词 P P（x x）：）：x2-1 x2-1（x+1x+1）（）（x 1x 1）Q Q（x x）：）：x+3 x+3对于对于-时为时为T T。1 1 全称量词全称量词 通常把通常把“所有所有”、“一切一切”、“任一任一”、“全体全体”、“凡是凡是”等词统称为全称

9、量词，记为等词统称为全称量词，记为 ；符号；符号“”表示对于个体域中所有的个体表示对于个体域中所有的个体 x，p(x)谓词均为谓词均为T。2 2存在量词存在量词 通常把通常把“存在存在”、“有些有些”、“至少有一个至少有一个”、“有的有的”等词统称为存在量词，记为等词统称为存在量词，记为 ；符号；符号“”表示对于个体域中存在某些个体表示对于个体域中存在某些个体x，Q(x)谓词均为谓词均为T。xxx)()(xpxxx)()(xQx3.量词的集合表示 设个体域x是有限集合S：S=a1，a2，an 由量词的意义可知 A(a1)A(a2)A(an)A(a1)A(a2)A(an)A()(xx)()(xA

10、x4.量词之间的关系 对于二元谓词对于二元谓词P(x,y)，存在以下量化的可能：，存在以下量化的可能：一般来讲，量词的先后次序不可交换。例如，一般来讲，量词的先后次序不可交换。例如，x和和y的个体域都是所有鞋子的集合，的个体域都是所有鞋子的集合，P(x,y)表示一只表示一只鞋子鞋子x可与另一只鞋子可与另一只鞋子y配对，配对，则表示则表示“存在一只鞋子存在一只鞋子x，它可以与任何一只鞋子，它可以与任何一只鞋子y配配对对”,这是不可能的，是个假命题。而这是不可能的，是个假命题。而 表示表示“对任何一只鞋子对任何一只鞋子y，总存在一些鞋子，总存在一些鞋子x可以可以与它配对与它配对”，这是真命题。，这

11、是真命题。),()(yxPyx),()(yxPyx),()(yxPyx),()(yxPyx),()(yxPxy),()(yxPxy),()(yxPxy),()(yxPxy),()(yxPyx),()(yxPxy 3.含有量词的等价式 量词的转换律量词的转换律 量词的分配律量词的分配律 )()()()(xAxxAx)()()()(xAxxAx)()()()()()()(xBxxAxxBxAx)()()()()()()(xBxxAxxBxAx)()()()(xBxAxBAx)()()()(xBxAxBAx3.含有量词的等价式 量词辖域扩张及收缩律 )()()()(PxAxPxAx)()()()(P

12、xAxPxAx)()()()(PxAxPxAx)()()()(PxAxPxAx3.含有量词的等价式 其他等价式其他等价式 量词消去规则量词消去规则 )B)()(B)()(xAxxAx)B)()(B)()(xAxxAx)(B)()(B)(xAxxxA)(B)()(B)(xAxxxA)(B)()()()(B)()(xxxAxxxAx)()()(yAxAx)()()()(为常量ccAxAx4.定理证明 (A(a1)A(a2)A(an)A(a1)A(a2)A(an)(A(a1)B(a1)(A(a2)B(a2)(A(an)B(an)(A(a1)A(a2)A(an)(B(a1)B(a2)B(an)()(x

13、Ax)()(xAx)()()()(xBxxAx)()()(xBxAx5.谓词表达式的范式 前束范式前束范式 若有一谓词表达式若有一谓词表达式W，它的所有量词均非否定地出现，它的所有量词均非否定地出现在表达式的前面，而它们的辖域为整个表达式，则称在表达式的前面，而它们的辖域为整个表达式，则称W为为前束范式。前束范式的一般形式为：前束范式。前束范式的一般形式为：例如例如 就是一就是一个前束范式。个前束范式。SkolemSkolem范式范式 在前束范式中，如果所有的存在量词都出现在全称量在前束范式中，如果所有的存在量词都出现在全称量词之前，则称这种形式的范式表达式为词之前，则称这种形式的范式表达式为

14、Skolem范式。范式。例如例如 不含有量词。的母式，是，或可以是式中MWMxxxMxxxnn),(,W2121),(),(),()()()(zxCzyxByxAzyx),(),(),()()()(zxCzyxByxAzyx42 谓词逻辑知识表示谓词逻辑知识表示 421 谓词逻辑知识表示方法谓词逻辑知识表示方法 1.用谓词逻辑表示简单事实用谓词逻辑表示简单事实 RAININGRAINING；SUNNY SUNNY；MANMAN（zhangsanzhangsan）；）；INROOM INROOM（robotrobot，room1room1）；）；MARRIEDMARRIED（fatherfath

15、er（lisilisi），），mathermather（lisilisi）。2.联结词和量词的应用 1 1、INROOMINROOM（robotrobot，room2room2）；）；2 2LIKELIKE（i i，musicmusic）LIKELIKE（i i，paintingpainting）；）；LIVE(LIVE(lisi,house1)COLOR(house1,yellow)lisi,house1)COLOR(house1,yellow)；3 3PLAY(lihao,basketball)PLAY(lihao,football)PLAY(lihao,basketball)PLAY(l

16、ihao,football)；4 4OWNS(heming,book-1)COLOR(book-1,blue);OWNS(heming,book-1)COLOR(book-1,blue);5 5GRASP(iGRASP(i，you)you)GRASP(youGRASP(you，i)i)；6 6 COLOR(xCOLOR(x,gray),gray);7.()7.()INROOM(xINROOM(x，room-1)room-1)()(xROBOTxx3.谓词逻辑的一般表示方法 例例4-4 用谓词逻辑表示用谓词逻辑表示“所有的整数不是所有的整数不是偶数就是奇数偶数就是奇数”。定义谓词定义谓词:INT

17、EGER(x):表示表示x是整数；是整数；EVEN(x):表示表示x是偶数；是偶数；ODD(x):表示是奇数。表示是奇数。该知识表示为该知识表示为:()(INTEGER(x)EVEN(x)ODD(x)x3.谓词逻辑的一般表示方法 例例4-5 用谓词逻辑表示如下知识用谓词逻辑表示如下知识:“王宏是计算机王宏是计算机系的一名学生系的一名学生”；“李明是王宏的同班同学李明是王宏的同班同学”；“凡是计算机系的学生都喜欢编程序凡是计算机系的学生都喜欢编程序”。首先定义谓词首先定义谓词:COMPUTER(x):表示表示x是计算机系的学生；是计算机系的学生；CLASSMATE(x，y):表示表示x是是y的同

18、班同学；的同班同学；LIKE(x，y):表示表示x喜欢喜欢y。用谓词公式表示上述知识用谓词公式表示上述知识:COMPUTER(wanghong)；CLASSMATE(liming，wanghong)；()(COMPUTER(x)LIKE(x，programing)。x4.用谓词逻辑表示状态 例例4-6 积木状态问题：假如给定积木世界的一个状积木状态问题：假如给定积木世界的一个状态，桌子态，桌子(Table)上放有三块积木上放有三块积木A、B和和C，且，且B在在A上，上，C放在放在A、B的左边，如图的左边，如图4-1所示。用谓词所示。用谓词逻辑给予描述这一积木世界问题的状态。逻辑给予描述这一积木

19、世界问题的状态。先定义几个谓词先定义几个谓词:ON(x，y)：x在在y上；上；ONTABLE（x)：x在桌子上；在桌子上；CLEAR（x)：x顶上是空的顶上是空的;RIGHT(x，y)：x在在y的右边。的右边。x，y的个体域都是的个体域都是A、B、CTableCAB图图4-1 积木世界的一积木世界的一个状态个状态4.用谓词逻辑表示状态 这个积木世界的状态可以表示成这个积木世界的状态可以表示成:ON(B，A)；RIGHT(B，C)；RIGHT(A C)；ONTABLE(A)；ONTABLE(C)；CLEAR(C)；CLEAR(B)。显然有以下关系：显然有以下关系：()(CLEAR(x)()ON(

20、y，x)TableCAB图图4-1 积木世界的一积木世界的一个状态个状态xy4.用谓词逻辑表示状态 例例4-6 机器人移盒子问题：在一个包含有凹室机器人移盒子问题：在一个包含有凹室(Alcove)的的房间内有两张桌子房间内有两张桌子A和和B，一个机器人，一个机器人(Robot)和一个盒子和一个盒子(Box)，如图，如图4-2所示。我们的任务是让机器人从凹室出发，所示。我们的任务是让机器人从凹室出发，把桌子把桌子A上的盒子移到桌子上的盒子移到桌子B上，然后回到凹室。试用谓词上，然后回到凹室。试用谓词逻辑描述这一行动过程。图逻辑描述这一行动过程。图4-2 机器人移盒子初始状态机器人移盒子初始状态R

21、obot 首先定义以下几个谓词首先定义以下几个谓词:TABLE(x)：X是桌子；是桌子；EMPTYHANDED(y)：y手中是空的；手中是空的；AT(y，z)：y在在z的附近；的附近；HOLDS(y，w)：y手中拿着手中拿着w；ON(w，x)：w在在x桌面上。桌面上。其中其中x，y，z，w个体域分别是个体域分别是a，b，robot，a，b，alcove，box。图4-2 机器人移盒子初始状态Robot a b alcove box4.用谓词逻辑表示状态 例例4-6 机器人移盒子问题：在一个包含有凹室机器人移盒子问题：在一个包含有凹室(Alcove)的的房间内有两张桌子房间内有两张桌子A和和B，

22、一个机器人，一个机器人(Robot)和一个盒子和一个盒子(Box)，如图，如图4-2所示。我们的任务是让机器人从凹室出发，所示。我们的任务是让机器人从凹室出发，把桌子把桌子A上的盒子移到桌子上的盒子移到桌子B上，然后回到凹室。试用谓词上，然后回到凹室。试用谓词逻辑描述这一行动过程。图逻辑描述这一行动过程。图4-2 机器人移盒子初始状态机器人移盒子初始状态Robot 首先定义以下几个谓词首先定义以下几个谓词:TABLE(x)：X是桌子；是桌子；EMPTYHANDED(y)：y手中是空的；手中是空的；AT(y，z)：y在在z的附近；的附近；HOLDS(y，w)：y手中拿着手中拿着w；ON(w，x)

23、：w在在x桌面上。桌面上。其中其中x，y，z，w个体域分别是个体域分别是a，b，robot，a，b，alcove，box。图4-2 机器人移盒子初始状态Robot a b alcove box机器人问题的初始状态和目标状态 问题的初始状态是下列问题的合取问题的初始状态是下列问题的合取:AT(robot，alcove)EMPTYHANDED(robot)ON(box，a)TABLE(a)TABLE(b)问题的目标状态是下列问题的合取问题的目标状态是下列问题的合取:AT(robot，alcove)EMPTYHANDED(robot)ON(box，b)TABLE(a)TABLE(b)机器人的操作有三

24、类 GOTO（x，y）：机器人从）：机器人从x处走到处走到y处。处。条件：条件：AT(robot，x)；动作动作:删除删除:AT(robot，x)；添加；添加:AT(robot，y)。PICKUPBOX(x):机器人在机器人在x处拿起盒子。处拿起盒子。条件条件:ON(box，x)，TABLE(x)，AT(robot，x)，EMPTYHANDED(robot)；动作动作:删除删除:EMPTYHANDED(robot)，ON(box，x)；添加添加:HOLDS(robot，box)。SETDOWN(x):机器人在机器人在x处放下盒子。处放下盒子。条件条件:AT(robot，x),TABLE(x)，

25、HOLDS(robot，box)；动作动作:删除删除:HOLDS(robot，box)；添加添加:EMPTYHANDED(robot)，ON(box，x)。机器人行动规划问题的求解过程 状态状态1 1：AT(robotAT(robot，alcove),EMPTYHANDEDalcove),EMPTYHANDED(robot),ON(boxrobot),ON(box，a),TABLE(a),TABLE(ba),TABLE(a),TABLE(b)状态状态2 2：AT(robotAT(robot，a)a)，EMPTYHANDED(robot)EMPTYHANDED(robot)，ON(boxON(b

26、ox，a),TABLE(a),TABLE(b)a),TABLE(a),TABLE(b)状态状态3 3：AT(robotAT(robot，a)a)，HOLDS(robotHOLDS(robot，box)box)，TABLE(a)TABLE(a)，TABLE(b)TABLE(b)状态状态4 4：AT(robotAT(robot，b)b)，HOLDS(robotHOLDS(robot，box)box)，TABLE(a)TABLE(a)，TABLE(b)TABLE(b)状态状态5 5：AT(robotAT(robot，b),EMPTYHANDED(robot),ON(boxb),EMPTYHANDED

27、(robot),ON(box，b),TABLE(a),TABLE(b)b),TABLE(a),TABLE(b)状态状态6 6：AT(robotAT(robot，alcove),EMPTYHANDED(robot),ON(boxalcove),EMPTYHANDED(robot),ON(box，b),TABLE(a),TABLE(bb),TABLE(a),TABLE(b)图图4-3 4-3 机器人行动规划问题的求解过程机器人行动规划问题的求解过程目标状态目标状态初始状态初始状态GOTO(xGOTO(x，y)y)用用alcovealcove代换代换x x，a a代换代换y y用用a a代换代换x

28、xPICKUPBOX(x)PICKUPBOX(x)用用a a代换代换x x，b b代换代换y yGOTO(xGOTO(x，y)y)用用b b代换代换x xSETDOWN(x)SETDOWN(x)用用b b代换代换x x，GOTO(xGOTO(x，y)y)alcovealcove代换代换y y5.逻辑表示与推理 例例4-7 已知下面事实：试问马科斯还活着吗？已知下面事实：试问马科斯还活着吗？马科斯是男人；马科斯是男人；马科斯是庞贝人；马科斯是庞贝人；马科斯出生于公元马科斯出生于公元40年；年；所有的人都会死；所有的人都会死；所有庞贝人都死于公元所有庞贝人都死于公元79年的火山爆发；年的火山爆发；

29、公元公元79年的火山爆发；年的火山爆发；所有会死的人数不会超过所有会死的人数不会超过150岁；岁；现在是现在是2002年年 活意即未死；活意即未死；如果某人死了，那么他后来的任何时刻都死了。如果某人死了，那么他后来的任何时刻都死了。马科斯问题的逻辑表示 MAN(marcus)；POMPEIAN(marcus)；BORN(marcus，40)；()MAN(x)MORTAL(x)；ERUPTED(volcano，79)()POMPEIAN(x)DIED(x，79)；ERUPTED(volcano，79)；MORTAL(x)BORN(x,t1)GT(T2-t1,150)DEAD(x,t2)NOW=2

30、011；ALIVE(x，t)DEAD(x,t)；DEAD(x,t1)GT(t2，t1)DEAD(x,t2)xx)()(21ttx)()(21ttx)(tx)()(21ttx马科斯问题的证明过程 图图4-4 4-4 证明马科斯已死的过程证明马科斯已死的过程ALIVE(marcusALIVE(marcus，now)now)用用9 9代换代换DEAD(marcusDEAD(marcus，now)now)用用1010代换代换DEAD(marcusDEAD(marcus,t1)GT(now)GT(now，t1)用用5 5代换代换ERUPTED(volcanoERUPTED(volcano，79)POMP

31、EIAN(marcus)GT(now79)POMPEIAN(marcus)GT(now，79)79)用用6 6、2 2代换代换GT(nowGT(now，79)79)用用8 8代换代换GT(2011GT(2011，79)79)计算计算GTGTnilnil43 逻辑推理的技术与算法逻辑推理的技术与算法 431 子句集及其化简子句集及其化简 1.子句与子句集子句与子句集定义定义1：不含有任何联接词以及量词的谓词称为不含有任何联接词以及量词的谓词称为原子谓词原子谓词。定义定义2：文字文字是原子谓词及其否定形式的统称。是原子谓词及其否定形式的统称。例如：例如：P(x)、P(x)、Q(x，y)、Q(x，y

32、)等都是文字。等都是文字。定义定义3：若若P是原子谓词，则称是原子谓词，则称P与与P为为互补文字互补文字。定义定义4：若干个文字的一个析取式称为一个若干个文字的一个析取式称为一个子句子句，例如：例如：P(x)(Q(x)；P(x，f(x)Q(x，g(x)都是子句。都是子句。定义定义5：由由r个文字组成的子句叫个文字组成的子句叫r-文字子句。文字子句。定义定义6：1-文字子句叫文字子句叫单元子句。单元子句。定义定义7：不含任何文字的子句叫不含任何文字的子句叫空子句空子句，记为或，记为或NIL，空子句，空子句是永假的，不可满足的。是永假的，不可满足的。定义定义8：所谓所谓子句集子句集是由子句或空子句

33、构成的一种集合。是由子句或空子句构成的一种集合。2.子句集的化简 消去联结词消去联结词“”“”、“”“”。缩小否定词的使用范围。缩小否定词的使用范围。变元适当改名变元适当改名(标准化标准化)。使量词间不含同名指导变元。使量词间不含同名指导变元和约束变元。和约束变元。化为前束范式。化为前束范式。消去存在量词。消去存在量词。若存在量词左边没有全称量词，只要用新的个体常量若存在量词左边没有全称量词，只要用新的个体常量替换该存在量词约束的变元，同时消去该存在量词。替换该存在量词约束的变元，同时消去该存在量词。若存在量词位于一个或多个全称量词的辖域内若存在量词位于一个或多个全称量词的辖域内(存在量存在量

34、词在右边词在右边)，则用这些全称量词指导变元的一个函数代替，则用这些全称量词指导变元的一个函数代替该存在量词辖域中的相应约束变元。该存在量词辖域中的相应约束变元。化为化为SkolemSkolem标准形。标准形。消去所有全称量词。消去所有全称量词。消去合取词，把母式用子句集的形式表示出来。消去合取词，把母式用子句集的形式表示出来。更换变元名称，使子句间无同名变元。更换变元名称，使子句间无同名变元。2.子句集的化简（子句集的化简（1/6）在谓词逻辑中，任何一个谓词公式都可以通过应用等价在谓词逻辑中，任何一个谓词公式都可以通过应用等价关系及推理规则化成相应的子句集。其化简步骤如下：关系及推理规则化成

35、相应的子句集。其化简步骤如下：(1)消去连接词消去连接词“”和和“”反复使用如下等价公式：反复使用如下等价公式：PQ PQ PQ (PQ)(PQ)即可消去谓词公式中的连接词即可消去谓词公式中的连接词“”和和“”。例如公式例如公式 (x)(y)P(x,y)(y)(Q(x,y)R(x,y)经等价变化后为经等价变化后为 (x)(y)P(x,y)(y)(Q(x,y)R(x,y)(2)减少否定符号的辖域减少否定符号的辖域反复使用反复使用双重否定率双重否定率 (P)P摩根定律摩根定律 (PQ)PQ (PQ)PQ量词转换率量词转换率 (x)P(x)(x)P(x)(x)P(x)(x)P(x)将每个否定符号将每

36、个否定符号“”移到仅靠谓词的位置，使得每个否定移到仅靠谓词的位置，使得每个否定符号最多只作用于一个谓词上。符号最多只作用于一个谓词上。例如，例如，上式经等价变换后为上式经等价变换后为 (x)(y)P(x，y)(y)(Q(x，y)R(x，y)2.子句集的化简（子句集的化简（2/6）(3)对变元标准化对变元标准化 在一个量词的辖域内，把谓词公式中受该量词约束的变元全在一个量词的辖域内，把谓词公式中受该量词约束的变元全部用另外一个没有出现过的任意变元代替，使不同量词约束的部用另外一个没有出现过的任意变元代替，使不同量词约束的变元有不同的名字。变元有不同的名字。例如，上式经变换后为例如，上式经变换后为

37、 (x)(y)P(x，y)(z)(Q(x，z)R(x，z)(4)化为前束范式化为前束范式 化为前束范式的方法化为前束范式的方法:把所有量词都移到公式的左边，并且把所有量词都移到公式的左边，并且在移动时在移动时不能改变其相对顺序不能改变其相对顺序。由于第。由于第(3)步已对变元进行了标步已对变元进行了标准化，每个量词都有自己的变元，这就消除了任何由变元引起准化，每个量词都有自己的变元，这就消除了任何由变元引起冲突的可能，因此这种移动是可行的。冲突的可能，因此这种移动是可行的。例如，上式化为前束范式后为例如，上式化为前束范式后为 (x)(y)(z)(P(x，y)(Q(x，z)R(x，z)2.子句集

38、的化简（子句集的化简（3/6）(5)消去存在量词消去存在量词 消去存在量词时，需要区分以下两种情况：消去存在量词时，需要区分以下两种情况：若存在量词不出现在全称量词的辖域内若存在量词不出现在全称量词的辖域内（即它的左边没有（即它的左边没有全称量词），只要用一个新的个体常量替换受该存在量词约全称量词），只要用一个新的个体常量替换受该存在量词约束的变元，就可消去该存在量词。束的变元，就可消去该存在量词。若存在量词位于一个或多个全称量词的辖域内若存在量词位于一个或多个全称量词的辖域内，例如，例如 (x1)(xn)(y)P(x1，x2,xn,y)则需要用则需要用Skolem函数函数f(x1，x2,xn

39、)替换受该存在量词约束替换受该存在量词约束的变元的变元y，然后再消去该存在量词。然后再消去该存在量词。例如，上步所得公式中存在量词例如，上步所得公式中存在量词(y)和和(z)都位于都位于(x)的辖域内，因此都需要用的辖域内，因此都需要用Skolem函数来替换。设替换函数来替换。设替换y和和z的的Skolem函数分别是函数分别是f(x)和和g(x)，则替换后的式子为则替换后的式子为 (x)(P(x,f(x)(Q(x,g(x)R(x,g(x)2.子句集的化简（子句集的化简（4/6）(6)化为化为Skolem标准形标准形 Skolem标准形的一般形式为标准形的一般形式为 (x1)(xn)M(x1,x

40、2,xn)其中，其中，M(x1,x2,xn)是是Skolem标准形的母式，它由子句的合标准形的母式，它由子句的合取所构成。取所构成。把谓词公式化为把谓词公式化为Skolem标准形需要使用以下等价关系标准形需要使用以下等价关系 P(QR)(PQ)(PR)例如，前面的公式化为例如，前面的公式化为Skolem标准形后为标准形后为 (x)(P(x,f(x)Q(x,g(x)(P(x,f(x)R(x,g(x)(7)消去全称量词消去全称量词 由于母式中的全部变元均受全称量词的约束，并且全称量词由于母式中的全部变元均受全称量词的约束，并且全称量词的次序已无关紧要，因此可以省掉全称量词。但剩下的母式，的次序已无

41、关紧要，因此可以省掉全称量词。但剩下的母式，仍假设其变元是被全称量词量化的。仍假设其变元是被全称量词量化的。例如，上式消去全称量词后为例如，上式消去全称量词后为 (P(x,f(x)Q(x,g(x)(P(x,f(x)R(x,g(x)2.子句集的化简（子句集的化简（5/6）(8)消去合取词消去合取词 在母式中消去所有合取词，把母式用子句集的形式表示出在母式中消去所有合取词，把母式用子句集的形式表示出来。其中，子句集中的每一个元素都是一个子句。来。其中，子句集中的每一个元素都是一个子句。例如，例如，上式的子句集中包含以下两个子句上式的子句集中包含以下两个子句 P(x,f(x)Q(x,g(x)P(x,

42、f(x)R(x,g(x)(9)更换变量名称更换变量名称 对子句集中的某些变量重新命名，使任意两个子句中不出对子句集中的某些变量重新命名，使任意两个子句中不出现相同的变量名。由于每一个子句都对应着母式中的一个合现相同的变量名。由于每一个子句都对应着母式中的一个合取元，并且所有变元都是由全称量词量化的，因此任意两个取元，并且所有变元都是由全称量词量化的，因此任意两个不同子句的变量之间实际上不存在任何关系。这样，更换变不同子句的变量之间实际上不存在任何关系。这样，更换变量名是不会影响公式的真值的。量名是不会影响公式的真值的。例如，例如，对前面的公式，可把第二个子句集中的变元名对前面的公式，可把第二个

43、子句集中的变元名x更更换为换为y，得到如下子句集得到如下子句集 P(x,f(x)Q(x,g(x)P(y,f(y)R(y,g(y)2.子句集的化简（子句集的化简（6/6）将逻辑表达式化成子句集例例4-8 求下列谓词表达式的子句集。求下列谓词表达式的子句集。解：利用上述步骤，按以下步骤进行求解：解：利用上述步骤，按以下步骤进行求解：消去消去 ：否定深入：否定深入：变元改名：变元改名：化为前束范式：化为前束范式：消去存在量词：消去存在量词：),(),()(),()(yxRyxQyyxPyx),(),()(),()()(yxRyxQyyxPyx),(),()(),()(yxRyxQyyxPyx),()

44、,()(),()(zxRzxQzyxPyx),(),(),()()()(zxRzxQyxPzyx)(,()(,()(,()(xgxRxgxQxfxPx将逻辑表达式化成子句集 化为化为Skolem标准形：标准形：消去全称量词：消去全称量词：消去合取词：消去合取词：更换变元名称：更换变元名称：)(,()(,()(,()(,()(xgxRxfxPxgxQxfxPx)(,()(,()(,()(,(xgxRxfxPxgxQxfxP)(,()(,(),(,()(,(xgxRxfxPxgxQxfxP)(,()(,(),(,()(,(ygyRyfyPxgxQxfxP432 置换与合一置换与合一 1.置换置换

45、置换是在一个谓词表达式中用置换项去替换变置换是在一个谓词表达式中用置换项去替换变量，其一般形式为有限集合量，其一般形式为有限集合t1/x1，t2/x2，tn/xn。其中。其中xi是变量，是变量，ti是不同于是不同于xi的项，可以是的项，可以是常量、函数，或者其他的变量。常量、函数，或者其他的变量。xixj(iji，j1，2，n)，ti/xi表示用表示用ti替换替换xi，xi不能循环地出不能循环地出现在另一个现在另一个ti中。中。例如例如 a/x，b/y，f(c)/z是一个置换，而是一个置换，而g(y)/x，f(x)/y就不是一个置换，原因是它在就不是一个置换，原因是它在x和和y之间出之间出现了

46、循环置换现象。通常置换用希腊字母现了循环置换现象。通常置换用希腊字母、表示。表示。置换的例示 在谓词表达式在谓词表达式 W=Px，f(y)，B中，若用置换中，若用置换=t1/x1，t2/x2，tn/xn，把，把W中所有的中所有的xi全部换全部换成成ti(i=1，2，n)，记为，记为W，所得结果称为，所得结果称为W在在置换置换下的例示。下的例示。表表4-4 四种不同的例示四种不同的例示 序号 置换 置换的例示 1=z/x，w/y W1=Px，f(y)，B1=Pz，f(w)，B 2=A/y W2=Px，f(y)，B2=Px，f(A)，B 3=g(z)/x，A/y W3=Px，f(y)，B3=Pg(

47、z)，f(A)，B 4=c/x，A/y W4=Px，f(y)，B4=Pc，f(A)，B 复合置换 若有两个置换若有两个置换=t1/x1，t2/x2，tn/xn，=u1/y1，u2/y2，um/ym。当当ti=xi时，删去时，删去ti/xi(i=1，2，n)；当当yix1，x2，xn时，删去时，删去uj/yj(i=1，2，m)；称集合称集合t1/x1，t2/x2，tn/xn，u1/y1，u2/y2，um/ym 最后所剩下的元素为置换最后所剩下的元素为置换与与的复合置换，记为的复合置换，记为。复合置换举例 例例4-9 设设=f(y)/x，z/y，=a/x，b/y，y/z，求，求。解：解：=t1/x

48、1，t2/x2，u1/y1，u2/y2，u3/y3 =f(b/y)/x，(y/z)/y，a/x，b/y，y/z=f(b)/x，y/y，a/x，b/y，y/z 其中其中y/y满足条件，满足条件，a/x、b/y满足条件给予删满足条件给予删除。从而得到：除。从而得到：=f(b)/x，y/z 一般情况下复合置换是不可交换的，即一般情况下复合置换是不可交换的，即。2.合一 合一是通过对项进行置换，使两个谓词表达式达到一致合一是通过对项进行置换，使两个谓词表达式达到一致的过程，通过合一，可把若干表达式合为一个表达式。合的过程，通过合一，可把若干表达式合为一个表达式。合一的一般定义为：一的一般定义为：设设W

49、=W1，W2，Wn，若存在一个置换，若存在一个置换，可使，可使W1=W2=Wn，则称，则称是是W的一个合一，称的一个合一，称W是可以合一是可以合一的。的。一般一个表达式集的合一不唯一。一般一个表达式集的合一不唯一。若若是表达式集是表达式集W的一个合一，如果对的一个合一，如果对W的任意一个合的任意一个合一一，都存在一个置换，都存在一个置换，使得，使得=，则称，则称为为W的最一般的最一般合一。合一。一个表达式集的最一般合一是唯一的。例如一个表达式集的最一般合一是唯一的。例如 W=P(u，y，g(y)，p(x，f(u)，z)有一个最一般合一：有一个最一般合一：=u/x，f(u)/y，g(f(u)/z

50、；例如；例如=a/x，f(a)/y，g(f(a)/z，a/u，存在一个置换：，存在一个置换：=a/u，使得使得=。433 鲁滨逊消解鲁滨逊消解(归结归结)原理原理 1.命题逻辑的消解原理命题逻辑的消解原理命题逻辑的消解原理命题逻辑的消解原理 因为因为PQ，QR PR，即即(PQ)(QR)(PR)，也，也就是说由就是说由C1L和和LC2可以推出可以推出C1C2来。来。基本思想基本思想 注意以下两个关键注意以下两个关键 第一，第一，子句集中的子句之间是合取关系。因此，子句集中只要有子句集中的子句之间是合取关系。因此，子句集中只要有一个子句为不可满足，则整个子句集就是不可满足的；一个子句为不可满足，