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

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

1、调课通知因下周五(11月12日)为广州亚运会开幕式官方放假时间，<数理逻辑>课程调到下周三(11月10日)5,6节在310305课室上课，特告之。第5章谓词逻辑的等值和推理演算5.1否定型等值式5.2量词分配等值式5.3范式5.4基本的推理公式5.5推理演算5.6谓词逻辑的归结推理法推理规则(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)构造性

2、二难推理规则(A®B)Ù(C®D)Ù(AÚC)Þ(BÚD)(11)合取引入规则A,BÞAÙB有关量词的推理规则全称量词消去规则（UI规则）全称量词引入规则（UG规则）存在量词引入规则（EG规则）存在量词消去规则（EI规则）使用推理规则的推演算举例前提:(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)前提引入③(x)(P(x)∨Q(x))R(x))①②分离④P(c)②EI⑤(P(c)∨Q(c))R(c)③

3、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))⑩置换证明:(x)(H(x)→M(x))，(x)H(x)(x)M(x)证明：①(x)H(x)前提引入②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(

4、c)②④分离⑥(x)M(x)⑤EG这个推理在逻辑上是错误的。因为②中的c为个体域中一个个体，用EI规则由③推到④不能选择②中的c，因为它要选的个体和②中的个体c不一定是同一个个体，故推理是错误的。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)

5、并将此归结式仍放入S中，重复此过程直至归结出空子句□，证明结束归结法证明举例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)②④归结⑦ØQ(y)Ú¬L(a,y)①③归结⑧¬L(a,b)⑤⑦归结⑨□

6、⑥⑧归结第二部分集合论引例有10名学生参加一个Party，一共要了8瓶饮料和6个雪糕，已知有1人什么也没要，其他人每种至多要1份，问：最后有多少人既要了饮料又要了雪糕？集合论是现代数学的重要基础，集合不仅可用来表示数及运算，更可用于非数值信息的表示和处理，如：数据的维护、数据间关系的描述，有些很难用传统的数值计算来处理，但可用集合运算来处理，它在计算机科学领域中是不可或缺的数学工具，在形式语言、自动机、人工智能、数据库等领域中都卓有成效地应用了集合论。第二部分主要介绍集合论的基础知识，如集合的基本概念、运算、性质、关系、函数等。第9章集合9.1集合的概念和表示方法9.2集合

7、间的关系和特殊集合9.3集合的运算9.4集合的图形表示法9.5集合运算的性质和证明9.6有限集合的基数9.1集合的概念和表示方法集合是不能精确定义的基本的数学概念。一个集合一般指的是一些可确定的、可分辨的事物构成的整体。集合的元素——集合中的对象或个体。集合的构成——集合可以由各种类型的事物构成。例如：26个英文字母的集合；C++语言中保留字的集合；坐标平面上所有点的集合；方程x2－1＝0的实数解集合；集合的表示法通常用大写英文字母来标记一些集合。例如，N——代表自然数集合(包括0)，Z——代表整数集合，Q——代表