《离散数学-1-8推理理论.ppt》由会员分享，可在线阅读，更多相关《离散数学-1-8推理理论.ppt（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一章 命题逻辑1-8 推理理论授课人：李朔Email:chn.nj.lS1在数学和其它自然科学中，经常要考虑从某些前提A1、A2、An出发，能推导出什么结论。数理逻辑的主要任务是用逻辑的方法研究数学中的推理。所谓推理推理是指从前提出发，应用推理规则推出结论的思维过程。任何一个推理都由前提和结论两部分组成。前提就是推理所根据的已知命题，结论则是从前提出发通过推理而得到的新命题。要研究推理，首先应该明确什么样的推理是有效的或正确的2一、有效推理1.假设一些命题为，并使用一些公认的规则，得到另外的命题，形成结论，这种过程就是论证论证。2.定义1-8.1 设A和C是2个命题公式，当且仅当AC为一重言
2、式，即AC，则称C为为A A的的有有效效结结论论。或C可由可由A A逻辑的推出。逻辑的推出。A叫做叫做C的前提的前提。3.3.上述定义可以推广到上述定义可以推广到n n个前提的情况：个前提的情况：4.设H1，H2，Hn,C是n+1个命题公式,当且仅当 H1H2HnC，5.称C是一组前提是一组前提H1，H2，Hn 的有效结论的有效结论。6.*判判断断有有效效结结论论的的过过程程就就是是论论证证过过程程，基本方法是真值表法、直接证法、间接证法。3二、真值表法由定义1-8.1可以看出，要证明C是一组前提H1，H2，Hn 的有效结论，只需证明H1H2HnC为重言式。而证证明明一一个个公公式式为为重重言
3、言式式，可可以以用用真真值值表表、等等值值演演算算、主主析析(合合)取取范范式式或或已已知知的的蕴蕴含含式式等方法进行。用等价演算和主析(合)取范式证明重言式的方法前面已经讨论过了，我们已经非常熟悉了。这里仅对真值表法作简单说明。（1）真值表法真值表法设设P1，P2，Pn出现于前提H1，H2，Hm 和结论C的全部命题变元，假定对P1，P2，Pn作了全部的真值指派，这样就能对应地确定H1，H2，Hn 和C的所有真值，列出这个真值表，即可看出 H1H2HmC 是否成立即即找找出出H1，H2，Hm 均均为为的的行行，对对于于每每一一个个这这样样的的行行，若若C也也为为,则则上上式式成成立立。或或C为
4、为，H1，H2，Hm 中中起起码码有有一一个个为为4二、真值表法例：分析事实：“如果我有时间，那么我就去上街；如果我上街，那么我就去书店买书；但我没有去书店买书，所以我没有时间。”。试指出这个推理前提和结论，并证明结论是前提的有效结论。解：令 ：我有时间。：我去上街。：我去书店买书。根据题意，前提为：，结论为：以下证明以下证明是一组前提是一组前提,的有效结论。的有效结论。即证明：即证明：(PQ)(QR)RP 5二、真值表法作公式PQ，QR，R，P的真值表从表中可以看出从表中可以看出:PQ，QR，R都为都为1的行的行(赋值赋值000的行的行)，P也为也为1。(或或 P为为0的的行行(赋赋值值10
5、0，101，110，111的的行行)PQ，QR，R至至少少有有一一个为个为0）所以所以(PQ)(QR)R PPQRPQQRRP00011110011101010101101111011000110101010011010101111100123C6三、命题逻辑的推理理论当推理中包含的命题变元较多时，真值表法或等值演算法，主析取范式法等方法的演算量太大。给推理带来了困难。为此引引入命题逻辑的推理理论入命题逻辑的推理理论。命题逻辑的推理是一个描述推理过程的命题公式序列，其中的每个命题公式或者是已知前提，或者是由某些前提应用推理规则得到的结论(中间结论或推理中的结论)。它有两种方法：直接证法（直接推
6、理）直接证法（直接推理）和间接证法（间接间接证法（间接推理）推理）。7直接证法（直接推理）直接证法（直接推理）直接证法（直接推理）基基本本思思想想是：由一组前提出发，利用一些公认的规则，根根据已知的等价式或蕴含式，推演得到有效结论据已知的等价式或蕴含式，推演得到有效结论。公认的推理规则有公认的推理规则有4 4条条：P规则规则：前提在推导过程中的任何时候都可以引入使用。T T规规则则：推导中，如果一个或多个公式蕴含着公式S，则 公式S可以引入到以后的推理之中。置换规则置换规则：在推导过程的任何步骤上，命题公式中的子 公式都可以用与之等价的公式置换。(等价式表）合取引入规则合取引入规则：任意两个命
7、题公式A,B可以推出AB常用的蕴含式和等价式见常用的蕴含式和等价式见P43P43表表1-8.31-8.3表表1-8.41-8.48直接证法（直接推理）例题：用直接推理法证明()()()证法1:(1)P -(P规则，引入前提规则，引入前提)(2)Q T(1)E 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规则，引入前提规则，
8、引入前提)(7)SR T(5),(6)I(对对(5),(6)式规则，根据式规则，根据I13 假言三段假言三段 论论)(8)T(7)E-(对对(7)式式T规则规则,根据根据E16蕴含等值式蕴含等值式)9直接证法（直接推理）证法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)I10直接证法（直接推理）用直接推理法证明(PQ)(QR)PR 证明：PQP P P Q T I 假言推理(I11)QR P R T I 假言推理假言推理(I11)11间接证法（间接推理）定义定义1-8.2假设公式H1，H2，Hm中的命题变元
9、P1，P2，Pn，对于P1，P2，Pn的一些真值指派，如果能使H1H2Hm的真值为，则称公式公式H1，H2，Hm是相是相容的。容的。如果对于P1，P2，Pn的每一组真值指派，使H1H2Hm的真值均为，则称公式公式H1，H2，Hm是不相容的。是不相容的。12间接证法（间接推理）将不相容的概念应用于命题公式的证明将不相容的概念应用于命题公式的证明(归谬法归谬法)设有一组前提设有一组前提H1，H2，Hn，要推出结论要推出结论C，即要证即要证 H1H2Hn C，令令 SH1H2Hn 则上式可以简记为则上式可以简记为 SC由永真蕴含的定义有由永真蕴含的定义有 1SCSC两边否定两边否定0SC H1H2H
10、nC即即要要证证明明C是是前前提提H1，H2，Hn的的有有效效结结论论，只只须证明须证明 H1H2HnC0(即即H1，H2，Hn 与与 C不相容）不相容）这种间接推理方法称为归谬法这种间接推理方法称为归谬法13间接证法（间接推理）例题例题证明，(C)可逻辑推出。证明：(1)P P (2)P(P(附加前提）附加前提）(3)(C)P P (4)C T(3)ET(3)E(E(E9 9德摩根律德摩根律)(5)B T(1),(2)T(1),(2)I(I(I1111假言推理假言推理)(6)T(4)IT(4)I(I(I1 1简化式简化式)(7)(矛盾）T(5),(6)IT(5),(6)I(I(I1 1合取引
11、合取引入入规则规则)14间接证法（间接推理）CP规则规则间接证法的另一种情况：要证H1H2Hn()。设SH1H2Hn，则上式可以简记为 S(AB)由永真蕴含的定义有 1S()S()(SR)C(SR)C (SR)C H1H2HnRC即 H1H2HnRC 所以，要要证证明明H1H2Hn(RC)，只只需需证证明明H1H2HnRC，其中其中R叫做附加前提叫做附加前提。*这种间接推理方法称为这种间接推理方法称为CP规则规则。15间接证法（间接推理）例题例题证明()，,B重言蕴含证明：(1)D P P(附加前提）(2)P P (3)T(1)(2)I T(1)(2)I 析取三断论析取三断论 (4)()P P
12、 (5)T(3),(4)IT(3),(4)I(I(I1111假言推理假言推理)(6)P P (7)T(5),(6)IT(5),(6)I(I(I1111假言推理假言推理)(8)D CP16间接证法（间接推理）例例 用CP规则证明：P(QR)，TP，QTR 证明：T P(附加前提)TP P P T 析取三段论析取三段论 P(QR)P QR T 假言推理假言推理 Q P R T 假言推理假言推理 TR CP规则17间接证法（间接推理）例试构造下面推理的证明。如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影时，小李也去看电影。解：（.将简单命题
13、符号化将简单命题符号化)设设P:小张去看电影。小张去看电影。Q:小王去看电影。小王去看电影。R:小李去看电影。小李去看电影。S:小赵去看电影。小赵去看电影。(2.找出前题与结论。找出前题与结论。)前提：前提：(PQ)R,SP,Q，结论：结论：SR）18间接证法（间接推理）故本题即要证明：(PQ)R,SP,Q推出推出SR 证明：(.用用CPCP规则证明规则证明)(1)SP(附加前提引入附加前提引入)(2)S PP(3)PT(1)(2)I(析取三段论析取三段论)(4)(P Q)RP(5)QP(6)P QT(3)(5)I(合取引入规则）合取引入规则）(7)RT(4)(6)I(假言推理假言推理)(8)
14、SRCP19间接证法（间接推理）例 构造下面推理的证明。如果小张守第一垒并且小李向B队投球，则A队将取胜；或者A队未取胜，或者A队获得联赛第一名；A队没有获得联赛的第一名；小张守第一垒。因此，小李没有向B队投球。解解:设设 P:P:小张守第一垒。小张守第一垒。Q:Q:小李向小李向B B队投球。队投球。R:AR:A队取胜。队取胜。S:AS:A队获得联赛第一名。队获得联赛第一名。20间接证法（间接推理）前提：前提：(PQ)R,RS,S,P PQ)R,RS,S,P 结论：结论：Q Q 证明：证明：(用归谬法用归谬法)(1)(1)Q Q P(P(附加前提）附加前提）(2)(2)RS RS (3)(3)
15、S S (4)(4)R T(2)(3)IR T(2)(3)I(析取三段论析取三段论)(5)(5)(PQ)R PPQ)R P (6)(6)(PQ)T(4)(5)IPQ)T(4)(5)I(拒取式拒取式)(7)(7)PQ T(6)EPQ T(6)E(德摩根律，置换）德摩根律，置换）(8)(8)P P P P (9)(9)Q T(7)(8)I(Q T(7)(8)I(析取三段析取三段论论 (10)(10)QQQQ（矛盾）矛盾）(1)(9)(1)(9)I I(合取引合取引入规则）入规则）21本课小结有效推理真值表法论证命题逻辑的推理理论直接证法，间接证法（归缪法、规则）22课后作业通读书本本节例题P47(2)a,c,e (3)a,b补充:构造下面推理的证明 以下前提已经成立:(1)甲或乙作的案(2)如果甲作的案,作案时间应在午夜后(3)若乙证词正确,则午夜灯光未灭(4)若乙证词不正确,则作案时间不在午夜之后(5)午夜灯光灭了 结论:乙作的案令A:甲做的案 B:乙做的案 C:作案时间在午夜前 D:乙证词正确 E:午夜灯光未灭23