離散數(shù)學(xué)(第5講)省名師優(yōu)質(zhì)課賽課獲獎(jiǎng)?wù)n件市賽課一等獎(jiǎng)?wù)n件

馮偉森Email：fws365@16九月2023離散數(shù)學(xué)計(jì)算機(jī)學(xué)院1/312023/9/16計(jì)算機(jī)學(xué)院2主要內(nèi)容1、命題公式蘊(yùn)涵

1）九類蘊(yùn)涵關(guān)系

2）蘊(yùn)涵關(guān)系基本性質(zhì)2、推理基本概念和推理形式3、推理規(guī)則

1）P規(guī)則

2）T規(guī)則

3）CP規(guī)則2/312023/9/16計(jì)算機(jī)學(xué)院3§1．6

命題公式蘊(yùn)涵定義1.18設(shè)A和B是兩個(gè)適當(dāng)公式，假如在任何解釋下，A取值1時(shí)B也取值1，則稱公式A蘊(yùn)涵公式B，并記A

B。定理1.11

A

BiffA→B為永真式。注意：蘊(yùn)涵和條件聯(lián)結(jié)詞→是完全不一樣?！敲}聯(lián)結(jié)詞，A→B是一個(gè)命題公式；

是公式間關(guān)系符，A

B不是一個(gè)命題公式，僅表示A，B間蘊(yùn)涵關(guān)系。3/312023/9/16計(jì)算機(jī)學(xué)院4基本蘊(yùn)涵（關(guān)系）式（蘊(yùn)涵定律）I1：P∧Q

P，P∧Q

Q

I2:～（P→Q）

P，～（P→Q）

～Q解釋：利用P→Q真值表，P→Q不成立只有一個(gè)情況，前件即P成立；一樣，P→Q不成立只有一個(gè)情況，后件即Q不成立。

I3：P

P∨Q，Q

P∨Q

I4：～P

P→Q，Q

P→Q解釋：類似I1，I2，自己思索。擴(kuò)充法則簡(jiǎn)化法則4/312023/9/16計(jì)算機(jī)學(xué)院5√I5：P∧（P→Q）

Q

假言推論√I6：～Q∧（P→Q）

～P拒取式（否定式假言推論）解釋：類似I1，I2，自己思索?！蘄7：～P∧（P∨Q）

Q析取三段論√I8：（P→Q）∧（Q→R）

P→R

假言三段論解釋：假如我是川大學(xué)生，則我擁有川大學(xué)籍；假如我擁有川大學(xué)籍，則我有川大學(xué)生證。所以，假如我是川大學(xué)生，則我有川大學(xué)生證。5/312023/9/16計(jì)算機(jī)學(xué)院6基本蘊(yùn)涵（關(guān)系）式（續(xù)）√I9：（P∨Q）∧（P→R）∧（Q→R）

R

二難推論解釋：和假言推論聯(lián)絡(luò)起來(lái)思索I10：（P→Q）∧（R→S）

（P∧R）→（Q∧S）√I11：（P

Q）∧（Q

R）

P

R

等價(jià)三段論√I12：（P∨Q）∧（～P∨R）

Q∨R

歸結(jié)原理

[解釋：（～P→Q）∧（P→R）

Q∨R]6/312023/9/16計(jì)算機(jī)學(xué)院7蘊(yùn)涵關(guān)系性質(zhì)①自反性A

A②反對(duì)稱性:

假如A

B，B

A，

iffA

B③A

B且A為永真式，則B必為永真式7/312023/9/16計(jì)算機(jī)學(xué)院8④傳遞性，假如A

B，B

C，則A

C【證實(shí)】由已知條件A

B，且B

C，依據(jù)定理1.11

(A→B）∧（B→C）是永真式；再由假言三段論，應(yīng)有（A→B）∧（B→C）

A→C；再依據(jù)性質(zhì)3，A→C也必是永真式，即A

C。■8/312023/9/16計(jì)算機(jī)學(xué)院9⑤

如A

B，A

C，iffA

B∧C【證實(shí)】“

”由

AB

且

AC得到A

B和AC都是永真式，于是（AB）∧（AC）也是永真式；不過(guò)，（AB）∧（AC）

（～A∨B）∧(～A∨C)

～A∨(B∧C)A→(B∧C)，所以A(B∧C)是永真式，即AB∧C。9/312023/9/16計(jì)算機(jī)學(xué)院10“”從證實(shí)過(guò)程看，性質(zhì)5反過(guò)來(lái)也對(duì)，即由

AB∧C能夠得到AB

且

AC。

⑥如A

B，C

B，則A∨C

B⑦A∧B

CiffA

B→C

該性質(zhì)是推理演繹中CP規(guī)則基礎(chǔ)⑧

A

BiffA∧～B是矛盾式

該性質(zhì)是反證法基礎(chǔ)10/312023/9/16計(jì)算機(jī)學(xué)院11定理1.12

A

Biff

～B

～A

該定理提供了逆向思維基礎(chǔ)11/312023/9/16計(jì)算機(jī)學(xué)院12例1-6.1考慮以下語(yǔ)句，并將其前提和結(jié)論符號(hào)化。1)、前提：

