北京邮电大学计算机学院离散数学 16- rules of inference

1、12022-5-8College of Computer Science & Technology, BUPT命题逻辑的推理n数理逻辑的主要任务是提供一套推理规则。从给定的前提出发，推导出一个结论来。n前提是一些已知的命题公式，结论是从前提出发,应用推理规则推出的命题公式。n而这推理过程称为演绎或形式证明. 22022-5-8College of Computer Science & Technology, BUPT关于重言蕴含 n定义：nA、C是两个公式，如果AC是重言式则称A重言蕴含C，或称A能逻辑地推出 C 记作A Cn说明：n与是有区别的，是联结词，AC仍然是公式，而是

2、公式关系符。n 描述了两个公式的关系，只能说A C式成立或不成立。n公式AC，当且仅当A真C假时才为假，因此A C要成立的充要条件是对一切赋值如果使A为真，必须使C也为真。 32022-5-8College of Computer Science & Technology, BUPT重言蕴含n定义：设A1、A2、Am，C是命题公式，如果（ A1、A2 、Am）C是重言式，则称C是前提集合 A1、A2、Am 的有效结论，或称由A1、A2 、Am 逻辑地推论出C。n由上面的定义，上面可以记作 A1、A2 Am C。 42022-5-8College of Computer Science

3、& Technology, BUPTRules of InferencenMany of the tautologies are rules of inference. They have the formnP1 P2.Pn QnwherenPi are called the hypotheses（前提）nandnQ is the conclusion（结论）.nQ logically follows from P1 , P2, ,Pn52022-5-8College of Computer Science & Technology, BUPTRules of Inferenc

4、e -推理规则nAs a rule of inference they take the symbolic form:P1P2.PnQnwhere means therefore or it follows that.62022-5-8College of Computer Science & Technology, BUPTNoten To prove the theorem means to show that the implication is a tautology. nnot trying to show that Q (the conclusion) is true, b

5、ut only that Q will be true if all the Pi are true. nmathematical proofs often begin with the statement suppose that P1 , P2, . . . , and Pn are true and conclude with the statement therefore, Q is true.nThe proof does not show that Q is true, but simply shows that Q has to be true if the Pi are all

6、 true.72022-5-8College of Computer Science & Technology, BUPTRules of InferencenArguments based on tautologies represent universally correct methods of reasoning. nTheir validity depends only on the form of the statements involved and not on the truth values of the variables they contain. Such a

7、rguments are called rules of inference.82022-5-8College of Computer Science & Technology, BUPTRules of InferencenThe various steps in a mathematical proof of a theorem must follow from the use of various rules of inference.nA mathematical proof of a theorem must begin with the hypotheses, procee

