离散件2-命题公式的蕴含.ppt

第五节命题公式的蕴含 一 定义 设A和B是两个WFF 如果在任何解释下 当A取值1时 B也取值1 就说A蕴含B A蕴含B记为A B 2 A B当且仅当A B是永真式 证明要点 当A B时 A取值1 B必取值1 因而A B恒取值1 即A B是永真式 反过来 当A B是永真式时 A取值1时 必然B取值1 从而A B 3 A B当且仅当A B且B A 二 判定A B的常用方法 1 按照定义 考察对任何使A取值1的解释是否都能使B也取值1 2 考察对任何使B取值0的解释是否都能使A也取值0 例 检查 P Q R R Q是否成立 解 先按第一种方法进行判断 PQR P Q RR Q0001101011100111101111111由此可见 蕴含式成立 再按第2种方式进行判别 PQR P Q RR Q0010010100下面的解释在判别中可以不考虑01101 三 几个基本蕴含式 1 P Q P P Q Q 简化法则 2 P P Q Q P Q 扩充法则 3 P 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 如果A C且B C 则A B C注意 由简化法则和扩充法则 也可导得A B C 6 A B C当且仅当A B C注 这个性质很重要 是CP规则的依据 使我们能把证明A B C转化为证明A B C 四 蕴含的基本性质 续 7 A B当且仅当A B是矛盾式注 这个性质为反证法提供了依据 8 A B当且仅当 B A注 这个性质表达了逆向思维原理 是另一种反证法形式 作业 习题一15 2 4 18 第六节命题逻辑的推理 一 定义1 设A1 A2 An B都是WFF 如果A1 A2 An B 就说B是前提A1 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 B C转化成证明A1 A2 An B C 三 推理的规则 1 直接法直接由前提出发利用规则推出结论的过程2 间接法又分两种方式1 第一种是反证法 把要证明的结论否定后加入前提 推出矛盾的过程 2 第二种是采用CP规则进行证明 这种方法常用于结论是条件式的情形 把条件式前件作为附加前提与原有前提一起推出后件即可 不同的证明方法有不同的效率 下面用例子说明 四 推理方法 例 证明A B D A C B C D 证明一 采用直接法序号公式采用规则 A CP C ATE A B D P C B D TI B C D TE BP C DTI 证毕 证明二 采用CP规则证明A B D A C B C D序号公式采用规则 A CP CP 附加 ATI A B D P B DTI BP DTI C DCP 证毕 例 证明A B D A C B C D 证明三 反证法 这时要把结论否定后作为附加前提 与原有前提一起推出矛盾 因为 C D C D 可以得到C和 D两个附加前提 证明序号公式采用规则 A CP CP 附加 ATI A B D P B DTI BP DTI DP 附加 证毕 例 证明A B D A C B C D 五 消解法应用于命题逻辑推理 消解法是基于反证法的一种机械推理方法 消解是指当子句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