離散數(shù)學(xué)命題邏輯4

《離散數(shù)學(xué)命題邏輯4》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第一章命題邏輯推理理論推理理論前提與有效結(jié)論證明方法推理定律和規(guī)則直接證明法間接證明法推理推理：由前提，依據(jù)推理規(guī)則，推導(dǎo)出結(jié)論的思維過程。命題邏輯中，前提和結(jié)論都用命題公式表示若前提為：P1、P2、···、Pn；有效結(jié)論：Q由前提P1、P2、···、Pn推出有效結(jié)論Q證明當(dāng)前提P1、P2、···、Pn都成立（為真）時，Q成立（為真）P1∧P2∧···∧Pn?Q（P1,P2,···,Pn?Q）證明永真蘊涵式的方法：證明:A?B：真值表法命題(等價)演算法利用等價公式和永真蘊涵公式證明假設(shè)推理法。(假設(shè)前

2、提為真，證明結(jié)論必為真)主析取范式法所以，P∧(P∨Q)∧(﹁(P∧Q))?﹁Q?1例1.6.1證明﹁Q是前提P，P∨Q,﹁(P∧Q)的有效結(jié)論證明:等價于證明P∧(P∨Q)∧(﹁(P∧Q))?﹁Q(1)真值表法(2)命題演算(3)利用等價公式和永真蘊涵公式證明(4)假設(shè)推理法P∧(P∨Q)∧(﹁(P∧Q))?﹁Q假設(shè)P∧(P∨Q)∧﹁(P∧Q)為真，則P和﹁(P∧Q)為真,所以P∧Q為假，因而Q為假。即﹁Q為真。這就證明了P∧(P∨Q)∧﹁(P∧Q)?﹁Q。(5)主范式法推理理論前提與有效結(jié)論證明方法

3、直接證明法間接證明法直接證明法由一組前提，利用一些公認(rèn)的推理規(guī)則，根據(jù)已知的等價或蘊含公式，推演得到有有效的結(jié)論。直接證明法遵循兩條規(guī)則(TP規(guī)則)：P規(guī)則：前提在推導(dǎo)過程中的任何時候都可以引入使用T規(guī)則：在推導(dǎo)中，如果有一個或多個公式、永真蘊含著公式S，則S可引入推導(dǎo)中推理定律——永真蘊涵式AT(AúB)(AùB)TA(A?B)ùATB(A?B)ù?BT?A(AúB)ù?BTA(A?B)ù(B?C)T(A?C)(A?B)ù(B?C)T(A?C)(A?B)ù(C?D)ù(AúC)T(BúD)(A?B)ù

4、(?A?B)ù(Aú?A)TB(A?B)ù(C?D)ù(?Bú?D)T(?Aú?C)直接證明法例1：請用直接證明法證明：(P∨Q),(P→R),(Q→S)?R∨S證明:(1)P∨Qp(2)┓P→QT(1)(3)Q→SP(4)┓P→ST(2)(3)(5)P→RP(6)┓R→┓PT(5)(7)┓R→ST(4)(6)(8)R∨ST(7)直接證明法例2證明：P→Q,┓Q∨R,┓R,┓(┓P∧S)?┓S./*逗號“,”和“∧”的含義相同*/證明(1)┓Q∨R利用P規(guī)則，引入前提(2)Q→R利用P規(guī)則，引入前提(3

5、)┓R利用P規(guī)則，引入前提(4)┓Q由(2),(3)，利用T規(guī)則(5)P→Q利用P規(guī)則，引入前提(6)┓P由(4),(5)，利用T規(guī)則(7)┓(┓P∧S)P利用P規(guī)則，引入前提(8)P∨┓S由(7)，利用T規(guī)則(9)┓S由(6),(8)，利用T規(guī)則直接證明法例3證明(A∨B)→(C∧D),(D∨F)→E?A→E/*逗號“,”和“∧”的含義相同*/證明(1)(A∨B)→(C∧D)P(2)┓(A∨B)∨(C∧D)T(1)(3)(┓(A∨B)∨C))∧(┓(A∨B)∨D)T(2)(4)┓(A∨B)∨DT(3)

6、(5)(┓A∧┓B)∨DT(4)(6)(┓A∨D)∧(┓B∨D)T(5)直接證明法例3證明(A∨B)→(C∧D),(D∨F)→E?A→E證明（續(xù)）(6)(┓A∨D)∧(┓B∨D)T(5)(7)┓A∨DT(6)(8)A→DT(7)(9)(D∨F)→EP(10)┓(D∨F)∨ET(9)(11)(┓D∧┓F)∨ET(10)(12)(┓D∨E)∧(┓F∨E)T(11)(13)┓D∨ET(12)(14)D→ET(13)(15)A→ET(8),(14)例4：請給出下面語句的前提和結(jié)論以及推理過程：或者天晴，或者

7、下雨。如果天晴，我去看電影。如果我去看電影，我就不看書。我在看書。所以天在下雨。推理過程：“如果我去看電影，我就不看書”但“我在看書”所以“我沒去看電影”而“如果天晴，我去看電影”所以“天不晴”由于“或者天晴，或者下雨。所以”天在下雨“或者天晴，或者下雨。如果天晴，我去看電影。如果我去看電影，我就不看書。我在看書。所以天在下雨。推理過程：“如果我去看電影，我就不看書”但“我在看書”所以“我沒去看電影”而“如果天晴，我去看電影”所以“天不晴”由于”或者天晴，或者下雨“所以”天在下雨“M：天晴

8、。Q：下雨。S：我看電影。R：我看書。M?QM?SS??RRQS??RPRP?STM?SP?MTM?QPQTM?Q,M?S,S??R,R?Q推理理論前提與有效結(jié)論證明方法直接證明法間接證明法間接證明法(1)設(shè)有一組前提P1、P2、···、Pn，要推出結(jié)論Q，證明P1∧P2∧···∧Pn?Q即證明(P1∧P2∧···∧Pn)→Q?1即證明┓(P1∧P2∧···∧Pn)∨Q?1即證明┓(┓(P1∧P2∧···∧Pn)∨Q)?0利用摩根律，即證明