8、d through various steps, each justified by some rule of inference, and arrive at the conclusion.92022-5-8College of Computer Science & Technology, BUPTmodus ponens(假言推理规则）nThe tautology P (PQ) Q becomesPPQQnThis means that whenever P is true and PQ is true we can conclude logically that Q is tru

9、e.102022-5-8College of Computer Science & Technology, BUPTFamous rules of inferencenPP Q Addition（析取引入规则）nP QPSimplification（合取消去规则）nQP QPModus Tollens （拒取式）nP QQ RP RHypothetical syllogism（假言三段论）112022-5-8College of Computer Science & Technology, BUPTFamous rules of inferencenP QPQDisjuncti

10、ve syllogism （析取三段论）nPQP QConjunction （合取引入规则）nP QP RQ R Resolution（消解规则）n(PQ) (RS)P RQ S Constructive dilemma (二难推论)122022-5-8College of Computer Science & Technology, BUPTFormal ProofsnTo prove an argument is valid or the conclusion follows logically from the hypotheses:nAssume the hypotheses

11、are truenUse the rules of inference and logical equivalences to determine that the conclusion is true.132022-5-8College of Computer Science & Technology, BUPTExamplenConsider the following logical argument:nIf horses fly or cows eat artichokes, then the mosquito is the national bird. If the mosq

12、uito is the national bird then peanut butter takes good on hot dogs. But peanut butter tastes terrible on hot dogs. Therefore, cows dont eat artichokes.142022-5-8College of Computer Science & Technology, BUPTExamplenAssign propositional variables to the component propositions in the argument:nF

13、Horses flynA Cows eat artichokesnM The mosquito is the national birdnP Peanut butter tastes good on hot dogs152022-5-8College of Computer Science & Technology, BUPTExamplenRepresent the formal argument using the variables1.(F A) M2.M P3.PAnUse the hypotheses 1., 2., and 3. and the above rules of

14、 inference and any logical equivalences to construct the proof.162022-5-8College of Computer Science & Technology, BUPTExamplenAssertion Reasons1.(F A) M Hypothesis 1.2.M P Hypothesis 2.3.(F A) Psteps 1 and 2 and hypothetical syll.4.P Hypothesis 3.5.(F A) steps 3 and 4 and modus tollens6.F A ste

15、p 5 and DeMorgan7.A F step 6 and commutativity of and8.A step 7 and simplificationnQ. E. D.172022-5-8College of Computer Science & Technology, BUPTExample 6nSuppose we have the following premises:“It is not sunny and it is cold.”“We will swim only if it is sunny.”“If we do not swim, then we will

16、 canoe.”“If we canoe, then we will be home early.”nGiven these premises, prove the theorem“We will be home early” using inference rules.182022-5-8College of Computer Science & Technology, BUPTExample 6 cont.nLet us adopt the following abbreviations:nsunny = “It is sunny”; cold = “It is cold”; sw

17、im = “We will swim”; canoe = “We will canoe”; early = “We will be home early”.nThen, the premises can be written as:(1) sunny cold (2) swim sunny(3) swim canoe (4) canoe early192022-5-8College of Computer Science & Technology, BUPTExample 6 cont.StepProved by1. sunny cold Premise #1.2. sunnySimp

18、lification of 1.3. swimsunnyPremise #2.4. swimModus tollens on 2,3.5. swimcanoe Premise #3.6. canoeModus ponens on 4,5.7. canoeearlyPremise #4.8. earlyModus ponens on 6,7.202022-5-8College of Computer Science & Technology, BUPTResolutionnExample 9nShow that the hypotheses (pq)r and rs imply the

19、conclusion ps.212022-5-8College of Computer Science & Technology, BUPT一阶逻辑推理定律(定义)n推出： AB n读作：A推出Bn含义：A为真时, B也为真nAB 当且仅当 AB是永真式n例如： xF(x) xF(x)F222022-5-8College of Computer Science & Technology, BUPT一阶逻辑推理定律(来源)n命题逻辑推理定律的代换实例n基本等值式生成的推理定律n其他的一阶逻辑推理定律 xA(x)xB(x) x(A(x)B(x) x(A(x)B(x) xA(x)xB

20、(x) x(A(x)B(x) xA(x)xB(x) x(A(x)B(x) xA(x)xB(x) 232022-5-8College of Computer Science & Technology, BUPT一阶逻辑推理定律(举例)n命题逻辑推理定律的代换实例 例如: 假言推理规则: (AB )AB 代入 A=F(a), B=G(a), 得到(F(a)G(a)F(a)G(a)242022-5-8College of Computer Science & Technology, BUPT一阶逻辑推理定律(举例、续)n基本等值式生成的推理定律 即由 AB 可得 AB 和 BA 例如

21、: 量词分配等值式: x(A(x)B(x) xA(x)xB(x) 可得 x(A(x)B(x) xA(x)xB(x) xA(x)xB(x) x(A(x)B(x)252022-5-8College of Computer Science & Technology, BUPT推理定律与推理规则n推理定律AB表示AB是永真式n推理规则是在证明过程中使用的规则n每一条推理定律都可以作为推理规则n有些推理规则不是推理定律262022-5-8College of Computer Science & Technology, BUPT一阶逻辑的常用推理规则n前提引入、结论引入、置换规则n假言推

22、理、附加、化简、拒取式、假言三段论、析取三段论、构造性两难、合取引入nUI、UG、EI、EG272022-5-8College of Computer Science & Technology, BUPTUI规则(universal instantiation)n 表示为 xA(x) xA(x) 或 A(y) A(c)n注意1: y是自由变项； c是个体常项n注意2: 被消去量词的辖域是整个公式n例如 (1) x(F(x)G(x) 前提引入 (2) F(a)G(a) (1)UI282022-5-8College of Computer Science & Technology,

23、 BUPTUG规则(universal generalization)n 表示为 A(y) xA(x)n注意1: y是自由变项n注意2: 量词加在整个公式前面n 例如 (1) F(y)G(y) 前提引入 (2) x(F(x)G(x) (1)UG292022-5-8College of Computer Science & Technology, BUPTEI规则(existential instantiation)n 表示为 xA(x) A(c)n注意1: c是特定的满足A的个体常项n注意2: 被消去量词的辖域是整个公式n 例如 (1) x(F(x)G(x) 前提引入 (2) F(a)

24、G(a) (1)EI302022-5-8College of Computer Science & Technology, BUPTEG规则(existential generalization)n 表示为 A(c) xA(x)n注意1: c是个体常项n注意2: 量词加在整个公式前面n 例如 (1) F(c)G(c) 前提引入 (2) x(F(x)G(x) (1)EG312022-5-8College of Computer Science & Technology, BUPT构造推理的证明(举例)n前提: x(F(x)G(x)，F(a) 结论: G(a) 证明: (1) F(

25、a) 前提引入 (2) x(F(x)G(x) 前提引入 (3) F(a)G(a) (2)UI (4) G(a) (1)(3)假言推理 322022-5-8College of Computer Science & Technology, BUPT构造推理的证明(举例、续)n前提: x(F(x)G(x)，xF(x) 结论: xG(x) 证明: (1) xF(x) 前提引入 (2) F(c) (1) EI (3) x(F(x)G(x) 前提引入 (4) F(c)G(c) (3) UI (5) G(c) (2)(4)假言推理 (6) xG(x) (5) EG332022-5-8College of Computer Science & Technology, BUPT构造推理的证明(举例、续)n“先EI，后UI”n证明: (1) x(F(x)G(x) 前提引入 (2) F(c)G(c) (2) UI (3) xF(x) 前提引入 (4) F(c) (3) EI n说明：这个证明是错的. (3)(4)应当在(1)(2)前，(4)中的c是特定的， (2)中的c是任意的342022-5-8College of Co