1、第二章第二章 谓词逻辑谓词逻辑n1谓词概念与表示谓词概念与表示n2命题函数与量词命题函数与量词n3谓词公式与翻译谓词公式与翻译n4变元约束变元约束n5谓词演算等价式与蕴含式谓词演算等价式与蕴含式n6前束范式前束范式n7谓词演算推理理论谓词演算推理理论第1页1 谓词概念与表示谓词概念与表示在研究命题逻辑中,原子命题是命题演算中最基本单位,在研究命题逻辑中,原子命题是命题演算中最基本单位,不再对原子命题进行分解不再对原子命题进行分解.这么会产生二大缺点:这么会产生二大缺点:(1)不能研究命题结构,成份和内部逻辑特征;)不能研究命题结构,成份和内部逻辑特征;(2)也不可能表示二个原子命题所含有共同特
2、征,甚至)也不可能表示二个原子命题所含有共同特征,甚至在命题逻辑中无法处理一些简单又常见推理过程。在命题逻辑中无法处理一些简单又常见推理过程。例:苏格拉底论证是正确,但不能用命题逻辑推理规则推导例:苏格拉底论证是正确,但不能用命题逻辑推理规则推导出来。出来。“全部人总是要死。全部人总是要死。A“苏格拉底是人。苏格拉底是人。B“所以苏格拉底是要死。所以苏格拉底是要死。”C第2页1 谓词概念与表示1.谓词:谓词:定义定义:用以刻划客体性质或关系即是:用以刻划客体性质或关系即是谓词谓词。我们可把原子命题分解为二部分:我们可把原子命题分解为二部分:主语(名词,代词)和谓语(动词)。主语(名词,代词)和
3、谓语(动词)。例:张华是学生,李明是学生。则可把它表示成:例:张华是学生,李明是学生。则可把它表示成:H:表示表示“是学生是学生”,j:表示表示“张华张华”,m:表示表示“李明李明”,则可用以下符号表示上述二个命题:则可用以下符号表示上述二个命题:H(j),H(m)。H作为作为“谓词谓词”用大写英文字母表示,用大写英文字母表示,j,m为主语,为主语,称为称为“客体客体”或称或称“个体个体”。客体普通用小写英文。客体普通用小写英文字母表示。字母表示。第3页1 谓词概念与表示(1)若谓词字母联络着一个客体,则称作)若谓词字母联络着一个客体,则称作一元谓词一元谓词;若谓;若谓词字母联络着二个客体,则
4、称作词字母联络着二个客体,则称作二元谓词二元谓词;若谓词字母联;若谓词字母联络着络着n个客体,则称作个客体,则称作n元谓词元谓词。(2)客体次序必须是有要求。)客体次序必须是有要求。例:河南省例:河南省北接北接河北省。河北省。nLb写成二元谓词为:写成二元谓词为:L(n,b),但不能写成,但不能写成L(b,n)。第4页2 命题函数与量词命题函数与量词1.命题函数命题函数客体在谓词表示式中能够是任意名词。客体在谓词表示式中能够是任意名词。例:例:C“总是要死。总是要死。”j:张三;:张三;t:老虎;:老虎;e:桌子。:桌子。则则C(j),C(t),C(e)均表示了命题。均表示了命题。在上面例子中
5、,在上面例子中,C:表示:表示“总是要死总是要死”;x:表示变元(客:表示变元(客体变元),则体变元),则C(x)表示表示“x总是要死总是要死”,则称,则称C(x)为命题函为命题函数。数。定义定义由一个谓词字母和一些非空客体变元集合所组成表由一个谓词字母和一些非空客体变元集合所组成表示式,称为简单示式,称为简单命题函数命题函数。第5页2 命题函数与量词命题函数与量词讨论定义:(a)当简单命题函数仅有一个客体变元时,称为一元简单命题函数;(b)若用任何客体去取代客体变元之后,则命题函数就变为命题;(c)命题函数中客体变元取值范围称为个体域(叙述域)。例:P(x)表示x是质数。这是一个命题函数。其
6、值取决于个体域。个体域(叙述域,客体域):用特定集合表示客体变元取值范围。第6页2 命题函数与量词命题函数与量词个体域给定形式有二种:详细给定。如:j,e,t全总个体域任意域:将各种个体域综合在一起作为叙述范围域称全总个体域。命题函数能够转变为命题,有两种方法:a)将x取定一个值。如:P(4),P(5)b)将谓词量化。如:xP(x),xP(x)第7页2 命题函数与量词命题函数与量词2.2.量词量词(1 1)全称量词“”为全称量词符号,读作“对于全部”,“对任一个”,“对一切”。例:“这里全部都是苹果”可写成:xA(x)或(x)A(x)几个形式读法:xP(x):“对全部x,x是”;xP(x):“
7、对全部x,x不是”;xP(x):“并不是对全部x,x是”;xP(x):“并不是全部x,x不是”。第8页2 命题函数与量词命题函数与量词例:将“对于全部x和任何y,假如x高于y,那么y不高于x”写成命题表示形式。解:x y(G(x,y)G(y,x)G(x,y):x高于y(2 2)存在量词“”为存在量词符号,读作“存在一个”,“对于一些”,“对于一些”,“最少存在一个”,“这里存在着这么”等等。“”表示式读法:x A(x):存在一个x,使x是;xA(x):存在一个x,使x不是;x A(x):不存在一个x,使x是;xA(x):不存在一个x,使x不是。第9页2 命题函数与量词命题函数与量词例:(a)存
8、在一个人;(b)某个人很聪明;(c)一些实数是有理数 将(a),(b),(c)写成命题。解:要求:M(x):x是人;C(x):x是很聪明;R(x):x是实数(特征谓词)Q(x):x是有理数。则 (a)x M(x);(b)x(M(x)C(x);(c)x(R(x)Q(x)。(3 3)量化命题真值:决定于给定个体域给定个体域:a1an以a1an中每一个代入xP(x)P(a1)P(an)xQ(x)Q(a1)Q(an)第10页*个体域不一样,则表示同一命题值不一样。Q(x):x5-1,0,3-3,6,215,30 xQ(x)T F FxQ(x)T T F2 命题函数与量词命题函数与量词第11页*个体域不
9、一样,则表示同一命题谓词公式形式不一样。例:“全部人必死。”令D(x):x是要死。下面给出不一样个体域来讨论:()个体域为:人类,则可写成xD(x);()个体域为任意域(全总个体域),则人必须首先从任意域中分离出来,设M(x),x是人,称M(x)为特征谓词。命题可写成 x(M(x)D(x)注注:若若一一个个谓谓词词P(x)P(x)是是用用来来限限制制个个体体变变元元取取值值范范围围,那那么称谓词么称谓词P(x)P(x)为为特征谓词特征谓词。2 命题函数与量词命题函数与量词第12页*对于同一个体域,用不一样量词时,特征谓词加入方法不一样。对于全称量词,其特征谓词以前件方式加入;对于存在量词,其特
10、征谓词以合取形式加入。2 命题函数与量词命题函数与量词第13页比如比如(1 1)每个学生都要参加考试。每个学生都要参加考试。令令P(x)P(x):x x是学生,是学生,Q(x):xQ(x):x要参加考试。可符要参加考试。可符号化为号化为:x x(P(x)P(x)Q(x)Q(x)(2 2)一些人是聪明。)一些人是聪明。M(x):xM(x):x是人,是人,R(x)R(x):x x是聪明。是聪明。可符号化为可符号化为:x x(M(x)R(y)M(x)R(y).2 命题函数与量词命题函数与量词第14页3谓词公式与翻译谓词公式与翻译1.1.谓词公式原子谓词公式:不出现命题联结词和量词谓词命名式称为原子谓
11、词公式,并用P(x1xn)来表示。(P称为n元谓词,x1xn称为客体变元),当n=0时称为零元谓词公式。定义(谓词公式归纳法定义)原子谓词公式是谓词公式;若A是谓词公式,则A也是谓词公式;若A,B都是谓词公式,则(AB),(AB),(AB),(AB)都是谓词公式;若A是谓词公式,x是任何变元,则xA,xA也都是谓词公式;只有按-所求得那些公式才是谓词公式。第15页3谓词公式与翻译谓词公式与翻译2、翻译、翻译n 普通来说,将自然语言翻译成谓词公式主要有以普通来说,将自然语言翻译成谓词公式主要有以下几个步骤:下几个步骤:n(1)确定个体域,如无尤其说明,普通使用全总个)确定个体域,如无尤其说明,普
12、通使用全总个体域;体域;n(2)依据个体域,分析命题中个体、个体性质以及)依据个体域,分析命题中个体、个体性质以及各个个体间关系,确定谓词;各个个体间关系,确定谓词;n(3)依据表示数量词确定量词;假如使用全总个体)依据表示数量词确定量词;假如使用全总个体域,则要加入特征谓词。域,则要加入特征谓词。n(4)利用联结词将整个命题符号化。)利用联结词将整个命题符号化。第16页3谓词公式与翻译谓词公式与翻译例1:任何整数或是正,或是负。解:设:I(x):x是整数;R1(x):x是正数;R2(x):x是负数。此句可写成:x(I(x)(R1(x)R2(x)。例2:试将苏格拉底论证符号化:“全部人总是要死
13、。因为苏格拉底是人,所以苏格拉底是要死。”解:设M(x):x是人;D(x):x是要死;M(s):苏格拉底是人;D(s):苏格拉底是要死。第17页3谓词公式与翻译谓词公式与翻译写成符号形式:写成符号形式:x(M(x)x(M(x)D(x)D(x),M(s)M(s)D(s)D(s)例例3 3:“没有不犯错人。没有不犯错人。”解:设解:设F(x)F(x)为为“x x犯错误犯错误”,M(x)M(x)为为“x x是人是人”(特征谓词)。(特征谓词)。可把此命题写成:可把此命题写成:(x(M(x)x(M(x)F(x)F(x)x(M(x)x(M(x)F(x)F(x)注:因为对个体描述性质刻划深度不一样,可翻译
14、注:因为对个体描述性质刻划深度不一样,可翻译成不一样形式谓词公式。成不一样形式谓词公式。第18页以下两例用以下两例用函数观点函数观点了解谓词逻辑翻译:了解谓词逻辑翻译:以下两例中个体域都是全人类以下两例中个体域都是全人类.例例1 1:“x是y外祖父”“x是z父亲且z是y母亲”F(x,z):x是z父亲;M(z,y):z是y母亲。则谓词公式可写成:z(F(x,z)M(z,y)。例例2 2 翻译翻译张强父亲是教授张强父亲是教授.解解:答案为答案为:P(f(z)P(f(z),其中其中,P(x):x,P(x):x是教授是教授;f(x):xf(x):x父亲;父亲;z:z:张强张强.3谓词公式与翻译谓词公式
15、与翻译第19页 例例3 3 将以下命题符号化。将以下命题符号化。(1 1)教室里有同学在讲话。教室里有同学在讲话。解解因为题中没有尤其指明个体域,所以这里采因为题中没有尤其指明个体域,所以这里采取全总个体域。取全总个体域。令令S(x)S(x):x x是同学,是同学,R(x)R(x):x x在教室里,在教室里,T(x)T(x):x x在讲话,则命题可符号化为:在讲话,则命题可符号化为:x(S(x)x(S(x)R(x)R(x)T(x)T(x)。3谓词公式与翻译谓词公式与翻译第20页 (2 2)在在我我们们班班中中,并并非非全全部部同同学学都都能能取取得得优优异成绩。异成绩。解解 令令S(x)S(x
16、):x x是是同同学学,C(x)C(x):x x在在我我们们班班中中,E(x)E(x):x x能能取取得得优优异异成成绩绩,则则命命题题可可符符号号化化为为:x(S(x)x(S(x)C(x)C(x)E(x)E(x)。或或者者,此此命命题题也也能能够够了了解解为为“在在我我们们班班中中存存在在不不能能取取得得优优异异成成绩绩同同学学”,则则该该命命题题也也可可符符号号化化为:为:x(S(x)x(S(x)C(x)C(x)E(x)E(x)。3谓词公式与翻译谓词公式与翻译第21页 (3 3)没有最大自然数。)没有最大自然数。解解命题中命题中“没有最大没有最大”显然是对全部自然数显然是对全部自然数而言,
17、所以可了解为而言,所以可了解为“对任意自然数对任意自然数x x,存在,存在着比着比x x更大自然数更大自然数”。令。令N(x):xN(x):x是自然数,是自然数,G(y,x):yG(y,x):y大于大于x x,则命题可符号化为:,则命题可符号化为:x(N(x)x(N(x)y(N(y)y(N(y)G(y,x)G(y,x)。3谓词公式与翻译谓词公式与翻译第22页4变元约束变元约束1.辖域:紧接在量词后面括号内谓词公式,叫做对辖域:紧接在量词后面括号内谓词公式,叫做对应量词作用域或辖域。应量词作用域或辖域。例:例:xP(x),x(P(x)Q(x)。若量词后括号内为原子谓词公式,则括号能够若量词后括号
18、内为原子谓词公式,则括号能够省去。省去。2.自由变元与约束变元自由变元与约束变元约束变元:在量词辖域内,且与量词下标相同变约束变元:在量词辖域内,且与量词下标相同变元。元。自由变元:当且仅当不受量词约束。自由变元:当且仅当不受量词约束。例:例:xP(x,y),x(P(x)y(P(x,y)。第23页辖域辖域,自由变元与约束变元自由变元与约束变元举例举例 在在 xP(x)xP(x)Q(x)Q(x)中中,x x辖域是辖域是P(x)P(x);在在 y y(C(y)C(y)x x(T(x)T(x)u uQ(Q(x,u)x,u)中中,u u辖域是辖域是Q(Q(x,u)x,u);x x辖域是辖域是T(x)T
19、(x)u uQ(Q(x,u)x,u);y y辖域是辖域是 C(y)C(y)x x(T(x)T(x)u uQ(Q(x,u)x,u).4变元约束变元约束第24页例:例:x y(P(x,y)Q(y,z)(x)p(x,y),下面描述下面描述中错误是()中错误是()A.(x)辖域是(辖域是(y)()(P(x,y)Q(y,z))Bz是该谓词公式约束变元是该谓词公式约束变元C.(x)辖域是)辖域是P(x,y)D.x是该谓词公式约束变元是该谓词公式约束变元4变元约束变元约束第25页4变元约束变元约束3.3.约束变元更名规则任何谓词公式对约束变元能够更名。我们认为xP(x,y)和zP(z,y)是一等价谓词公式,
20、不过需注意,不能用同一变元去表示同一谓词公式中二个变元。比如:yP(y,y)是不正确。下面介绍约束变元更名规则:(a)在更名中要把公式中全部相同约束变元全部同时改掉;(b)更名时所用变元符号在量词辖域内未出现。第26页4变元约束变元约束例:xP(x)yR(x,y)可改写成xP(x)zR(x,z),但不能改成xP(x)xR(x,x),xR(x,x)中前面x原为自由变元,现在变为约束变元了。4.4.区分是命题还是命题函数方法(a)若在谓词公式中出现有自由变元,则该公式为命题函数;(b)若在谓词公式中变元均为约束变元,则该公式为命题。例:xP(x,y,z)是二元命题函数,yxP(x,y,z)是一元命
21、题函数,而谓词公式中假如没有自由变元出现,则该公式是一个命题。第27页4变元约束变元约束5.自由变元代入规则:对公式中自由变元更改叫做自由变元代入规则:对公式中自由变元更改叫做代入。代入。(a)对公式中出现该自由变元每一处进行代入。对公式中出现该自由变元每一处进行代入。(b)用以代入变元与原公式中全部变元名称不能相用以代入变元与原公式中全部变元名称不能相同。同。第28页4变元约束变元约束6.量词对变元约束,往往与量词次序相关。量词对变元约束,往往与量词次序相关。若谓词公式中出现多个量词,则按照从左到右次序读若谓词公式中出现多个量词,则按照从左到右次序读出,不能颠倒次序。出,不能颠倒次序。例:例
22、:y x(xy-2)表示任何表示任何y均存在均存在x,使得,使得xy-2。例:设个体域是整数集,则以下命题真值为真是(例:设个体域是整数集,则以下命题真值为真是(c)A y x(xy=1)B x y(xy0)C x y(xy=y2)D y x(xy=x2)第29页5谓词演算等价式与蕴含式谓词演算等价式与蕴含式1、基本定义基本定义:谓词公式等价,谓词公式等价,永真,永假,可满足永真,永假,可满足定义定义A,B为二个谓词公式,E为它们共同个体域,若对A和B任一组变元进行赋值,使得A和B值相同,则称A和B在个体域E上是互为等价,记为AB或 EB定义定义给定谓词公式A,E是A个体域。若给A中客体变元指
23、派E中每一个客体所得命题值均为真,则称A在E中是永真。若E为任意域则称A是永真。A第30页5谓词演算谓词演算 等价式与蕴含式等价式与蕴含式定义定义给定谓词公式给定谓词公式A,E是是A个体域。若给个体域。若给A中中客体变元指派客体变元指派E中每一个客体所得命题值均为假,中每一个客体所得命题值均为假,则称则称A在在E中是永假。若中是永假。若E为任意域则称为任意域则称A是永假。是永假。定义定义给定谓词公式给定谓词公式A,E是是A个体域。若给个体域。若给A中中客体变元指派客体变元指派E中每一个客体,在中每一个客体,在E中存在一些客中存在一些客体,使得指派后真值为体,使得指派后真值为“T”,则,则A称是
24、可满足。称是可满足。第31页5谓词演算等价式与蕴含式谓词演算等价式与蕴含式2.不含量词谓词公式永真蕴含式和等价公式不含量词谓词公式永真蕴含式和等价公式 只要用只要用原子谓词公式原子谓词公式去代替第一章中永真蕴含式去代替第一章中永真蕴含式和等价公式中和等价公式中原子命题变元原子命题变元,则在第一章中永真,则在第一章中永真蕴含式和等价公式均可变成谓词演算中永真蕴含蕴含式和等价公式均可变成谓词演算中永真蕴含式和等价公式:式和等价公式:第32页5谓词演算等价式与蕴含式谓词演算等价式与蕴含式命题逻辑命题逻辑谓词逻辑谓词逻辑(x)(x)(x)(x)(x).(x)(x)(x)(x)(x)(x)(x)(x)(
25、x)(x).第33页5谓词演算等价式与蕴含式谓词演算等价式与蕴含式3.含有量词等价式和永真蕴含式含有量词等价式和永真蕴含式设个体域为:设个体域为:S=a1,a2,an,我们有:,我们有:xA(x)A(a1)A(a2)A(an)xA(x)A(a1)A(a2)A(an)上例说明:上例说明:若个体域是有限,则可省掉量词。若个体域是有限,则可省掉量词。第34页5谓词演算等价式与蕴含式谓词演算等价式与蕴含式下面分类介绍在谓词公式中含有量词等价式和永真蕴含下面分类介绍在谓词公式中含有量词等价式和永真蕴含式。式。(1)量词转换律:)量词转换律:xP(x)xP(x)xP(x)xP(x)下面证实:下面证实:xP
26、(x)xP(x)设个体域为:设个体域为:S=a1,a2,an xP(x)(P(a1)P(a2)P(an)P(a1)P(a2)P(an)xP(x)第35页5谓词演算等价式与蕴含式谓词演算等价式与蕴含式下面举例说明量化命题和非量化命题差异下面举例说明量化命题和非量化命题差异:否定形式不一样否定形式不一样例:例:否定以下命题:否定以下命题:(a)上海是一个小城镇上海是一个小城镇A(s)(b)每一个自然数都是偶数每一个自然数都是偶数 x(N(x)E(x)上述二命题否定为:上述二命题否定为:(a)上海不是一个小城镇上海不是一个小城镇A(s)(b)有一些自然数不是偶数有一些自然数不是偶数 x(N(x)E(
27、x)x(N(x)E(x)x(N(x)E(x)x(N(x)E(x)结论:对于非量化命题否定只需将动词否定,而对于量化命结论:对于非量化命题否定只需将动词否定,而对于量化命题否定不但对动词进行否定而且对量词同时进行否定,其题否定不但对动词进行否定而且对量词同时进行否定,其方法是:方法是:x否定变为否定变为 x,x否定变为否定变为 x。第36页量词转换律推广应用量词转换律推广应用:把把深入到谓词公式深入到谓词公式前面去方法。前面去方法。x yP(x,y,z)x yP(x,y,z)x yP(x,y,z)5谓词演算等价式与蕴含式谓词演算等价式与蕴含式第37页5谓词演算等价式与蕴含式谓词演算等价式与蕴含式
28、(2)量词辖域扩张及其收缩律量词辖域扩张及其收缩律 xA(x)P x(A(x)P)xA(x)P x(A(x)P)xA(x)P x(A(x)P)xA(x)P x(A(x)P)P为不含有变元任何谓词公式为不含有变元任何谓词公式第38页5谓词演算等价式与蕴含式谓词演算等价式与蕴含式证实:证实:xA(x)P x(A(x)P)设个体域为:设个体域为:S=a1,a2,an xA(x)P(A(a1)A(a2)A(an)P(A(a1)P)(A(a2)P)(A(an)P)x(A(x)P)第39页5谓词演算等价式与蕴含式谓词演算等价式与蕴含式从上述几个等价公式能够推出以下等价式:从上述几个等价公式能够推出以下等价
29、式:xA(x)B x(A(x)B)xA(x)B x(A(x)B)A xB(x)x(AB(x)A xB(x)x(AB(x)证实证实:xA(x)B x(A(x)B)xA(x)B xA(x)B xA(x)B x(A(x)B)x(A(x)B)第40页5谓词演算等价式与蕴含式谓词演算等价式与蕴含式(3)量词分配律)量词分配律 x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)第41页5谓词演算等价式与蕴含式谓词演算等
30、价式与蕴含式证实证实(1)x(A(x)B(x)xA(x)xB(x)设个体域为:设个体域为:S=a1,a2,an x(A(x)B(x)(A(a1)B(a1).(A(an)B(an)(A(a1)A(an)(B(a1)B(an)xA(x)xB(x)(2)xA(x)xB(x)x(A(x)B(x)证证 xAxA(x)(x)x xB(x)B(x)(xAxA(x)(x)x xB(x)B(x)蕴涵表示蕴涵表示 x xA A(x)(x)x xB(x)B(x)量词否定量词否定 x(x(A A(x)(x)B(x)B(x)量词分配量词分配 x(Ax(A(x)(x)B(x)B(x)蕴涵表示蕴涵表示第42页5谓词演算等价
31、式与蕴含式谓词演算等价式与蕴含式(4)量词转换以及添加和除去永真蕴含式与等价式)量词转换以及添加和除去永真蕴含式与等价式 xP(x)xP(x)xPP xPP(P为不含为不含x变元)变元)第43页5谓词演算等价式与蕴含式谓词演算等价式与蕴含式(5)含有多个量词)含有多个量词永真蕴含式与等价式永真蕴含式与等价式:()量词出现次序直接关系到命题含义:)量词出现次序直接关系到命题含义:例:设例:设A(x,y)表示表示x和和y同姓,论域同姓,论域x是甲村人,是甲村人,论域论域y是乙村人,则:是乙村人,则:x yA(x,y)表示对于甲村全部人,乙村都有些人表示对于甲村全部人,乙村都有些人和他同姓。和他同姓
32、。y xA(x,y)表示存在一个乙村人,甲村全部人和表示存在一个乙村人,甲村全部人和他同姓。他同姓。第44页5谓词演算等价式与蕴含式谓词演算等价式与蕴含式()在含有多个量词谓词公式中)在含有多个量词谓词公式中,x y,x y位位置是能够改变置是能够改变,且不影响命题真值。且不影响命题真值。即即相同量词间次序是能够任意调动,不一样量相同量词间次序是能够任意调动,不一样量词间次序则不能随意调动。所以有:词间次序则不能随意调动。所以有:x yP(x,y)y xP(x,y)x yP(x,y)y xP(x,y)第45页6 前束范式前束范式定义定义一个公式,假如量词均非否定地在全式开头,它们作用域延伸到整
33、个公式末尾,则称此公式叫前束范式。例:xyz(Q(x,y)R(z)(前束范式)定理定理 任何一个谓词公式均和一个前束范式等价。转换方法:利用量词转换把深入到原子谓词公式前,利用约束变元更名规则,利用量词辖域扩张收缩律,把量词移到全式最前面,这么一定可得到等价前束范式。第46页6 前束范式前束范式例:例:xP(x)R(x)yP(y)R(x)y(P(y)R(x)例:把例:把 xP(x)xQ(x)变成前束范式。变成前束范式。xP(x)xQ(x)xP(x)xQ(x)xP(x)xQ(x)x(P(x)Q(x)第47页7 谓词演算推理理论谓词演算推理理论下面分别介绍四个推理规则下面分别介绍四个推理规则(1)
34、全称指定规则()全称指定规则(US规则)。规则)。假如对个体域中全部客体假如对个体域中全部客体x,A(x)成立,则对个体成立,则对个体域中某个任意客体域中某个任意客体c,A(c)成立。该规则表示成:成立。该规则表示成:xA(x)A(c)(x,c 个体域个体域)(2)全称推广规则()全称推广规则(UG规则)规则)假如能够证实对个体域中每一个客体假如能够证实对个体域中每一个客体c,命题,命题A(c)都成立,则可得到结论都成立,则可得到结论 xA(x)成立。成立。该规则表示该规则表示成:成:A(c)xA(x)第48页7 谓词演算推理理论谓词演算推理理论(3)存在指定规则()存在指定规则(ES规则)规
35、则)假如对于个体域中一些客体假如对于个体域中一些客体A(x)成立,则必有某成立,则必有某个特定客体个特定客体c,使,使A(c)成立。该规则表示成:成立。该规则表示成:xA(x)A(c)(4)存在推广规则()存在推广规则(EG规则)规则)假如对个体域中某个特定客体假如对个体域中某个特定客体c,有,有A(c)成立,成立,则在个体域中,必存在则在个体域中,必存在x,使,使A(x)成立。成立。该规则表该规则表示成:示成:A(c)xA(x)第49页7 谓词演算推理理论谓词演算推理理论2推论规则及使用说明推论规则及使用说明命题逻辑中命题逻辑中P,T,CP规则和直接、间接证实法,都规则和直接、间接证实法,都
36、能够引用到谓词逻辑推论规则中来,不过要注意能够引用到谓词逻辑推论规则中来,不过要注意对量词做适当处理对量词做适当处理.其处理方法是:用其处理方法是:用US,ES在推导中去掉量词,用在推导中去掉量词,用UG,EG使结论量化(加上量词)。使结论量化(加上量词)。第50页7谓词演算推理理论谓词演算推理理论规则使用说明:规则使用说明:(1)在使用)在使用ES,US时时,谓词公式必须是前束范式谓词公式必须是前束范式(2)推导中连续使用)推导中连续使用US规则可用相同变元规则可用相同变元 xP(x)P(y),xQ(x)Q(y)(3)推导中既用)推导中既用ES,又用,又用US,则必须先用则必须先用ES,后用
37、,后用US方可取相同变元,反之不行。方可取相同变元,反之不行。xP(x)P(y)xQ(x)Q(y)(4)推导中连续使用)推导中连续使用ES规则时,使用一次更改一个变规则时,使用一次更改一个变元。元。第51页例:例:x个体域为个体域为I=整数整数,P(x):x是偶数,是偶数,Q(x):x是是奇数。奇数。xP(x)P(c)xQ(x)Q(c)上述写法是错误,应更改为:上述写法是错误,应更改为:xP(x)P(c)xQ(x)Q(d)7谓词演算推理理论谓词演算推理理论第52页 在在谓词逻辑谓词逻辑中,中,惯惯用推理方法有用推理方法有两种:直接两种:直接证证法和法和间间接接证证法,其内容法,其内容与命与命题
38、逻辑题逻辑中中类类似。似。n直接证法直接证法 例例 证实苏证实苏格拉底三段格拉底三段论论:“人都是人都是要死,要死,苏苏格拉底是人,所以格拉底是人,所以苏苏格拉底格拉底是要死。是要死。”7谓词演算推理理论谓词演算推理理论第53页7谓词演算推理理论谓词演算推理理论例:证实苏格拉底论证例:证实苏格拉底论证(x)(M(x)D(x)M(s)D(s)(1)x(M(x)D(x)P(2)M(s)D(s)US(1)(3)M(s)P(4)D(s)T(2)(3)I第54页Cp规则证实规则证实例:证例:证:x(P(x)Q(x)xP(x)xQ(x)(1)xP(x)附加前提附加前提(2)x(P(x)Q(x)P(3)P(
39、c)Q(c)ES(2)(4)P(c)US(1)(5)Q(c)T(3)(4)I(6)xQ(x)EG(5)(7)xP(x)xQ(x)CP7谓词演算推理理论谓词演算推理理论第55页7谓词演算推理理论谓词演算推理理论间接间接证法证法例:证实:例:证实:x(P(x)Q(x),xP(x)xQ(x)(1)xQ(x)附加前提附加前提(2)xQ(x)T(1)E(3)Q(c)US(2)(4)xP(x)P(5)P(c)US(4)(6)P(c)Q(c)T(3)(5)I(7)x(P(x)Q(x)UG(6)(8)x(P(x)Q(x)P(9)x(P(x)Q(x)x(P(x)Q(x)T(7)(8)I(10)F第56页n例例
40、指出以下推导中错误,并加以更正。指出以下推导中错误,并加以更正。(1)(1)xP(x)xP(x)P P (2)P(c)(2)P(c)ES(1)ES(1)(3)(3)xQ(x)xQ(x)P P (4)Q(c)(4)Q(c)ES(2)ES(2)解解 第二次使用存在量词消去规则时,所指定特定第二次使用存在量词消去规则时,所指定特定个体应该是证实序列以前公式中没有出现过,正确个体应该是证实序列以前公式中没有出现过,正确推理是:推理是:(1)(1)xP(x)xP(x)P P (2)P(c)(2)P(c)ES(1)ES(1)(3)(3)xQ(x)xQ(x)P P (4)Q(d)(4)Q(d)ES(2)ES
41、(2)7谓词演算推理理论谓词演算推理理论第57页例例 将以下推理符号化并给出形式证实将以下推理符号化并给出形式证实:每一个大学生不是文科生就是理科生;有大学生是每一个大学生不是文科生就是理科生;有大学生是优等生;小张不是文科生但他是优等生。所以,假如小优等生;小张不是文科生但他是优等生。所以,假如小张是大学生,他就是理科生。张是大学生,他就是理科生。n解解个体域取全总个体域,设个体域取全总个体域,设P(x):x是大学生,是大学生,Q(x):x是文科生,是文科生,S(x):x是理科生,是理科生,T(x):x是是优等生,优等生,c:小张,则:小张,则前提:前提:x(P(x)(Q(x)S(x),x(
42、P(x)T(x),Q(c)T(c)结论:结论:P(c)S(c)7谓词演算推理理论谓词演算推理理论第58页推理形式:推理形式:x(P(x)(Q(x)S(x),x(P(x)T(x),Q(c)T(c)P(c)S(c)(1)P(c)附加前提附加前提(2)x(P(x)(Q(x)S(x)P(3)P(c)(Q(c)S(c)US(2)(4)Q(c)S(c)T(1)(3)I(5)Q(c)T(c)P(6)Q(c)T(5)I(7)S(c)T(4)(6)I(8)P(c)S(c)CP7谓词演算推理理论谓词演算推理理论第59页例例 将以下推理符号化并给出形式证实将以下推理符号化并给出形式证实:晚会上全部些人都唱歌或跳舞了
43、,所以或者全部些人晚会上全部些人都唱歌或跳舞了,所以或者全部些人都唱歌了,或者有些人跳舞了。(个体域为参加晚会都唱歌了,或者有些人跳舞了。(个体域为参加晚会人)人)解解设设P(x):x唱歌了,唱歌了,Q(x):x跳舞了,则跳舞了,则前提:前提:x(P(x)Q(x)结论:结论:xP(x)xQ(x)7谓词演算推理理论谓词演算推理理论第60页推理形式:推理形式:x(P(x)Q(x)xP(x)xQ(x)(1)(xP(x)xQ(x)附加前提附加前提(2)x P(x)x Q(x)T(1)E(3)x P(x)T(2)I(4)P(a)ES(3)(5)x Q(x)T(2)I(6)Q(a)US(5)(7)x(P(
44、x)Q(x)P(8)P(a)Q(a)US(7)(9)Q(a)T(4)(8)I(10)Q(a)Q(a)矛盾矛盾T(6)(9)I所以,假设不成立,原推理形式正确。所以,假设不成立,原推理形式正确。7谓词演算推理理论谓词演算推理理论第61页7谓词演算推理理论谓词演算推理理论例:二个量词推理比较复杂:xP(x)x(P(x)Q(x)R(x),xP(x),xQ(x)x y(R(x)R(y)(1)xP(x)P(2)P(w)ES(3)P(w)Q(w)T(4)xP(x)x(P(x)Q(x)R(x)P(5)x(P(x)Q(x)R(x)T第62页7谓词演算推理理论谓词演算推理理论(6)P(w)Q(w)R(w)US(
45、7)R(w)T(8)xR(x)EG(9)xQ(x)P(10)Q(z)ES(11)P(z)Q(z)T(12)P(z)Q(z)R(z)US第63页7谓词演算推理理论谓词演算推理理论(13)R(z)T(14)yR(y)EG(15)xR(x)yR(y)T(16)x y(R(x)R(y)T 三个量词推理过程更为复杂第64页第二章小结学习第二章要注意以下几点:(1)同一个命题在不一样个体域内可能有不一样符号化形式,同时也可能有不一样真值,因而在将一个命题符号化之前,必须搞清个体域。(2)在将命题符号化时,要尤其注意量词与联结词搭配。经常情况是全称量词与蕴含词搭配,存在量词与合取词搭配。所以有下面两种形式公
46、式:x(A(x)B(x)x(A(x)B(x)(3)记住主要等价式。会用约束变元和自由变元换名规则进行等价演算,求出给定公式前束范式。(4)在谓词演算推理证实中,要尤其注意US,UG,ES,EG规则成立条件。第65页例题选讲例1.符号化以下命题:(1)没有不犯错误人;(2)发光不都是金子;(3)在南京高校学习学生,未必都是南京籍学生。解:(1)设M(x):x是人。Q(x):x犯错误。本题符号化为:x(M(x)Q(x)或者:(x)(M(x)Q(x)(2)设L(x):x是发光东西。G(x):x是金子。x(L(x)G(x)或 x(L(x)G(x)第66页例题选讲(3)设S(x):x是南京高校学习学生。F(x):x是南京籍学生。则 x(S(x)F(x)本题也可加深刻划:S(x):x是学生。L(x):x在学习。H(x):x在南京高校。G(x):x是南京籍人。则(x)(S(x)L(x)H(x)G(x)S(x)第67页