离散数学DISCRETE MATHEMATICS-精选.ppt

本次课重点 命题逻辑的推理 * 第六节 命题逻辑的推理 一、定义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。 (E = EQUIVALENCY I=IMPLICATION) * 3。CP规则 结论转作前提规则。 适用于结论为条件式时，把条件式前件 转变成附加的前提后证明出后件的情况。 也就是把 A1，A2，?，An ? B?C 转化成证明A1，A2，?，An，B ?C。 * 四、推理方法 1。直接法 直接由前提出发利用规则推出 结论的过程 2。间接法 又分两种方式 1） 第一种是反证法，把要证明的结论否 定后加入前提，推出矛盾的过程。 * 2）第二种是采用C P规则进行证明。 这种方法常用于结论是条件式的情形， 把条件式前件作为附加前提与原有前 提一起推出后件即可。 不同的证明方法有不同的效率，下面 用例子说明。 * 例：证明 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 ⑺