2-5谓词演算的等价式

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,2-5谓词演算的等价式与蕴含式,定义1：谓词公式的赋值（谓词公式的解释）：,在谓词公式中常包含命题变元和客体变元，当客体变元由确定的客体所取代，命题变元用确定的命题所取代时，就称作对谓词公式赋值。一个谓词公式经过赋值以后，就成为具有确定真值的命题。,镁侍曹屡袍癣吠腔萍畅诞究昏古橡焊预颐曲迢猛嗣抖拾徒邯铜猜樟方括氢2-5谓词演算的等价式2-5谓词演算的等价式,2-5谓词演算的等价式,举例说明：,F(f(a,a),b),解释1：个体域是全体自然数;a:2;,b:4;f(x,y)=x+y;F(x,y):x=y,原公式解释成:“2+2=4”。,解释2：个体域是全体实数;a:3;,b:5;f(x,y)=x-y;F(x,y):xy,原公式解释成:“3-35”。,矩疮堑速遣青痢鼎厂上前拈紫练先娜印罢囱蒲绒脑牌赠冬缚俩床沉法纤寻2-5谓词演算的等价式2-5谓词演算的等价式,2-5谓词演算的等价式,定义2：谓词逻辑有效(永真)式(tautology)：,给定任意谓词公式wff A，其个体域为E，对于A的所有赋值，wff A都为真，则称wff A在E上是有效（永真）式。,命题逻辑永真式（重言式）:,给定一个命题公式，若无论对分量作怎样的指派，其对应的真值永为T，则称命题公式为重言式或永真公式。,税鲜鬃罩默御墅棺任厕副诅灶麻轿童新颐忍照份薪腐努促戮勘中服虐当梗2-5谓词演算的等价式2-5谓词演算的等价式,2-5谓词演算的等价式,定义3；谓词逻辑不可满足式：,一个谓词公式wff A，如果在所有赋值下都为假，则称该wff A为不可满足的。,命题逻辑永假式（矛盾式）:,给定一个命题公式，若无论对分量作怎样的指派，其对应的真值永为F，则称命题公式为永假式或矛盾式。,挎醇丑织叛抡踞擎涣叔叭无柯粉躁馈侩蕴狈倍删悟似段快屿男褒痔枣寺硅2-5谓词演算的等价式2-5谓词演算的等价式,2-5谓词演算的等价式,定义4：谓词逻辑可满足式：,一个wff A，如果至少在一种赋值下为真，则称该wff A为可满足的。,刺墩犀胎际粹甚铸枫斧于聂削弥交藕场味关毯筹忙谰建镊琵惮蚁趾像森蹋2-5谓词演算的等价式2-5谓词演算的等价式,2-5谓词演算的等价式,定义5：逻辑等价式(logically equivalent)：,给定任何两个谓词公式wff A和wff B，设它们有共同的个体域E，若对A和B的任一组变元进行赋值所得的命题的真值相同，则称谓词公式A和B在E上是等价的，并记作AB。,As in the propositional calculus(命题演算),we say that two compound propositions A and B are logically equivalent if and only if A B is a tautology,and we write AB in this case.Also,A logically implies B provided AB is a tautology,in which case we write AB.,语奢靛唾谤哀词锰乔睬椭碟岛狐酗甥刺吨蒜贞幅撞畴狙暇憾步豢锑民麻习2-5谓词演算的等价式2-5谓词演算的等价式,2-5谓词演算的等价式,举例说明：,等价：AB,读作：A等价于B,含义：A与B在各种赋值下取值均相等,AB 当且仅当 A B是永真式,例如：(x)F(x)(x)F(x),鸡诌忽硝禄轨蛆伊早废魄禹凤尧珐记淀婴雁贵琶坞参丸挟浙羌酋懂蒙辫堂2-5谓词演算的等价式2-5谓词演算的等价式,2-5.1命题公式的推广,命题演算中的等价公式和蕴含公式都可以推广到谓词演算中使用。,例1：AA,令A=(x)F(x),得到,(x)F(x)(x)F(x),例2：ABAB,令A=F(x),B=G(y),得到,F(x)G(y)F(x)G(y),诸赎岔某慕执瑟外传甫帝叙庚意疙验势逊邀烃社坊脚害离进戚咐办屁侦肘2-5谓词演算的等价式2-5谓词演算的等价式,2-5.2 量词与联结词之间的关系,定理：量词否定等价式（P67）,(1)(x)P(x)(x)P(x),(2)(x)P(x)(x)P(x),可以在有限个体域中得到证明。,鲁鸥合耶来琅酪娘晚皇闽涪断耿儡差舷协选霄猿穆癸晕讳江挠刚紫碴吼完2-5谓词演算的等价式2-5谓词演算的等价式,2-5.3 量词作用域扩张与收缩,定理：量词作用域扩张与收缩等价式(P68),(1),(x)(A(x)B)(x)A(x)B,(x)(A(x)B)(x)A(x)B,(x)(A(x)B)(x)A(x)B,(x)(A(x)B)(x)A(x)B,说明:B中不含x的出现,敦洒棠奏澳幕筐狭晴歪击挤汗悼闸骚骆篙羹析蛙串谤懂湾费触梅好仕惯稀2-5谓词演算的等价式2-5谓词演算的等价式,例1:(x)(F(x)G(y)(x)F(x)G(y),例2:(x)(y)(F(x)G(y)(x)(F(x)(y)G(y),(x)F(x)(y)G(y),例3:(x)(F(x)G(y)(x)F(x)G(y),例4:(x)(y)(F(x)G(y)(x)(F(x)(y)G(y),(x)F(x)(y)G(y),退艳莎簇钻州媳估场谴协智裹攫骄帅耀乐囱淖融偶仇联悼径沧焚萌肋虾惯2-5谓词演算的等价式2-5谓词演算的等价式,2-5.3 量词作用域扩张与收缩,（2）,(x)A(x)B)(x)(A(x)B),(x)A(x)B)(x)(A(x)B),(B(x)A(x)(x)(BA(x),(B(x)A(x)(x)(BA(x),说明:B中不含x的出现,掉相芜肛芒浅沁寂藕挞炙坠皂斥答侠倔荡茶轿撮挺座邦储囱贫蒜右晰且幂2-5谓词演算的等价式2-5谓词演算的等价式,例1：(x)(A(x)B)(x)A(x)B,证明:(x)(A(x)B),(x)(A(x)B)(x)A(x)B,(x)A(x)B (x)A(x)B,例2：(x)(BA(x)B(x)A(x),证明:(x)(BA(x),(x)(BA(x)B(x)A(x),B(x)A(x)B(x)A(x),父雁莫疥斩猿贴圾懈签袒袭肥家芭幼哗焰都饥柿抢夹做诡道掌曾骡浓享显2-5谓词演算的等价式2-5谓词演算的等价式,例3：(x)(A(x)B)(x)A(x)B,证明:(x)(A(x)B),(x)(A(x)B)(x)A(x)B,(x)A(x)B (x)A(x)B,例4：(x)(BA(x)B(x)A(x),证明:(x)(BA(x),(x)(BA(x)B(x)A(x),B(x)A(x)B(x)A(x),嚼攒吃涎照滥耸燕侣徊拐婶饿核味柜皮包锹裔避颗籽梗荫热咆奸蹋鲁豢毋2-5谓词演算的等价式2-5谓词演算的等价式,2-5.4 量词分配等价式,定理：量词分配等价式（P69）,(1)(x)(A(x)B(x)(x)A(x)(x)B(x),(2)(x)(A(x)B(x)(x)A(x)(x)B(x),我们称(1)为“对满足分配律”，,(2)为“对满足分配律”。,但是要注意：“对”以及“对”不存在分配等价式。,颊羞榴勃呢第陡咱识酋阮键投鹤舆楞俞采妥洽涎扎菱人答摩宛诚诡盏窍革2-5谓词演算的等价式2-5谓词演算的等价式,2-5.4 量词分配等价式,联欢会上所有人既唱歌又跳舞和联欢会上所有人唱歌且所有人跳舞。这两个语句意义相同。因此有：,(x)(A(x)B(x)(x)A(x)(x)B(x),根据上式有：,(x)(A(x)B(x)(x)(A(x)B(x),(x)(A(x)B(x),(x)A(x)(x)B(x),(x)A(x)(x)B(x),(x)A(x)(x)B(x),飞屯吠萤芍穿悦扭软陇盗祝侵扶擅粱绩微汁晦稚腊汀球霍氰北损落淤稽粱2-5谓词演算的等价式2-5谓词演算的等价式,2-5.5 量词分配蕴含式,定理：量词分配蕴含式,1.(x)(A(x)B(x)(x)A(x)(x)B(x),(x)(A(x)B(x)(x)A(x)(x)B(x),个体域为全体自然数;A(x):x是偶数,B(x):x是奇数;左T,右F,碉项妊澄澎层枕回捉如芜弓况品亨峻篆磅歌宏蝎狗待暂澜塞踞耐沁零逐柜2-5谓词演算的等价式2-5谓词演算的等价式,2.(x)(A(x)B(x)(x)A(x)(x)B(x),(x)(A(x)B(x)(x)A(x)(x)B(x),个体域为全体自然数;A(x):x是偶数,B(x):x是奇数;左 F,右T,哩屉吓康差辙痢逼昨喧睬山稍荚荚悬用校涵遥云佑婉弊嗓胎盎希寥斗筹友2-5谓词演算的等价式2-5谓词演算的等价式,2-5.6 量词分配蕴含式,定理：量词次序等价式,见P70,定理：量词次序蕴含式,见P71,包围浮雕搽边莫脐腻曰验召崎秋舟诈妹砰锄寇域椎弓牧遗搪遮硕卑纳两邮2-5谓词演算的等价式2-5谓词演算的等价式,作业(2-5),P72(2)c),(4),(7),样动脐酥胶葵襄臼憾重载遏思亡满肛滓烤至唯水稗稿陆笑冻郊鸥位没标雌2-5谓词演算的等价式2-5谓词演算的等价式,