北京郵電大學(xué)--計算機(jī)學(xué)院--離散數(shù)學(xué)-1.6--rules-of-inference

1、1,2024/3/18,College of Computer Science & Technology, BUPT,命題邏輯的推理,數(shù)理邏輯的主要任務(wù)是提供一套推理規(guī)則。從給定的前提出發(fā)，推導(dǎo)出一個結(jié)論來。前提是一些已知的命題公式，結(jié)論是從前提出發(fā),應(yīng)用推理規(guī)則推出的命題公式。而這推理過程稱為演繹或形式證明.,2,2024/3/18,College of Computer Science & Technology,

2、 BUPT,關(guān)于重言蘊(yùn)含?,定義：A、C是兩個公式，如果A→C是重言式則稱A重言蘊(yùn)含C，或稱A能邏輯地推出 C 記作A ? C說明：→與?是有區(qū)別的，→是聯(lián)結(jié)詞，A→C仍然是公式，而?是公式關(guān)系符。? 描述了兩個公式的關(guān)系，只能說A ? C式成立或不成立。公式A→C，當(dāng)且僅當(dāng)A真C假時才為假，因此A ? C要成立的充要條件是對一切賦值如果使A為真，必須使C也為真。,3,2024/3/18,College of Computer

3、 Science & Technology, BUPT,重言蘊(yùn)含?,定義：設(shè)A1、A2、…、Am，C是命題公式，如果（ A1、A2 、…、Am）→C是重言式，則稱C是前提集合{ A1、A2、…、Am }的有效結(jié)論，或稱由{A1、A2 、…、Am }邏輯地推論出C。由上面?的定義，上面可以記作 A1、A2 … Am ? C。,4,2024/3/18,College of Computer Science & Techno

4、logy, BUPT,Rules of Inference,Many of the tautologies are rules of inference. They have the formP1 Ù P2Ù.....ÙPn ?QwherePi are called the hypotheses（前提）andQ is the conclusion（結(jié)論）.Q logically follows

5、from P1 , P2, …,Pn,5,2024/3/18,College of Computer Science & Technology, BUPT,Rules of Inference -推理規(guī)則,As a rule of inference they take the symbolic form:P1P2..Pn\Qwhere \ means 'therefor

6、e' or 'it follows that.',6,2024/3/18,College of Computer Science & Technology, BUPT,Note,To "prove the theorem" means to show that the implication is a tautology. not trying to show that Q (the

7、 conclusion) is true, but only that Q will be true if all the Pi are true. mathematical proofs often begin with the statement "suppose that P1 , P2, . . . , and Pn are true" and conclude with the statement &qu

8、ot;therefore, Q is true‘.The proof does not show that Q is true, but simply shows that Q has to be true if the Pi are all true.,7,2024/3/18,College of Computer Science & Technology, BUPT,Rules of Inference,Arguments

9、 based on tautologies represent universally correct methods of reasoning. Their validity depends only on the form of the statements involved and not on the truth values of the variables they contain. Such arguments are

10、called rules of inference.,8,2024/3/18,College of Computer Science & Technology, BUPT,Rules of Inference,The various steps in a mathematical proof of a theorem must follow from the use of various rules of inference.

11、A mathematical proof of a theorem must begin with the hypotheses, proceed through various steps, each justified by some rule of inference, and arrive at the conclusion.,9,2024/3/18,College of Computer Science & Techn

