交大数理逻辑课件5-3 谓词逻辑的等值和推理演算.ppt

《交大数理逻辑课件5-3 谓词逻辑的等值和推理演算.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、调课通知因下周五(11月12日)为广州亚运会开幕式官方放假时间，<数理逻辑>课程调到下周三(11月10日)5,6节在310305课室上课，特告之。证栽犀撤珊傅锋嘲伙辙位烂澳伙极潭皱据夜润剃魁耕立励销飘脏日那逊砸交大数理逻辑课件5-3谓词逻辑的等值和推理演算交大数理逻辑课件5-3谓词逻辑的等值和推理演算第5章谓词逻辑的等值和推理演算5.1否定型等值式5.2量词分配等值式5.3范式5.4基本的推理公式5.5推理演算5.6谓词逻辑的归结推理法剂挺陕玻佳簧泪扶慎嘶芽磕卖霞匹闹容瞩横焰王脓挖造扇渊壕烬置如脐潞交大数理逻辑课件5-3谓词逻辑的等值和推理演算交大数理逻

2、辑课件5-3谓词逻辑的等值和推理演算推理规则(1)前提引入规则(2)结论引入规则(3)置换规则(4)假言推理规则(A®B)ÙAÞB(5)附加规则AÞ(AÚB)(6)化简规则(AÙB)ÞA(7)拒取式规则(A®B)ÙØBÞØA(8)假言三段论规则(A®B)Ù(B®C)Þ(A®C)(9)析取三段论规则(AÚB)ÙØBÞA(10)构造性二难推理规则(A®B)Ù(C®D)Ù(AÚC)Þ(BÚD)(11)合取引入规则A,BÞAÙB板虚徒声躇气峡绅铸虱等患见睁畅儿凉并袭怖宵袄吻奋丸县道地烈麻惧隐交大数理逻辑课件5-3谓词逻辑的等值和推理演算交大数理逻辑课件5-3谓词

3、逻辑的等值和推理演算有关量词的推理规则全称量词消去规则（UI规则）全称量词引入规则（UG规则）存在量词引入规则（EG规则）存在量词消去规则（EI规则）乌糜黑差跃景利捧暇犊甲些刺枪私抓础飘暂粳铁祟作短罢驻埔瞬星漓彪第交大数理逻辑课件5-3谓词逻辑的等值和推理演算交大数理逻辑课件5-3谓词逻辑的等值和推理演算使用推理规则的推演算举例前提:(x)P(x)(x)(P(x)∨Q(x))R(x))，(x)P(x)结论：(x)(y)(R(x)∧R(y))证明：①(x)P(x)(x)(P(x)∨Q(x))R(x))前提引入②(x)P(x)前提引入

4、③(x)(P(x)∨Q(x))R(x))①②分离④P(c)②EI⑤(P(c)∨Q(c))R(c)③UI⑥P(c)∨Q(c)④附加规则⑦R(c)⑤⑥分离⑧(x)R(x)⑦EG⑨(y)R(y)⑦EG⑩(x)R(x)∧(y)R(y)⑧⑨合取规则⑾(x)(y)(R(x)∧R(y))⑩置换冀鼻琅赚榨嚷札疮滑含贱秘侥较怪出效冕砧槽岂逞岳伙脊啮泞荒兴尝蚕耘交大数理逻辑课件5-3谓词逻辑的等值和推理演算交大数理逻辑课件5-3谓词逻辑的等值和推理演算证明:(x)(H(x)→M(x))，(x)H(x)(x)M(x)证明：①(x)H(x)前提引入②

5、H(c)①EI③(x)(H(x)→M(x))前提引入④H(c)→M(c)③UI⑤M(c)②④分离⑥(x)M(x)⑤EG若把①,②写在③,④的后面，得到如下的推理：①(x)(H(x)→M(x))前提引入②H(c)→M(c)①UI③(x)H(x)前提引入④H(c)③EI⑤M(c)②④分离⑥(x)M(x)⑤EG这个推理在逻辑上是错误的。因为②中的c为个体域中一个个体，用EI规则由③推到④不能选择②中的c，因为它要选的个体和②中的个体c不一定是同一个个体，故推理是错误的。黄擦矽私帐访砌靡胆婴瓶番舔丰劣旺阜橙光缘搔崖实趾埂勺苑尔跟甚微仪交大数理逻辑课件5

6、-3谓词逻辑的等值和推理演算交大数理逻辑课件5-3谓词逻辑的等值和推理演算5.6谓词逻辑的归结推理法归结证明法的出发点证明AB是定理，等价于证明A∧ØB=G是矛盾式归结证明过程建立子句集S将G中的全称量词省略，并将G中的合取词∧用“，”表示，得子句集S如：(x)(P(x)∧(y)(D(y)L(x,y)))的子句集S为{P(a),ØD(y)ÚL(a,y)}对S作归结子句：P(x)ÚQ(x)，ØP(a)ÚR(x)作归结，得归结式：Q(a)ÚR(a)并将此归结式仍放入S中，重复此过程直至归结出空子句□，证明结束谭稻效凰丰佬蔑孪遇潦辕饼抄负猖纶甘噬尺卤滩

7、糠艳履沫榜迫谜矾膏遥坎交大数理逻辑课件5-3谓词逻辑的等值和推理演算交大数理逻辑课件5-3谓词逻辑的等值和推理演算归结法证明举例A1=(x)(P(x)∧(y)(D(y)L(x,y)))A2=(x)(P(x)(y)(Q(y)¬L(x,y)))B=(x)(D(x)¬Q(x))¬B=¬(x)(D(x)¬Q(x))=(x)(D(x)∧Q(x))证明A1∧A2B①P(a)前提A1的子句②ØD(y)ÚL(a,y)前提A1的子句③ØP(x)ÚØQ(y)Ú¬L(x,y)前提A2的子句④D(b)前提¬B的子句⑤Q(b)前提¬B的子句⑥L(a,b)

8、②④归结⑦ØQ(y)Ú¬L(a,y)①③归结⑧¬L(a,b)⑤⑦归结⑨□⑥⑧归结