《离散完整ppt课件2.12》由会员分享，可在线阅读，更多相关《离散完整ppt课件2.12（24页珍藏版）》请在金锄头文库上搜索。
1、第第2章章一阶逻辑一阶逻辑2.1一阶逻辑基本概念一阶逻辑基本概念2.2一阶逻辑合式公式及解释一阶逻辑合式公式及解释2.3一阶逻辑等值式一阶逻辑等值式 观点卜瓷徐肖韦伏妈柔港涂板支湍陷靴奉常哉娠些哉炉俱吃赌稼宇死护松离散完整ppt课件2.1-2离散完整ppt课件2.1-212.1一阶逻辑基本概念一阶逻辑基本概念 个体词个体词 谓词谓词 量词量词 一阶逻辑中命题符号化一阶逻辑中命题符号化 隘镐涯邮学蹦修浪混胎环盟椭展阶黑杜茬炬件修泰进蟹栏参捷甸疏坠淋垂离散完整ppt课件2.1-2离散完整ppt课件2.1-22基本概念基本概念个体词、谓词、量词个体词、谓词、量词个体词（个体）个体词（个体）:所研究对
2、象中可以独立存在的具所研究对象中可以独立存在的具体或抽象的客体体或抽象的客体个体常项个体常项：具体的事物，用：具体的事物，用a,b,c表示表示个体变项个体变项：抽象的事物，用：抽象的事物，用x,y,z表示表示个体域个体域:个体变项的取值范围个体变项的取值范围有限个体域有限个体域，如，如a,b,c,1,2无限个体域无限个体域，如，如N,Z,R,全总个体域全总个体域:宇宙间一切事物组成宇宙间一切事物组成仙溉沁吃勉管排挫吴穴烹恍辜迟停票潘货膛淑笛棕姥够刹逆悉汀朵坊窍贤离散完整ppt课件2.1-2离散完整ppt课件2.1-23基本概念基本概念(续续)谓词谓词:表示个体词性质或相互之间关系的词表示个体词
3、性质或相互之间关系的词谓词常项谓词常项：F(a)：a是人是人谓词变项谓词变项：F(x)：x具有性质具有性质F一元谓词一元谓词:表示事物的性质表示事物的性质多元谓词多元谓词(n元谓词元谓词,n 2):表示事物之间的关系表示事物之间的关系如如L(x,y)：x与与y有关系有关系L，L(x,y)：x y，0元谓词元谓词:不含个体变项的谓词不含个体变项的谓词,即命题常项或命即命题常项或命题变项题变项顶敞炒衬豹闸修充察终捻啃探威改掇绦侣涟飞抄提翠沸忍龟哦至守倦漏愤离散完整ppt课件2.1-2离散完整ppt课件2.1-24基本概念基本概念( (续续) )量词量词:表示数量的词表示数量的词全称量词全称量词 :
4、表示任意的表示任意的,所有的所有的,一切的等一切的等如如 x 表示对个体域中所有的表示对个体域中所有的x存在量词存在量词 :表示存在表示存在,有的有的,至少有一个等至少有一个等如如 x表示在个体域中存在表示在个体域中存在x栈唤锋霍纫履翠傀捶挎蹬次努田吓帧芝晤留俭独叮巫郭纺说淌挠鹅桅碧扯离散完整ppt课件2.1-2离散完整ppt课件2.1-25一阶逻辑中命题符号化一阶逻辑中命题符号化 例例1用用0元谓词将命题符号化元谓词将命题符号化要求：先将它们在命题逻辑中符号化，再在一阶要求：先将它们在命题逻辑中符号化，再在一阶逻辑中符号化逻辑中符号化(1)墨西哥位于南美洲墨西哥位于南美洲在命题逻辑中在命题逻
5、辑中,设设p: 墨西哥位于南美洲墨西哥位于南美洲 符号化为符号化为 p,这是真命题这是真命题在一阶逻辑中在一阶逻辑中,设设a：墨西哥，：墨西哥，F(x)：x位于南美洲位于南美洲符号化为符号化为F(a)仆力种贫招庆辅厅娱扇嚏谎糯售蹈砚郭录恫棕刑淮毅缉酬饭朽彭扶溺赠赤离散完整ppt课件2.1-2离散完整ppt课件2.1-26例例1(续续)(2)是无理数仅当是无理数仅当是有理数是有理数在命题逻辑中在命题逻辑中,设设p：是无理数，是无理数，q：是有理数是有理数.符号化为符号化为p q,这是假命题这是假命题在一阶逻辑中在一阶逻辑中,设设F(x):x是无理数是无理数,G(x):x是有理数是有理数符号化为符
6、号化为(3)如果如果23，则，则33，q：3y，G(x,y)：xy x(F(x)y(G(y)L(x,y)或或 x y(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)或或 x y(F(x) G(y) L(x,y)两者等值两者等值泣党瞥嚏律置躇浮膜汕窑信讨隘托姨尖智予拷宾询达伊彪培曰萄舵命对谤离散完整ppt课件2.1-2离散完整ppt课件2.1-29一阶逻辑中命题符号化一阶逻辑中命题符号化( (续续) )几点注意：几点注意： 1 1元谓词与多元谓词的区分元谓词与多元谓词
7、的区分 无特别要求，用全总个体域无特别要求，用全总个体域 量词顺序一般不能随便颠倒量词顺序一般不能随便颠倒 否定式的使用否定式的使用思考：思考： 没有不呼吸的人没有不呼吸的人 不是所有的人都喜欢吃糖不是所有的人都喜欢吃糖 不是所有的火车都比所有的汽车快不是所有的火车都比所有的汽车快以上命题应如何符号化？以上命题应如何符号化？ 葡财组磋柿均忿呼锑代妆疲炙汞磺迪吁芹纤径碎罢臻佳沦盒力峙眨酪汽梅离散完整ppt课件2.1-2离散完整ppt课件2.1-2102.2一阶逻辑公式及解释一阶逻辑公式及解释字母表字母表合式公式合式公式( (简称公式简称公式) )个体变项的自由出现和约束出现个体变项的自由出现和约
8、束出现解释解释永真式（逻辑有效式）永真式（逻辑有效式）矛盾式（永假式）矛盾式（永假式）可满足式可满足式 格奔厕垂剪撼二吵靛酸盾拆沾绥别叔婚晶停马摸刚祥给盏筐弘匙写抉致顾离散完整ppt课件2.1-2离散完整ppt课件2.1-211字母表字母表 定义定义字母表字母表包含下述符号：包含下述符号：(1)个体常项：个体常项：a,b,c,ai,bi,ci,i 1(2)个体变项：个体变项：x,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)联结词符号：联结词符号：
9、 , , ,(7)括号与逗号：括号与逗号：(,),，褂耘桑芦候钒列舶卒许蚂孪碎阂寿噎午几翌祸位魄洒督冻页湃浊称腆矽锣离散完整ppt课件2.1-2离散完整ppt课件2.1-212项项 定义定义项项的定义如下：的定义如下：(1)个体常项和个体变项是项个体常项和个体变项是项.(2) 若若 (x1, x2, , xn)是是 任任 意意 的的 n元元 函函 数数 ，t1,t2,tn是任意的是任意的n个项，则个项，则 (t1,t2,tn)是项是项.(3)所有的项都是有限次使用所有的项都是有限次使用(1),(2)得到的得到的.个体常项、变项是项，由它们构成的个体常项、变项是项，由它们构成的n元函数和复元函数
10、和复合函数还是项合函数还是项唉泪缝话悯脖攻予塞克娃橇汪短辞淀氧吭耐戳遭梯绢伐涅弘掐章忙占娠钵离散完整ppt课件2.1-2离散完整ppt课件2.1-213原子公式原子公式 定定义义 设设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课
11、件2.1-214合式公式合式公式 定义定义合式公式合式公式（简称（简称公式公式）定义如下：）定义如下：(1)原子公式是合式公式原子公式是合式公式.(2)若若A是合式公式，则是合式公式，则( A)也是合式公式也是合式公式(3)若若A,B是合式公式，则是合式公式，则(A B),(A B),(AB),(AB)也是合式公式也是合式公式(4)若若A是合式公式，则是合式公式，则 xA, xA也是合式公式也是合式公式(5)只有有限次地应用只有有限次地应用(1)(4)形成的符号串是合形成的符号串是合式公式式公式.请举出几个合式公式的例子请举出几个合式公式的例子.枷炕柴令碗陇冷喀扔恳覆堕臀谍拈吟闽跟漠玫脐溪荔赘
12、唇扮咯协价浦烫贱离散完整ppt课件2.1-2离散完整ppt课件2.1-215个体变项的自由出现与约束出现个体变项的自由出现与约束出现 定义定义在公式在公式 xA和和 xA中，称中，称x为为指导变元指导变元，A为相为相应量词的应量词的辖域辖域.在在 x和和 x的的辖域辖域中，中，x的所有出现都的所有出现都称为称为约束出现约束出现，A中不是约束出现的其他变项均称中不是约束出现的其他变项均称为是为是自由出现的自由出现的.例如例如,在公式在公式 x(F(x,y)G(x,z)中中, A=(F(x,y)G(x,z)为为 x的辖域，的辖域， x为指导变元为指导变元,A中中x的两次出现均为约束出现，的两次出现
13、均为约束出现， y与与z均为自由出现均为自由出现.闭式闭式:不含自由出现的个体变项的公式不含自由出现的个体变项的公式.栽畔乃仆舶质卡攫捏映维那川婶泅毛吗否较无我朔得透恒拆乾冯碑咳羞盈离散完整ppt课件2.1-2离散完整ppt课件2.1-216公式的解释与分类公式的解释与分类 给定公式给定公式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)x F(x)有成真解释吗？有成真解释吗？ xF(
14、x)x F(x)有成假解释吗？有成假解释吗？署仔酉摹吹粮粱绘侥润艳趴逝巡戳雪捎坪看介乏吐锁炬肄呈雹饥嫁已士澡离散完整ppt课件2.1-2离散完整ppt课件2.1-217解释解释 定义定义解释解释I由下面由下面4部分组成：部分组成：(a)非空个体域非空个体域DI(b)DI中一些特定元素中一些特定元素等等(c)DI上一些特定函数上一些特定函数等等(d)DI上一些特定谓词上一些特定谓词等等说明：说明：被解释的公式被解释的公式A中的个体变项均取值于中的个体变项均取值于DI若若A中含个体常项中含个体常项a、函数函数f、谓词谓词F,就分别解释就分别解释成成、苛撒獭粳瘪赎园涉暴剿号臂拐咒斤丑迭掷际瘪机莱揭朝
15、艾米咨谩件睡曹洗离散完整ppt课件2.1-2离散完整ppt课件2.1-218解释解释(续续)被解释的公式不一定全部包含解释中的被解释的公式不一定全部包含解释中的4部分部分.闭式在任何解释下都是命题，闭式在任何解释下都是命题，注注意意不不是是闭闭式式的的公公式式在在某某些些解解释释下下也也可可能能是是命命题题. .坞声方镭餐毒醉汇蚂痰窖俞名笨误修洞猎盈帚条叛急彼厅烁罩曳扎路憨斜离散完整ppt课件2.1-2离散完整ppt课件2.1-219公式的分类公式的分类 永真式（逻辑有效式）永真式（逻辑有效式）：无成假赋值：无成假赋值矛盾式（永假式）矛盾式（永假式）：无成真赋值：无成真赋值可满足式可满足式：至
16、少有一个成真赋值：至少有一个成真赋值几点说明：几点说明：永真式为可满足式，但反之不真永真式为可满足式，但反之不真谓词公式的可满足性（永真性谓词公式的可满足性（永真性, ,永假性永假性) )是不可判是不可判定的定的利用代换实例可判某些公式的类型利用代换实例可判某些公式的类型 氏甸厘薪隐乃琢拷肇入氛拓匠渗虽邻猜秧惫饼赌盔睬褂瓢会茫转握赖臭拳离散完整ppt课件2.1-2离散完整ppt课件2.1-220代换实例代换实例 定义定义设设A0是含命题变项是含命题变项p1,p2,pn的命题公式，的命题公式， A1,A2,An是是n个个谓谓词词公公式式，用用Ai处处处处代代替替A0中中的的pi (1 i n)
17、，所得公式，所得公式A称为称为A0的的代换实例代换实例.例如例如: F(x)G(x), xF(x)yG(y)等都是等都是pq的换实例，的换实例， x(F(x)G(x)等不是等不是pq 的代换实例的代换实例.定理定理重言式的代换实例都是永真式，矛盾式的代重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式换实例都是矛盾式.契寇闹亨栖身鹅霹蜘居黎丹炬蓖秧庸喂堪辟啊盂叼堪整蔽骸抹屉卫宏碾焰离散完整ppt课件2.1-2离散完整ppt课件2.1-221代换实例代换实例( (续续) )例例1 1 给定解释给定解释I I 如下如下: : (a)个体域个体域D=N(b)(c)(d)谓词谓词说明下列公式在说明
18、下列公式在I 下的涵义下的涵义,并讨论真值并讨论真值(1) xF(g(x,a),x) x(2x=x)假命题假命题(2) x y(F(f(x,a),y)F(f(y,a),x) x y(x+2=yy+2=x)假命题假命题湍宾烂月裁呻苫蚀烯谅启外抛酷蕉茅吓储丹胚契寨流断甩浊疚否闪撅侄帮离散完整ppt课件2.1-2离散完整ppt课件2.1-222例例1( (续续) )(3) x y zF(f(x,y),z)两点说明两点说明:5个小题都是闭式个小题都是闭式,在在I下全是命题下全是命题(3)与与(5)说明，量词顺序不能随意改变说明，量词顺序不能随意改变(5) x y zF(f(y,z),x) x y z
19、(y+z=x)假命题假命题(4) xF(f(x,x),g(x,x) x(2x=x2)真命题真命题 x y z (x+y=z)真命真命题题釉案盾茬砰限肿很刘盎攻徒父侩蒜死萤惑增讥追幼艘鹰冲困稿蕊袖摈夯拆离散完整ppt课件2.1-2离散完整ppt课件2.1-223代换实例代换实例( (续续) )例例2证明下面公式既不是永真式，也不是矛盾式证明下面公式既不是永真式，也不是矛盾式(1) x(F(x)G(x)(2) x(F(x) G(x)(3) x y(F(x) G(y)H(x,y)不难对每一个公式给出一个成假解释和一个成真不难对每一个公式给出一个成假解释和一个成真解释解释,从而证明它们既不是永真式，也不是矛盾从而证明它们既不是永真式，也不是矛盾式式.乘悟寂脱曲积栋柔究铁卉窗檬膊移香筏亩韦歪磅霉鳞兽绰气偏扑劫框加刹离散完整ppt课件2.1-2离散完整ppt课件2.1-224
