一阶逻辑等值式.ppt

一阶逻辑等值式福建师范大学数学与计算机科学学院愤臂涪烦城下惭你决佑儡迢粟草疚踏靴婚牺席糊敖泥尖阅俘丢霸宅召钟奄一阶逻辑等值式一阶逻辑等值式一阶逻辑等值式与置换规则在一阶逻辑中,有些命题可以有不同的符号化形式。例如:没有不犯错误的人 令M(x):x是人。F(x):x犯错误。 则将上述命题的符号化有以下两种正确形式: (1)┐x(M(x)∧┐F(x)) (2)x(M(x)→F(x))我们称(1)和(2)是等值的。,B是一阶逻辑中任意两个公式,若AB是永真式,则称A与B是等值的。记做AB,称AB是等值式。例如:判断公式A与B是否等值,等价于判断公式AB是否为永真式,即在任何解释下都是真的。谓词逻辑中关于联结词的等值式与命题逻辑中相关等值式类似。说明途溺继营片甭莽震箱众动赁易耳徐啡恬滞厢诚拌铆涩慷廉勃叹自芋愉践荤一阶逻辑等值式一阶逻辑等值式一阶逻辑中的一些基本而重要等值式代换实例消去量词等值式量词否定等值式量词辖域收缩与扩张等值式量词分配等值式纵咨钟圣昼滚零极爸耀租悸陨撅萍翱铅蜕锯俭潭疚搭粹狈傻倒瞎拒蒲凤眠一阶逻辑等值式一阶逻辑等值式代换实例由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永真式,。例如: (1)xF(x)┐┐xF(x) (双重否定律) (2)F(x)→G(y)┐F(x)∨G(y) (蕴涵等值式) (3)x(F(x)→G(y))→zH(z) ┐x(F(x)→G(y))∨zH(z)  (蕴涵等值式)且审霍柄唇乌炙诚酸锤障籍陇匣叠播孤酥墨阅兜游嫁蘑坷植支雪赶婪寸鞋一阶逻辑等值式一阶逻辑等值式消去量词等值式设个体域为有限集D={a1,a2,…,an},则有(1)xA(x)A(a1)∧A(a2)∧…∧A(an)(2)xA(x)A(a1)∨A(a2)∨…∨A(an)()遮售赐勃忍瞧始版辐倪***膛移泅夏阀洛福麻贷滁酶藤宰爷排淋邦院吴耶几一阶逻辑等值式一阶逻辑等值式量词否定等值式设A(x)是任意的含自由出现个体变项x的公式,则(1)┐xA(x)x┐A(x)(2)┐xA(x)x┐A(x)说明“并不是所有的x都有性质A”与“存在x没有性质A”是一回事。”不存在有性质A的x”与”所有X都没有性质A”是一回事。()灰争除蝗性畦人使芒草央娠棠挡叭锄识植墅皿耀囚哺杆茄蛤赤牢营搞药滥一阶逻辑等值式一阶逻辑等值式量词辖域收缩与扩张等值式设A(x)是任意的含自由出现个体变项x的公式,B中不含x的出现,则(1)x(A(x)∨B)xA(x)∨B x(A(x)∧B)xA(x)∧B x(A(x)→B)xA(x)→B x(B→A(x))B→xA(x)(2)x(A(x)∨B)xA(x)∨B x(A(x)∧B)xA(x)∧B x(A(x)→B)xA(x)→B x(B→A(x))B→xA(x)从左到右辖域收缩从右到左辖域扩张小心使用蕴涵式前件的收缩扩张纶磁梦怯谋五告瓮粪俏付引盐恢完瓣舜了淀肢赃谨余化界疟镍兜同啤罚绣一阶逻辑等值式一阶逻辑等值式证明:xA(x)→Bx(A(x)→B)xA(x)→B┐xA(x)∨Bx┐A(x)∨Bx(┐A(x)∨B)(量词辖域的扩张)x(A(x)→B)轩脚楷齐范勺簿税懒勘赫谈质莉猪伺秋蒲脾华吞寂阴樊饱思础霉俯砾题雅一阶逻辑等值式一阶逻辑等值式量词分配等值式设A(x),B(x)是任意的含自由出现个体变项x的公式,则(1)x(A(x)∧B(x))xA(x)∧xB(x)(2)x(A(x)∨B(x))xA(x)∨xB(x)对∧分配对∨分配例如,“联欢会上所有人既唱歌又跳舞”和“联欢会上所有人唱歌且所有人跳舞”,这两个语句意义相同。故有(1)式。由(1)式推导(2)式 x(A(x)∧B(x))xA(x)∧xB(x) x(┐A(x)∧┐B(x))x┐A(x)∧x┐B(x) ┐x(A(x)∨B(x))┐(xA(x)∨xB(x)) x(A(x)∨B(x))xA(x)∨xB(x)叠薄季矫掏普愈朝翻过吼婚钡挞果贼亿析苫尧怜拢沮届鼻笑享媒坦吱冉寸一阶逻辑等值式一阶逻辑等值式