12、ology, BUPT,modus ponens(假言推理規(guī)則）,The tautology P Ù (P?Q) ? Q becomesPP?Q\QThis means that whenever P is true and P?Q is true we can conclude logically that Q is true.,10,2024/3/18,College of Computer Scien

13、ce & Technology, BUPT,Famous rules of inference,P\P Ú Q Addition（析取引入規(guī)則）P Ù Q\PSimplification（合取消去規(guī)則）~QP ? Q\~PModus Tollens （拒取式）P ? QQ ? R\P ? RHypothetical syllogism（假言三段論）,11,2024/3/

14、18,College of Computer Science & Technology, BUPT,Famous rules of inference,P ÚQ~P\QDisjunctive syllogism （析取三段論）PQ\P Ù QConjunction （合取引入規(guī)則）P ÚQ~P Ú R\Q Ú R Resolu

15、tion（消解規(guī)則）(P?Q) Ù (R?S)P Ú R\QÚ S Constructive dilemma (二難推論),12,2024/3/18,College of Computer Science & Technology, BUPT,Formal Proofs,To prove an argument is valid or the conclusion follows log

16、ically from the hypotheses:Assume the hypotheses are trueUse the rules of inference and logical equivalences to determine that the conclusion is true.,13,2024/3/18,College of Computer Science & Technology, BUPT,Exa

17、mple,Consider the following logical argument:If horses fly or cows eat artichokes, then the mosquito is the national bird. If the mosquito is the national bird then peanut butter takes good on hot dogs. But peanut butte

18、r tastes terrible on hot dogs. Therefore, cows don't eat artichokes.,14,2024/3/18,College of Computer Science & Technology, BUPT,Example,Assign propositional variables to the component propositions in the argumen

19、t:F Horses flyA Cows eat artichokesM The mosquito is the national birdP Peanut butter tastes good on hot dogs,15,2024/3/18,College of Computer Science & Technology, BUPT,Example,Represent the formal argument

20、using the variables1.(F Ú A) ? M2.M ? P3.~P\~AUse the hypotheses 1., 2., and 3. and the above rules of inference and any logical equivalences to construct the proof.,16,2024/3/18,College of Computer Science &am

21、p; Technology, BUPT,Example,Assertion 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 mo

22、dus tollens6.~F Ù~A step 5 and DeMorgan7.~A Ù~F step 6 and commutativity of 'and'8.~A step 7 and simplificationQ. E. D.,17,2024/3/18,College of Computer Science & Technology, BUPT,Example

23、6,Suppose 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 canoe.”“If we canoe, then we will be home early.”Given these premises, pr

24、ove the theorem“We will be home early” using inference rules.,18,2024/3/18,College of Computer Science & Technology, BUPT,Example 6 cont.,Let us adopt the following abbreviations:sunny = “It is sunny”; cold = “It i

25、s cold”; swim = “We will swim”; canoe = “We will canoe”; early = “We will be home early”.Then, the premises can be written as:(1) ?sunny ? cold (2) swim ? sunny(3) ?swim ? canoe (4) canoe ? early,19,2024/3/18,College

26、 of Computer Science & Technology, BUPT,Example 6 cont.,StepProved by1. ?sunny ? cold Premise #1.2. ?sunnySimplification of 1.3. swim?sunnyPremise #2.4. ?swimModus tollens on 2,3.5. ?swim?canoe Premise #3.

27、6. canoeModus ponens on 4,5.7. canoe?earlyPremise #4.8. earlyModus ponens on 6,7.,20,2024/3/18,College of Computer Science & Technology, BUPT,Resolution,Example 9Show that the hypotheses (p?q)?r and r?s imply

28、the conclusion p?s.,21,2024/3/18,College of Computer Science & Technology, BUPT,,一階邏輯推理定律(定義),推出： A?B 讀作：A推出B含義：A為真時, B也為真A?B 當(dāng)且僅當(dāng) A?B是永真式例如： ?xF(x) ? ?xF(x),,F,22,2024/3/18,College of Computer Science & Tec

29、hnology, BUPT,一階邏輯推理定律(來源),命題邏輯推理定律的代換實例基本等值式生成的推理定律其他的一階邏輯推理定律 ?xA(x)∨?xB(x) ? ?x(A(x)∨B(x)) ?x(A(x)∧B(x)) ? ?xA(x)∧?xB(x) ?x(A(x)→B(x)) ? ?xA(x)→?xB(x) ?x(A(x)→B(x)) ? ?xA(x)→?xB(x)

30、 ?,23,2024/3/18,College of Computer Science & Technology, BUPT,一階邏輯推理定律(舉例),命題邏輯推理定律的代換實例 例如: 假言推理規(guī)則: (A→B )∧A?B 代入 A=F(a), B=G(a), 得到(F(a)→G(a))∧F(a)?G(a),24,2024/3/18,College of Computer Science

31、 & Technology, BUPT,一階邏輯推理定律(舉例、續(xù)),基本等值式生成的推理定律 即由 A?B 可得 A?B 和 B?A 例如: 量詞分配等值式: ?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)),25,2024/3/18,Co

32、llege of Computer Science & Technology, BUPT,推理定律與推理規(guī)則,推理定律A?B表示A→B是永真式推理規(guī)則是在證明過程中使用的規(guī)則每一條推理定律都可以作為推理規(guī)則有些推理規(guī)則不是推理定律,26,2024/3/18,College of Computer Science & Technology, BUPT,一階邏輯的常用推理規(guī)則,前提引入、結(jié)論引入、置換規(guī)則假言推理、附

