山东科技大学离散数学离散数学15

1、离 散 数 学Discrete Mathematics Email:二零一零年三月1上次课内容回顾析取范式主析取范式合取范式主合取范式小项大项2第一章 第5讲 18 推理理论在数学和其它自然科学中，经常要考虑从某些前提A1，A2，An能够推导出什么结论。例如：从分子学说，原子学说，能够得到什么结论；从光的波动学说，能得到什么结论。我们一般地要对“假设”的内容作深入分析，并推究其间的关系，从而得到结论。但也有一些推理，只需分析假设中的真值和联结词，便可获得结论。 3 在数理逻辑中，集中注意的是研究和提供用来从前提导出结论的推理规则和论证原理，这些规则有关的理论称为推理理论。 在实际应用的推理中，

2、我们常常把本门学科的一些定律、定理和条件，作为假设前提，尽管这些前提在数理逻辑中实非永真，但在推理过程中，却总是假设这些命题为T，并使用一些公认的规则，得到另外的命题，形成结论，这种过程就是论证。 注意，必须把推理的有效性和结论的真实性区别开。 4一、有效结论1. 定义 定义1-8.1 设A和C是两个命题公式，当且仅当AC为一重言式，即A C，称C是A的有效结论。或C可由A逻辑地推出。3 . 论证过程 判别有效结论的过程就是论证过程。2. 推广 有效结论定义可以推广到有n个前提的情况。 设H1，H2，Hn，C是命题公式，当且仅当 H1H2Hn C (A)称C是一组前提H1，H2，Hn的有效结论

3、。5二、证明方法1. 真值表法2. 直接证法3. 间接证法6二、证明方法1. 真值表法2. 直接证法3. 间接证法71. 真值表法设P1，P2，Pn是出现于前提H1，H2，Hn和结论C中的全部命题变元，假定对P1，P2，Pn作了全部的真值指派，这样就能对应地确定H1，H2，Hn和C的所有真值，列出这个真值表，即可看出(A)式是否成立。H1，H2，Hn真值均为T的行，对于每一个这样的行，若C也有真值T，则(A)式成立；或者看C的真值为F的行，在每一个这样的行中，H1，H2，Hn的真值至少有一个为F，则(A)式也成立。8例题1 一份统计表格的错误或者是由于材料不可靠，或者是由于计算有错误；这份统计

4、表格的错误不是由于材料不可靠，所以这份统计表格是由于计算有错误。解 设各命题变元为 P：统计表格的错误是由于材料不可靠。 Q：统计表格的错误是由于计算有错误。 本例可译为：Q是前提PQ，P的有效结论，即 P(PQ) Q9我们列出真值表1-8.1如下PQPQPTT T FTF T FFT T TFF F T 从表上看到只有在第三行PQ和P的真值都为T，这时Q的真值亦为T。故 (PQ)(P) Q 成立。 或者考察Q的真值为F的情况，在第二行和第四行，其相应的PQ或P中至少有一真值为F，故亦说明 (PQ)(P) Q成立。 10例题2 如果张老师来了，这个问题可以得到解答，如果李老师来了，这个问题也可

5、以得到解答，总之张老师或李老师来了，这个问题就可得到解答。解 若设 P：张老师来了。 Q：李老师来了。 R：这个问题可以得到解答。 上述语句可翻译成下述命题关系式 (PR)(QR)(PQ) R11列出真值表PQRPRQRPQTTT T T TTTF F F TTFT T T TTFF F T TFTT T T TFTF T F TFFT T T FFFF T T F 从真值表看到，PR，QR，PQ的真值都为T的情况为第一行、第三行和第五行，而在这三行中R的真值均为T。故 (PR)(QR)(PQ) R12真值表法证明前真：看后真；后假：前至少有一个假。13二、证明方法1. 真值表法2. 直接证法

6、3. 间接证法14 2. 直接证法 直接证法就是由一组前提，利用一些公认的推理规则，根据已知的等价或蕴含公式，推演得到有效的结论。 真值表法是把所给前提一起使用，而直接证法则是不断使用前提和前面推出的结论，构成推导序列，是把前提一步一步拿来使用。P规则 前提在推导过程中的任何时候都可以使用。 T规则 在推导中，如果有一个或多个公式重言蕴含着公式S，则公式S可作为条件引入推导之中。15常用的蕴含式（43页表1-8.3）I1PQ PI9P,Q PQI2PQ QI10P,PQ QI3P PQI11P,PQ QI4Q PQI12Q,PQ PI5P PQI13PQ, QR PRI6Q PQI14PQ,P

7、R,QR RI7(PQ) PI15AB (AC)(BC)I8(PQ) QI16AB (AC)(BC)16常用的等价式(43页表1-8.4)E1P PE12R (PP) RE2PQ QPE13R (P P) RE3P Q Q PE14R (P P) TE4(PQ) R P (QR)E15R (PP) TE5(P Q) R P (Q R)E16PQ P QE6P (Q R) (PQ) (PR)E17(P Q) PQE7P (QR) (P Q) (P R)E18PQ Q PE8(PQ) P QE19P (QR) (PQ) RE9(P Q) P QE20P Q (PQ) (QP)E10P P PE21

