谓词逻辑幻灯片.ppt

《谓词逻辑幻灯片.ppt》由会员分享，可在线阅读，更多相关《谓词逻辑幻灯片.ppt（68页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、谓词逻辑第1页，共68页，编辑于2022年，星期二n n之所以出现这种推理本身是正确的,但无法证明其有效性的问题,是因为没有对原子命题的内部形式结构极其逻辑关系进行讨论,这正是谓词逻辑首先要研究的内容.n n本书讨论的谓词逻辑是一阶逻辑.n n利用谓词逻辑建立起来的数据库设计理论,具有牢固的数学基础和一定的智能特点.同时,现实世界中的任何问题只要能用谓词逻辑推理系统方式表示出来,就可以将它写成逻辑程序设计PROLOG(PROgramming in LOGic)语言,并用计算机加以实现,如已经开发出的一些智能教学专家系统等.第2页，共68页，编辑于2022年，星期二4.1 个体、谓词、量词和函词

2、个体、谓词、量词和函词n n1.1.个体个体n n下面下面4 4个命题均为原子命题：个命题均为原子命题：n n(1)5(1)5是素数是素数.n n(2)3大于大于2.2.n n(3)(3)张三是学生张三是学生.n n(4)(4)所有的人都是要死的所有的人都是要死的.n n上面出现的上面出现的5 5、3 3和和2、张三以及人是命题分别考虑的对象，、张三以及人是命题分别考虑的对象，称为个体称为个体.命题的考虑对象称为个体个体个体个体(individual)(individual)，它，它是独立存在的事物是独立存在的事物.个体可以是具体的，如个体可以是具体的，如5、3 3和和2 2、张三，也可以是抽

3、象的，如人等张三，也可以是抽象的，如人等.第3页，共68页，编辑于2022年，星期二n n表示特定的、具体的个体称为个体常量(constant),用字母表中靠前的小写英文字母a,b,c,或带下标表示,如在(2)中,可以用a:3,b:2,也可以直接用表示该个体常量的原符号表示,如“3”、“2”、“张三”等.不确定的个体称为个体变元(variable),用字母表中靠后的小写英文字母x,y,z,或带下标表示表示.n n在讨论个体时,通常要指定个体讨论的范围,称为个体域个体域(domain of individuals)或论域(universe),用D表示.如同时讨论(1)和(2)时,第4页，共68页

4、，编辑于2022年，星期二n n可以指定个体域为正整数集合可以指定个体域为正整数集合,也可以是整数集合也可以是整数集合,还可还可以是实数集合等以是实数集合等,要同时讨论要同时讨论(3)(3)和(4),(4),可以指定个体域为所有人组成的集合,也可以是所有动物组成的集合等.指定个体域D后后,所涉及到的个体变元在所给的个体所涉及到的个体变元在所给的个体域中可任意取元素域中可任意取元素.n n个体域可以是有限集合个体域可以是有限集合,可以是无限集合可以是无限集合.我们把世界上所有对象,如所有的动物、所有植物、所有字母、如所有的动物、所有植物、所有字母、所有数字等组成的集合称为全总个体域所有数字等组成

5、的集合称为全总个体域,简称全域简称全域,它它是最大的个体域是最大的个体域.之所以要给出这样的个体域之所以要给出这样的个体域,是因为在是因为在很多问题讨论时都没有指定个体域很多问题讨论时都没有指定个体域,这时就在全总个体这时就在全总个体域中讨论域中讨论,它是默认的个体域它是默认的个体域.第5页，共68页，编辑于2022年，星期二n n2.谓词n n(1)中“是素数”，(3)中“是学生”,(4)中“是要死的”是表示一个个体具有的性质,(2)中“大于”是表示两个个体之间的关系.我们把表示个体性质以及个体之间关系的词称为谓词(predicate).n n表示一个个体性质的谓词称为1元谓词,表示n个个体

6、之间关系的谓词称为n元谓词.第6页，共68页，编辑于2022年，星期二n n一般用大写字母,如P,Q,R,等大写英文字母表示谓词,对于任意的n元谓词,为了把谓词及其元数同时表示出来,象表示n元函数一样,用诸如P(x1,x2,xn)表示.例如,用P(x):x是素数,S(x):x是学生,D(x):x是要死的,G(x,y):x y,R(x,y,z):x 通过y和z等等.n n对于n元谓词P(x1,x2,xn)(n 1),当个体变元取定个体域D中元素后就是一个命题,如G(3,2):3 2,它是关于命题的函数,称为命题函数(propositional function).显然,命题函数不是命题.第7页，

