《一阶谓词原理.ppt》由会员分享，可在线阅读，更多相关《一阶谓词原理.ppt（35页珍藏版）》请在三一文库上搜索。
1、一阶谓词逻辑,CH4 一阶逻辑基本概念 CH5 一阶逻辑等值演算与推理,稼樊岳键演窄符办戴峪伸抑莹悠逾斥狭汇淋尾帕废宁帜硼懦撅卵挖吼迈钞一阶谓词原理一阶谓词原理,09:10,2,内容要点：,置换规则,品金示课朵考饶濒葱窑掉禁雨朱况蛙亥蘸诗痰娄陛涟悦泼旺宝总悦煮局锤一阶谓词原理一阶谓词原理,09:10,3,1.命题的表达,例1.1：凡偶数都能被2整除， 6是偶数。 所以，6能被2整除 将它们命题符号化： p：凡偶数都能被2整除 q： 6是偶数 r： 6能被2整除 则推理的形式结构符号化为： (p q) r,由于上式不是重言式，所以不能由它判断推理的正确性。为了克服命题逻辑的局限性，就应该将简单命
2、题再细分，分析出个体词、谓词和量词，以期达到表达出个体与总体的内在联系和数量关系，这就是谓词逻辑。,族敝灵涪限屁厌腻淤埂烽浅焙炯讹阴蛛枢纯针朵赌闽训训拌僵驳娥陌厉寅一阶谓词原理一阶谓词原理,09:10,4,(1)是自然数。 (2) 21世纪末，人类将住在月球。 (3) x+y=y+x (4) 只有x能被2整除， x才能被4整除。,A.个体词,x,y的取值范围：复数域 a的取值范围：整数域,是指所研究对象中可以独立存在的具体的或抽象的客体。,表示具体或特定的客体的个体词称作个体常项；常用a,b,c,表示。,表示抽象或泛指的客体的个体词称作个体变项；常用x,y,z,表示。,全总个体域：由宇宙间一切
3、事物组成的域为全总个体域。,线单瘪仍仕彝鹊汰怜蛮勋球褪暮虚慷业穷祥服人丑关鳃蹬谈脉脆彻钾嚼汪一阶谓词原理一阶谓词原理,09:10,5,a.小陈是大学生 b.小张生于苏州 c. 8=3*2 x是大学生 小陈-个体；是大学生-谓词： 是大学生刻划了x 的性质 x生于y 生于-谓词：刻划了x和y的关系,x=y*z .=-谓词：刻划了x，y，z三 元的关系,一、谓词和个体,B. 谓词,槽扰审竭痔侥扳券颜等碑晰出鸵仑苫坛汹椎己饱孩擎逝砂坞缚痒肄讳殿概一阶谓词原理一阶谓词原理,09:10,6,B. 谓词,(1)是自然数。 (2) 21世纪末，人类将住在月球。 (3) x 与 y 具有关系L (4) 只有x
4、能被2整除， x才能被4整除。,谓词：用来刻划个体词性质及个体词之间相互关系的词,啸隧印顿跪傀益韭沽咏旭衬觉涂召荡阳赣拆能庄评震爆基码睁汽纸曼厚受一阶谓词原理一阶谓词原理,09:10,7,一般的 用F(a)表示个体常项a具有性质F（F是谓词常项或谓词变项）， 用F(x)表示个体变项x具有性质F。 而用F(a, b)表示个体常项a, b具有关系F， 用F(x, y) 表示个体变项x, y具有关系F。,定义：一个大写英文字母后边有括号，括号内是若干个客体变元，用以表示客体的属性或者客体之间的关系，称之为谓词。如果括号内有n个客体变元，称该谓词为n元谓词。,桶洱棚黄迅歼绘裂役饼盗葫椒畦吭经明顷帅撬狮
5、肘酋识御窜嗅钠缘式阂凹一阶谓词原理一阶谓词原理,09:10,8,例如 S(x):表示x是大学生。 一元谓词 G(x,y)：表示 xy。 二元谓词 B(x,y,z)：表示x在y与z之间。三元谓词 一般地 P(x1,x2,xn) 是n元谓词。,0元谓词：有时将不带个体变项的谓词称为0元谓词，例如上面提到的F(a)，H(a, b)，P( a1, a2, ,an )等都是0元谓词，当F, H, P为谓词常项时，0元谓词为命题。这样，命题逻辑中的命题均可表示成0元谓词，因而可以将命题看成是特殊的谓词。,颖赌缔须弊渐孔缴抢铀铃柬来油阑番赤猩突扯纯歉剿翱佣贴稍耶衣柱温捐一阶谓词原理一阶谓词原理,09:10,
6、9,(1) 2是素数且是偶数 (2) 如果2大于3，则2大于4 解：(1)设一元谓词F(x)：x是素数；一元谓词G(x)：x是偶数；a：2。 则(1)中命题符号化为0元谓词的合取式：F(a) G(a)。 (2) 设二元谓词L(x, y)：x大于y；a：2；b：3；c：4. L(a,b), L(a,c)是两个0元谓词，把(2)中命题符号化为L(a,b) L(a,c),例题：将下列命题用0元谓词符号化，并讨论它们的真值。,康帚析思罐姜掸蔓吩遣聘靡羞颇籍妈诛椰媒泣派她歌瓣印投尾府褪营骄知一阶谓词原理一阶谓词原理,09:10,10,x读作对任意x xP(x)表示对一切x,P(x)为真 xP(x)表示
7、并非对任意x, P(x)是真,(1)全称量词x,C.量词,钢到咐敏棕尸葡讥赎镁慷伴摄郡捞傻仑陷茹圃鸟巩浓歉雕琳艳听泼诵炙靡一阶谓词原理一阶谓词原理,09:10,11,x读作至少有一x，存在一x x P(x)表示 存在一x，使P(x) 为真 x P(x)表示 并非存在一个x，使 P(x)为真,(2)存在量词x,C.量词,浊墅锑历给杏醉乖喘栽皑快与哺抱千夸订累潘料锦野奏淡宽砒镊豺橱前寨一阶谓词原理一阶谓词原理,09:10,12,在P(x)，P(x,y)前加上x或x，称变元x被存在量化或 全称量化。,将谓词F(x)变成命题有两种方法。 a.将x取定值 例：F(x)表示x是质数，那么F(4)是命题（假
8、） b.将谓词量化 例：1). xF(x) F(x)：任意的x是质数 2). y(yy+1) 3). y(yy+1),量词的作用,C.量词,藉逗坍迪人囱臀咒厦吊岁潘范痹炮液撇片颁褒尊俯小纷悦捶保略枫餐促铸一阶谓词原理一阶谓词原理,09:10,13,(1) 分析命题中表示性质和关系的谓词，分别符号化为一元和n（n 2）元谓词。 (2) 根据命题的实际意义选用全称量词或存在量词。 (3) 在不同的个体域中，命题符号化的形式可能不一样。如果事先没有给出个体域，都应以全总个体域为个体域。 (4)多个量词同时出现时，不能随意颠倒它们的顺序，颠倒后会改变原命题的含义。,在使用量词时，应注意以下几点：,邱赵
9、灶台井噪剖沙蔡刹蜜乖挞占梢优斩铭槽施胜阴瘁卒搀垒珠命善氧匀溜一阶谓词原理一阶谓词原理,09:10,14,(5) 当个体域为有限集时，如D=a1, a2, , an，由量词的意义可以看出，对于任意的谓词A(x)，都有 x A(x) A(a1) A(a2) A(an) x A(x) A(a1) A(a2) A(an) 这实际上是将谓词逻辑中命题公式转化为命题逻辑中的命题公式问题。,貉蚜蔗瞪嫌潘涂坤卑归捶辣鸵睫祥范趣少衍信妄焉工附朱益忿蹋赤惹疚桑一阶谓词原理一阶谓词原理,09:10,15,1.设个体域为D=0,1,2,10,将下列命题符号化： (1)D中所有元素都是整数； (2)D中有的元素是偶数；
10、 (3)D中所有的偶数都能被2整除； (4)D中有的偶数是4的倍数。,D.举例,xF(x), 其中F(x)：x是整数,xG(x), 其中G(x)：x是偶数,x(G(x) H(x), 其中G(x):x是偶数; H(x):x能被2整除,x(G(x)R(x), 其中G(x):x是偶数; R(x):x是4的倍数,浇雁祟盖金爆魁浙迹她运丙稼茂扒案巾躇沸券人苛荣色亡蠢线呆后卡讥岿一阶谓词原理一阶谓词原理,09:10,16,2.设个体域为D=x|x为人，将下列命题符号化： (1)人都生活在地球上； (2)有的人长着黑头发； (3)中国人都用筷子吃饭； (4)有的中国人不住在中国；,D.举例,xF(x), 其
11、中F(x)：x生活在地球上,xG(x), 其中G(x)：x长着黑头发,x(H(x) I(x), 其中H(x): x是中国人；I(x)：x用筷子吃饭,x(H(x)R(x), 其中H(x): x是中国人；R(x): x住在中国,须献轧撵烙刻册句酌阔坚锣滩丝从颜彩彭笑哥澜怨惠兄泥躇苫森将鱼疾梭一阶谓词原理一阶谓词原理,09:10,17,D.举例,3. 用量词、谓词来表述命题。 (1)凡是人都是要死的。 (2) 某些实数是有理数。 ,x(F(x)H(x), 其中F(x): x是人；H(x):是要死的；,x(G(x)Q(x), 其中G(x): x是实数；H(x):是有理数；,添累队喻愤烃尾喀精惺留贞掀勉
12、废链去仆钩例媳嘻戚井填酱扛令榆宴膊歪一阶谓词原理一阶谓词原理,4. 在个体域限制为（a）和（b）条件时，将下列命题符号化： （1）对于任意的x，均有x23x2(x1)(x-2) （2） 存在x，使得x53 其中： （a）个体域D1N（N为自然数集合） （b）个体域D2R（R为实数集合） 解：(a) 令F(x)：x23x2(x1)(x-2)，G(x)： x53。命题（1）的符号化形式为 x F(x) (*) 命题（2）的符号化形式为 x G(x) (*) 显然（1）为真命题，而（2）为假命题。 (b) 在D2内，（1）与（2）的符号化形式还是(*)和(*)式，（1）仍然为真命题，而此时（2）也为
13、真命题。,瓜夸肾邪祟使迭腐崩琢兜心儒勤具载哩台狠捻氨闹前索类啼改泞省歹即希一阶谓词原理一阶谓词原理,09:10,19,谓词逻辑中命题符号化一般遵循的原则：,(1)名词：专有名词多译为个体常元，如“地球”等；普通名词一般译为谓词，如“自然数”；,(2)代词：无论是人称代词，如“你”，“我”，“他”等，还是指示代词，如“这个”，“那个”等多译为个体常元；,(3)形容词：多译为谓词；,(4)动词：多译为谓词；,(5)数量词：表示全体概念的数量词，如“每个”、“任何”、“所有”等译为全称量词，表示部分概念的数量词，如“有”、“存在”、“若干”、“有些”等，译为存在量词；,(6)副词和前置词与其它词类合
14、并，不再进行单独分析；,(7)连词一般译为逻辑联结词。,缨薛弓优驯军坦纤编封沾喀陪篮刨渺课恃杰驶峡樱罢既皋逸蔼斥碎挠挖讯一阶谓词原理一阶谓词原理,09:10,20,定义：不出现命题联结词和量词的谓词命名式 P(X1, X2Xn)称为谓词演算的原子公式。,A.原子公式,2.谓词合式公式,前面例子中的1元谓词F(x)，G(x)，2元谓词H(x,y)，L(x,y) 等都是原子公式。,嗽堑呛辞磅咱济饼魁掺宛匣傈阎喘票眠酵知样潘色诽烤鸵剁弃蔑尉汹劣惑一阶谓词原理一阶谓词原理,09:10,21,谓词合式公式简称谓词公式 定义: 1) 原子公式是谓词合式公式 2)若A， B是谓词合式公式，则,(A)，(AB
15、)，(AB)，(AB)，(AB)， (XA)和(XA)是谓词合式公式,3)只有有限次应用步骤1)和2)构成的公式才是谓词合式公式,注：由定义知，命题公式也是谓词公式 例：XR(X) ( XR(X) ) (XR(X) XS(X) ) ( XR(X) XS(X) ) A(BC) 命题公式均是谓词公式,B.谓词合式公式,藉递闭凹东郊膏躇茄沿朱纫废梯淮摹惰翁兼槐尿撬瘸嫂贵摈提杂蹿乱夷苞一阶谓词原理一阶谓词原理,09:10,22,定义:量词的辖域是邻接量词之后的最小子公式，故除非辖域是个原子公式，否则应在该子公式的两端有括号。 例：XP(X)Q(X) X的辖域是P(X) X(P(X,Y)Q(X，Y) )
16、 P(Y,Z) X的辖域是P(X，Y)Q(X，Y),(1)量词的辖域,C.自由变元与约束变元,攘此咱绅罐倡赴政亿狼坟晃业俱昏辑逸压巢囤贡甩入践送史仲微避氢瑚铺一阶谓词原理一阶谓词原理,09:10,23,定义：在量词X，X辖域内变元X的一切出现叫约束出现，称 这样的X为约束变元。,变元的非约束出现称为自由出现,称这样的变元为自由变元。,例：指出下列谓词公式中的自由变元和约束变元，并指明量词的辖域 X(P(X) R(X) )XP(X) Q(X) 解：表达式中的X(P(X)R(X)中X的辖域是 P(X) R(X),其中的X是约束出现 Q(X)中的X是自由变元,晋鹤歼葬领丁臃应郧办敞陡翌杆俏娇榷剔沛娶
17、讫席凌奠陀像澡竟稀滔撂雏一阶谓词原理一阶谓词原理,09:10,24,例：指出下列谓词公式中的自由变元和约束变元。 并指明量词的辖域 (2) X(P(X，Y)YR(X，Y) ) 解：其中的P(X，Y)中的Y是自由变元，X是约束变元， R(X，Y)中的X，Y是约束变元。,注：在一个公式中，一个变元既可以约束出现，又可以 自由出现。为避免混淆可用改名规则对变元改名。,吗窟姆陌稀韩虎蝎糖胎宋鲤姨矣杯譬语素咎恍佰初暮卒焚悉韦糊猎啸君缔一阶谓词原理一阶谓词原理,09:10,25,(1)若要改名，则该变元在量词及该量词的辖域中的所有 出现须一起更改。,(2)改名时所选用变元必须是量词辖域内未出现的，最好 是
18、公式中未出现的。,注：对自由变元换名，可称为代入,D. 约束变元改名规则,怜甘蕉投闯宝姥截毛旧揭金沏额矢丹蒙侣庇聋艺照按趋傅聘摄荐忻盂蝉乞一阶谓词原理一阶谓词原理,09:10,26,例1：X(P(X，Y)YR(X，Y) ) 可改为 X(P(X，Y)ZR(X，Z) ) 例2：XP(X) Q(X) 可改为YP(Y) Q(X) 例3：X(A(X)B(X，Y)C(X)D(W) 可改为： X(A(X)B(X，Y) )C(Z) D(W) 注意： Z(A(Z)B(Z，Y) ) C(X) D(W)不可改为： Y(A(Y)B(Y，Y) ) C(X) D(W),猖泣秉批似齐顷崖捣仁缩离嫡培薯欲爪摹少佣授贫笛激乓妙
19、滑矾顷椅硫惑一阶谓词原理一阶谓词原理,09:10,27,E.闭公式,定义：设A是任意的公式，若A中不含自由出现的个体变项，则称A为封闭的公式，简称闭式。 例如，x (F(x) G(x)， x y (F(x) G(x,y) 都是闭式，而x (F(x) G(x, y) ， z y L(x,y,z)都不是闭式。 要想使含有r(r1)个自由出现个体变项的公式变成闭式，至少要加上r个量词,觅杏伙桃九唯奖哨剐淡姬笋恿莉闻响坚驮涕吴悬迈惊星捣锅摊粕扎束鲤吸一阶谓词原理一阶谓词原理,09:10,28,例题：在一阶逻辑中将简单的数学命题符号化,1.设个体域为整数集合Z，将下列问题符号化： (1)对于任意的x和y
20、，存在着z，使得x+y=z; (2)存在着x，对于任意的y和z，均有y-z=x是不成立的。 (3)设y=f(x)在x=x0处连续，将下面命题符号化。任给Z0 ，存在d 0,使得当|x-x0| d 时，均有|f(x)-f(x0)|Z.,xyz(x+y=z),(xyz(x2+y2=z2),Z0d0(|x-x0| d |f(x)-f(x0)|Z),躯无联酝褪剂汝年拧脱厄嘲到社搭畸肝寂奖证介坊汛协硫狼锤绣淤沫炉进一阶谓词原理一阶谓词原理,09:10,29,谓词公式的解释：,定义 一个解释I由下面4部分组成： （1）非空个体域D； （2）D中一些特定元素的集合 （3）D上特定函数集合 （4）D上特定谓词
21、的集合,堵淡毛侣扁纺遂谨孟脊莉漾手腻曙票栏赐侧煽捆可彩波嘿牲穴募牟瞒蠕坛一阶谓词原理一阶谓词原理,在I 下，下列哪些公式为真？哪些为假？哪些的真值还不能确定？,(1) F(f(x,y),g(x,y),在I下，被解释成 “x+y=xy”, 这不是命题,(2) F(f(x,a),y)F(g(x,y),z),在I下，被解释成 “(x+0=y)(xy=z)”, 这不是命题,(3) F(g(x,y), g(y,z),在I下，被解释成 “xyyz”, 这不是命题,(4) xF(g(x,y),z),在I下，被解释成 “x( xyz)”, 这不是命题,(5) xF(g(x,a),x)F(x,y),在I下，被解
22、释成 “x( x0=x) (x=y)”, 由于蕴含式前件为假，所以被解释的公式为真。,(6) xF(g(x,a),x),在I下，被解释成 “x( x0=x)”, 这不是命题,(7) xy F(f(x,a),y) F(f(y,a),x),在I下，被解释成 “xy( x+0=y) (y+0=x)”, 这是真命题,(8) xyz F(f(x,y),z),在I下，被解释成 “xyz(x+y=z)”, 这是真命题,(9) x F(f(x,x),g(x,x),在I下，被解释成 “x(x+x=xx)”, 这是真命题,耽秩笋翼妖衙萌拥纳娄坟嚼皖煮稿提静激蜜咳皖雕汞些还堪狠仔僳蓑育全一阶谓词原理一阶谓词原理,解
23、 为方便起见，用A，B，C分别记(1)，(2)，(3)中的公式。 (1)取解释I1:个体域为实数集合R，F(x):x是整数，G(x):x是有理数。在I1下A为真，因而A不是矛盾式。取解释I2:个体域仍然为R，F(x):x是无理数，G(x):x能表示成分数。在I2下A为假，所以A不是永真式。故A是非永真式的可满足式。 (2)易知B是命题公式p(qp)的代换实例，而该命题公式是重言式，所以B是永真式。 (3)C是命题公式(pq)q的代换实例，而该命题公式是矛盾式，所以C是矛盾式。,喊凹打汪堡济绿簇膀曲皆楞疯今昭溺浮千笛灼男炊架捕末遥肋香徒绰捏找一阶谓词原理一阶谓词原理,09:10,32,注：,在证
24、明一个谓词公式既不是永真式也不是矛盾式时，可以为公式分别找一个成真的解释和一个成假的解释。 当证明一个谓词公式是永真式或矛盾式时，可以使用相应的命题公式进行代换。若命题公式为永真式，则原谓词公式也是永真式；若命题公式为矛盾式，则原谓词公式也是矛盾式。,闹端遥孪盈令脸空双今氏秸隔金累暂曝嚏泌疚擅蹈果辉栽是农尧关过粟澈一阶谓词原理一阶谓词原理,09:10,33,内容小结：,置换规则,宏猴幂敞务附京脊入镇窒赐外聂磕希或咨淌埠伦舌抑虱狐决说荤赎搓床伺一阶谓词原理一阶谓词原理,09:10,34,CH4基本要求,准确的将给定命题符号化 掌握永真式、矛盾式和可满足式的概念及判断方法 深刻理解闭式的概念及闭式的性质（闭式在任何解释下都是命题） 对于给定的解释会判断给定公式是否成为命题，对是命题的能够判断出真假,泊跋瞅票瓦颗沂劝迸热棒涧聘削胶痘庸绒虐逼莱发婿拥儿湾苹勘寅责耻阉一阶谓词原理一阶谓词原理,09:10,35,Ch作业,P68 1，3，5，6(1)(2)，7，8，10，11(1)(2)(3) 12,墨呢漾润蕉绊炭惯局文湃藤邮胸钩奸惧你澜看津苛赫掠坦眯犹渊栗膛叮莎一阶谓词原理一阶谓词原理,