您所在位置：网站首页 > 高等教育 > 其它相关文档四川大学离散数学课件2-命题公式的蕴含

四川大学离散数学课件2-命题公式的蕴含

20页

卖家[上传人]：suns****4568

文档编号：88921386

上传时间：2019-05-13

文档格式：PPT

文档大小：276.50KB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

20 金贝

/ 20 举报版权申诉马上下载

文本预览

下载提示

常见问题

1、第五节命题公式的蕴含,一、定义：设A和B是两个WFF，如果在任何解释下，当A取值1 时，B也取值1，就说A蕴含B。 A 蕴含 B记为 AB。 2. AB当且仅当 AB是永真式。证明要点：当AB时，A取值1，B必取值1，因而AB恒取值1，即AB 是永真式；反过来，当 AB是永真式时，A取值1时，必然B取值1，从而AB。 3. A B当且仅当AB且BA。,二、判定AB的常用方法,1。按照定义，考察对任何使 A取值1的解释是否都能使 B也取值1 。 2。考察对任何使 B取值0的解释是否都能使A也取值0。,例：检查（PQ） RRQ 是否成立？,解: 先按第一种方法进行判断. P Q R （PQ） R RQ 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 1 由此可见，蕴含式成立。,再按第2种方式进行判别,P Q R （PQ） R RQ 0 0 1 0 0 1 0 1 0 0 下面的解释在判别中可以不考虑 0 1 1 0 1,三、几个基本蕴含式,1. P Q P， P Q Q （简化法则） 2. P PQ，Q PQ （扩充法则） 3. P

2、（P Q） Q （假言推理） 4. (P Q) (Q R) ( P R) （假言三段论式）,四、蕴含的基本性质,1. A A (自反性) 2. 如果A B且B A, 则A B (反对称性) 3. 如果A B且B C, 则A C (传递性) 4. 如果A B且A C, 则A B C 注意:由简化法则和传递性，性质4实际包含一个充要条件。,四、蕴含的基本性质（续）,5. 如果 AC 且 BC, 则 A B C 注意：由简化法则和扩充法则，也可导得A B C。 6. A B C当且仅当 A BC 注：这个性质很重要，是CP规则的依据。使我们能把证明 A BC 转化为证明 A B C。,四、蕴含的基本性质（续）,7. A B当且仅当 A B是矛盾式注：这个性质为反证法提供了依据。 8. A B当且仅当 B A 注：这个性质表达了逆向思维原理，是另一种反证法形式。,作业: 习题1.5 1(2)(4), 4 （吴子华） or 习题一 15(2)(4), 18 （冯伟森）,第六节命题逻辑的推理,一、定义1：设A1，A2，An，B都是WFF，如果A1 A2 An B，就说B是前提A1

3、，A2，An的有效结论或逻辑结果。也说由A1，A2，An 推出了B。定义2：设 G 是一个 WFF的集合，A1，A2，An 是一个有限的WFF序列。如果序列中的每个公式 Ai 要么是G中的一个元素，要么是它前面的若干公式的逻辑结果，就说An是G的逻辑结果，或者说由G可以演绎出An。,前面已介绍的基本等价式、基本蕴含式和由蕴含性质导出的基本结果，都可以作为推理的公理集合。,二、推理的公理集合：,1。P规则引入前提规则 2。T 规则变换规则。分两种情形：如果当前结果是由前面公式经过等价变换得到的，就把这个变换规则记为TE。如果是经过蕴含变换得到的，就记为TI。 3。CP规则结论转作前提规则。适用于结论为条件式时，把条件式前件转变成附加的前提后证明出后件的情况。也就是把A1，A2，An BC 转化成证明A1，A2，An，B C。,三、推理的规则：,1。直接法直接由前提出发利用规则推出结论的过程 2。间接法又分两种方式 1）第一种是反证法，把要证明的结论否定后加入前提，推出矛盾的过程。 2）第二种是采用C P规则进行证明。这种方法常用于结论是条件式的情形，把条件式前件作

4、为附加前提与原有前提一起推出后件即可。不同的证明方法有不同的效率，下面用例子说明。,四、推理方法,例：证明 A （B D），A C，B C D,证明一、采用直接法序号公式采用规则 A C P C A TE A （B D） P C （B D） TI B （C D） TE B P C D TI （证毕）,证明二、采用CP规则证明,A （B D），A C，B C D 序号公式采用规则 A C P C P（附加） A TI A （B D） P B D TI B P D TI C D CP （证毕）,证明三、反证法。这时要把结论否定后作为附加前提，与原有前提一起推出矛盾。因为 ( C D )C D，可以得到C和 D两个附加前提。证明 A （B D），A C，B C D 序号公式采用规则 A C P C P（附加） A TI A （B D） P B D TI B P D TI D P(附加) （证毕）,五、消解法应用于命题逻辑推理,消解法是基于反证法的一种机械推理方法。消解是指当子句C1和C2一起恰好含有一对互反的句节时，消去这对互反句节后，由剩余句节构成新子句的过程。例如：由子句 P Q 和 Q R 经消解后得到新子句 P R。,消解法的应用过程如下： 1）把前提中每个公式以及否定后的结论通过化合取范式的办法分解成子句集。 2）如果子句 C1和 C2恰有一对互反的句节，则由消去这对互反句节后的 C1和 C2经析取构成新的子句，并加入子句集。 3）如果重复2）能导出空子句，则得到证明。,例：利用消解法证明A （B D），A C，B C D,解：首先由上式得到子句集G=A B D，A C，B ，C，D 消解过程如下：序号子句说明 A B D 引用子句 A C 引用子句 C B D 由消解 B 引用子句 C D 由消解 C 引用子句 D 由消解 D 引用子句由消解,作业：习题1.6 1(4)(5)，2(2), 4(3) （吴子华） or 习题一 20(4)(5)，21(2), 23(3) （冯伟森）,

《四川大学离散数学课件2-命题公式的蕴含》由会员suns****4568分享，可在线阅读，更多相关《四川大学离散数学课件2-命题公式的蕴含》请在金锄头文库上搜索。

点击阅读更多内容

TA的资源