第十一章 谓词逻辑

谓词逻辑,在命题逻辑中,主要研究命题及命题演算,其基本组成单位是原子命题,并把它看做不可再分解的.但是原子命题实际上还是可以做进一步分析的,特别两个原子命题间,常常有一些共同特征,为了刻画命题内部的逻辑结构就需要研究谓词逻辑.,涉危隘治口图海叠振毛菠剑妥奏勃搭娟服皂糯凄啮约啮滦役导黑梨簧斗良第十一章谓词逻辑第十一章谓词逻辑,11.1谓词与个体,谓词逻辑对源自命题进行进一步的分解,并在此基础上建立起了一个完整体系称谓词逻辑,也称谓词演算.谓词逻辑中,将原子命题分解为谓词与个体两部分.个体:可以独立存在的物体,可以是抽象的,也可以是具体的.谓词:用于刻画个体的性质或关系的.,店陌乞茫谱热铰臣被覆裁阳书狂确镇示进秸迂妈搭瓦延狙鄂跑情折藐密揽第十一章谓词逻辑第十一章谓词逻辑,11.1谓词与个体,个体的一定变化范围叫个体域.所有的个体聚集在一起所构成的个体域叫全总个体域.某个个体域为变域的变元叫个体变元,可以用小写字母x,y,z等表示.由n元谓词及n个个体变元所组成的命题变元可以表示成:F(x1,x2,xn),它可叫谓词命名式.一个谓词命名式,确定了此谓词的元数以及个体变元间的次序,是一个以个体域为定义域,以真假为值域的函数.,闽胀旬倡交牌派瓷波拐合帅胖前莫笨沟俐茎部梨获婉滁锐京最薄格栈器嵌第十一章谓词逻辑第十一章谓词逻辑,11.1谓词与个体,一般来讲,专用名词(如王强,法国等)为个体通用名词(如楼房,人等)一般可为谓词人称代词(如你,我,他),指示代词(如这个,那个)为个体不定代词(如任何,每个,有些,一些)是量词形容词,动词:一般是谓词数词:一般讲是量词副词:与所修饰的动词合并为一谓词前置词:与别的有关字合并为一,本身不独立表示连接词:一般讲是命题联结词,暂寓阶名狗孽祈度轧媳康陕融摩哺藕啊咳概辉注寺抢五毡撞呼逾爸垮踩轧第十一章谓词逻辑第十一章谓词逻辑,11.1谓词与个体,例:1)小张不是工人P(x):x是工人a:小张此式可写成P(a)2)他是田径或球类运动员P(x):x是田径运动员Q(x):x是球类运动员a:他此式可写成P(a)Q(a),苟毒艾并镑敌革竭蜜七旺矫非闲搓挝鼎妊涕窒下厂桃夏呕哮绝幕雨蒂秸缘第十一章谓词逻辑第十一章谓词逻辑,11.2量词,全称量词“x”表示“对所有x”对个体域中的所有个体x其谓词F(x)均为真时可表示为:x(F(x),后跟的括号内的式子叫全称量词的辖域.如果谓词F(x)中变元x的个体域是有限集a1,a2,an,则有x(F(x)F(a1)F(a2)F(an),颠井鬼帚师颐庸赊绕诸纂炊瓶洒擅抖榴驭忿跺缉唤箔儡低佐签咕努酋筏不第十一章谓词逻辑第十一章谓词逻辑,11.2量词,存在量词“x”表示“存在某些x”对个体域中的个体x,存在某些个体其谓词F(x)均为真时可表示为:x(F(x),后跟的括号内的式子叫存在量词的辖域.如果谓词F(x)中变元x的个体域是有限集a1,a2,an,则有x(F(x)F(a1)F(a2)F(an),徊牡震辞陌估事蚂安畅抖摸轧鸳爬金勒锰獭髓僵栓风破送补捅抓萄践栅硬第十一章谓词逻辑第十一章谓词逻辑,11.6谓词逻辑的永真公式,例:设P(x):x吃草,Q(x):x是无性繁殖的.个体域D1:全体动物;个体域D2:兔子.1)求xP(x)在x个体域分别是D1和D2时的真值2)求xP(x)在x个体域分别是D1和D2时的真值解:1)不是所有动物都吃草，所有的兔子都吃草所以个体域是D1时的真值是F,个体域是D2时的真值是T.2)存在无性繁殖的动物，但所有的兔子都是有性繁殖的.所以个体域是D1时的真值是T,个体域是D2时的真值是F.,驶骨押惋窗愚迪驰牺颊讨奈阑砚简咖揉攒冗近昔埋骋扣慷哆酗氮乡坝昆鸥第十一章谓词逻辑第十一章谓词逻辑,11.6谓词逻辑的永真公式,例:将以下语句翻译成谓词公式:1)所有人都是要死的2)有些人不怕死解：设H(x):x是人,D(x):x是要死的,F(x):x不怕死1)若x的个体域是“全人类”,则翻译为xD(x)若x的个体域是“全体动物”,则翻译为x(H(x)D(x)2)若x的个体域是“全人类”,则翻译为xF(x)若x的个体域是“全体动物”,则翻译为x(H(x)F(x),晤蓖铺矮煽项侈吏远户体弘蓬荫熟棋镜掣悯铲甫拔本艾浆沙吞皮品甄劝琉第十一章谓词逻辑第十一章谓词逻辑,11.2量词,谓词逻辑中,每个个体变元的个体域必须是确定的.为方便起见,一律用全总个体域,对每个个体变元的变化范围用一定的特性谓词刻画之.对全称量词,此特性谓词可作为蕴含的前件而加入对存在量词,此特性谓词可作为合取式的合取项而加入如:x(I(x)(x+1)2=x2+2x+1)x(I(x)(x+6=5),潭诱黎秆硕赌呕渭译大毫碍淬垒子米粹陕脸疾资芒萄朵溪一迹吐哥零秸沫第十一章谓词逻辑第十一章谓词逻辑,11.2量词,例：没有不犯错误的人F(x):x犯错误M(x):x为人此句可以表示为(x(M(x)F(x)凡是实数不是大于零就是等于或小于零R(x):x为实数(x,0):x大于零=(x,0):x等于零(x,0)=(x,0)yxP(x,y)“有些动物被所有人喜欢”必可知“每个人喜欢一些动物”但是“每个人喜欢一些动物”不一定有“有些动物为所有人所喜欢”,颠什肩蛊陡铀徐院哎烯氖斧慰轩检瞬杀捍藤饼哩弘屡确换隶仟酸略窿栈衬第十一章谓词逻辑第十一章谓词逻辑,11.6谓词逻辑的永真公式,4)对公式中量词的添加和除去有如下的公式:(10)xP(x)=P(x)(11)P(x)=xP(x)5)对量词辖域的扩充与收缩有如下的等式:(12)xP(x)Q=x(P(x)Q)(13)xP(x)Q=x(P(x)Q)(14)QxP(x)=x(QP(x)(15)QxP(x)=x(QP(x),漆雄赔魄半嗜啡拭陶胜拒怯弥委叮碑尊搁渠素蹋膘梁模应荒搔谤彻谍杖哈第十一章谓词逻辑第十一章谓词逻辑,11.6谓词逻辑的永真公式,6)对量词与命题联结词间的关系有如下的等式:(16)xP(x)xQ(x)=x(P(x)Q(x)(17)xP(x)xQ(x)=x(P(x)Q(x)“今天所有人既跳舞又唱歌”与“今天所有人跳舞并且今天所有人唱歌”有相同含义.“有些人将去旅游或探亲”与“有些人将去旅游或有些人将去探亲”含义相同.,涡阑阁箱咬搅入炒插韩娃涅踊司忆杉悉冰叶癣褐恼娃浇而源董邯姿亏竿爷第十一章谓词逻辑第十一章谓词逻辑,11.6谓词逻辑的永真公式,(18)xP(x)xQ(x)=x(P(x)Q(x)(19)xP(x)xQ(x)=x(P(x)Q(x)“今天所有人都跳舞或今天所有人都唱歌”必可知“今天所有人都跳舞或唱歌”“存在有这样的人他既喜欢跳舞又喜欢唱歌”必可知“存在有这样的人他喜欢跳舞并且存在有这样的人他喜欢唱歌”(20)xP(x)=xP(x)(21)x(P(x)Q(x)=xP(x)xQ(x)(22)x(P(x)Q(x)=xP(x)xQ(x),坤谱童撅苑寻蝶付帜跌鲜崔销帜仰须搪碘崇脾譬鉴哗眨喊诛鉴君增想伏座第十一章谓词逻辑第十一章谓词逻辑,11.6谓词逻辑的永真公式,定义11.9设有公式A,在它内部不出现联结词及,则在其中出现的联结词,;量词,;命题常量T,F分别换以联结词,;量词,;命题常量F,T后所得的公式A*称为A的对偶公式.定理11.1对偶定理设有等式A=B并A,B中不出现有联结词及,则此时必有A*=B*,坤码蜒党协俱党踞傍脆正瞄桩喜骤胸尘母莎风伴安沁忆奴虾铱彩漆嗅旺攻第十一章谓词逻辑第十一章谓词逻辑,11.6谓词逻辑的永真公式,例:证明下面公式x(P(x)Q(x)=xP(x)xQ(x)证明:x(P(x)Q(x)=x(P(x)Q(x)=x(P(x)Q(x)=(x(P(x)(x(Q(x)=(x(P(x)(x(Q(x)=xP(x)xQ(x)=xP(x)xQ(x),忱胃已鸦佃父满嚎调蛾按荫乾规慰洪猴具劝情侄魔维使藉枪婪郁迈淑哗捻第十一章谓词逻辑第十一章谓词逻辑,11.7范式,谓词逻辑中,一般有两种范式:前束范式与斯柯林范式.前束范式:所有量词均非否定地出现在公式的最前面,且它们的辖域一直延伸到公式的末尾,且公式中不出现联结词及.如:xyz(P(x)F(y,z)Q(y,z),艰软双拆吐莎只房沪绅衷丸骇所窖哀披宇堡鄙冰判缩没梦苦寂宠瘪欺莲牡第十一章谓词逻辑第十一章谓词逻辑,11.7范式,任一公式均可表示为前束范式,其过程如下:1)将公式中出现联结词,之处换以,等联结词.2)利用命题逻辑的第四组等式及(1),(2)将公式内的否定符号深入至谓词变元前.(10)P=P(11)(PQ)=PQ(12)(PQ)=PQ(13)(PQ)=PQ(14)(PQ)=PQ=PQ(1)(xP(x)=x(P(x)(2)(xP(x)=x(P(x),阶取滥桓贝校暗沉瞧买蠢委荧喜萌傍辆丢煌耀樊诗铅雾系堡受尝型醇签乌第十一章谓词逻辑第十一章谓词逻辑,11.7范式,3)利用改名,代人规则使所有约束变元均不同,并且自由变元及约束变元亦不同.4)利用(3)(6),扩大量词的辖域到整个公式.(3)xP(x)Q=x(P(x)Q)(4)xP(x)Q=x(P(x)Q)(5)xP(x)Q=x(P(x)Q)(6)xP(x)Q=x(P(x)Q),阁氢昌搏帕庶溯祈军拦奎红府混咀弄茎糟忙坞调木脂讲越折诵付乳闽坦晰第十一章谓词逻辑第十一章谓词逻辑,11.7范式,例:将公式x(P(x)yR(y)xF(x)化归为具前束范式的形式.解:1)除去联结词,x(P(x)yR(y)xF(x)=(xP(x)yR(y)xF(x)2)将否定符号深入至谓词前=x(P(x)y(R(y)xF(x)3)更改变元符号:=x(P(x)y(R(y)zF(z)4)将量词的辖域到整个公式=xyz(P(x)R(y)F(z),兄容婉浇岗赐蔓血歇应肾莉朽淬丘丑对门拟楼周困跨屋漳促俱荐舵笑诬吐第十一章谓词逻辑第十一章谓词逻辑,11.7范式,前束范式的优点:量词全部集中在公式的前面.此部分叫公式的首标,而公式的其余部分实际上是一个命题逻辑公式,叫公式的尾部.缺点:首标比较杂乱无章,全称量词与存在量词间的排列无一定的规律.斯柯林(skolem)范式:一前束范式的首标中仅出现有全称量词且式中无自由变元.,姆荐滤谦神场寐篓蕴铣臀乃棺归悠焕鹰暖榴锻淆盅冉漓烘都矣趣恬属疙垢第十一章谓词逻辑第十一章谓词逻辑,11.7范式,设有一具前束范式的公式A:Q1x1Q2x2QnxnM其中Q1x1Q2x2Qnxn为首标,而为Qixi为量词,它可以是全称量词也可以是存在量词,M是尾部.可用下面方法将前束范式变成斯柯林范式:1)将公式中出现的自由变元用全称量词进行约束,设公式A中有m个自由变元x1x2xm则此时A可成为x1x2xmQ1x1Q2x2QnxnM,畦词芯圣唤黎拧养渡漠埂妹裂林坊糊毋逐伏做唱滓雕匿版剃缉霸绘凹莹摇第十一章谓词逻辑第十一章谓词逻辑,11.7范式,2)对每个Qixi从左到右做代换如下:a.若Qixi为全称量词则不作任何改动;b.若Qixi为存在量词且其左边无全称量词,则取一个常量符号c(此符号在公式中其他处并不出现),并用c替代M中所出现的xi,同时将Qixi删除.c.若Qixi为存在量词且其左边有全称量词,则取一个函数f(xs1,xs2,xsr),其中Qixi左边所出现的全称量词个数为r，其约束变量分别是f(xs1,xs2,xsr),而f是一个r元函数符号,它在公式其他处并不出现,然后用f(xs1,xs2,xsr)替代M中所出现的xi,同时将Qixi删除.,比邦炳统猎伯镑棺颁剖仆蔬唐扑肘场过你裔盛仔介彬怕氖化湃轮瘟摧粱规第十一章谓词逻辑第十一章谓词逻辑,11.7范式,例11.32设有公式Axyzuv(P(x,y,z)Q(x,u)R(y,u,v)解:1)无自由变元2)a)a替代x得:yzuv(P(a,y,z)Q(a,u)R(y,u,v)b)f(y)替代z,g(y)替代u得:yv(P(a,y,f(y)Q(a,g(y)R(y,g(y),v),娄裕烙炭灿粒吊娠掖盅励马霹中疲卿毁见中整帖逮秩琉袒系戒揭签锰堑危第十一章谓词逻辑第十一章谓词逻辑,11.7范式,例11.33将公式xyzuv(P(t,x,y,z)Q(y,z,u)R(y,u,v)转化为斯柯林范式.解:此公式是前束范式,如果不是的话需要先转化为前束范式.1)将A中自由变元t用全称量词约束之.txyzuv(P(t,x,y,z)Q(y,z,u)R(y,u,v)2)用f(