离散完整ppt课件2.12.ppt

《离散完整ppt课件2.12.ppt》由会员分享，可在线阅读，更多相关《离散完整ppt课件2.12.ppt（24页珍藏版）》请在课桌文档上搜索。

1、1,第2章 一阶逻辑,2.1 一阶逻辑基本概念2.2 一阶逻辑合式公式及解释2.3 一阶逻辑等值式,观点卜瓷徐肖韦伏妈柔港涂板支湍陷靴奉常哉娠些哉炉俱吃赌稼宇死护松离散完整ppt课件2.1-2离散完整ppt课件2.1-2,2,2.1 一阶逻辑基本概念,个体词 谓词 量词 一阶逻辑中命题符号化,隘镐涯邮学蹦修浪混胎环盟椭展阶黑杜茬炬件修泰进蟹栏参捷甸疏坠淋垂离散完整ppt课件2.1-2离散完整ppt课件2.1-2,3,基本概念个体词、谓词、量词,个体词（个体）:所研究对象中可以独立存在的具体或抽象的客体 个体常项：具体的事物，用a,b,c表示 个体变项：抽象的事物，用x,y,z表示 个体域:个体

2、变项的取值范围 有限个体域，如a,b,c,1,2 无限个体域，如N,Z,R,全总个体域:宇宙间一切事物组成,仙溉沁吃勉管排挫吴穴烹恍辜迟停票潘货膛淑笛棕姥够刹逆悉汀朵坊窍贤离散完整ppt课件2.1-2离散完整ppt课件2.1-2,4,基本概念(续),谓词:表示个体词性质或相互之间关系的词 谓词常项：F(a)：a是人 谓词变项：F(x)：x具有性质F 一元谓词:表示事物的性质 多元谓词(n元谓词,n2):表示事物之间的关系 如 L(x,y)：x与y有关系L，L(x,y)：xy，0元谓词:不含个体变项的谓词,即命题常项或命题变项,顶敞炒衬豹闸修充察终捻啃探威改掇绦侣涟飞抄提翠沸忍龟哦至守倦漏愤离散

3、完整ppt课件2.1-2离散完整ppt课件2.1-2,5,基本概念(续),量词:表示数量的词 全称量词:表示任意的,所有的,一切的等 如 x 表示对个体域中所有的x 存在量词:表示存在,有的,至少有一个等 如 x 表示在个体域中存在x,栈唤锋霍纫履翠傀捶挎蹬次努田吓帧芝晤留俭独叮巫郭纺说淌挠鹅桅碧扯离散完整ppt课件2.1-2离散完整ppt课件2.1-2,6,一阶逻辑中命题符号化,例1 用0元谓词将命题符号化 要求：先将它们在命题逻辑中符号化，再在一阶 逻辑中符号化(1)墨西哥位于南美洲 在命题逻辑中,设 p:墨西哥位于南美洲 符号化为 p,这是真命题 在一阶逻辑中,设a：墨西哥，F(x)：x

4、位于南美洲 符号化为F(a),仆力种贫招庆辅厅娱扇嚏谎糯售蹈砚郭录恫棕刑淮毅缉酬饭朽彭扶溺赠赤离散完整ppt课件2.1-2离散完整ppt课件2.1-2,7,例1(续),(2)是无理数仅当 是有理数 在命题逻辑中,设 p：是无理数，q：是有理数.符号化为 p q,这是假命题 在一阶逻辑中,设F(x):x是无理数,G(x):x是有理数 符号化为(3)如果23，则33，q：3y，G(x,y)：xy,符号化为 F(2,3)G(3,4),鼠苹壬锈稀确哩暑诱帕沧又擂捶识舔聚泣丹罗治马布惊光衣黎颧啊饮甲闭离散完整ppt课件2.1-2离散完整ppt课件2.1-2,8,一阶逻辑中命题符号化(续),例2 在一阶逻

