ch02谓词逻辑

1、第2章 谓词逻辑,搬鹿斯群栓锨鹊妮害摇筷霞渗藻燎斩僧浮一秋善锹假瓷懊钎殿卸圆设倔鸦ch02谓词逻辑ch02谓词逻辑,在命题逻辑中，我们把命题分解到原子命题为止，认为原子命题是不能再分解的，仅仅研究以原子命题为基本单位的复合命题之间的逻辑关系和推理。 实际上，简单命题还可以进行分解，例如，“王平是大学生”这一简单命题可以分解为主语(王平)和谓语(是大学生)，命题逻辑反映不出这一特点。 其次，如下两个简单命题“王平是大学生”和“李明是大学生”，有一个共同特点是大学生，这一共性在命题逻辑中也表示不出来。因此，有必要推广命题逻辑。,第 2 章 谓词逻辑,刨刘饭矾捕貌件较遮忙盂入旋后哪惩见岂凯圾侩霄杭瘴

2、绒畴裙枉宗车熬舍ch02谓词逻辑ch02谓词逻辑,第三，有些简单而正确的推理过程在命题演算里不能得到证明。例如著名的苏格拉底三段论： “人都是要死的，苏格拉底是人，所以苏格拉底是要死的。” 在命题逻辑中，三个原子命题分别用P，Q，R表示，现在要证明PQR，即证明PQR是重言式，但这在命题逻辑中是不可能的。因此从推理的角度看，也有必要推广命题逻辑。 谓词逻辑就是命题逻辑的自然推广。本章介绍的谓词逻辑内容仅限于一阶谓词逻辑或狭义谓词逻辑，即谓词中的变元不再是谓词变元。,第 2 章 谓词逻辑,耽勇料错荚湿秀挠查厚唤窑馆溢波炸东喂雷搏坪搂熔椿从抖标匡娥搓嚷畏ch02谓词逻辑ch02谓词逻辑,本章内容提

3、要： 1.个体、谓词和量词的概念 2.谓词演算公式 3.谓词演算的等值公式 4.前束范式 5.推理理论 6.谓词逻辑在计算机科学中的应用,第 2 章 谓词逻辑,茸浙展低摊饥央邻抛裳遭蹦贴凑禄贸姆粒伺掘泪孽屡懊佬攻头槛胖座吨吧ch02谓词逻辑ch02谓词逻辑,定义2.1 可以独立存在的物体称为个体，它可以是一个具体的事物，也可以是一个抽象的概念。 如王平，李明，计算机，离散数学，精神等都可以作为个体。 定义2.2 将表示具体的或确定的个体称为个体常元，而将表示抽象的或泛指的（或者说取值不确定的）个体称为个体变元。 个体常元一般用小写英文字母a,b,c或带下标的ai,bi,ci表示，个体变元一般用

4、小写英文字母x,y,z或带下标的xi,yi,zi表示。,2.1 个体 、谓词和量词,2.1.1 个体,诗觅角寨硅炊翻钥真碟菜禄砸毛棵甜拴姑悠薄迁宣旦颓枢睬捆看纱隧疹悟ch02谓词逻辑ch02谓词逻辑,定义2.3 个体变元的取值范围称为个体域或论域，把宇宙间一切事物组成的个体域称为全总个体域。 个体域可以是有穷集合，例如1,2,3,4,5，a,b,c等，也可以是无穷集合，例如自然数集，实数集等。同时约定，本书在论述或推理中如无指明所采用的个体域，则都是使用全总个体域。,2.1 个体 、谓词和量词,2.1.1 个体,惫譬杂劣坍军尚额夕龄冀磊蹋歪痰茶贱泽胚默寡袒饲乾柴彬骏奇养矿戌邢ch02谓词逻辑c

5、h02谓词逻辑,定义2.4 表示单个个体的性质或两个以上个体关系的词叫谓词。 定义2.5 表示具体性质或关系的谓词称为谓词常元，表示抽象的或泛指的性质或关系的谓词称为谓词变元。 无论是谓词常元或变元都用大写英文字母P,Q,R或带下标的Pi,Qi,Ri表示，要根据上下文区分。,2.1 个体 、谓词和量词,2.1.2 谓词,弛梳腔猾凭秒犬越临沈烦竟辣辟卉嘉檀辅王抨气姬歧点哀链代俭蛊磺灌痒ch02谓词逻辑ch02谓词逻辑,定义2.6 由一个谓词(如P)和n个个体变元(如x1，x2，xn)组成的P(x1，x2，xn)，称它为n元原子谓词或n元命题函数，简称n元谓词。 当n=1时，称一元谓词；当n=2时

6、，称为二元谓词，。特别地，当n=0，称为零元谓词，即不带个体变元的谓词为零元谓词。零元谓词是命题，这样命题与谓词就得到了统一，因而可将命题看成特殊的谓词。,2.1 个体 、谓词和量词,2.1.2 谓词,座称震圃拆桓咏溯崩堑藩剧涌牙痊捧雌仓舒伟聂岛失谤誊诀弛王闪内岸争ch02谓词逻辑ch02谓词逻辑,例2.1 分析下列命题的个体与谓词。 （1）5是质数。 解 “5”是个体常元，“是质数”是谓词，记为P。这里的谓词是一元谓词，属于谓词常元。,2.1 个体 、谓词和量词,2.1.2 谓词,计滴宫谆粕探蜘稠减升污邢时站汞痘执止砸套扫巨匀沼广猾曲封寝笑多财ch02谓词逻辑ch02谓词逻辑,（2）张三与李