7、共68页，编辑于2022年，星期二n nRemark 谓词的选取与个体域有关.n n例如,对于命题“所有人都是要死的”,若在所有人组成的个体域D中考虑,只需一个谓词D(x):x是要死的；若在全域D中考虑,需要两个谓词P(x):x是人,D(x):x是要死的,其中P 称为特性谓特性谓词词,使用这个特性谓词是将“人”从全域中分离出来.第8页，共68页，编辑于2022年，星期二n n3.量词n n(1)量词的概念n n对于命题函数,如P(x):x是素数,在个体域D为自然数集合N时,对于x的每一个取值,就得到一个命题.n n使成为命题的另一种方法是量化个体变元.常使用的方法有两种：全称量化和存在量化.如

8、D中任意x有P(x),即“任意自然数是素数”,D中存在x有P(x),即“有些自然数是素数”,它们都是命题了.第9页，共68页，编辑于2022年，星期二n n表示个体数量特征的词称为量词量词(quantifier),常用的量词有:全称量词(universal quantifier)和存在量词(existential quantifier).全称量词相当于“任意”、“全部”、“所有”、“每一个”、“一切”等,存在量词相当于“有些”、“某些”、“有的”、“存在”、“至少有一个”等.本书不涉及存在唯一量词.n n现在的量化仅对个体进行,不对谓词进行,因而称为一阶谓词逻辑.第10页，共68页，编辑于20