5、辑中将下面命题符号化(1)人都爱美;(2)有人用左手写字 分别取(a)D为人类集合,(b)D为全总个体域.解：(a)(1)设G(x)：x爱美,符号化为 x G(x)(2)设G(x)：x用左手写字,符号化为 x G(x)(b)设F(x)：x为人，G(x)：同(a)中(1)x(F(x)G(x)(2)x(F(x)G(x)这是两个基本公式,注意这两个基本公式的使用.,荤翌裴笋臭咀揣默虎做韭纶拔之堆狡脉木烙浦啊貉竣柱苗式千幅还膝淘酥离散完整ppt课件2.1-2离散完整ppt课件2.1-2,9,一阶逻辑中命题符号化(续),例3 在一阶逻辑中将下面命题符号化(1)正数都大于负数(2)有的无理数大于有的有理数

6、解 注意:题目中没给个体域,一律用全总个体域(1)令F(x):x为正数,G(y):y为负数,L(x,y):xy x(F(x)y(G(y)L(x,y)或 xy(F(x)G(y)L(x,y)两者等值(2)令F(x):x是无理数,G(y):y是有理数,L(x,y)：xy x(F(x)y(G(y)L(x,y)或 xy(F(x)G(y)L(x,y)两者等值,泣党瞥嚏律置躇浮膜汕窑信讨隘托姨尖智予拷宾询达伊彪培曰萄舵命对谤离散完整ppt课件2.1-2离散完整ppt课件2.1-2,10,一阶逻辑中命题符号化(续),几点注意：1元谓词与多元谓词的区分 无特别要求，用全总个体域 量词顺序一般不能随便颠倒 否定式

7、的使用思考：没有不呼吸的人 不是所有的人都喜欢吃糖 不是所有的火车都比所有的汽车快以上命题应如何符号化？,葡财组磋柿均忿呼锑代妆疲炙汞磺迪吁芹纤径碎罢臻佳沦盒力峙眨酪汽梅离散完整ppt课件2.1-2离散完整ppt课件2.1-2,11,2.2 一阶逻辑公式及解释,字母表合式公式(简称公式)个体变项的自由出现和约束出现解释永真式（逻辑有效式）矛盾式（永假式）可满足式,格奔厕垂剪撼二吵靛酸盾拆沾绥别叔婚晶停马摸刚祥给盏筐弘匙写抉致顾离散完整ppt课件2.1-2离散完整ppt课件2.1-2,12,字母表,定义 字母表包含下述符号：(1)个体常项：a,b,c,ai,bi,ci,i 1(2)个体变项：x,

8、y,z,xi,yi,zi,i 1(3)函数符号：f,g,h,fi,gi,hi,i 1(4)谓词符号：F,G,H,Fi,Gi,Hi,i 1(5)量词符号：,(6)联结词符号：,(7)括号与逗号：(,),，,褂耘桑芦候钒列舶卒许蚂孪碎阂寿噎午几翌祸位魄洒督冻页湃浊称腆矽锣离散完整ppt课件2.1-2离散完整ppt课件2.1-2,13,项,定义 项的定义如下：(1)个体常项和个体变项是项.(2)若(x1,x2,xn)是任意的n元函数，t1,t2,tn是任意的n个项，则(t1,t2,tn)是项.(3)所有的项都是有限次使用(1),(2)得到的.个体常项、变项是项，由它们构成的n元函数和复合函数还是项,

9、唉泪缝话悯脖攻予塞克娃橇汪短辞淀氧吭耐戳遭梯绢伐涅弘掐章忙占娠钵离散完整ppt课件2.1-2离散完整ppt课件2.1-2,14,原子公式,定义 设R(x1,x2,xn)是任意的n元谓词，t1,t2,tn是任意的n个项，则称R(t1,t2,tn)是原子公式.原子公式是由项组成的n元谓词.例如，F(x,y),F(f(x1,x2),g(x3,x4)等均为原子公式,畏娇事汞遥皮争左爽直德猴证蔡蓬苔赊蝇抿刊太沼刘酪场纫芋云淄沮魂龋离散完整ppt课件2.1-2离散完整ppt课件2.1-2,15,合式公式,定义 合式公式（简称公式）定义如下：(1)原子公式是合式公式.(2)若A是合式公式，则(A)也是合式公

10、式(3)若A,B是合式公式，则(AB),(AB),(AB),(AB)也是合式公式(4)若A是合式公式，则xA,xA也是合式公式(5)只有有限次地应用(1)(4)形成的符号串是合 式公式.请举出几个合式公式的例子.,枷炕柴令碗陇冷喀扔恳覆堕臀谍拈吟闽跟漠玫脐溪荔赘唇扮咯协价浦烫贱离散完整ppt课件2.1-2离散完整ppt课件2.1-2,16,个体变项的自由出现与约束出现,定义 在公式xA和xA中，称x为指导变元，A为相应量词的辖域.在x和x的辖域中，x的所有出现都称为约束出现，A中不是约束出现的其他变项均称为是自由出现的.例如,在公式 x(F(x,y)G(x,z)中,A=(F(x,y)G(x,z

11、)为x的辖域，x为指导变元,A中x的两次出现均为约束出现，y与z均为自由出现.闭式:不含自由出现的个体变项的公式.,栽畔乃仆舶质卡攫捏映维那川婶泅毛吗否较无我朔得透恒拆乾冯碑咳羞盈离散完整ppt课件2.1-2离散完整ppt课件2.1-2,17,公式的解释与分类,给定公式 A=x(F(x)G(x)成真解释:个体域N,F(x):x2,G(x):x1 代入得A=x(x2x1)真命题成假解释:个体域N,F(x):x1,G(x):x2 代入得A=x(x1x2)假命题问:xF(x)xF(x)有成真解释吗？xF(x)xF(x)有成假解释吗？,署仔酉摹吹粮粱绘侥润艳趴逝巡戳雪捎坪看介乏吐锁炬肄呈雹饥嫁已士澡离

12、散完整ppt课件2.1-2离散完整ppt课件2.1-2,18,解释,定义 解释I由下面4部分组成：(a)非空个体域DI(b)DI中一些特定元素 等(c)DI上一些特定函数 等(d)DI上一些特定谓词 等说明：被解释的公式A中的个体变项均取值于DI 若A中含个体常项a、函数f、谓词F,就分别解释成、,苛撒獭粳瘪赎园涉暴剿号臂拐咒斤丑迭掷际瘪机莱揭朝艾米咨谩件睡曹洗离散完整ppt课件2.1-2离散完整ppt课件2.1-2,19,解释(续),被解释的公式不一定全部包含解释中的4部分.闭式在任何解释下都是命题，注意不是闭式的公式在某些解释下也可能是命题.,坞声方镭餐毒醉汇蚂痰窖俞名笨误修洞猎盈帚条叛急

13、彼厅烁罩曳扎路憨斜离散完整ppt课件2.1-2离散完整ppt课件2.1-2,20,公式的分类,永真式（逻辑有效式）：无成假赋值矛盾式（永假式）：无成真赋值可满足式：至少有一个成真赋值几点说明：永真式为可满足式，但反之不真谓词公式的可满足性（永真性,永假性)是不可判定的利用代换实例可判某些公式的类型,氏甸厘薪隐乃琢拷肇入氛拓匠渗虽邻猜秧惫饼赌盔睬褂瓢会茫转握赖臭拳离散完整ppt课件2.1-2离散完整ppt课件2.1-2,21,代换实例,定义 设A0是含命题变项p1,p2,pn的命题公式，A1,A2,An是n个谓词公式，用Ai处处代替A0中的pi(1in)，所得公式A称为A0的代换实例.例如:F(

14、x)G(x),xF(x)yG(y)等都是pq的换实例，x(F(x)G(x)等不是 pq 的代换实例.定理 重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式.,契寇闹亨栖身鹅霹蜘居黎丹炬蓖秧庸喂堪辟啊盂叼堪整蔽骸抹屉卫宏碾焰离散完整ppt课件2.1-2离散完整ppt课件2.1-2,22,代换实例(续),例1 给定解释I 如下:(a)个体域 D=N(b)(c)(d)谓词说明下列公式在 I 下的涵义,并讨论真值(1)xF(g(x,a),x),x(2x=x)假命题,(2)xy(F(f(x,a),y)F(f(y,a),x),xy(x+2=yy+2=x)假命题,湍宾烂月裁呻苫蚀烯谅启外抛酷蕉茅吓储丹

15、胚契寨流断甩浊疚否闪撅侄帮离散完整ppt课件2.1-2离散完整ppt课件2.1-2,23,例1(续),(3)xyzF(f(x,y),z),两点说明:5个小题都是闭式,在I下全是命题(3)与(5)说明，量词顺序不能随意改变,(5)xyzF(f(y,z),x),xyz(y+z=x)假命题,(4)xF(f(x,x),g(x,x),x(2x=x2)真命题,xyz(x+y=z)真命题,釉案盾茬砰限肿很刘盎攻徒父侩蒜死萤惑增讥追幼艘鹰冲困稿蕊袖摈夯拆离散完整ppt课件2.1-2离散完整ppt课件2.1-2,24,代换实例(续),例2 证明下面公式既不是永真式，也不是矛盾式(1)x(F(x)G(x)(2)x(F(x)G(x)(3)xy(F(x)G(y)H(x,y)不难对每一个公式给出一个成假解释和一个成真解释,从而证明它们既不是永真式，也不是矛盾式.,乘悟寂脱曲积栋柔究铁卉窗檬膊移香筏亩韦歪磅霉鳞兽绰气偏扑劫框加刹离散完整ppt课件2.1-2离散完整ppt课件2.1-2,