离散数学(第8讲)谓词逻辑3

《离散数学(第8讲)谓词逻辑3》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章一阶谓词逻辑(3)栾新成四川大学软件学院luanxch@sina.com8599782213808024081主要内容1、谓词公式的蕴涵2、谓词逻辑的推理方法3、消解(归结)法2021年10月4日2谓词公式的蕴涵定义2-4.1：设A和B是以D为论域的两个谓词公式,如果在任一解释下,当公式A取值真(1)时,公式B也取值真(1),则称A蕴涵B,记作AB定理2-4.1：ABiifAB是永真式。2021年10月4日3谓词公式的蕴涵I1：PP∨Q，QP∨Q～PP→Q，QP→Q（扩充法则(析取引入律)I2：P∧QP，P∧QQ～（P→Q）P，～（P→Q）～Q（化

2、简法则(合取消去律)I3：P∧（P→Q）Q（假言推论（分离规I4：～Q∧（P→Q）～P（否定式假言推论（拒取式）2021年10月4日4I5：～P∧（P∨Q）Q析取三段论（选言三段论）I6：（P→Q）∧（Q→R）P→R假言（前提条件）三段论I7：（P∨Q）∧（P→R）∧（Q→R）R二难推论I8：（P→Q）∧（R→S）（P∧R）→（Q∧S）I9：（PQ）∧（QR）PRI10：（P∨Q）∧（～P∨R）Q∨R归结原理2021年10月4日5蕴涵定律I11:(x)P(x)∨（x）Q(x)（x）(P(x)∨Q(x))I12:(x)(P(x)∧Q(x))（

3、x）P(x)∧（x）Q(x)I13:(x)(P(x)→Q(x))(x)P(x)→(x)Q(x)I14:(x)P(x)→（x）Q(x)（x）(P(x)→Q(x))I15:(x)(P(x)Q(x))(x)P(x)(x)Q(x)2021年10月4日6蕴涵定律I14的证明:（x）P(x)（x）Q(x)（～x）P(x)∨（x）Q(x)（x）～P(x)∨（x）Q(x)（x）(～P(x)∨Q(x))（x）(P(x)Q(x))2021年10月4日7蕴涵定律例4.11）设G(x)：x是高才生；H(x)：x是运动健将。其中：个体域是某班的

4、学生则(x)G(x)∨(x)H(x)表示：“该班的所有学生是高才生或该班的所有学生是运动健将”；(x)(G(x)∨H(x))表示：“该班的所有学生是高才生或是运动健将”。显然，前者可推出后者，但反之则不然。即有I11:(x)G(x)∨(x)H(x)(x)(G(x)∨H(x))。2021年10月4日8蕴涵定律2)设G(x)：x是高才生；H(x)：x是运动健将。其中：个体域是某班的学生。则(x)(G(x)∧H(x))表示：“该班的一些学生既是高才生又是运动健将”；(x)G(x)∧(x)H(x)表示：“该班的一些学生是高才生且该班的一些学生是运动健将”。显然，前

5、者可推出后者，但反之则不然。即有I12:(x)(G(x)∧H(x))(x)G(x)∧(x)H(x)2021年10月4日9两个量词的蕴涵式I16:xyP(x,y)yxP(x,y)I17:yxP(x,y)xyP(x,y)I18:yxP(x,y)xyP(x,y)I19:xyP(x,y)yxP(x,y)I20:xyP(x,y)yxP(x,y)I21:yxP(x,y)xyP(x,y)I22:xyP(x,y)xyP(x,y)I23:yxP(x,y)yxP(x,y2021年10月4日10两个量词的蕴涵式

6、上述结论的量词关系可用如下图表示：2021年10月4日E41E40(x)(y)(y)(x)I16I17(y)(x)(x)(y)I23I18I19(x)(y)(y)(x)I22I20I21(y)(x)(x)(y)11谓词逻辑的推理方法同在命题逻辑中一样，谓词逻辑主要的推理规则有：①P规则（称为前提引用规则）：在推导的过程中，可随时引入前提集合中的任意一个前提；②Ｔ规则（逻辑结果引用规则）：在推导的过程中，利用基本等价式和蕴涵式，由证明过程中某些中间公式变换出新的公式，若依据的是等价式，规则标明为TE，若依据的是蕴涵式，规则标明为TI。③ＣＰ规则（

7、附加前提规则）：如果能从给定的前提集合G与公式P推导出S，则能从此前提集合G推导出P→S。即G1,G2,…,GnP→S当且G1,G2,…,Gn，PS2021年10月4日12推理规则量词的四条重要的推理规则：US(全称指定规则)：(x)G(x)G(y)①(UniversalSpecify)(x)G(x)G(c)②ES(存在指定规则)：(x)G(x)G(c)③(ExistentialSpecify)UG(全称推广规则)：G(y)(x)G(x)④(UniversalGeneralize)E