1.假如明天天晴，我們準(zhǔn)備外出旅游。P→Q

2．明天確實(shí)天晴。 P結(jié)論：我們外出旅游。 Q上述例子可描述為：P→Q，P

Q(假言推論)2)、前提：1.假如一個(gè)人是單身漢，則他不幸福。P→Q2.假如一個(gè)人不幸福，則他死得早。

Q→R結(jié)論：?jiǎn)紊頋h死得早。

P→R上述例子可描述為：

P→Q，Q→R

P→R(假言三段論)12/312023/9/16計(jì)算機(jī)學(xué)院13例1-6.1(續(xù)1)3)、某女子在某日晚歸家途中被殺害，據(jù)多方調(diào)查確證，兇手必為王某或陳某，但后又查證，作案之晚王某在工廠值夜班，沒(méi)有外出，依據(jù)上述案情可得前提以下：

前提：

1.兇手為王某或陳某。

P∨Q 2.假如王某是兇手，則他在作案當(dāng)晚必外出。

P→R 3.王某案發(fā)之晚并未外出。

～R結(jié)論：陳某是兇手。

Q則上述例子可描述為：

P→R，～R

～P

(拒取式)

P∨Q，～P

Q

(析取三段論)13/312023/9/16計(jì)算機(jī)學(xué)院14例1-6.1(續(xù)2)4)、前提：

1.假如某同學(xué)為省二級(jí)以上運(yùn)動(dòng)員，則他將被大學(xué)錄用。

P→R 2.假如某同學(xué)高考總分在560分以上，則將被大學(xué)錄用。

Q→R 3.某同學(xué)高考總分在560分以上或者是省二級(jí)運(yùn)動(dòng)員。

P∨Q 結(jié)論：該同學(xué)被大學(xué)錄用。

R 則上述例子可描述為：

P∨Q，P→R，Q→R

R(二難推論)14/312023/9/16計(jì)算機(jī)學(xué)院15§1．7命題邏輯推理方法

命題演算一個(gè)主要任務(wù)在于提供一個(gè)正確思維規(guī)律，即推理規(guī)則，應(yīng)用此規(guī)則從一些前提中推導(dǎo)出一個(gè)結(jié)論來(lái)，這種推導(dǎo)過(guò)程稱為演繹或形式證實(shí)。定義1.19

設(shè)A1,A2,…,An,B是公式,假如

A1,A2,…,An

B則稱B是A1,A2,…,An

邏輯結(jié)果（有效結(jié)論）。也能夠說(shuō)由A1,A2,…,An推出結(jié)論B。15/312023/9/16計(jì)算機(jī)學(xué)院16

在更普通意義上，我們有下述定義定義1.20設(shè)G是由一組命題公式組成集合，假如存在命題公式有限序列：

A1，A2，……，An（=B）其中，Ai（i<n-1）或者是G中某個(gè)公式，或者是前面一些Aj（j<i）有效結(jié)論，而且An就是B，則稱公式B是G邏輯結(jié)果（有效結(jié)論），或者稱由G演繹出結(jié)論B來(lái)。16/312023/9/16計(jì)算機(jī)學(xué)院17我們有下述結(jié)論：

公式B是公式集合G＝{A1,A2,…,An}邏輯結(jié)果當(dāng)且僅當(dāng)A1∧A2∧…∧An→B為永真公式。17/312023/9/16計(jì)算機(jī)學(xué)院18解釋

1)這里需要尤其注意是：推理有效性和結(jié)論真實(shí)性是不一樣，有效推理不一定產(chǎn)生真實(shí)結(jié)論；而產(chǎn)生真實(shí)結(jié)論推理過(guò)程未必是有效，因?yàn)橛行评碇锌赡馨瑸椤凹佟鼻疤?，而無(wú)效推理卻可能包含為“真”前提。18/31解釋2)由此可見(jiàn)，推理有效性是一回事，前提與結(jié)論真實(shí)是否是另一回事。所謂推理有效，指是它結(jié)論是在它前提下合乎邏輯結(jié)果。也即，假如它前提都為真，那么所得結(jié)論也必定為真，而并不是要求前提或結(jié)論一定為真或?yàn)榧伲偃缤评硎怯行г?，那么不可能它前提都為真時(shí)，而它結(jié)論為假。2023/9/16計(jì)算機(jī)學(xué)院1919/312023/9/16計(jì)算機(jī)學(xué)院20推理規(guī)則

