离散数学命题逻辑4

《离散数学命题逻辑4》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章命题逻辑推理理论推理理论前提与有效结论证明方法推理定律和规则直接证明法间接证明法推理推理：由前提，依据推理规则，推导出结论的思维过程。命题逻辑中，前提和结论都用命题公式表示若前提为：P1、P2、···、Pn；有效结论：Q由前提P1、P2、···、Pn推出有效结论Q证明当前提P1、P2、···、Pn都成立（为真）时，Q成立（为真）P1∧P2∧···∧Pn⇒Q（P1,P2,···,Pn⇒Q）证明永真蕴涵式的方法：证明:AB：真值表法命题(等价)演算法利用等价公式和永真蕴涵公式证明假设推理法。(假设前

2、提为真，证明结论必为真)主析取范式法所以，P∧(P∨Q)∧(﹁(P∧Q))﹁Q1例1.6.1证明﹁Q是前提P，P∨Q,﹁(P∧Q)的有效结论证明:等价于证明P∧(P∨Q)∧(﹁(P∧Q))﹁Q(1)真值表法(2)命题演算(3)利用等价公式和永真蕴涵公式证明(4)假设推理法P∧(P∨Q)∧(﹁(P∧Q))﹁Q假设P∧(P∨Q)∧﹁(P∧Q)为真，则P和﹁(P∧Q)为真,所以P∧Q为假，因而Q为假。即﹁Q为真。这就证明了P∧(P∨Q)∧﹁(P∧Q)⇒﹁Q。(5)主范式法推理理论前提与有效结论证明方法

3、直接证明法间接证明法直接证明法由一组前提，利用一些公认的推理规则，根据已知的等价或蕴含公式，推演得到有有效的结论。直接证明法遵循两条规则(TP规则)：P规则：前提在推导过程中的任何时候都可以引入使用T规则：在推导中，如果有一个或多个公式、永真蕴含着公式S，则S可引入推导中推理定律——永真蕴涵式AÞ(AÚB)(AÙB)ÞA(A®B)ÙAÞB(A®B)ÙØBÞØA(AÚB)ÙØBÞA(A®B)Ù(B®C)Þ(A®C)(A«B)Ù(B«C)Þ(A«C)(A®B)Ù(C®D)Ù(AÚC)Þ(BÚD)(A®B)Ù

4、(ØA®B)Ù(AÚØA)ÞB(A®B)Ù(C®D)Ù(ØBÚØD)Þ(Ø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规则，引入前提(2)Q→R利用P规则，引入前提(3

5、)┓R利用P规则，引入前提(4)┓Q由(2),(3)，利用T规则(5)P→Q利用P规则，引入前提(6)┓P由(4),(5)，利用T规则(7)┓(┓P∧S)P利用P规则，引入前提(8)P∨┓S由(7)，利用T规则(9)┓S由(6),(8)，利用T规则直接证明法例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证明（续）(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：请给出下面语句的前提和结论以及推理过程：或者天晴，或者

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

8、。Q：下雨。S：我看电影。R：我看书。MQMSSRRQSRPRPSTMSPMTMQPQTMQ,MS,SR,RQ推理理论前提与有效结论证明方法直接证明法间接证明法间接证明法(1)设有一组前提P1、P2、···、Pn，要推出结论Q，证明P1∧P2∧···∧Pn⇒Q即证明(P1∧P2∧···∧Pn)→Q⇔1即证明┓(P1∧P2∧···∧Pn)∨Q⇔1即证明┓(┓(P1∧P2∧···∧Pn)∨Q)⇔0利用摩根律，即证明