33、加、化簡、拒取式、假言三段論、析取三段論、構(gòu)造性兩難、合取引入UI、UG、EI、EG,27,2024/3/18,College of Computer Science & Technology, BUPT,UI規(guī)則(universal instantiation),表示為 ?xA(x) ?xA(x) ———— 或 ————? A(y) ? A(c)注意1: y是自由變項； c

34、是個體常項注意2: 被消去量詞的轄域是整個公式例如 (1) ?x(F(x)→G(x)) 前提引入 (2) F(a)→G(a) (1)UI,28,2024/3/18,College of Computer Science & Technology, BUPT,UG規(guī)則(universal generalization),表示為 A(

35、y) ———— ? ?xA(x)注意1: y是自由變項注意2: 量詞加在整個公式前面 例如 (1) F(y)→G(y) 前提引入 (2) ?x(F(x)→G(x)) (1)UG,29,2024/3/18,College of Computer Science & Technology, BUPT,EI規(guī)則(existential instantiat

36、ion),表示為 ?xA(x) ————? A(c)注意1: c是特定的滿足A的個體常項注意2: 被消去量詞的轄域是整個公式 例如 (1) ?x(F(x)∧G(x)) 前提引入 (2) F(a)∧G(a) (1)EI,30,2024/3/18,College of Computer Science & Technol

37、ogy, BUPT,EG規(guī)則(existential generalization),表示為 A(c) ———— ? ?xA(x)注意1: c是個體常項注意2: 量詞加在整個公式前面 例如 (1) F(c)∧G(c) 前提引入 (2) ?x(F(x)∧G(x)) (1)EG,31,2024/3/18,College of

38、 Computer Science & Technology, BUPT,構(gòu)造推理的證明(舉例),前提: ?x(F(x)?G(x))，F(xiàn)(a) 結(jié)論: G(a) 證明: (1) F(a) 前提引入 (2) ?x(F(x)?G(x)) 前提引入 (3) F(a)?G(a) (2)UI

39、 (4) G(a) (1)(3)假言推理,32,2024/3/18,College of Computer Science & Technology, BUPT,構(gòu)造推理的證明(舉例、續(xù)),前提: ?x(F(x)?G(x))，?xF(x) 結(jié)論: ?xG(x) 證明: (1) ?xF(x) 前提引入 (2) F(

40、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) EG,33,2024/3/18,Coll

41、ege of Computer Science & Technology, BUPT,構(gòu)造推理的證明(舉例、續(xù)),“先EI，后UI”證明: (1) ?x(F(x)?G(x)) 前提引入 (2) F(c)?G(c) (2) UI (3) ?xF(x) 前提引入 (4) F(c)

42、 (3) EI ? ? ? 說明：這個證明是錯的. (3)(4)應(yīng)當(dāng)在(1)(2)前，(4)中的c是特定的， (2)中的c是任意的,34,2024/3/18,College of Computer Science & Technology, BUPT,構(gòu)造推理的證明(舉例、續(xù)),前提: ~?x(F(x)∧H(x)), ?x(G(

43、x)?H(x)), 結(jié)論: ?x(G(x)?~F(x)) 證明: (1) ~?x(F(x)∧H(x)) 前提引入 (2) ?x(~F(x)∨~H(x)) (1)置換 (3) ?x(H(x)?~F(x)) (2)置換 (4) H(y)?~F(y) (3) UI (5) ?x(G

44、(x)?H(x)) 前提引入 (6) G(y)?H(y) (5) UI (7) G(y)?~F(y) (4)(6)假言三段論 (8) ?x(G(x)?~F(x)) (7) UG,35,2024/3/18,College of Computer Science & Technolo

45、gy, BUPT,Example,Every man has two legs. John Smith is a man. Therefore, John Smith has two legs.Define the predicates:M(x): x is a manL(x): x has two legsJ: John Smith, a member of the universe,36,2024/3/18,College

46、of Computer Science & Technology, BUPT,Example,The argument becomes1."x[M(x) ? L(x)]2.M( J )\L( J)The proof is1."x[M(x) ? L(x)] Hypothesis 12.M( J ) ? L(J ) step 1 and UI3.M( J ) Hypothesis 24