8、P Q (PQ) (P Q)E11PP PE22(P Q) P Q17例题1 证明 (PQ) (PR)(QS) SR(8) SR T(7) E(7) SR T(5),(6) I(6) PR P(5) SP T(4) E(4) PS T(2) ,(3) I(3) QS P(2) PQ T(1) E证法1(1) PQ P18例题1 证明 (PQ) (PR)(QS) SR证法2 (1) PR P (2) PQ RQ T(1) I (3) QS P (4) QR SR T(3) I (5) PQ SR T(2),(4) I (6) PQ P (7) SR T(5),(6) I 19例题2 证明 (WR

9、) V ,VCS,SU, C U W (13) W T(12) I(12) W R T(11) E (11) (WR) T(7),(10) I(10) (WR) CS T(8),(9) I(9) VCS P(8) (WR) V P(7) (CS) T(6) E(6) C S T(4),(5) I(5) C T(1) I(4) S T(2) ,(3) I(3) SU P (2) U T(1) I证明(1) C U P20二、证明方法1. 真值表法2. 直接证法3. 间接证法213. 间接证法(1)定义 定义1-8.2 假设公式H1，H2，Hn 中的命题变元为P1，P2，Pn ，对于P1，P2，P

10、n的一些真值指派，如果能使H1 H2 Hn的真值为T，则称公式H1，H2，Hn 是相容的。如果对于P1，P2，Pn的每一组真值指派使得H1 H2 Hn的真值均为F，则称公式H1，H2，Hn是不相容的。22(2)证法 可以把不相容的概念应用于命题公式的证明。 设有一组前提H1，H2，Hn ，要推出结论C，即证H1 H2 Hn C，记作S C，即C S为永真，或CS为永真，故C S为永假 。因此要证明H1 H2 Hn C，只要证明H1，H2，Hn与是C是不相容的。即假定C为真，推出矛盾。23例题3 证明 AB， (BC)可逻辑推出A(7) B B(矛盾) T(3),(6) I(6) B T(5)

11、I(3) B T(1),(2) I(5) B C T(4) E(4) (BC) P(2) A P(附加前提)(1) AB P证明24例题4 证明 (PQ) (PR)(QS) SR(13) (P R) (P R)(矛盾) T(9),(12) I(12) (P R) T(11) E(11) PR T(10) E (10) P R P (9) P R T(2),(8) I(8) (S R ) (P R ) T(7) I(7) S P T(6) E(6) P S T(4),(5) I(5) Q S P(4) P Q T(3) E(3) PQ P(2) S R T(1) E(1) (SR) P(附加前提

12、)证明25(3) CP规则（ 结论为R C时使用） 间接证法的另一种情况是：若要证H1 H2 Hn (R C)。 设H1 H2 Hn 为S ，即证S (R C) 或S ( RC)，故S ( RC)为永真式。因为S ( RC) S( RC) (S R)C (S R)C (S R) C，所以若将R作附加前提，如有(S R) C，即证得S (RC)。 由(S R) C，证得S (RC)称为CP规则。26例题5 证明 A(BC)，DA ，B 重言蕴含DC(8) DC CP(7) C T(5),(6) I (6) B P (5) BC T(3),(4) I(4) A(BC) P (3) A T(1),(

13、2) I(2) DA P(1) D P(附加前提)证明27例题6 设有下列情况，结论是否有效？ (a)或者是天晴，或者是下雨。 (b)如果是天晴，我去看电影。. (c)如果我去看电影，我就不看书。 结论：如果我在看书则天在下雨。 (1) R P(附加前提) (2) S R P (3) R S T(2) E (4) S T(1),(3) I (5) M S P (6)M T(4),(5) I (10) (M Q) (Q M) T(9) E (11) Q M T(10) I(12) M Q T(11) E(13) Q T(6),(12) I(14) RQ CP(8) ( M Q) T(7) E(9

14、) M Q T(8) E(7) MQ P 解 若设M：天晴。 Q：下雨。 S：我看电影。R：我看书。故本题即证：M Q，MS，S R，推出RQ28真值表法：前真：看后真；后假：前至少有一个假。直接证法：由一组前提，利用一些公认的推理规则，根据已知的等价或蕴含公式，推演得到有效的结论。间接证法要证明H1 H2 Hn C，只要证明H1，H2，Hn与是C是不相容的。要证明H1 H2 Hn (R C)。 如能证明H1 H2 Hn R C，即证得H1 H2 Hn (RC)。这个证明称为CP规则。命题推理方法29作业P46-P47(1)a、b(2)a、c、e(3)a、c(4)b、c30第一章 内容回顾一、知识点1命题的概念、表示方法；联结词的逻辑意义。2命题公式的递归定义，自然语言翻译成命题