在數(shù)理邏輯中，主要推理規(guī)則有：①P規(guī)則（稱為前提引用規(guī)則）：在推導(dǎo)過(guò)程中，可隨時(shí)引入前提集合中任意一個(gè)前提；②Ｔ規(guī)則（邏輯結(jié)果引用規(guī)則）：在推導(dǎo)過(guò)程中，利用基本等價(jià)式和蘊(yùn)涵式，由證實(shí)過(guò)程中一些中間公式變換出新公式，若依據(jù)是等價(jià)式，規(guī)則標(biāo)明為T(mén)E，若依據(jù)是蘊(yùn)涵式，規(guī)則標(biāo)明為T(mén)I。20/31推理規(guī)則③ＣＰ規(guī)則（附加前提規(guī)則）：假如能從給定前提集合G與公式P推導(dǎo)出S，則能從以前提集合G推導(dǎo)出P→S。即G1,G2,…,Gn

P→S當(dāng)且僅當(dāng)

G1,G2,…,Gn，P

S

2023/9/16計(jì)算機(jī)學(xué)院2121/312023/9/16計(jì)算機(jī)學(xué)院22推理方法1.真值表法

依據(jù)前提A1,A2,…,An和結(jié)論B,結(jié)構(gòu)條件式（A1∧A2∧…∧An）→B真值表,若它為永真式，則結(jié)論B是有效。真值表法標(biāo)準(zhǔn)上能夠處理推理有效性問(wèn)題，但當(dāng)出現(xiàn)在公式中命題變?cè)獢?shù)目很大時(shí)，此法顯得不切實(shí)用，且煩瑣乏味，對(duì)培養(yǎng)邏輯推理能力及訓(xùn)練推理技巧毫無(wú)幫助。22/312023/9/16計(jì)算機(jī)學(xué)院232、演繹法演繹法是從前提（假設(shè)）出發(fā)，依據(jù)公認(rèn)推理規(guī)則，推導(dǎo)出一個(gè)結(jié)論來(lái)。

1）直接法

2）利用CP規(guī)則3、間接證實(shí)法（反證法）23/312023/9/16計(jì)算機(jī)學(xué)院24直接證實(shí)法例1-7．1

求證S∨R是前提{P∨Q，P→R，Q→S}有效結(jié)論。(結(jié)構(gòu)性二難推論)證：步驟公式依據(jù)（注釋）①P∨QP②～P→QT，①，E1，E2

③Q→SP④～P→ST,②,③,I9⑤～S→PT，④，E14，E23⑥P→RP⑦～S→RT，⑤，⑥，I9⑧S∨RT，⑦，E2，E1

故{P∨Q，P→R，Q→S}

S∨R24/312023/9/16計(jì)算機(jī)學(xué)院25利用CP規(guī)則例1-7．2

證實(shí)R→S能夠從前提

{P→（Q→S），～R∨P，Q}推出證：①RP（附加前提）②～R∨PP③PT，①，②，I8④P→（Q→S）P⑤Q→ST，③，④，I5⑥QP⑦ST，⑥，⑤，I5

⑧R→SCP，①，⑦25/312023/9/16計(jì)算機(jī)學(xué)院26依據(jù)蘊(yùn)涵關(guān)系性質(zhì)8，

A

BiffA∧～B是矛盾式

將結(jié)論否定加入到前提集合中組成一組新前提，然后證實(shí)這組新前提集合是不相容，即蘊(yùn)涵一個(gè)矛盾式。

即，若

A1,A2,…,An,～B

R∧～R則

A1,A2,…,An

B間接證實(shí)法（反證法）26/312023/9/16計(jì)算機(jī)學(xué)院27例1-7．3證實(shí)：{R→～Q，R∨S，S→～Q，P→Q}

～P

證：①～（～P）P（假設(shè)前提）②PT，①，E1③P→QP④QT,②,③,I5

⑤S→～QP⑥～ST，④，⑤，I23，E1，I5⑦R∨SP⑧RT，⑥，⑦，I7⑨R→～QP⑩～QT，⑧，⑨，I5

⑾Q∧～QF，④，⑩Ｅ19∴{R→～Q，R∨S，S→～Q，P→Q}

～P27/31例1-7．4把命題“假如小王不去，小張或小李就要去；假如小李去，小王就一定要去；另外，假如小林也去，小張就不愿去；所以，假如小王不去，小林也不會(huì)去”翻譯成命題邏輯形式并證實(shí)命題是真。解：

令