9、22年，星期二n n(2)量词的使用n n首先注意,量词单独使用是没有意义的,量词的后面一定要跟个体变元,如x,y,x,y,x,x等是一个整体.量词后面所跟的个体变元称为指导变元.例如,n n若将命题函数中的所有个体变元都进行了量化,则得到一个命题,否则不是命题.第11页，共68页，编辑于2022年，星期二n n(3)量词与个体域n n量词是对个体变元进行量化,所给的个体域D至关重要.同一个带量词的命题,如xyG(x,y),而G(x,y):x y,则在自然数集合N中,xyG(x,y)表示没有最小的自然数,是假命题,而在整数集合Z中,xyG(x,y)表示没有最小的整数,是真命题.n na.xP(

10、x)n nb.P(x)n nc.xP(x)n nd.P(a)第12页，共68页，编辑于2022年，星期二n n(4)量词的辖域、约束变元与自由变元n nx(P(x)D(x);n nx(R(x)Q(x).n n量词x或x的作用或管辖的范围称为x或x的作用域或辖域(scope),辖域内的个体变元称为约束变元(bound variable).n n若量词后有括号,则括号里面的部分是其辖域.x(P(x)D(x)?n n若没有括号,则与量词相邻的部分是辖域.第13页，共68页，编辑于2022年，星期二n n不受任何量词约束的变元称为自由变元(free variable).n n(5)约束变元与自由变元的

11、改名(rename)n n对于上小节中的“所有人都是要死的”,也可以y(P(y)Q(y),w(P(w)Q(w).第14页，共68页，编辑于2022年，星期二n n之所以要改名,一是为了避免同一个个体变元既是约束的又是自由的；二是为了方便后面计算谓词公式的范式.n n需要注意的是,在对个体变元改名时,n n(1)将量词辖域中某约束变元及相应的指导变元改成本辖域中未曾出现过的(约束或自由)个体变元,其他个体变元不变；n n(2)某自由变元全部改成同一个与出现的别的所有个体变元不同的个体变元.第15页，共68页，编辑于2022年，星期二n n4.函词n n要把如“张三的父亲”、“两个数的平方和”等表

12、示出来,就要用函数,在谓词逻辑中习惯称为函词(function:函数).n n设个体域D为所有人组成的集合,f(x):x的父亲,则f是D上(即D到D)的1元函数.令D=R,f(x,y)=x2+y2,则f是D上(即D2到D)的2元函数.n n作业 习题4.1 3,5,6,7.第16页，共68页，编辑于2022年，星期二4.2 谓词公式及命题的符号化谓词公式及命题的符号化n n1.谓词公式n n谓词公式(predicate formula)简称公式,同命题公式一样采用的是递归定义.我们通过例子给出谓词公式的定义.n n(1)P(t1,t2,tn),n 0;n nti可以是个体常量、个体变元,也可以

13、是用函词表示的个体常量或个体变元.n n n=0:1,0,p,q,r,(0元谓词?)n n 第17页，共68页，编辑于2022年，星期二n n(2)若若A是谓词公式是谓词公式,则则 A是谓词公式是谓词公式.n nW(a);n nP(x).n n(3)若若A和和B是谓词公式是谓词公式,则则A*B是谓词公式是谓词公式,其中其中*是是2元逻辑联结词元逻辑联结词.n nR(x)Q(x),Q(x)R(x);n nB(x)G(x).第18页，共68页，编辑于2022年，星期二n n(4)若若A是谓词公式是谓词公式,则则 xA和和 xA是谓词公式是谓词公式.n nx(R(x)Q(x),n nx(Q(x)R(

14、x);n nyG(x,y).n n(5)有限次使用上面的有限次使用上面的(1)(2)(3)(4)得到的符号串得到的符号串是仅有的谓词公式是仅有的谓词公式.n n跟命题公式的理解一样,只要是书写正确、意义清楚的符号串或表达式是谓词公式.由于在(1)中规定了命题常量和命题变元是谓词公式,所以命题公式是谓词公式.第19页，共68页，编辑于2022年，星期二n n2.命题的符号化n n与命题逻辑中命题的符号化不同,我们是在谓词逻辑或一阶逻辑中将命题符号化,它要求必须使用谓词.n n在谓词逻辑中将命题符号化,首先找出所给命题中的所有个体常量,并用a,b,c,表示；其次是确定在给定个体域中应该选用的所有谓

15、词,特别注意特性谓词的选取；再其次是确定量词；最后通过找出联结词,将所给命题符号化.第20页，共68页，编辑于2022年，星期二n n在谓词逻辑中将命题符号化是本章重点内容之一.这种形式化方法和技巧在软件测试、软件工程及软件理论等研究中是至关重要的.n n再看下面的例子.n n例4-1 在谓词逻辑中,将下列命题符号化.n n(1)小孙选修模糊数学或人工智能课程.n n(2)米卢教练是年老的但是健壮的.n nSolution(1)用a:小孙,F(x):x选修模糊数学,A(x):x选修人工智能.第21页，共68页，编辑于2022年，星期二n n(2)用b:米卢教练,O(x):x是年老的,S(x):

16、x健壮的.n n例4-2 在谓词逻辑中,将下列命题符号化.n n(1)所有有理数是实数.n n(2)有些实数是有理数.n nSolution 令R(x):x是实数,Q(x):x是有理数,则n n(1)n n(2)n nRemark 在符号化时,与的正确选择.第22页，共68页，编辑于2022年，星期二n n例4-4 在谓词逻辑中,将下列命题符号化.n n(1)没有一个自然数大于等于任意自然数.n n(2)存在唯一的偶素数.n nSolution(1)令N(x):x是自然数,G(x,y):x y.n n(2)令E(x):x是偶数,P(x):x是素数,E(x,y):x=y.第23页，共68页，编辑

17、于2022年，星期二n n例4-5 在谓词逻辑中,将命题“经过两个不同的点有且仅有一条直线”符号化.n nSolution 令P(x):x是点,L(x):x是直线,E(x,y):x=y,R(x,y,z):z通过x和y.第24页，共68页，编辑于2022年，星期二n n例4-6 在谓词逻辑中,将下列命题符号化.n n(1)没有最大的素数.n n(2)并非所有的素数都不是偶数.n n(3)任意大于4的偶数都是两个奇素数之和(这是著名的歌德巴赫猜想：1+1=2).n nRemark 命题的符号化是没有止境的.n n n n作业 习题4.1 2,3,4,5,6.第25页，共68页，编辑于2022年，星

18、期二4.3 谓词公式的解释及类型谓词公式的解释及类型n n4.3.1 谓词公式的解释n n谓词公式的取值(1或0),取决于对其进行的解释或赋值,它类似于对命题公式的指派,其重要性是显而易见的.但与命题公式不同的是,谓词公式的解释有无限多种,每种解释(interpretation)I由下面5部分组成,下面结合谓词公式进行说明.第26页，共68页，编辑于2022年，星期二n n(1)指定个体域D.n n个体域D可以是有限集合,也可以是无限集合.为了方便,取D=1,2.n n(2)对于谓词公式中的命题变元指派其真值.第27页，共68页，编辑于2022年，星期二n n(3)对于谓词公式中的个体常量及其

19、自由变元解释为指定个体域D中的元素.n n谓词公式中的个体常量为a,应解释为D中某个体,如 ,它表示a取D中元素2；对于公式 中的自由变元z,它可以在D中任意取值,但对它进行解释时,还得要任意指定D中一个元素,如 .第28页，共68页，编辑于2022年，星期二n n(4)对于谓词公式中的函词解释为D上的函数.n nf是一个2元函词,可以将解释为如下的D上的2元函数,如：n n也可以写成下述形式:第29页，共68页，编辑于2022年，星期二n n(5)对于谓词公式中的谓词解释为D上的谓词.n nP是1元谓词,Q是2元谓词,对谓词进行解释,有两种方式：n na.根据谓词定义,可以将P解释为P(x)

20、:x是素数,将Q解释为Q(x,y):x y.n nb.根据命题函数的定义:n n上述两种对谓词的解释方式a,b是相同的.第30页，共68页，编辑于2022年，星期二n n谓词公式在任何解释I下都会取得一个真值.在求其真值之前,再回忆一下,4.1节在给定个体域D后关于xP(x)和xP(x)的理解.实际上,若D为有限集合:n nRemember 两个消去量词的逻辑等值式：第31页，共68页，编辑于2022年，星期二第32页，共68页，编辑于2022年，星期二n n例4-8 分别求下列两个谓词公式,n n(1)x(A(x)B(x),n n(2)xA(x)xB(x),n n在给定解释I:D=Z,A(x

21、):x是偶数,B(x):x是奇数下的真值.n nSolution(1)在所给解释I下,x(A(x)B(x)表示“任意整数是偶数或奇数”是真命题.n n(2)在所给解释I下,xA(x)表示“任意整数是偶数”是假命题,xB(x)表示“任意整数是奇数”是假命题,于是xA(x)xB(x)在所给解释I下取假.第33页，共68页，编辑于2022年，星期二n n4.3.2 谓词公式的类型n nDef 在任何解释下均为真的谓词公式称为永真式或有效式(valid).n n下面的几个例子说明,在谓词逻辑中是如何证明一个公式是永真式的.n n例4-9 证明谓词公式xA(x)A(t)永真.n nProof 任意给定个

22、体域D上的解释I,假定在该解释下xA(x)取1,则对于任意d D,A(d)取1,于是A(t)为1.第34页，共68页，编辑于2022年，星期二n n例4-10 证明谓词公式(xA(x)xB(x)(x(A(x)B(x)永真.n nProof 任意给定个体域D上的解释I,假定在该解释下xA(x)xB(x)取1,则xA(x)或xB(x)取1,这时x(A(x)B(x)取1,因此(xA(x)xB(x)(x(A(x)B(x)永真.第35页，共68页，编辑于2022年，星期二n n例4-11 证明谓词公式xyA(x,y)yxA(x,y)永真.n nProof 任意给定个体域D上的解释I,假定在该解释下xyA

23、(x,y)取1,则存在d0 D,对于任意d D,有A(d0,d)为1,所以yxA(x,y)为1.n nRemark 对于命题逻辑中的任何永真式,如(p q)p q,分别用任意谓词公式A,B去全部替换命题变元p,q所得到的谓词公式(A B)A B是永真式.这一点是显然的.第36页，共68页，编辑于2022年，星期二n nDef(P123)至少存在一种解释使其为1的谓词公式称为可满足式可满足式(contingency,satisfactable formula),否则称为不可满足式或或矛盾式或永假永假式式(contradiction).既存在取1的解释,又存在取0的解释的谓词公式称为中性式中性式(

24、neutral formula).n n1936年Church(丘奇)和Turing(图灵)分别独立证明了：中性谓词公式无法在有限步内判定；永真(或永假)谓词公式可在有限步内判定.n n作业 习题4.3 1,2,3,5,6.第37页，共68页，编辑于2022年，星期二4.4 逻辑等值的谓词公式逻辑等值的谓词公式 n n4.4.1 谓词公式等值的定义n n与两个命题公式等值完全类似,有n nDef 4-3(P125)设A和B是谓词公式,若A和B在任何解释下的取值都相同,则称A和B是等值的,记为 A=B.n n显然,A=B的充要条件是谓词公式A B永真.第38页，共68页，编辑于2022年，星期二

25、n n根据命题逻辑中的等值式容易得到一些谓词逻辑中的等值式.n n 例如,对于命题变元p 和q,有p q=p q,因为p q p q永真,所以对于谓词公式A和B,有A B A B,进而有A B=A B.照这种方式,可以得到很多的谓词逻辑中的等值式.第39页，共68页，编辑于2022年，星期二n n4.4.2 基本等值式(remember)n n10个与量词有关谓词逻辑中的基本等值式.n nI.量词转换n n(1)xA(x)=xA(x).n n(2)xA(x)=xA(x).n n例举例说明I(1)(2)成立.n nSolution 令D是全班所有同学组成的集合,A(x):x今天来上课,则“并非每

26、位同学今天都来上课”逻辑等价于“有同学今天没有来上课”,“并非有同学今天来上课”逻辑等价于“每位同学今天都没有来上课”.第40页，共68页，编辑于2022年，星期二n nII.量词辖域的收缩与扩张n n设B中不含自由变元x,则有n n(1)x(A(x)B)=xA(x)B.n n(2)x(A(x)B)=xA(x)B.n n(3)x(A(x)B)=xA(x)B.n n(4)x(A(x)B)=xA(x)B.n n首先要说明的是,A(x)单独看A(x)!含自由变元x,而B中不含自由变元x,但A(x)和B都可能含其他自由变元.第41页，共68页，编辑于2022年，星期二n n就(1)来说,左边x的辖域为

27、A(x)B,右边x的辖域为A(x),从左边到右边量词的辖域收缩了,而从右边到左边量词的辖域扩张了.n n可以粗略地这样理解,因为B中不含自由变元x,所以x及x对B都不起作用.n n(1)的证明?对于任意的个体域D上的解释I,假定x(A(x)B)真,则对于任意dD,A(d)B真,于是A(d)和B都为真,所以xA(x)和B取真,因此xA(x)B真.反过来亦成立.第42页，共68页，编辑于2022年，星期二n n例4-13(P126)证明下列与蕴涵联结词有关的4个等值式,其中B中不含自由变元x.n n(1)x(A(x)B)=xA(x)B.n n(2)x(B A(x)=B xA(x).n n(3)x(

28、A(x)B)=xA(x)B.n n(4)x(B A(x)=B xA(x).n nProof(3)第43页，共68页，编辑于2022年，星期二n nIII.量词分配(?)律n n(1)x(A(x)B(x)=xA(x)xB(x).n n(2)x(A(x)B(x)=xA(x)xB(x).n nRemark n n(1)x(A(x)B(x)xA(x)xB(x).n n(2)x(A(x)B(x)xA(x)xB(x).n n在给定解释I:D=Z,A(x):x是偶数,B(x):x是奇数.How to understand?How to understand?D D=班上同学,A A(x x):):x x会唱

29、歌,B B(x x):):x会跳舞会跳舞.第44页，共68页，编辑于2022年，星期二n nProof (2)任意给定个体域D上的解释I,若x(A(x)B(x)在I下取真,则存在dD,使得A(d)B(d),于是A(d)或B(d)为真,因此xA(x)或xB(x)取真,进而xA(x)xB(x)真.n n反过来亦成立(?).第45页，共68页，编辑于2022年，星期二n nIV.双重量词n n(1)xyA(x,y)=yxA(x,y).n n(2)xyA(x,y)=yxA(x,y).n nRemark xyA(x,y)yxA(x,y).n nD=R;D=N.n nA(x,y):x y.第46页，共68

30、页，编辑于2022年，星期二n n例4-14 xy(A(x)B(y)=xA(x)yB(y).n nProofn n最后要说明的是,等值置换定理在谓词逻辑中仍然成立.n n作业 习题4.4 1,5,7,8.第47页，共68页，编辑于2022年，星期二4.5 谓词公式的前束范式谓词公式的前束范式n n讨论谓词公式的标准形式是很有意义的.n n我们仅讨论谓词公式的前束范式.实际上,在前束范式的基础上,可以进一步得出谓词公式的Skolem范式,进而得出一个谓词公式永真(假)在有限步内可判定的著名结论(Church&Turing).第48页，共68页，编辑于2022年，星期二n n4.5.1 谓词公式的

31、(前+束)范式的定义n nDef 设A是谓词公式,若 n n直观地理解,谓词公式的前束范式是将所有量词放在最前面,去作用整个B.第49页，共68页，编辑于2022年，星期二n n4.5.2 谓词公式的前束范式的计算n n前束范式的计算步骤如下:n nStep1 将逻辑联结词归约到只含,的谓词公式.n n因为在要求记住的谓词逻辑等值式中,没有出现除,外的其他联结词.n nStep2 使用以下两个等值式将否定联结词往里面移:n n(1)xA(x)=xA(x).(2)xA(x)=xA(x).n nStep3 使用等值式将所有量词移到最前面,必要时使用改名技巧.第50页，共68页，编辑于2022年，星

32、期二n n例4-15 求xA(x)xB(x)的前束范式.n nSolutionn nxA(x)xB(x)=x(A(x)B(x).n n例4-16 求xA(x)xB(x)的前束范式.n nSolutionn nxA(x)xB(x)n n=xA(x)xB(x)n n=xA(x)xB(x)n n=x(A(x)B(x).第51页，共68页，编辑于2022年，星期二n n例4-17 求xA(x)xB(x)的前束范式.n nSolutionn nxA(x)xB(x)n n=xA(x)yB(y)n n=x(A(x)yB(y)n n=xy(A(x)B(y)n n采用改名的技巧总可以利用等值式得出前束范式,但要

33、求前束范式中的量词要尽可能地少.第52页，共68页，编辑于2022年，星期二n n例4-18 求xF(y,x)yG(y)的前束范式.n nSolutionn nxF(y,x)yG(y)n n=xF(y,x)yG(y)n n=xF(y,x)yG(y)n n=x(F(y,x)yG(y)n n=x(F(t,x)yG(y)n n=xy(F(t,x)G(y).n n作业 习题4.5 2(1)(2),3(1)(2).第53页，共68页，编辑于2022年，星期二4.6 谓词逻辑中的推理谓词逻辑中的推理n n4.6.1 逻辑蕴涵式n n首先,根据命题逻辑中的逻辑蕴涵式可以产生谓词逻辑的逻辑蕴涵式.如在命题逻辑

34、中有p q,p q,则(p q)p q永真,对于谓词公式A和B,(A B)A B永真,从而有A B,A B.第54页，共68页，编辑于2022年，星期二n n其次,可以得出与量词有关的一些逻辑蕴涵式.n n例4-19 证明xA(x)A(t).n nProof 因为由4.3节例2知,xA(x)A(t)永真.n n例4-20 证明xyA(x,y)yxA(x,y).n nProof 任意给定个体域D上的解释I,假定在该解释下xyA(x,y)取1,则存在d0 D,对于任意d D,有A(d0,d)为1,所以yxA(x,y)为1.因此,xyA(x,y)yxA(x,y)永真.故之.第55页，共68页，编辑于

35、2022年，星期二n n例4-21 证明yxA(x,y)不是xyA(x,y)的有效结论.n nProof D=R,A(x,y):x y+3.n nyxA(x,y)?n nxyA(x,y)?n nxyA(x,y)yxA(x,y)?第56页，共68页，编辑于2022年，星期二n n4.6.2 基本推理规则n n命题逻辑中的基本推理规则可以很方便地推广到谓词逻辑,参见上章3.7节.n n谓词逻辑中有两个非常重要与量词有关的逻辑蕴涵式.n nTheorem 4-1 下列逻辑蕴涵式成立:n n(1)xA(x)xB(x)x(A(x)B(x).n n(2)x(A(x)B(x)xA(x)xB(x).How t

36、o understand?D D=班上同学班上同学,A A(x x):x x会唱歌会唱歌,B(x x):):x会跳舞会跳舞.第57页，共68页，编辑于2022年，星期二n n例4-22(P130)证明或反驳下列结论.n n(1)xA(x)xA(x).n n(2)x(A(x)B(x)xA(x)xB(x).n nSolutionn n(1)D=Z,A(x):x是偶数.n n(2)D=1,2,n nx(A(x)B(x)=1?n nxA(x)xB(x)=0?第58页，共68页，编辑于2022年，星期二n n4.6.3 谓词逻辑的自然推理系统n n谓词逻辑的自然推理系统是命题逻辑的自然推理系统的一种推广

37、.初始符号增加了函词、谓词、量词；谓词公式的形成规则参见4.2节谓词公式的定义；没有公理；基本推理规则增加定理4-1中两个逻辑蕴涵式,以及下述4个与量词有关的基本推理规则.n n我们以最简洁的方式加以介绍.第59页，共68页，编辑于2022年，星期二n nI.US(Universal quantifier Specification)规则:全称量词消去规则n n(1)xA(x)n n(2)A(c)(其中c为个体域中任意个体)n nII.UG(Universal quantifier Generalization)规则:全称量词产生规则n n(1)A(c)(其中为个体域中任意个体)n n(2)x

38、A(x)第60页，共68页，编辑于2022年，星期二n nIII.ES(Existential quantifier Specification)规则:存在量词消去规则n n(1)xA(x)n n(2)A(c)(其中c为个体域中某个体)n nRemark 由xA(x)推出A(c),要确保c与其他自由变元无关.n nIV.EG(Existential quantifier Generalization)规则:存在量词产生规则n n(1)A(c)(其中c为个体域中某个体)n n(2)xA(x)第61页，共68页，编辑于2022年，星期二n n例4-23 证明苏格拉底三段论推理的有效性.n nPro

39、of 用s:苏格拉底,P(x):x是人,D(x):x是要死的,n n(1)P(s)Pn n(2)x(P(x)D(x)Pn n(3)P(s)D(s)US(1)n n(4)D(s)T(1)(3)第62页，共68页，编辑于2022年，星期二n n例4-24 用构造法证明以下推理:n nx(F(x)G(x),xF(x)xG(x).n nProofn n(1)xF(x)P n n(2)F(c)ES(1)n n(3)x(F(x)G(x)P n n(4)F(c)G(c)US(3)n n(5)G(c)T(2)(4)In n(6)xG(x)EG(5)第63页，共68页，编辑于2022年，星期二n nRemark

40、 (1)(2)与(3)(4)的顺序不能颠倒.(2)中F(c)中的c是某个体,(4)中F(c)G(c)中的c本来是任意个体,现取为(2)中出现的c,这是可以的.但反过来就不行.n n避免这种错误的最好方法是象上面的证明过程一样,先消去存在量词,再消去全称量词.第64页，共68页，编辑于2022年，星期二n n例4-25(P131)用构造法证明以下推理:n nx(F(x)H(x),x(G(x)H(x)x(G(x)F(x).n nProof(1)x(F(x)H(x)P n n(2)x(F(x)H(x)T(1)En n(3)F(c)H(c)US(2)n n(4)H(c)F(c)T(3)En n(5)x

41、(G(x)H(x)Pn n(6)G(c)H(c)US(5)n n(7)G(c)F(c)T(4)(6)In n(8)x(G(x)F(x)UG(7)第65页，共68页，编辑于2022年，星期二n n例4-26 设个体域D为所有人组成的集合,在谓词逻辑中符号化下列各命题,并用构造法证明以下推理:每位科学家都是勤奋的,每个勤奋且身体健康的人在事业上都会获得成功,存在身体健康的科学家,所以存在事业获得成功或事业半途而废的人.n nSolution 令Q(x):x是勤奋的,F(x):x是健康的,S(x):x是科学家,C(x):x是事业获得成功的人,F(x):x是事业半途而废的人,则第66页，共68页，编辑

42、于2022年，星期二n n关于多重量词的推理,需要注意的问题比较多.n n例4-27(P132)指出下列推理步骤中的错误.n n(1)xy(x y)Pn n(2)y(c y)US(1)n n(3)c d ES(2)n n(4)x(x d)UG(3)n n(5)yx(x y)EG(4)第67页，共68页，编辑于2022年，星期二n nSolution(3)错.在(2)中的c是个体域中任意个体,实际上是自由变元,当由(2)消去存在量词y时,不能利用ES规则.换句话说,(3)中所得到的d与c密切相关.n n已经有例子表明,xyA(x,y)yxA(x,y)不是永真式.n n作业 习题4.6 711.第68页，共68页，编辑于2022年，星期二