7、四是同学。 解 “张三”与“李四”是个体常元，分别记为a，b，“与是同学”是谓词，记为Q。这里的谓词是二元谓词，属于谓词常元。 （3）x与y具有关系R。 解 “x”与“y”是个体变元，谓词为R。这里的谓词是二元谓词，属于谓词变元。,2.1 个体 、谓词和量词,2.1.2 谓词,荷借叼屿伐洁函歉骨惨窑恕肮使剔利苞客潮榔形栽妊辽舱需仍哦屠万钝秤ch02谓词逻辑ch02谓词逻辑,例2.2 用个体，谓词表示下列命题。 （1）张华是大学生。 解 令a：张华； S(x)：x是大学生。整个命题可表示为：S(a)。 说明： 若x的个体域为某大学计算机系的全体学生，则S(a)为真； 若x的个体域为某中学的全体学

8、生，则S(a)为假； 若x的个体域为某电影院中的观众，则S(a)真值不确定。所以个体变元在哪些个体域取特定的值，对命题的真值极有影响。,2.1 个体 、谓词和量词,2.1.2 谓词,擅示潍锭斑膛串啃迅钒演咎蜡玩劣共颗愿勋竖跨矽旬促斩摈流塔俺于可韧ch02谓词逻辑ch02谓词逻辑,（2）武汉位于重庆和上海之间。 解 令a：武汉； b：重庆； c：上海； P(x,y,z)：x位于y和z之间。整个命题可表示为P(a,b,c)。 说明：显然P(a,b,c)为真，但P(b,a,c)为假。所以个体变元的顺序影响命题真值，不能随意改动。,2.1 个体 、谓词和量词,2.1.2 谓词,裂租巩叔欠溪忧苫杯洗木瓮

9、琐馆弗迄椿木的卷平讲蒂促欺聘扇脂窝崩寓挠ch02谓词逻辑ch02谓词逻辑,定义2.7 表示个体常元或变元之间数量关系的词叫量词；表示“全部”，“所有的”，“一切的”，“每一个”，“任意的”等数量关系的词叫全称量词，用符号“”表示；表示“存在一些”，“有一些”，“至少有一个”等数量关系的词叫存在量词，用符号“”表示；表示“存在惟一”，“恰有一个”等数量关系的词叫存在惟一量词，用符号“！”表示。,2.1 个体 、谓词和量词,2.1.3 量词,曙众泳掂锡纱种僵熊池镁笺寂欺剑哉响慕任谈敏眠乡挡幅藕征绷藕恍涡芥ch02谓词逻辑ch02谓词逻辑,注意：量词的优先级高于任何联结词，所以(x)P(x1,x2,

10、xn)、(x)P(x1,x2,xn)、可分别写成xP(x1,x2,xn)、xP(x1,x2,xn)，但要注意明确量词的辖域（辖域将在下一节讨论）。,2.1 个体 、谓词和量词,2.1.3 量词,波辣保戮疹促衍罩姑僚妮闰伪温烦命歧倾近蛋玫姜惺孽藉浩铲股抡莉韩存ch02谓词逻辑ch02谓词逻辑,例2.3 符号化下列命题（设个体域为整数集合）。 （1）所有的整数都是有理数。 （2）有些整数是奇数。 （3）存在着惟一的偶素数。 解 （1）令P(x)：x是有理数，则命题可表示为：xP(x)。 （2）令Q(x)：x是奇数，则命题可表示为：xQ(x)。 （3）令R(x)：x是偶数，S(x)：x是素数，则命题

