离散数学-1-8推理理论.ppt

1,第一章 命题逻辑,1-8 推理理论 授课人：李朔 Email:chn.nj.lS,2,在数学和其它自然科学中，经常要考虑从某些前提A1、A2、An出发，能推导出什么结论。 数理逻辑的主要任务是用逻辑的方法研究数学中的推理。所谓推理是指从前提出发，应用推理规则推出结论的思维过程。任何一个推理都由前提和结论两部分组成。前提就是推理所根据的已知命题，结论则是从前提出发通过推理而得到的新命题。 要研究推理，首先应该明确什么样的推理是有效的或正确的,3,一、有效推理,假设一些命题为，并使用一些公认的规则，得到另外的命题，形成结论，这种过程就是论证。 定义1-8.1 设A和C是2个命题公式，当且仅当AC为一重言式，即AC，则称C为A的有效结论。或C可由A逻辑的推出。A叫做C的前提。 上述定义可以推广到n个前提的情况： 设H1，H2，Hn,C是n+1个命题公式,当且仅当 H1H2HnC， 称C是一组前提H1，H2，Hn 的有效结论。 *判断有效结论的过程就是论证过程，基本方法是真值表法、直接证法、间接证法。,4,二、真值表法,由定义1-8.1可以看出，要证明C是一组前提H1，H2，Hn 的有效结论，只需证明H1H2HnC为重言式。而证明一个公式为重言式，可以用真值表、等值演算、主析(合)取范式或已知的蕴含式等方法进行。用等价演算和主析(合)取范式证明重言式的方法前面已经讨论过了，我们已经非常熟悉了。这里仅对真值表法作简单说明。 （1）真值表法 设P1，P2，Pn出现于前提H1，H2，Hm 和结论C的全部命题变元，假定对P1，P2，Pn作了全部的真值指派，这样就能对应地确定H1，H2，Hn 和C的所有真值，列出这个真值表，即可看出 H1H2HmC 是否成立 即找出H1，H2，Hm 均为的行，对于每一个这样的行，若C也为,则上式成立。或C为， H1，H2，Hm 中起码有一个为,5,二、真值表法,例：分析事实：“如果我有时间，那么我就去上街；如果我上街，那么我就去书店买书；但我没有去书店买书，所以我没有时间。”。试指出这个推理前提和结论，并证明结论是前提的有效结论。 解：令 ：我有时间。 ：我去上街。 ：我去书店买书。 根据题意，前提为：， 结论为： 以下证明是一组前提,的有效结论。 即证明：(PQ)(QR)RP,6,二、真值表法,作公式PQ，QR，R，P的真值表 从表中可以看出:PQ，QR，R都为1的行(赋值000的行)，P也为1。 (或P为0的行(赋值100，101，110，111的行) PQ，QR，R至少有一个为0） 所以 (PQ)(QR)RP,7,三、命题逻辑的推理理论,当推理中包含的命题变元较多时，真值表法或等值演算法，主析取范式法等方法的演算量太大。给推理带来了困难。为此引入命题逻辑的推理理论。命题逻辑的推理是一个描述推理过程的命题公式序列，其中的每个命题公式或者是已知前提，或者是由某些前提应用推理规则得到的结论(中间结论或推理中的结论)。它有两种方法：直接证法（直接推理）和间接证法（间接推理）。,8,直接证法（直接推理）, 直接证法（直接推理） 基本思想是：由一组前提出发，利用一些公认的规则，根据已知的等价式或蕴含式，推演得到有效结论。 公认的推理规则有4条： P规则：前提在推导过程中的任何时候都可以引入使用。 T规则：推导中，如果一个或多个公式蕴含着公式S，则 公式S可以引入到以后的推理之中。 置换规则：在推导过程的任何步骤上，命题公式中的子 公式都可以用与之等价的公式置换。(等价式表） 合取引入规则：任意两个命题公式A,B可以推出AB 常用的蕴含式和等价式见P43表1-8.3 表1-8.4,9,直接证法（直接推理）,例题：用直接推理法证明 ()() () 证法1: (1) P -(P规则，引入前提) (2) Q T(1) E -(对(1)式T规则,根据E16蕴含等值式) (3) P -(P规则，引入前提) (4) T(2),(3) I-(对(2),(3)式规则，根据I13 假言三 段论) (5) SP T(4) E -(对()式T规则,根据E16蕴含等值式) (6) P -(P规则，引入前提) (7) SR T(5),(6) I (对(5),(6)式规则，根据I13 假言三段 论) (8) T(7) E -(对(7)式T规则,根据E16蕴含等值式),10,直接证法（直接推理）,证法2: (1) P (2)R T(1) I (3) P (4)R SR T(3) I (5)SR T(2)(4) I (6) P (7) T(5),(6) I,11,直接证法（直接推理）,用直接推理法证明(PQ)(QR)PR 证明： PQ P P P Q T I 假言推理(I11) QR P R T I 假言推理(I11),12,间接证法（间接推理）,定义1-8.2 假设公式H1，H2，Hm中的命题变元P1，P2，Pn，对于P1，P2，Pn的一些真值指派，如果能使H1H2Hm的真值为，则称公式H1，H2，Hm是相容的。如果对于P1，P2，Pn的每一组真值指派，使H1H2Hm的真值均为，则称公式H1，H2，Hm是不相容的。,13,间接证法（间接推理）,将不相容的概念应用于命题公式的证明(归谬法) 设有一组前提H1，H2，Hn ，要推出结论C， 即要证 H1H2Hn C ， 令 SH1H2Hn 则上式可以简记为 SC 由永真蕴含的定义有 1SCSC 两边否定 0SC H1H2HnC 即要证明C是前提H1，H2，Hn的有效结论，只须证明 H1H2HnC0 (即H1，H2，Hn 与 C不相容） 这种间接推理方法称为归谬法,14,间接证法（间接推理）,例题证明，(C)可逻辑推出。 证明： (1) P (2) P(附加前提） (3)(C) P (4)C T(3) E (E9德摩根律) (5)B T(1),(2) I (I11假言推理) (6) T(4) I (I1简化式) (7)(矛盾） T(5),(6)I(I1合取引入 规则),15,间接证法（间接推理）,CP规则 间接证法的另一种情况：要证H1H2Hn()。 设SH1H2Hn，则上式可以简记为 S(AB) 由永真蕴含的定义有 1S()S() (SR)C(SR)C (SR)C H1H2HnRC 即 H1H2HnRC 所以，要证明H1H2Hn (RC)，只需证明H1H2HnRC，其中R叫做附加前提。 *这种间接推理方法称为CP规则。,16,间接证法（间接推理）,例题证明()， ,B重言蕴含 证明：(1) D P (附加前提） (2) P (3) T(1)(2) I 析取三断论 (4)() P (5) T(3),(4) I (I11假言推理) (6) P (7) T(5),(6)I (I11假言推理) (8) D CP,17,间接证法（间接推理）,例 用CP规则证明： P(QR)，TP，QTR 证明： T P(附加前提) TP P P T 析取三段论 P(QR) P QR T 假言推理 Q P R T 假言推理 TR CP规则,18,间接证法（间接推理）,例 试构造下面推理的证明。 如果小张和小王去看电影，则小李也去看电影； 小赵不去看电影或小张去看电影； 小王去看电影。 所以，当小赵去看电影时，小李也去看电影。 解：（.将简单命题符号化) 设 P:小张去看电影。 Q:小王去看电影。 R:小李去看电影。 S:小赵去看电影。 (2.找出前题与结论。) 前提：(PQ)R,SP,Q ， 结论：SR ）,19,间接证法（间接推理）,故本题即要证明： (PQ)R,SP,Q推出SR 证明： (.用CP规则证明) (1) S P(附加前提引入) (2) SP P (3) P T(1)(2) I (析取三段论) (4) (PQ)R P (5)Q P (6)PQ T(3)(5) I (合取引入规则） (7)R T(4)(6) I (假言推理) (8) SR CP,20,间接证法（间接推理）,例 构造下面推理的证明。 如果小张守第一垒并且小李向B队投球，则A队将取胜； 或者A队未取胜，或者A队获得联赛第一名； A队没有获得联赛的第一名； 小张守第一垒。 因此，小李没有向B队投球。 解:设 P:小张守第一垒。 Q:小李向B队投球。 R:A队取胜。 S:A队获得联赛第一名。,21,间接证法（间接推理）,前提：(PQ)R,RS,S ,P 结论：Q 证明：(用归谬法) (1) Q P(附加前提） (2)RS (3)S (4)R T(2)(3) I(析取三段论) (5)(PQ)R P (6)(PQ) T(4)(5) I(拒取式) (7) PQ T(6) E(德摩根律，置换） (8)P P (9)Q T(7)(8) I(析取三段论 (10)QQ（矛盾） (1)(9) I(合取引入规则）,22,本课小结,有效推理 真值表法论证 命题逻辑的推理理论直接证法，间接证法（归缪法、规则）,