煎瘫肮凰伪贞蓉语挡被紊轮抖织堤边皑袍踏赘纯势焉嫂嘉贪婴呆划彪滑季一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt第五章第五章 一阶逻辑等值演算与推理一阶逻辑等值演算与推理5.1 5.1 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则倒我被传烽渡膝湾求堰误淆洲街俺铸傲鹤诗堡矩知意炊澜盖惠乒瞄婆照逮一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt1 定义定义5.15.1（等值式）（等值式） 设A A，B B是一阶逻辑中任意两个公式，若A AB B是永真式，则称A A和B B是等值的，记作A AB B，称A AB B是等值式。 下面给出一阶逻辑中的一些基本而重要的等值式： 由于命题逻辑的重言式的代换实例都是一阶逻辑的永真式，所以命题逻辑中2424个等值式模式（p.24p.24）给出的代换实例都是一阶逻辑的等值式模式。例如： xFxF（x x） xFxF（x x） x x y y（F F（x x，y y）GG（x x，y y） x x y y（F F（x x，y y）GG（x x，y y） 等都是A AAA的代换实例。胁郎袭参央急余垂奴点滓四稀歹胚踌谬监秽梁哄窍脚眷示杨狼案芒书悲毡一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt2 下面介绍一些一阶逻辑固有的等值式，这些等值式都与量词有关。 1 1、消去量词等值式、消去量词等值式 设个体域为有限集D=aD=a1 1，a a2 2，a an n ，则有 （1 1） xAxA（x x） A A（a a1 1）AA（a a2 2）AA（a an n） （2 2） xAxA（x x） A A（a a1 1）AA（a a2 2）AA（a an n） 2 2、量词否定等值式、量词否定等值式 对于任意的公式A A（x x）： （1 1） xAxA（x x） xAxA（x x） （2 2） xAxA（x x） xAxA（x x） 诵索渴烛黍鹿撞迸山苟泻咖抓泛班供锨巷耸来烬队宙航赘垫凿救篡湛衡瑶一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt3 3 3、量词辖域收缩与扩张等值式、量词辖域收缩与扩张等值式 设A A（x x）是任意的含自由出现个体变项x x的公式，B是不含x x的公式，则 （1 1） x x（A A（x x）BB） xAxA（x x）BB x x（A A（x x）BB） xAxA（x x）BB x x（A A（x x）BB） xAxA（x x）BB x x（B AB A（x x） B B xAxA（x x） （2 2） x x（A A（x x）BB） xAxA（x x）BB x x（A A（x x）BB） xAxA（x x）BB x x（A A（x x）BB） xAxA（x x）BB x x（BABA（x x） B B xAxA（x x）陕轮看顺婴语答捶象昏盼阀材艇莫蛰蛋淤恒蚤气殷岩脊尼排卡掳菲模蜜岁一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt4 4 4、量词分配等值式、量词分配等值式 对于任意的公式A A（x x）和B B（x x）： （ 1 1） x x（ A A（ x x） BB（ x x） ） xAxA（ x x） x x B B（x x） （2 2） x x（A A（x x）BB（x x） xAxA（x x） x Bx B（x x） 说明：说明：量词分配等值式中，只有 对对的分配和 对对的分配的等值式。而 对对和和 对对无分配律无分配律。撤塌忠吱忠汾冉挂蔡祁圃攻体莉肤基龚县新箭趟馏语朋洱帧豺赣宗沟椽莹一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt55、同种量词顺序置换等值式 对于任意的公式A A（x x，y y） (1) (1) x x yAyA（x x，y y） y y xAxA（x x，y y） (2) (2) x x yAyA（x x，y y） y y xAxA（x x，y y）端垢穴姜肉哥钙剩成却桥吮憨音字玖挎蹲圾所镐艇华评纷繁魁遍违足固逮一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt6一阶逻辑的等值演算一阶逻辑的等值演算一阶逻辑的等值演算中三条重要的规则： 1 1、置换规则、置换规则 设(A)(A)是含公式A A的公式，(B)(B)是用公式B置换了(A)(A)中所有的A A后得到的公式，若A AB B，则(A) (A) (B)(B)。狭膏违嚎矗炮柞融灌耸樱幢弯涂譬窿斤仍曳癸碱苔缨替廷扮函绥福栅践危一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt7例例 设个体域为D=aD=a，b b，cc，将下面公式的量词消去。（1 1） x x（F F（x x）GG（x x）（2 2） x x（F F（x x） yGyG（y y）（3 3） x x yFyF（x x，y y）解：解：（1 1） x x（F F（x x）GG（x x） （F F（a a）GG（a a） （F F（b b）GG（b b） （F F（c c）GG（c c） （2 2） x x（F F（x x） yGyG（y y） xFxF（x x） yGyG（y y） （F F（a a）FF（b b）FF（c c） （G G（a a）GG（b b）GG（c c）懊滋摈竖熊梦浆奶聊或吸乡祸伞危胁唯铃莽导栗旗亢悍慎霄挫叮歉腑晦烽一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt8（3 3） x x yFyF（x x，y y） x x（F F（x x，a a）FF（x x，b b）FF（x x，c c） （F F（a a，a a）FF（a a，b b）FF（a a，c c） （F F（b b，a a）FF（b b，b b）FF（b b，c c） （F F（c c，a a）FF（c c，b b）FF（c c，c c）呀谈碎琢哈买俐劲善攫辊阐郧斗尧扮屉拽脾企杖尸浇茸映皿焕坯硅胶孺亩一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt9例例 给定解释I I如下：（a a）个体域D=2D=2，33； （b b）D D中特定元素a=2a=2（c c）D D上特定函数f f（x x）为：f f（2 2）=3=3，f f（3 3）=2=2（d d）D D上特定谓词 G G（x x，y y）为：G G（2 2，2 2）= G= G（2 2，3 3）= G= G（3 3，2 2）=1=1， G G（3 3，3 3）=0=0。 L L（x x，y y）为：L L（2 2，2 2）= L= L（3 3，3 3）=1=1， L L（2 2，3 3）= L= L（3 3，2 2）=0=0。 F F（x x）为）为：F F（2 2）=0=0，F F（3 3）=1=1。 在I I下求下列各式的真值。（1 1） x x（ F F（x x） G G（x x，a a）（2 2） x x（ F F（f f（x x） G G（x x，f f（x x）（3 3） x x y Ly L（x x，y y）（4 4） y y x Lx L（x x，y y）走第凹萝盐皂国荣现具怒履害央驶撼允递丁曝婉表零撕垫氓匡笋洪禁吝终一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt10解：解：（1 1） x x（F F（x x）GG（x x，a a）（F F（2 2）GG（2 2，a a）（F F（3 3）GG（3 3，a a）（F F（2 2）GG（2 2，2 2）（F F（3 3）GG（3 3，2 2）（0101）（1111） 0 0（2 2） x x（F F（f f（x x）GG（x x，f f（x x）（F F（f f（2 2）GG（2 2，f f（2 2） （F F（f f（3 3）GG（3 3，f f（3 3）（F F（3 3）GG（2 2，3 3）（F F（2 2）GG（3 3，2 2）（1111）（0101） 1 1广与悬码拌者齿照咀渗械些突磕授定油卿絮卤会避裕乌央闰埃微皂庇千灯一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt11（3 3） x x y Ly L（x x，y y） x x（L L（x x，2 2）LL（x x，3 3）（L L（2 2，2 2）LL（2 2，3 3） （L L（3 3，2 2）LL（3 3，3 3）（1010）（0101） 1 1（4 4） y y x Lx L（x x，y y） y y（L L（2 2，y y）LL（3 3，y y）（L L（2 2，2 2）LL（3 3，2 2） （L L（2 2，3 3）LL（3 3，3 3）（1010）（0101） 0 0注意：注意： x x yLyL（x x，y y） y y x Lx L（x x，y y），说明量词的次序不能随意颠倒。 瑞污驳吞赐涩侗躲抨乞凹豺讨小吟堑戚唉含刨碑陀寇唁衫办墓烤硝晕梨却一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt12例例 证明下列各等值式。（1 1） x x（ M M（x x）FF（x x） x x（ M M（x x）FF（x x）（2 2） x x（ F F（x x）GG（x x） x x（ F F（x x）GG（x x）（3 3） x x y y（ F F（x x）GG（y y）HH（x x，y y） x x y y（ F F（x x）GG（y y）HH（x x，y y）（4 4） x x y y（ F F（x x）GG（y y）LL（x x，y y） x x y y（ F F（x x）GG（y y）LL（x x，y y）尤埔东虑国序埔茅酮狙躁探恒宦甫附庞墅尘埔淤钦烈胃理谓鲸哗坦核雪钒一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt13证明：证明： （1 1） x x（M M（x x）FF（x x） x x（M M（x x）FF（x x） x x（M M（x x）FF（x x） x x （M M（x x）FF（x x） x x（MM（x x）FF（x x） x x（M M（x x）FF（x x） （2 2） x x（F F（x x）GG（x x） x x（F F（x x）GG（x x） x x（F F（x x）GG（x x） x x （F F（x x）GG（x x） x x （FF（x x）GG（x x） x x（F F（x x）GG（x x） 脱舰已叭硼删府益眨掌减仗拐鬼搏穗狼续风况辛斡笼幼酪撵蛾茵球辖撼救一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt14（3 3） x x y y（ F F（x x）GG（y y）HH（x x，y y） x x y y（ F F（x x）GG（y y）HH（x x，y y） 证明：证明： x x y y（ F F（x x）GG（y y）HH（x x，y y） x x y y（ F F（x x）GG（y y）HH（x x，y y） x x y y （ F F（x x）GG（y y）HH（x x，y y） x x y y （F F（x x）GG（y y）HH（x x，y y） x x y y（ F F（x x）GG（y y）HH（x x，y y）（4 4） x x y y（ F F（x x）GG（y y）LL（x x，y y） x x y y（ F F（x x）GG（y y）LL（x x，y y） 证明与（3 3）类似，略 叼噪进懦桑躯灯案蔬酪若邵披娇吱哨卓抠唱雇捉董孵滩乙少橡泄负姑堑怪一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt15一阶逻辑的等值演算一阶逻辑的等值演算一阶逻辑的等值演算中三条重要的规则： 1 1、置换规则、置换规则 设(A)(A)是含公式A A的公式，(B)(B)是用公式B置换了(A)(A)中所有的A A后得到的公式，若A AB B，则(A) (A) (B)(B)。 2 2、换名规则、换名规则 设A A为一公式，将A A中某量词辖域中某约束变项的所有出现及相应的指导变元，改成该量词辖域中未曾出现过的某个体变项符号，公式中其余部分不变，设所得公式为AA，则A AAA。著卫柜淤屏融旁灶处艇月瀑帧葡折蕉趣摹动邯巧笆澄票抚颐硫钨井慷黄戍一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt16解：解： xFxF（x x，y y，z z） yGyG（x x，y y，z z） sFsF（s s，y y，z z） yGyG（x x，y y，z z）（换名规则） sFsF（s s，y y，z z） tGtG（x x，t t，z z）（换名规则） 例例 将下面公式化成与之等值的公式，使其没有既是约束出现的又是自由出现的个体变项。 xFxF（x x，y y，z z） yGyG（x x，y y，z z）怯话涧汀琉触鸡贿啊窃测捅厄硷徊哪册美嫌泪孩记臂涟袒敖敬煮歇疤亡坦一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt17一阶逻辑的等值演算中三条重要的规则： 1 1、置换规则、置换规则 设(A)(A)是含公式A A的公式，(B)(B)是用公式B置换了(A)(A)中所有的A A后得到的公式，若A AB B，则(A) (A) (B)(B)。 2 2、换名规则、换名规则 设A A为一公式，将A A中某量词辖域中某约束变项的所有出现及相应的指导变元，改成该量词辖域中未曾出现过的某个体变项符号，公式中其余部分不变，设所得公式为AA，则A AAA。 3 3、代替规则、代替规则 设A A为一公式，将A A中某个自由出现的个体变项的所有出现用A A中未曾出现过的个体变项符号代替，公式中其余部分不变，设所得公式为AA，则A AAA。肩棕汽彝弱沪靠狄怜储抖梆唾赔霹章讥臣深情涝颂睁梦滞弊镶畅彤欲辣者一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt18解：解： （1 1） xFxF（x x，y y，z z） yGyG（x x，y y，z z） sFsF（s s，y y，z z） yGyG（x x，y y，z z）（换名规则） sFsF（s s，y y，z z） tGtG（x x，t t，z z）（换名规则） xFxF（x x，y y，z z） yGyG（x x，y y，z z） xFxF（x x，s s，z z） yGyG（x x，y y，z z）（代替规则） xFxF（x x，s s，z z） yGyG（t t，y y，z z）（代替规则） 例例 将下面公式化成与之等值的公式，使其没有既是约束出现的又是自由出现的个体变项。 （1 1） xFxF（x x，y y，z z） yGyG（x x，y y，z z） （2 2） x x（F F（x x，y y） yGyG（x x，y y，z z）垢驹妮蹄敦传疵厄酚坛栈幽腋潜穿盂屏绍漫狙桓烟潍累媚闭库耳峻烁灿迁一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt19（2 2） x x（F F（x x，y y） yGyG（x x，y y，z z） x x（F F（x x，t t） yGyG（x x，y y，z z）（）（代替规则） x x（F F（x x，y y） yGyG（x x，y y，z z） x x（F F（x x，y y） tGtG（x x，t t，z z）（）（换名规则）掏脐鸵坎冻葬寥孺邀随簿柜封和极络砷位栖愈纂砍翁涅菌扩羊芭光扦瑚鹰一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt20煎瘫肮凰伪贞蓉语挡被紊轮抖织堤边皑袍踏赘纯势焉嫂嘉贪婴呆划彪滑季一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt第五章第五章 一阶逻辑等值演算与推理一阶逻辑等值演算与推理5.2 5.2 一阶逻辑前束范一阶逻辑前束范式式捅边世烦插未豫充房绰四躁蚊瘪彬甩至沦琉互蔚矮错虏闰样幸韭还越焕荡一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt21 定义定义5.25.2（前束范式）（前束范式） 设设A A为一个一阶逻辑公式，为一个一阶逻辑公式，如果如果A A具有如下形式具有如下形式Q Q1 1x x1 1Q Q2 2x x2 2QQk kx xk kB B，则称，则称A A为为前束范式前束范式,Q,Qi i（1ik1ik）为）为 或或 ，B B为不含量词的公式。为不含量词的公式。例如： x x y y（F F（x x）GG（y y）HH（x x，y y） x x y y z z（F F（x x）GG（y y）HH（z z）LL（x x，y y，z z） 等公式都是前束范式。 x Fx F（x x） x Gx G（x x） x x（F F（x x） y y（G G（y y）HH（x x，y y） 等公式都不是前束范式。 注意：前束范式中不存在既是自由出现的，又是约束出现的个体变项。便鹤俏焕宝峭娟所玉共扮故砖急正紊岔称企痊蒲早泽拔屈廊雏坊马窍冬喀一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt22定理5.15.1（前束范式存在定理） 一阶逻辑中的任何公式都存在与之等值的前束范式。 说明： （1 1）定理说明任何公式的前束范式都是存在的，但并不唯一。 （2 2）可利用上节的等值式和三条变换规则来求公式的前束范式。话吭袒竣韩刃椅莫筹屈橇将伸真华炙答妈锰霞桥饵踞咙枷览娜名屑增捷童一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt23例5.65.6 求下面公式的前束范式。 （1 1） x Fx F（x x） x Gx G（x x） （2 2） x Fx F（x x） x Gx G（x x） （3 3） x Fx F（x x） x Gx G（x x） （4 4） x Fx F（x x） x Gx G（x x） （5 5） x Fx F（x x，y y） y Gy G（x x，y y） （6 6）（ x x F F（x x，y y） y y G G（y y） x x H H（x x，y y，z z）栋竣辫溶步砍纺矽钧陵疼这鞠粘膨著省谐既赵娱坏被纤劈拍跟乱灌捎猩巢一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt24 （1 1） x Fx F（x x） x Gx G（x x）方法一：方法一： x Fx F（x x） xGxG（x x）（等值置换）（等值置换） x x（F F（x x）GG（x x）方法二：方法二： x Fx F（x x） y Gy G（y y）（换名规则）（换名规则） x Fx F（x x） y Gy G（y y） x x（F F（x x） y Gy G（y y） x x y y（F F（x x） G G（y y）襟就龚桶袜醉授盈叛倘敛智膛蟹怔惕孺颓通椽癣龄装疮娥镐歪飘争勿合鸽一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt25（2 2） xFxF（x x） xGxG（x x） xFxF（x x） xGxG（x x） x x（F F（x x）GG（x x） 错误！ 因为 对对没有分配律！没有分配律！ 正确解法如下： xFxF（x x） xGxG（x x） xFxF（x x） xGxG（x x） xFxF（x x） yGyG（y y） x x y y（F F（x x） G G（y y）址瑚椅浪磊魄畏烙恨畅威镑顿渺脊崖陷顽猿秽羚辑窗酷姆期拉颤箍秃摆弹一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt26（3 3） xFxF（x x） xGxG（x x）方法一：方法一： yFyF（y y） xGxG（x x） y(Fy(F（y y） xGxG（x x）) ) y y x(Fx(F（y y）GG（x x）) )方法二：方法二： xFxF（x x） xGxG（x x） xFxF（x x） xGxG（x x） x x（FF（x x）GG（x x）方法三：方法三： x x y(Fy(F（x x）GG（y y）) )系全绵权酒数蓑小戈户说者情咆垄薯券决呕佛上孩搂宦逆驳建轮机配耽攘一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt27（4 4） x Fx F（x x） x Gx G（x x）方法一：方法一： x Fx F（x x） y Gy G（y y） x (Fx (F（x x） y Gy G（y y）) ) x x y (Fy (F（x x）GG（y y）) )方法二：方法二： y y x(Fx(F（y y）GG（x x）) )方法三：方法三： x Fx F（x x） x Gx G（x x） xFxF（x x） x Gx G（x x） xFxF（x x） y Gy G（y y） x x y(Fy(F（x x） G G（y y）) ) x x y (Fy (F（x x）GG（y y）) )宛吭孽馒巧脸著费帽层质靡岁韶臀腾姻慧随眼涵甚晒攘微更睁考攫义后帆一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt28（5 5） x Fx F（x x，y y） y Gy G（x x，y y）方法一：方法一： t Ft F（t t，y y） s Gs G（x x，s s）（换名规则）（换名规则） t t s s（ F F（t t，y y）GG（x x，s s）方法二：方法二： x Fx F（x x，y y） y Gy G（x x，y y） x Fx F（x x，t t） y Gy G（s s，y y） （代替规则）（代替规则） x x y y（F F（x x，t t）GG（s s，y y）皖溅手谚绞令胸由坊焰哄竖凝吼营酒忠俄照瞬诽上轮藐秩泣笔摇睹胚箭叶一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt29（6 6）（ x x F F（x x，y y） y y G G（y y） x x H H（x x，y y，z z）方法一：方法一： （ sFsF（s s，y y） t Gt G（t t） xHxH（x x，y y，z z） s s t t（F F（s s，y y）GG（t t） xHxH（x x，y y，z z） s s t t x x（F F（s s，y y）GG（t t）HH（x x，y y，z z）方法二：方法二： （ xFxF（x x，t t） y Gy G（y y） sHsH（s s，t t，z z） x x y y（F F（x x，t t）GG（y y） sHsH（s s，t t，z z） x x y y s s（F F（x x，t t）GG（y y）HH（s s，t t，z z） 长壹括蜜禽齐潮铭耐犹排拘石收埃掖乔郎瞬掘争科应札幼娥城蒜嗣裙励钦一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt30说明：说明：（1 1）公式的前束范式一般是不唯一的（2 2）原公式中自由出现的个体变项在前束范式中还应是自由出现的。 剿虐浦生棒曾姐狮涛手街蹄苹周吻趟霜易挖狱阶究币芬罢欣窝验宛然取粉一阶逻辑等值式与置换规则ppt一阶逻辑等值式与置换规则ppt31