11、可表示为！x(R(x)S(x)。,2.1 个体 、谓词和量词,2.1.3 量词,浆波钡购负曰佳本鼠疤诈在寞洪坪悦池吾可熏摸缝柄跌墨改催懈甘启痔贴ch02谓词逻辑ch02谓词逻辑,定义2.8 若一个谓词P(x)是用来限制个体变元的取值范围，那么称谓词P(x)为特性谓词。 在使用全总个体域时，对个体变化的真正取值范围，用特性谓词加以限制。一般地，对全称量词，将特性谓词作蕴含的前件；对存在量词，将特性谓词作合取项。,2.1 个体 、谓词和量词,2.1.3 量词,菊蜂温远濒柱元侵本菏灿荷窝满饮担憾镣吻矾俘酱梭浆摇肄负禹婚辗欲晶ch02谓词逻辑ch02谓词逻辑,例2.4 用全总个体域对例2.3中的所有命

12、题进行符号化。 解 在例2.3的基础上增加一个特性谓词I(x)：x是整数。则各命题可表示为： （1）x(I(x)P(x) （2）x(I(x)Q(x) （3）！x(I(x)R(x)S(x),2.1 个体 、谓词和量词,2.1.3 量词,旺梳诗雄氮酣乏王妨瞅聪玄聚俘蛮旱珊骆篙络范莫办确饱庇蚁指颠剑诊冻ch02谓词逻辑ch02谓词逻辑,练习 将下列命题符号化。 (1)天下乌鸦一般黑。 (2)任何金属都可以溶解在某种液体中。,2.1 个体 、谓词和量词,2.1.3 量词,绚流恰嗽恿梭奏籽谤智枣井嫉仍忌新簿糊俱桑疚梢些呵岁饼诣华私让凯顾ch02谓词逻辑ch02谓词逻辑,在谓词前加上量词，称为谓词的量化。

13、若一个谓词中所有个体变元都量化了，则该谓词就变成了命题。这是因为在谓词被量化后，可以在整个个体域中考虑命题的真值了。这如同数学中的函数f(x)， 的值是不确定的，但 可确定其值。,2.1 个体 、谓词和量词,2.1.3 量词,趴朽漫芳圾鼻愁降殖乙里媒鞍讥椿啥钩巴贺肘清所腆榜峙来讳扁已驶水发ch02谓词逻辑ch02谓词逻辑,定义2.9 由n元谓词P和n个个体变元x1，x2，xn所构成的不含命题联结词和量词的谓词表达式P(x1，x2，xn)称为谓词逻辑中的原子谓词公式，简称原子公式。 由定义可知，一个命题或一个命题变元也称为原子公式，也就是说，当n=0时，P(x1，x2，xn)为原子命题P。,2.

14、2 谓词 公式,2.2.1 谓词公式与翻译,检遏旭彰汞锗涤骗凳充胰钟毒设锗八培慎汰爆沥撰厦凭找捣餐掉衍托钩猎ch02谓词逻辑ch02谓词逻辑,定义2.10 谓词公式归纳定义如下： （1）原子公式是谓词公式； （2）如果是谓词公式，则也是谓词公式； （3）如果和是谓词公式，则，和也都是谓词公式； （4）如果是谓词公式，x是个体变元，则x(x)，x(x)和！x(x)也都是谓词公式； （5）只有有限次地应用（1）（4）构成的符号串才是谓词公式。,2.2 谓词 公式,2.2.1 谓词公式与翻译,迪堤赞愧利活溜侮尉星砰喀沛波恳臃壬只供考传血肪立愈析浚懊川毡抢润ch02谓词逻辑ch02谓词逻辑,由定义可知

15、，谓词公式是由原子公式、命题联结词、量词以及圆括号按照上述规则组成的一个符号串。因此，命题逻辑中的命题公式是谓词公式的一个特例。 为叙述方便，我们下面讨论只含“x”和“x”的谓词公式，事实上，量词“！x”可以通过量词“x”和“x”来表示。,2.2 谓词 公式,2.2.1 谓词公式与翻译,菠耿彝七砸忌栈业沪杆淆抑蕾矾抖涕铭悲橙登卡嘴套另搞乙当畅忿枪黄尼ch02谓词逻辑ch02谓词逻辑,一般来说，将自然语言翻译成谓词公式主要有以下几个步骤： （1）确定个体域，如无特别说明，一般使用全总个体域； （2）根据个体域，分析命题中的个体、个体性质以及各个个体间的关系，确定谓词； （3）根据表示数量的词确定

16、量词； （4）利用联结词将整个命题符号化。,2.2 谓词 公式,2.2.1 谓词公式与翻译,杏政轰刁造测注茵睹炙颈删淫浊恤逮墙北墒葡渠壤辞窗需橱隶捷在稻外玻ch02谓词逻辑ch02谓词逻辑,例2.5 将下列命题符号化。 （1）教室里有同学在讲话。 解 因为题中没有特别指明个体域，所以这里采用全总个体域。 令S(x)：x是同学， R(x)：x在教室里，T(x)：x在讲话，则命题可符号化为：x(S(x)R(x)T(x)。,2.2 谓词 公式,2.2.1 谓词公式与翻译,甩瘁总锋刑衣平匪秧骚谐庞峙护挤昔肇师蝗翻屏待伏操泪明昌肝淖特堪林ch02谓词逻辑ch02谓词逻辑,（2）在我们班中，并非所有同学都

17、能取得优秀成绩。 解 令S(x)：x是同学， C(x)：x在我们班中， E(x)：x能取得优秀成绩，则命题可符号化为：x(S(x)C(x)E(x)。或者，此命题也可以理解为“在我们班中存在不能取得优秀成绩的同学”，则该命题也可符号化为：x(S(x)C(x)E(x)。,2.2 谓词 公式,2.2.1 谓词公式与翻译,烃傈虱度尚乃痴峻坚熔晤喧颈沏套推栽徊譬栈纽徽瞄窥镐汇彭象锻任鞘胎ch02谓词逻辑ch02谓词逻辑,（3）没有最大的自然数。 解 命题中“没有最大的”显然是对所有的自然数而言，所以可理解为“对任意的自然数x，存在着比x更大的自然数”。令N(x):x是自然数， G(x,y):x大于y，则

18、命题可符号化为：x(N(x)y(N(y)G(y,x)。,2.2 谓词 公式,2.2.1 谓词公式与翻译,潍旁槐恋屠炽鸥沦腺谬迹要推皑锰栓径夏桂圣沪执泰谨阿它皱捂荷萧堵秃ch02谓词逻辑ch02谓词逻辑,（4）今天有雨雪，有些人会跌跤。 解 令R：今天下雨， S：今天下雪，M(x)：x是人，F(x)：x会跌跤，则命题可符号化为：(RS)x(M(x)F(x)。,2.2 谓词 公式,2.2.1 谓词公式与翻译,散揪漏绝帐谭陛哭勃餐武篡忙措碴喻解沏停瞒设毖靶粟伯笑还镊渝哑种盈ch02谓词逻辑ch02谓词逻辑,定义2.11 设是谓词公式，是中连续的符号串且也是谓词公式，则称是的子公式。 例如，=x(P(

19、x)y(Q(y)R(x,y)，=y(Q(y)R(x,y)，则是的子公式。而P(x)y不是谓词公式，因而也不是的子公式。,2.2 谓词 公式,2.2.1 谓词公式与翻译,抨月侧预莎瑶粟赛拘亡诛骚忿孝甫炸芋址橇拍闺拉裂够瘩蓖腰搞叼肚阴沿ch02谓词逻辑ch02谓词逻辑,定义2.11 设是一个谓词公式，x(x)和x(x)是的子公式，则称x(x)与x(x)是的约束部分，x称为是约束出现的。约束出现的变元称为约束变元，不是约束出现的变元称为自由变元。(x)称为是x在中的辖域（或作用域），(x)称为是x在中的辖域。,2.2 谓词 公式,2.2.2 自由变元与约束变元,哥错陕劲置税老舌劣恿巴滚使崇董目诸锗咳

20、设茫奶护晦赶拙拔擎拇的痕杨ch02谓词逻辑ch02谓词逻辑,确定一个量词的辖域即是找出位于该量词之后的相邻接的子公式，具体地讲： 若量词后有括号，则括号内的子公式就是该量词的辖域； 若量词后无括号，则与量词邻接的子公式为该量词的辖域。 另外，当多个量词连续出现，它们之间无括号分隔时，后面的量词在前面量词的辖域之中，且量词对变元的约束与量词的次序有关，一般不能随意调动。,2.2 谓词 公式,2.2.2 自由变元与约束变元,衣肛汽虎迎引蛛容兹培挡纪翰恫缓抿封腮砚掣更馏蓉箱窍款舶诉辨侥烯哇ch02谓词逻辑ch02谓词逻辑,例2.6 指出下列谓词公式中的自由变元和约束变元，并指明量词的辖域。 （1）x

21、(P(x)y(Q(y)R(x,y) （2）x(P(x)Q(y)yR(x,y) 解 （1）量词x的辖域是P(x)y(Q(y)R(x,y)，y的辖域是Q(y)R(x,y)；x和y的所有出现都是约束出现。 （2）量词x的辖域是P(x)Q(y)，这里的x是约束变元，y是自由变元；y的辖域是R(x,y)，这里的x是自由变元，y是约束变元。,2.2 谓词 公式,2.2.2 自由变元与约束变元,绳泄粪谢窘卤蜕堰浪顷亦息谤冤句颅鬼观涎坯双麻绦再余掷铭望鸽狗五哲ch02谓词逻辑ch02谓词逻辑,从上面的例子中可以看出，一个个体变元在谓词公式中既可以自由出现，又可以约束出现。但是，在一个公式里每个变元最好以一种形

22、式出现。这就需要对谓词公式进行改名和代入。 所谓改名就是把一变元改为另一变元，并要求改名后的式子与原式同真假。 所谓代入就是把一变元代以公式(公式的值的变域应与变元的变域相同)，并要求代入后的公式为原式的特例。,2.2 谓词 公式,2.2.2 自由变元与约束变元,牙狰范郁赃宠罚佳凹膏同杉布俐杭蝶凤彰讫肋楔里妖伪缅竿墓愉誊阴恤熔ch02谓词逻辑ch02谓词逻辑,改名的规则如下： (1)改名只对约束变元进行，不对自由变元进行； (2)改名必须处处进行，即对某量词约束的变元改名时，必须对原式中该变元的一切受该量词约束的约束出现改名； (3)对受某量词约束的变元改名时新名决不能与该量词的辖域中的其它自

23、由变元同名； (4)改名前与改名后的约束关系保持不变。 总之，正确的改名结果是每个变元只以一种形式出现，最多只受一个量词约束。,2.2 谓词 公式,2.2.2 自由变元与约束变元,沫锹躇眨佑亦屉哩姆脑侧流沾束狄吟蚂间科秤铣三康蚌逢菊晶硼诉吏虎月ch02谓词逻辑ch02谓词逻辑,例2.7 对公式x(P(x,y)yQ(y)M(x,y)(xR(x)Q(x)中的约束变元进行改名。使每个变元在公式中只以一种形式出现（即约束出现或自由出现）。 解 在该公式中，将P(x,y)和M(x,y)中的约束变元x改名为z，R(x)中的x改名为S，Q(y)中的y改名为t，改名后为： z(P(z,y)tQ(t)M(z,y

24、)(SR(S) Q(x)。,2.2 谓词 公式,2.2.2 自由变元与约束变元,墅铬缅爽洱误菜佩风土导排禾板妆归桓忌矮浪彻琅贿细滇艘赫改李散铁迭ch02谓词逻辑ch02谓词逻辑,代入的规则如下： (1)代入只对自由变元进行； (2)代入必须处处进行，即对某自由变元施行代入时，必须对该自由变元的一切自由出现施行代入； (3)代入前后的约束关系保持不变； (4)代入前先对原式改名，使原式中所有约束变元名与代入式中所有变元名互不相同，然后施行代入； (5)对命题变元和谓词变元也可施行代入，但必须保持代入前后约束关系不变。,2.2 谓词 公式,2.2.2 自由变元与约束变元,汀穷氮通郊呼盈迟碎墙娩腻冰

25、安们铜瞪式产矗众更季霉亭晋绢芒抿铣吃洒ch02谓词逻辑ch02谓词逻辑,例2.8 对公式(yA(x,y)(xB(x,z)C(x,y,z)xzC (x,y,z)中的自由变元进行代入, 使每个变元在公式中只以一种形式出现（即约束出现或自由出现）。 解 将该公式中的自由变元x用t代入，y用u代入，z用v代入，代入后为： (yA(t,y)(xB(x,v)C(t,u,v) xzC(x,u,z)。,2.2 谓词 公式,2.2.2 自由变元与约束变元,片翁碾沛手紧囊伶妈率畴谓周谐扶涨盎辣泞硒呢浑秘狞沥涂嘲谚教尿卓奇ch02谓词逻辑ch02谓词逻辑,定义2.12 设有一谓词公式，其自由个体变元为x1,x2,x

26、h；命题变元为P1,P2,Pk，则我们把表示为： (x1,x2,xh；P1,P2,Pk) 如果对个体域指定以D，对x1,x2,xh在个体域上分别指派以个体a1,a2,ah；对P1,P2,Pk分别指派以P1*,P2*,Pk*(其中Pi*或为0,或为1，i=1,2,k)，则称对作了一个个体域D上的指派，记为(a1,a2,ah； P1*,P2*,Pk*)。如果该值为真，则该指派为的成真指派；如果该值为假，则该指派称为的成假指派。,2.2 谓词 公式,2.2.3 谓词公式的分类,萨佣锤肥把障命衙碉苇囤硷赁穴聂瞻霸对毯也揖贾沽耗僧桶巧恰趣纤廓宅ch02谓词逻辑ch02谓词逻辑,例2.9 求公式=x(P(

27、x)Q(x,y)R的成真指派和成假指派，其中P(x)表示“x是偶数”，Q(x,y)表示“y能整除x”,的个体域D=3,4，R是命题变元。 解,2.2 谓词 公式,2.2.3 谓词公式的分类,情蛮谢黍种获荤泉克撩甸秦职者萌午砍咨依坡皿贰典恬玲阐手阻敷州君吭ch02谓词逻辑ch02谓词逻辑,定义2.13 如果公式对个体域D中任何指派均取得真值，则称为D中的永真式；如果均取得假值，则称为D中的永假式；如果至少有一个指派取得真值，则称为D中的可满足式。,2.2 谓词 公式,2.2.3 谓词公式的分类,杏锚委攻萤雍亲粮璃轨眷稠覆湖绝靶棉岗冠郴痢持算官零坊巫服吝幼痈他ch02谓词逻辑ch02谓词逻辑,例2

28、.10 判断下列公式的类型。 （1）xyG(x-y,x+y)(QQ) （2）G(x-y,x+y) （3）xy(G(x,y)G(x,y)Q 其中x,y的个体域为整数集I，Q为命题变元， G(x,y)表示xy。,2.2 谓词 公式,2.2.3 谓词公式的分类,衬哮匡邦做搅鸵敌诌妻弯亡麓蹲脱看棘戮战官堂茧桂瑚拍傻摔姑沈卤噬程ch02谓词逻辑ch02谓词逻辑,解 (1)无论对Q指派何种命题常元，QQ的真值总为1，而在I中对任意的x，总存在y=1使x-1x+1成立，所以xyG(x-y,x+y)在I中总为真，因此xyG(x-,x+y)(QQ)对任意的指派总为真，是永真式。,2.2 谓词 公式,2.2.3

29、谓词公式的分类,飘壁岔寝龙置历粟崭甭颖幕营帅薛蘸吼供羞忆淆襄绸粥否骨挎桥涉贴笛信ch02谓词逻辑ch02谓词逻辑,（2）因为x-yx+y在I中的真值不确定，当指派x=1,y=1时，02，即x-yx+y取值为真；当指派x=1,y=-1时，20不成立，即x-yx+y取值为假，所以，公式G(x-y,x+y)是可满足式。 （3）无论在个体域I中对x，y指派什么个体常元，G(x,y)G(x,y)总为假，从而xy(G(x,y)G(x,y)Q总为假，所以该公式是永假式。,2.2 谓词 公式,2.2.3 谓词公式的分类,搬持拓虾坷契狸袱盯育杏右吼篓征腔杜唐文肇阐哎丰纂培犀娠莆现俭点教ch02谓词逻辑ch02谓

30、词逻辑,定义2.14 设，为任意两个谓词公式，它们有共同的个体域D，若在D中为永真式，则称公式和在D上等值，记为，称为等值式。,2.3 等值演算,2.3.1 等值式的基本概念,突廷察洪布择娘局役藕堤衫蟹瘸钵侣烧剪贮捂溃崩糟蛀哥靶鼎交善凤法獭ch02谓词逻辑ch02谓词逻辑,1. 由命题公式推广的等值式 利用代入定理将命题演算中的等值公式推广而得到谓词演算中的等值公式。 例如，在命题演算中有公式：PQPQ，可推广而得：P(x)Q(x)P(x)Q(x)， xP(x)xQ(x)xP(x)xQ(x)等等。 利用以上方法，可得一类公式。,2.3 等值演算,2.3.2 常用等值式及等值演算,颜根盘若异要澜

31、阔狠捉柄纷耿赫嚣趴讥穆茫凌惮拭范依拽圃磁拄枯萄甫傣ch02谓词逻辑ch02谓词逻辑,2. 关于量词与联结词的一元谓词等值式 1）消去量词等值式 设个体域为有限集D=a1,a2,an，则有 （1）xA(x)A(a1)A(a2)A(an) （2）xA(x)A(a1)A(a2)A(an) 2）量词转换律 （1）xA(x)xA(x) （2）xA(x)xA(x),2.3 等值演算,2.3.2 常用等值式及等值演算,涸厦啸确傅拂豁俊调沏尽给弛纂荐僻扮摧料霹驴紧袱日恒炯闷鸥津怀碴战ch02谓词逻辑ch02谓词逻辑,3）量词辖域的收缩与扩张律（下述等值式中，变元x不在B中出现） （1）x(A(x)B)xA(x

32、)B （2）x(A(x)B)xA(x)B （3）x(A(x)B)xA(x)B （4）x(BA(x)BxA(x) （5）x(A(x)B)xA(x)B （6）x(A(x)B)xA(x)B （7）x(A(x)B)xA(x)B （8）x(BA(x)BxA(x),2.3 等值演算,2.3.2 常用等值式及等值演算,诗杂替妻寇氦士胎叭琴藕勤夫甲咐亦浚供郸已典则缎渠捣忿防纹呕斤例隶ch02谓词逻辑ch02谓词逻辑,4）量词分配律 （1）x(A(x)B(x)xA(x)xB(x) （2）x(A(x)B(x)xA(x)xB(x) 要特别注意的是，量词分配律中的“”和“”联结词不要记错。,2.3 等值演算,2.3.

33、2 常用等值式及等值演算,巫赊窜赠僻溜句箩豢咙兜娄猴岂蹋嘲吼粗银友椒超峪膘修弄磐栽醋亢拨挂ch02谓词逻辑ch02谓词逻辑,例2.11 证明x(A(x)B(x)xA(x)xB(x) 证明 令个体域为D，设在任一指派下，左式T，则在D中存在一个个体c使得A(c)B(c)T，从而A(c)T或B(c)T，因此有xA(x)T或xB(x)T，所以xA(x)xB(x)T。 反之，设在任一指派下，右式T，则xA(x)T或xB(x)T，即在D中存在两个个体c，d使得A(c)T或B(d)T，从而在D中存在一个个体c或d（不妨设c）使得A(c)B(c)T，所以x(A(x)B(x)T。 由以上两方面知等值式成立。,

34、2.3 等值演算,2.3.2 常用等值式及等值演算,妹釉纷旨篇够件蛀粹酉董桂陌在宅镁眶低丑祈潮枉臻酸馅斟删闪触堡事绞ch02谓词逻辑ch02谓词逻辑,思考 判断以下两个式子是否成立？ (1)xA(x)xB(x)x(A(x)B(x) (2)xA(x)xB(x)x(A(x)B(x),2.3 等值演算,2.3.2 常用等值式及等值演算,缀蒲弱新励肾戳防需抱摸褥照录跑梁爸蒂狙辐巡僳瑶凌骏戮卑昌髓僻烈须ch02谓词逻辑ch02谓词逻辑,3. 关于二元谓词的等值式 在上一节我们曾指出，量词出现的次序直接关系到命题的意义，但也有例外，相同量词间的次序是可以任意调动的，不同量词间的次序则不能随意调动。因此有下

35、面两个等值式成立。 （1）xy(A(x,y)yx(A(x,y) （2）xy(A(x,y)yx(A(x,y),2.3 等值演算,2.3.2 常用等值式及等值演算,洒匀严曳胆例靠枣枚欣疯甩弘兢岩跺鸭饥腋呀豌窃暂针到粕拧吼柜顶碉口ch02谓词逻辑ch02谓词逻辑,思考 判断式子xyP(x,y)yxP(x,y)是否成立？,2.3 等值演算,2.3.2 常用等值式及等值演算,蔗丢磅佣垦韧董钝艺釉皱凤碧稀畴鄂箭鹊灭畏揽保侩霜淘纷振纱镁痴大蒂ch02谓词逻辑ch02谓词逻辑,例2.12 证明下列等值式。 （1）x(A(x)B(x)xA(x)xB(x) 证明 x(A(x)B(x) x(A(x)B(x) xA(

36、x)xB(x) xA(x)xB(x) xA(x)xB(x),2.3 等值演算,2.3.2 常用等值式及等值演算,咆鹿面燃秤雌厢堂耘击锣肿栗瞩饰扑执彤墓旬雇茎泌芝疤疙司瘩婶沿武少ch02谓词逻辑ch02谓词逻辑,（2）xy(P(x)Q(y)xP(x)yQ(y) 证明 xy(P(x)Q(y) xy(P(x)Q(y) x(P(x)yQ(y) xP(x)yQ(y) xP(x)yQ(y) xP(x)yQ(y),2.3 等值演算,2.3.2 常用等值式及等值演算,粥霖兆演飘它槛挫征映绘宪臭能婪狙宴察赌慈烧河犬陪悉蜀猩挤禹磨泊咕ch02谓词逻辑ch02谓词逻辑,定义2.16 一个谓词公式，如果量词均在全式的

37、开头，它们的辖域延伸到整个公式的末尾，则称该公式为前束范式，其标准形式为： L1x1L2x2Lnxn 其中：Li(i=1,2,n)为或，xi为个体变元，为不含量词的谓词公式。 例如，yuv(A(x,y)B(u,y)R(u,v)是前束范式。,2.4 范式,2.4.1 前束范式,锯恫镍怠限递税练相加亲炙厩贪蔚从飞殊认情莱匣妄睦羽问琴伴弯血耕棺ch02谓词逻辑ch02谓词逻辑,定理2.3（前束范式存在定理） 任意一个谓词公式都存在着与之等值的前束范式。 下面给出将谓词公式化为前束范式的步骤： (1)消去联结词，及多余的量词； (2)将联结词向内深入，使之只作用于原子谓词公式； (3)利用改名或代入规

38、则使所有约束变元的符号均不同，并且自由变元与约束变元的符号也不同； (4)利用量词辖域的扩张与收缩律，扩大量词的辖域至整个公式。,2.4 范式,2.4.1 前束范式,尾抵壹稍型棋梅谤卷涯且饲溜月缨救晋问包蚁廓绷屹无姓斯抉谭缅耽炕淑ch02谓词逻辑ch02谓词逻辑,例2.16 将公式xy(z(P(x,z)P(y,z)zQ(x,y,z)化为前束范式。 解 xy(z(P(x,z)P(y,z)zQ(x,y,z) xy(z(P(x,z)P(y,z)zQ(x,y,z) （消去） xy(z(P(x,z)P(y,z)zQ(x,y,z) （深入） xy(z(P(x,z)P(y,z)uQ(x,y,u) （改名）

39、xyzu(P(x,z)P(y,z)Q(x,y,u) （量词前移）,2.4 范式,2.4.1 前束范式,疮恳轮漳致治昧蓬补趴开餐挂栈扬船良搞阜贩删肌臃萎方斋吐荆厨基容努ch02谓词逻辑ch02谓词逻辑,定义2.17 一个公式，如果具有形式： L1x1L2x2Lnxn(11121l1)(21222l2)(m1m2mlm) 则称该式为前束合取范式。 一个公式，如果具有形式： L1x1L2x2Lnxn(11121l1)(21222l2)(m1m2mlm) 则称该式为前束析取范式。 其中：Li(i=1,2,n)为或，xi为 个体变元，ij为原子谓词公式或其否定。,2.4 范式,2.4.1 前束范式,桂辈

40、碉娠辰帅夕驱戊从誉卡猿群斩三尾违分傲双笔式工骄讽拧垢曼壶嘎玉ch02谓词逻辑ch02谓词逻辑,定理2.4 任意一个谓词公式都存在着与之等值的前束合取（析取）范式。 将一个谓词公式化为前束合取范式或前束析取范式时，只需在前面求前束范式的（1）（4）四个步骤基础上再增加一个步骤： （5）利用分配律将公式化为前束合取范式或前束析取范式。,2.4 范式,2.4.1 前束范式,蒜悔加铣乡议助累肿哲岔凌招嵌缉悼副嘻佰晚凝彪短恍戚周梁序阂孰罩逾ch02谓词逻辑ch02谓词逻辑,例2.14 将公式x(yA(x,y)xy(B(x,y)y (A(y,x)B(x,y)化为前束合取范式和前束析取范式。,2.4 范式,

41、2.4.1 前束范式,扔脐匪壤熏处限任辅兽葱愈旷涛柱寅蠢囤韵吉避辖舵迟圆企佣谦少兰同旷ch02谓词逻辑ch02谓词逻辑,前束范式的优点是全部量词集中在公式前面，其缺点是全称量词与存在量词的排列无一定规则，这样当把一个公式化为前束范式时，其表达形式会显现多种情形，不便应用。1920年司柯伦(Skolem)提出对前束范式中量词出现的次序给出规定：每个存在量词均在全称量词之前。按此规定得到的范式形式，称为司柯伦范式。显然，任意一个谓词公式均可化为司柯伦范式。它的优点是：全公式按顺序可分为三部分，公式的所有存在量词、所有全称量词和辖域。这给谓词逻辑的研究提供了一定的方便。 例如，xyz(P(x,y)(

42、Q(y,z)R(x)是司柯伦范式。,2.4 范式,2.4.2 司柯伦范式,函炙摸其沃任特宪蝎崎君搀桅谆常诀刽薄宪戴瑞纯醛昆虚蜜期藕敞巳昂慑ch02谓词逻辑ch02谓词逻辑,1. 由命题逻辑推理定律推广而来的谓词逻辑推理定律 利用代入定理将命题逻辑中的推理定律推广而得到谓词逻辑中的推理定律。 如在命题逻辑中有公式： ， 可推广而得： xA(x)yB(y)xA(x)， xA(x)xA(x)yB(y) 等等。,2.5 谓词逻辑的推理演算,2.5.1 推理定律,封癸烹也拜兑义哼束每喷拒鹃遭蔗岳概钓阎蘑约洒隆烂肖惟暇匪沮瞄盈壕ch02谓词逻辑ch02谓词逻辑,2. 由基本等值式生成的推理定律 2.3节给

43、出的等值式中的每个等值式可生成两个推理定律。例如， xA(x)xA(x)，xA(x)xA(x) 和xA(x)xA(x), xA(x)xA(x) 等等。,2.5 谓词逻辑的推理演算,2.5.1 推理定律,皖纪锹楔劳栏瞪防居吁皂砌羔品虫佃苯粉跳翁羔示憎槛廉柯幻盔浩瑚献纵ch02谓词逻辑ch02谓词逻辑,3. 一些特有的重要推理定律 （1）xA(x)xB(x)x(A(x)B(x) （2）x(A(x)B(x)xA(x)xB(x) （3）x(A(x)B(x)xA(x)xB(x) （4）x(A(x)B(x)xA(x)xB(x) 等等。,2.5 谓词逻辑的推理演算,2.5.1 推理定律,捷割拐墒吻硕蹈缀据喧

44、介绵愿窘蜀塑塔止涛鼠柠球睡希傈漂韦街对轧房霄ch02谓词逻辑ch02谓词逻辑,1. 全称量词消去规则（US） （1）xA(x)A(y) 或 （2）xA(x)A(c) 2. 全称量词引入规则（UG） A(y)xA(x) 3. 存在量词消去规则（ES） xA(x)A(c) 4. 存在量词引入规则（EG） A(c)xA(x),2.5 谓词逻辑的推理演算,2.5.2 推理规则,亭暖绘求著僚粉卒吕葬家疫势朝凄吮粪摧溶瓦苦佛曲坑漂篷廓鹊敷皿扇技ch02谓词逻辑ch02谓词逻辑,在谓词逻辑中，常用的推理方法有两种：直接证法和间接证法，其内容与命题逻辑中的类似。 1直接证法 例2.15 证明苏格拉底三段论：“

45、人都是要死的，苏格拉底是人，所以苏格拉底是要死的。”,2.5 谓词逻辑的推理演算,2.5.3 推理方法,购感昧碉欠卉舰层罢热额唯馋络凋胞爵蔷腕钡扳罕旋野嘘舀恤瞪默霖优虽ch02谓词逻辑ch02谓词逻辑,解 个体域取全总个体域，令F(x)：x是人，G(x)：x是要死的，a:苏格拉底，则 前提：x(F(x)G(x), F(a) 结论：G(a) 推理形式：x(F(x)G(x), F(a)G(a) (1) x(F(x)G(x) P (2) F(a)G(a) US,(1) (3) F(a) P (4) G(a) T,I,(2),(3),2.5 谓词逻辑的推理演算,2.5.3 推理方法,缚核犁之呐浪谱憨苯

46、彰谤低伟雄了桔霸治倘庭秀剖冕银蚜浦辆袒逢烁绽甩ch02谓词逻辑ch02谓词逻辑,例2.18 指出下列推导中的错误，并加以改正。 (1) xP(x) P (2) P(c) ES,(1) (3) xQ(x) P (4) Q(c) ES,(2) 解 第二次使用存在量词消去规则时，所指定的特定个体应该是证明序列以前公式中没有出现过的，正确的推理是： (1) xP(x) P (2) P(c) ES,(1) (3) xQ(x) P (4) Q(d) ES,(2),2.5 谓词逻辑的推理演算,2.5.3 推理方法,遍立汝沮契平俱拽或烯蚤丰燕鉴臀澄把裤柜鸡佐霸纹酝羡吱瀑岛氰儿率莹ch02谓词逻辑ch02谓词逻

47、辑,2. 间接证法 间接证法主要有两种，反证法和CP规则。 1）反证法 例2.19 将下列推理符号化并给出形式证明: 晚会上所有人都唱歌或跳舞了，因此或者所有人都唱歌了，或者有些人跳舞了。（个体域为参加晚会的人）,2.5 谓词逻辑的推理演算,2.5.3 推理方法,效获技焉其贷屋允物氮泞郧粳赐嗣怯缠外肠缎弦娘貌您彦盾缄抨掉貌睹尾ch02谓词逻辑ch02谓词逻辑,解 设P(x)：x唱歌了，Q(x)：x跳舞了，则 前提：x(P(x)Q(x) 结论：xP(x)xQ(x) 推理形式：x(P(x)Q(x)xP(x)xQ(x) (1) (xP(x)xQ(x) P(附加) (2) xP(x)xQ(x) R,E

48、,(1) (3) xP(x) T,I,(2) (4) P(a) ES,(3) (5) xQ(x) T,I,(2) (6) Q(a) US,(5) (7) x(P(x)Q(x) P (8) P(a)Q(a) US,(7) (9) Q(a) T,I,(4),(8) (10) Q(a)Q(a) T,I,(6),(9),矛盾 因此，假设不成立，原推理形式正确。,2.5 谓词逻辑的推理演算,2.5.3 推理方法,底灶远姐受肌抹圆劝生氟购窥糯驱饺慰迢衡操刻诌略户旨恰挽妆捷六谁滇ch02谓词逻辑ch02谓词逻辑,2）CP规则 例2.20 将下列推理符号化并给出形式证明: 每一个大学生不是文科生就是理科生；有的大学生是优等生；小张不是文科生但他是优等生。因此，如果小张是大学生，他就是理科生。,2.5 谓词逻辑的推理演算,2.5.3 推理方法,剪贡俊增矗棋子酗释够揽它揭欺邯怨郊局极他距逾构搁奄捍玉狐饭佯良伞ch02谓词逻辑ch02谓词逻辑,解 个体域取全总个体域，设P(x)：x是大学生，Q(x)：x是文科生，S(x)：x是