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

第五节 命题公式的蕴含,一、定义：设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 （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，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规则进行证明。这种方法常用于结论是条件式的情形，把条件式前件作为附加前提与原有前提一起推出后件即可。 不同的证明方法有不同的效率，下面用例子说明。,四、推理方法,例：证明 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) （冯伟森）,