第五講命題邏輯

第五講命題邏輯第一頁(yè)，共六十頁(yè)，2022年，8月28日第一節(jié)命題公式與真值函項(xiàng)第二節(jié)命題公式之間的邏輯等值關(guān)系第三節(jié)基本的有效推理式第四節(jié)推理有效性的形式證明第五節(jié)無(wú)效推理的證明第二頁(yè)，共六十頁(yè)，2022年，8月28日第一節(jié)

命題公式與真值函項(xiàng)1.1命題公式1.2命題公式與真值函項(xiàng)第三頁(yè)，共六十頁(yè)，2022年，8月28日1.1命題公式初始符號(hào)命題變?cè)簆，q，r，…命題聯(lián)結(jié)詞：∧，∨，→，，輔助符號(hào)：（，）邏輯變?cè)壿嫵Ｔo助符號(hào)第四頁(yè)，共六十頁(yè)，2022年，8月28日第1類符號(hào)是邏輯變?cè)鼈兪浅橄蟮拿}代表，如果代表真命題，變?cè)≈禐檎?，如果代表假命題則取值為假。因此1類符號(hào)稱作以真值為定義域的變?cè)?。?類符號(hào)是邏輯常元，它們有確定的邏輯解釋因而能夠表達(dá)某種確定的真假聯(lián)系。第3類符號(hào)則是為避免歧義以構(gòu)造合式命題公式所需要的輔助符號(hào)。第五頁(yè)，共六十頁(yè)，2022年，8月28日形成規(guī)則1、所有命題變?cè)敲}公式；2、如果是命題公式，那么是命題公式3、如果、是命題公式，那么（），（∧）、（Φ∨Ψ）和（ΦΨ）也是命題公式；4、只有符合以上3條的才是命題公式。第六頁(yè)，共六十頁(yè)，2022年，8月28日

pq∧r，pq，p∧→qr從邏輯的角度看，命題公式是構(gòu)造出來(lái)的，具體命題只是命題公式的例示，即命題公式的一個(gè)特例。如下具體命題都是命題公式“（p∧q）→r”的例示：如果加溫到了一定限度且加壓到一定限度，那么空氣可以液化。如果考試合格并且體驗(yàn)合格，那么就可以上大學(xué)。第七頁(yè)，共六十頁(yè)，2022年，8月28日1.2命題公式與真值函項(xiàng)命題公式就相當(dāng)于一個(gè)函數(shù)式，公式的值由變?cè)闹滴ㄒ淮_定。命題公式是一個(gè)以真假為定義域，并且也以真假為值域的特殊函數(shù)。真假是命題的邏輯值，簡(jiǎn)稱真值。因此，命題公式被稱作真值函項(xiàng)。第八頁(yè)，共六十頁(yè)，2022年，8月28日1.2命題公式與真值函項(xiàng)我們可以看到，給定ｎ個(gè)命題變?cè)?，則有２n種真假取值，然后構(gòu)成2２n個(gè)真值函項(xiàng)。這些不同的真值函項(xiàng)分為三大類：①恒真式。不論其中的變?cè)∈裁礃拥闹担?xiàng)式的值恒為真。②恒假式。無(wú)論其中的變?cè)∈裁礃拥闹?，函?xiàng)式的值恒為假。③協(xié)調(diào)式。既不是恒真式也不是恒假式函項(xiàng)式。顯然，協(xié)調(diào)式在其變?cè)哪承┤≈到M合下為真，在另一些取值組合下又為假的。因此。協(xié)調(diào)式的真假由變?cè)恼婕贈(zèng)Q定。第九頁(yè)，共六十頁(yè)，2022年，8月28日第二節(jié)命題公式之間的邏輯等值關(guān)系2.1命題公式之間的邏輯等值2.2幾個(gè)重要的重言等值式2.3命題聯(lián)結(jié)詞的相互定義第十頁(yè)，共六十頁(yè)，2022年，8月28日2.1命題公式之間的邏輯等值邏輯等值的公式：表達(dá)同一真值函項(xiàng)的公式在任何情況下都具有相同的邏輯值，我們稱這些公式是邏輯等值的公式。真值表：判定兩個(gè)公式是否是邏輯等值的例1、判定命題公式“﹁p∨﹁q”與“﹁(p∧q)”是否邏輯等值。例2、判定命題公式“(p∧q)→r”與“p∨(q→r)”是否邏輯等值。第十一頁(yè)，共六十頁(yè)，2022年，8月28日2.1命題公式之間的邏輯等值如果兩個(gè)公式是等值的，那么以這兩個(gè)公式為子公式構(gòu)造一個(gè)等值式：（﹁p∨﹁q）（﹁(p∧q)）。這個(gè)等值式是恒真的，由此可推知，一個(gè)等值式是重言式，那么它的兩個(gè)子公式邏輯等值。如果一個(gè)等值式是重言式，那么我們就用符號(hào)“”代替等值聯(lián)結(jié)“”。第十二頁(yè)，共六十頁(yè)，2022年，8月28日2.2幾個(gè)重要的重言等值式1、交換律(p∧q)(q∧p)

(p∨q)(q∨

p)2、結(jié)合律((p∧q)∧r)(p

∧(q∧r))((p∨q)∨r)(p

∨(q∨r))3、德摩根律?(p∧q)?p∨?q；

?(p∨q)?p∧?q。第十三頁(yè)，共六十頁(yè)，2022年，8月28日4、分配律p∧(q∨r)(p∧q)∨(p∧r)

p∨(q∧r)(p∨q)→(p∨r)5、實(shí)質(zhì)蘊(yùn)涵（p→q）（p∨q）6、假言易位（p→q）（q→p)7、移出律(p∧q)→rp→(q→r)8、實(shí)質(zhì)等值(pq)(p→q)∧(q→p)9、雙否律p

p10、重言律pp∧ppp∨p第十四頁(yè)，共六十頁(yè)，2022年，8月28日2.3命題聯(lián)結(jié)詞的相互定義“，∨”、“，∧”、“，→”例、證明用“，∨”構(gòu)造的命題公式可以定義所有五種基本命題公式。第十五頁(yè)，共六十頁(yè)，2022年，8月28日第三節(jié)基本的有效推理式3.1推理的有效性3.2基本的有效推理式第十六頁(yè)，共六十頁(yè)，2022年，8月28日

3.1推理的有效性（1）“如果張珊是中國(guó)公民并且她有選舉權(quán)，那么張珊年滿18歲。張珊是中國(guó)公民，但是她還沒滿18歲。所以，張珊沒有選舉權(quán)?！保?）“如果張珊是中國(guó)公民并且她有選舉權(quán)，那么張珊年滿18歲。張珊是中國(guó)公民，但是她還沒滿18歲。張珊沒有選舉權(quán)?！钡谑唔?yè)，共六十頁(yè)，2022年，8月28日第三節(jié)基本的有效推理式3.1推理的有效性推理是一個(gè)包含特殊詞項(xiàng)的命題集合，根據(jù)這樣的詞項(xiàng)，我們可以區(qū)分出前提和結(jié)論。推理的有效性是由推理的形式?jīng)Q定的。它表現(xiàn)為作為前提的命題同作為結(jié)論的命題之間的一種邏輯關(guān)聯(lián)性，這種邏輯關(guān)聯(lián)取決于構(gòu)成推理的命題的形式結(jié)構(gòu)特征。第十八頁(yè)，共六十頁(yè)，2022年，8月28日如果前提真時(shí)結(jié)論必然是真的，我們就稱前提和結(jié)論之間有必然的邏輯聯(lián)系。這種聯(lián)系保證了推理決不會(huì)出現(xiàn)前提真而結(jié)論假的情況。因此，可以由前提的真來(lái)保證結(jié)論真，由前提可靠有效地推演出結(jié)論的可靠。前提和結(jié)論之間具有必然邏輯聯(lián)系的推理就是有效推理。如果前提和結(jié)論之間不具有必然的邏輯聯(lián)系，那么前提真時(shí)結(jié)論是否為真不能確定，即不能由前提的真有效地推導(dǎo)出結(jié)論真，這樣的推理就是無(wú)效推理。第十九頁(yè)，共六十頁(yè)，2022年，8月28日推理：設(shè)命題序列Γ=<p1,p2….pn,q>是一個(gè)推理形式，其中p1,p2….pn是前提，q是結(jié)論。

Γ是一個(gè)有效的推理式，當(dāng)且僅當(dāng)，如果p1,p2….pn真那么q一定為真。

Γ是無(wú)效推理式，如果至少有一個(gè)的代換示例使得p1,p2….pn真但q假。第二十頁(yè)，共六十頁(yè)，2022年，8月28日根據(jù)合取式的邏輯特征：p∧q

∴p合取消去簡(jiǎn)記為∧-合取引入簡(jiǎn)記為∧+Pq∴p∧q3.2基本的有效推理式小張喜愛音樂，小張喜愛體育，所以，小張不但喜愛音樂，也喜愛體育。小張既有優(yōu)點(diǎn)，也有缺點(diǎn)，所以，小張是有優(yōu)點(diǎn)的。第二十一頁(yè)，共六十頁(yè)，2022年，8月28日根據(jù)析取式的邏輯特征：選言三段論簡(jiǎn)記∨-pq?p

∴q附加規(guī)則簡(jiǎn)記∨+

p∴pq3.2基本的有效推理式或者李某是嫌疑犯，或者王某是嫌疑犯(或者二者都是)；李某不是嫌疑犯；所以，王某是嫌疑犯。發(fā)燒可由肺炎引起；所以，發(fā)燒或者可由肺炎引起或者可由感冒引起。第二十二頁(yè)，共六十頁(yè)，2022年，8月28日根據(jù)蘊(yùn)涵式的邏輯特征：分離規(guī)則簡(jiǎn)記MPp→q

p

∴q逆分離規(guī)則簡(jiǎn)記MTp→q

?

q

∴?

p二難推理(CD)(p→q)∧(r→s)

p∨r

∴q∨s假言三段論簡(jiǎn)記HSp→q

q→r

∴p→r3.2基本的有效推理式(p→q)∧(r→s)

q∨s

∴p∨r破壞式二難推理(DD)第二十三頁(yè)，共六十頁(yè)，2022年，8月28日第四節(jié)推理有效性的形式證明4.1推理有效性與命題演算4.2有效推理的形式證明4.3等值替換規(guī)則4.4條件證明規(guī)則C.P4.5間接證明規(guī)則RAA4.6證明重言式第二十四頁(yè)，共六十頁(yè)，2022年，8月28日4.1推理有效性與命題演算對(duì)于簡(jiǎn)單的復(fù)合命題推理，我們可以直接根據(jù)這些基本有效式來(lái)判定推理是否有效。但是對(duì)于復(fù)雜的推理這樣就不夠了。例1如果商品短缺日益嚴(yán)重，那么物價(jià)會(huì)上漲。如果存在生產(chǎn)過剩，那么物價(jià)不會(huì)上漲。如果存在通貨膨脹威脅，那么財(cái)政控制將繼續(xù)。如果政府改組，那么財(cái)政控制將取消?；蛘叽嬖谏a(chǎn)過剩，或者政府改組。因此，商品短缺不會(huì)日益嚴(yán)重，或者不再存在通貨膨脹威脅。第二十五頁(yè)，共六十頁(yè)，2022年，8月28日4.1推理有效性與命題演算命題演算系統(tǒng)建立命題演算系統(tǒng)有兩種方法：一是公理化方法，一是自然演繹方法。公理化的命題演算系統(tǒng)是在形式語(yǔ)言基礎(chǔ)上增添公理和變形規(guī)則建構(gòu)起來(lái)的。自然演繹系統(tǒng)，沒有公理，只有一系列推理規(guī)則。它是引入特定前提為假設(shè)，根據(jù)推理規(guī)則推演出結(jié)論而建構(gòu)起來(lái)的演算系統(tǒng)。第二十六頁(yè)，共六十頁(yè)，2022年，8月28日4.2有效推理的形式證明在命題演算系統(tǒng)中對(duì)推理有效性的證明稱作形式證明?，F(xiàn)在給出自然演繹系統(tǒng)中形式證明的定義：形式證明的定義一個(gè)形式證明是一個(gè)命題公式序列A1,A2,An。其中任一的Ai（1in）或者是前提，或者是由前面的公式根據(jù)推理規(guī)則得到的。序列的最后一個(gè)公式An恰好是結(jié)論。第二十七頁(yè)，共六十頁(yè)，2022年，8月28日4.2有效推理的形式證明自然演繹系統(tǒng)形式證明是建立在推理規(guī)則基礎(chǔ)之上的。這些規(guī)則大約可分為四部分：一是基本推導(dǎo)規(guī)則，二是等值替換規(guī)則，三是條件證明規(guī)則，四是間接證明規(guī)則。第二十八頁(yè)，共六十頁(yè)，2022年，8月28日根據(jù)合取式的邏輯特征：p∧q∴p分解式簡(jiǎn)記為∧-組合式簡(jiǎn)記為∧+Pq∴p∧q根據(jù)析取式的邏輯特征：選言三段論簡(jiǎn)記∨-P∨q?p∴q附加式簡(jiǎn)記∨+P∴P∨q根據(jù)蘊(yùn)涵式的邏輯特征：分離式簡(jiǎn)記MPp→q

p∴q逆分離式簡(jiǎn)記MTp→q

?

q∴?

p二難推理CD(p→q)∧(r→s)

p∨r∴q∨s假言三段論簡(jiǎn)記HSp→q

q→r∴p→r一、基本推導(dǎo)規(guī)則：(p→q)∧(r→s)

q∨s∴p∨r破壞式二難推理DD第二十九頁(yè)，共六十頁(yè)，2022年，8月28日例1如果商品短缺日益嚴(yán)重，那么物價(jià)會(huì)上漲。如果存在生產(chǎn)過剩，那么物價(jià)不會(huì)上漲。如果存在通貨膨脹威脅，那么財(cái)政控制將繼續(xù)。如果政府改組，那么財(cái)政控制將取消?；蛘叽嬖谏a(chǎn)過剩，或者政府改組。因此，商品短缺不會(huì)日益嚴(yán)重，或者不再存在通貨膨脹威脅。解：設(shè)“商品短缺日益嚴(yán)重”為A，“物價(jià)會(huì)上漲”為B，“存在生產(chǎn)過?！睘镃，“存在通貨膨脹威脅”為D，“財(cái)政控制將繼續(xù)”為E，“政府改組”為F。首先將該推理形式化，在此基礎(chǔ)上建立該推理有效性的形式證明。第三十頁(yè)，共六十頁(yè)，2022年，8月28日①A→BP②C→BP③D→EP④F→EP⑤C∨FP/∴A∨D⑥（C→B）∧（F→E）②④∧+⑦B∨E⑥⑤CD⑧（A→B）∧（D→E）①③∧+⑨A∨D⑦⑧DD第三十一頁(yè)，共六十頁(yè)，2022年，8月28日我們還看到，整個(gè)形式證明的內(nèi)容可分為三部分：第一部分是序號(hào)，它既標(biāo)示了命題公式出現(xiàn)的順序，這些序號(hào)同時(shí)又是在它后面出現(xiàn)的那個(gè)公式的代表。第二部分是若干個(gè)命題公式，它們或者是前提，或者是由前面的公式根據(jù)推理規(guī)則得到的。第三部分則是一些根據(jù)，它說(shuō)明每個(gè)命題公式在為什么在形式證明中出現(xiàn)。形式證明的這三個(gè)構(gòu)成部分缺一不可。第三十二頁(yè)，共六十頁(yè)，2022年，8月28日4.3等值替換規(guī)則例:(A∨B)→C\A→C運(yùn)用八條基本規(guī)則不能建立有關(guān)這個(gè)推理的形式證明。等值替換規(guī)則實(shí)際上就是引入一些邏輯等值式作為推理規(guī)則，并規(guī)定在形式證明中，等值式兩邊的公式可以相互替換使用。第三十三頁(yè)，共六十頁(yè)，2022年，8月28日二、置換規(guī)則交換律(Com)：p∧qq∧p

p∨q

q∨p結(jié)合律(Ass)：p∧(q∧r)

(p∧q)∧rp∨(q∨r)(p∨q)∨r德·摩根律(Dem)：

?(p∧q)(?p∨?q)?(p∨q)(?p∧?q)分配律(Dist):p∧(q∨r)(p∧q)∨(p∧r)；p∨(q∧r)(p∨q)∧(p∨r)實(shí)質(zhì)蘊(yùn)涵律(Impl)：（p→q）

（p∨q）假言易位律（Tran):（p→q）

（q→p）移出律(Exp)：[p∧q]→r

p→(q→r)實(shí)質(zhì)等值(Eq)：pq

(p→q)∧(q→p)雙否律(DN)：p??p重言律(Taut)：p(p∧p)p(p∨p)第三十四頁(yè)，共六十頁(yè)，2022年，8月28日(A∨B)→C\A→C證：①(A∨B)→CP\A→C②

(A∨B)∨C①Impl③(A∧

B)∨C②DeM④(A∨C)∧(B∨C)③Dist⑤A∨C④∧-⑥A→C⑤Impl第三十五頁(yè)，共六十頁(yè)，2022年，8月28日作業(yè)一、運(yùn)用真值表方法,判定下列命題是不是等值命題。l．如果這匹馬兒不吃飽草,那么這匹馬兒不能跑。2．或者這匹馬兒吃飽草,或者這匹馬兒不能跑。3．既要這匹馬兒跑,又要這匹馬兒不吃飽草,這是辦不到的。1.p→q；2.p∨q；3.(q∧p)。第三十六頁(yè)，共六十頁(yè)，2022年，8月28日4.4證明的方法一推理有效性的形式證明(一)條件證明規(guī)則有了基本推導(dǎo)規(guī)則和等值替換規(guī)則還不足以為所有有效的復(fù)雜推理建立形式證明，例如下列推理A→（B→C）\∴（A→B）→（A→C）

這個(gè)推理是有效的，但要證明其有效性還需要引入新的推理規(guī)則。因此我們引入條件證明規(guī)則C.P。引入這條規(guī)則還有一個(gè)作用，即可以簡(jiǎn)化證明過程。第三十七頁(yè)，共六十頁(yè)，2022年，8月28日4.4證明的方法條件證明規(guī)則的根據(jù)：有效推理的邏輯特征是：前提真時(shí)結(jié)論必真，不存在有使其前提真而結(jié)論假的例示。如果我們以有效推理的前提的合取為前件，結(jié)論為后件構(gòu)造一個(gè)蘊(yùn)涵式，那么這個(gè)蘊(yùn)涵式就不可能前件真而后件假。相反，如果推理式不是有效的，那么存在這樣的例示使得該推理式前提真而結(jié)論假。因此，與這個(gè)推理式相應(yīng)的蘊(yùn)涵式就不可能是重言式。第三十八頁(yè)，共六十頁(yè)，2022年，8月28日4.4證明的方法

由此我們看到，如果用一個(gè)推理式前提的合取為前件，結(jié)論為后件構(gòu)造一個(gè)蘊(yùn)涵式，那么這個(gè)推理式與該蘊(yùn)涵式之間存在這樣一種等價(jià)關(guān)系：如果推理式是有效的，那么蘊(yùn)涵式是重言式；如果推理式不是有效的，那么蘊(yùn)涵式就不是重言式。

等值替換規(guī)則中的移出律(Exp)指出，如下兩個(gè)蘊(yùn)涵式是邏輯等值的：((p∧q)→r)(p→(q→r))兩個(gè)蘊(yùn)涵式分別對(duì)應(yīng)于如下推理式：第三十九頁(yè)，共六十頁(yè)，2022年，8月28日4.4證明的方法

(p∧q)→r對(duì)應(yīng)于

p→(q→r)對(duì)應(yīng)于

pp??????q∴q→r∴r這兩個(gè)推理式的區(qū)別在于：命題公式“q”在左邊的推理式中是前提，而在右邊的推理式中是結(jié)論的構(gòu)成部分。就是說(shuō)，右邊的推理式比左邊的少了一個(gè)前提“q”，并且它們有不同的結(jié)論：左邊推理式的結(jié)論是“r”，右邊推理式的則是“q→r”，“q”從前提中消去而變成了結(jié)論的前件。第四十頁(yè)，共六十頁(yè)，2022年，8月28日4.4證明的方法由于兩個(gè)蘊(yùn)涵式是邏輯等值的，即如果一個(gè)是重言式，另一個(gè)也必是；一個(gè)不是重言式，另一個(gè)也必不是。因此這兩個(gè)推理式是等價(jià)的：如果一個(gè)推理式有效，另一個(gè)必有效；一個(gè)是無(wú)效的，另一個(gè)也必?zé)o效。條件證明規(guī)則C.Pp??q∴p→q第四十一頁(yè)，共六十頁(yè)，2022年，8月28日4.4證明的方法例1A→（B→C）\∴（A→B）→（A→C）證明：①A→（B→C）P②（A∧B）→C①Exp③（B∧A）→C②Com④B→（A→C）③Exp

⑤A→B⑥A→（A→C）④⑤HS⑦（A∧A）→C⑥Exp⑧A→C⑦Taut⑨（A→B）→（A→C）⑤-⑧C?P第四十二頁(yè)，共六十頁(yè)，2022年，8月28日4.4證明的方法由上例中我們看到，第⑤步是將結(jié)論的前提作為一個(gè)附加前提引入了形式證明中，到第⑧步推出了結(jié)論的后件，于是就運(yùn)用C?P規(guī)則消去⑤這個(gè)附加前提，即以⑤為前件⑧為后件而得到⑨，⑨恰好是結(jié)論。我們?cè)谝敫郊忧疤幄莸耐瑫r(shí)就用線段標(biāo)明了這個(gè)附加前提的轄域。在轄域中出現(xiàn)的⑥、⑦和⑧這幾個(gè)公式依賴于①和⑤這兩個(gè)前提。而公式⑨出現(xiàn)在附加前提⑤的轄域之外，因?yàn)镃?P規(guī)則的運(yùn)用已經(jīng)將⑤從前提中消去，⑨就只依賴于前提①了。第四十三頁(yè)，共六十頁(yè)，2022年，8月28日4.4證明的方法因此，標(biāo)明轄域在條件證明規(guī)則C?P的運(yùn)用中有很重要的意義。我們規(guī)定，凡引入附加前提必須標(biāo)明該前提的轄域。而轄域沒有封閉，證明就不能結(jié)束，因?yàn)檫@時(shí)推演出的公式還依賴于附加前提，即依賴于給定前提之外的東西。如果轄域已經(jīng)封閉，那么在轄域中出現(xiàn)的公式不能再作為推演的根據(jù)，因?yàn)槲覀儽仨毐ＷC推出的結(jié)論只依賴于給定的前提，不需要除前提外的其它東西。錯(cuò)誤地運(yùn)用條件證明規(guī)則舉例：第四十四頁(yè)，共六十頁(yè)，2022年，8月28日4.4證明的方法①V∨UP②U∨WP③（V∧X）→WP\∴V→X④V⑤U①④∨-

⑥W②⑤∨-⑦（V∧X）③⑥MT⑧V∨X⑦DeM⑨V→X⑧Impl注意：這個(gè)形式證明的錯(cuò)誤在于附加前提④的轄域沒有封閉。雖然公式⑨與結(jié)論有完全相同的形式，但它是出現(xiàn)在附加前提④的轄域內(nèi)，除給定前提①②③外，它還依賴于④，而④是原前提中沒有的。第四十五頁(yè)，共六十頁(yè)，2022年，8月28日4.4證明的方法例2A→（B∧D）B→（（C→（C∨E））→F）/∴A→F證明：①A→（B∧D）P②B→（（C→（C∨E））→F）P③A④B∧D①③MP⑤B④∧-⑥（C→（C∨E））→F②⑤MP⑦C⑧C∨E⑦∨+⑨C→（C∨E）⑦-⑧C?P⑩F⑥⑨MP⑾A→F③-⑩C?P第四十六頁(yè)，共六十頁(yè)，2022年，8月28日4.4證明的方法(二)間接證明規(guī)則RAA

間接證明又叫做歸謬證明或反證法。這是一種在數(shù)學(xué)中經(jīng)常用到的證明方法。當(dāng)我們要證明某一定理時(shí)，先引入該定理的否定作為假設(shè)，然后由這一假設(shè)推導(dǎo)出矛盾。由于矛盾是不可能的，假設(shè)一定錯(cuò)誤，即該定理的否定不成立。由此就間接地證明了該定理成立。間接證明規(guī)則就是根據(jù)這一思路得到的。當(dāng)我們?yōu)橐挥行评斫⑿问阶C明時(shí)，不是直接去證明由前提推演出結(jié)論，而是將結(jié)論的否定作為一個(gè)補(bǔ)充前提引入形式證明。然后由擴(kuò)充的前提集合推演出一個(gè)矛盾：即推演出一個(gè)形式為“p∧p”的命題公式。由這個(gè)矛盾我們實(shí)際上推演出對(duì)這個(gè)補(bǔ)充前提的否定，即對(duì)結(jié)論的否定的否定，再根據(jù)雙否律DN，就相當(dāng)于推演出結(jié)論。第四十七頁(yè)，共六十頁(yè)，2022年，8月28日4.4證明的方法例3

A→（B∧C）（B∨D）→ED∨A/∴E證明：⑴A→（B∧C）P⑵（B∨D）→EP⑶D∨AP/∴E

⑷ERAA⑸（B∨D）⑵⑷MT⑹B∧D⑸DeM⑺D⑹COM，∧-⑻A⑶⑺∨-⑼B∧C⑴⑻MP

⑽B⑼∧-⑾B⑹∧-

⑿B∧B⑽⑾∧+第四十八頁(yè)，共六十頁(yè)，2022年，8月28日4.4證明的方法在這個(gè)形式證明中，公式⑷是結(jié)論“E”的否定，它是作為補(bǔ)充前提引入證明的。證明的最后一步是公式⑿，它是一個(gè)矛盾式，恒為假。如果推理是有效的，前提真時(shí)結(jié)論必真?，F(xiàn)在由于引入補(bǔ)充前提⑷而推出了假結(jié)論，因此公式⑷這個(gè)補(bǔ)充前提一定不成立。⑷不成立即結(jié)論的否定不成立，即“E”，根據(jù)雙否律推出“E”?！癊”即結(jié)論，因此結(jié)論成立。由例3可見，運(yùn)用間接證明規(guī)則就是將結(jié)論的否定作為補(bǔ)充前提引入證明，最后推出矛盾。由此間接地證明結(jié)論成立，推理有效。第四十九頁(yè)，共六十頁(yè)，2022年，8月28日4.4證明的方法(三)證明重言式

有一種命題的真是無(wú)條件的，不依賴于其它命題。這樣的命題就是重言式。形式證明同樣適用于證明重言式?？梢宰C明重言式是不需要任何前提就可以推演出的命題。雖然證明重言式不需要任何前提，但建立形式證明需要有出發(fā)點(diǎn)。這意味著我們只能用條件證明或者間接證明的方法來(lái)證明重言式，因?yàn)橹挥羞@兩種方法可以引入假設(shè)前提。我們以假設(shè)前提為出發(fā)點(diǎn)就能建立重言式的形式證明。第五十頁(yè)，共六十頁(yè)，2022年，8月28日4.4證明的方法用條件證明方法證明重言式就是先引入假設(shè)前提，然后逐步消去所有假設(shè)前提而推演出一個(gè)公式，這個(gè)命題公式就是不依賴于任何前提的重言式。例4證明A→（B→A）是重言式。證明：①A

②A∨B①∨+③B∨A②Com

④B→A③Impl⑤A→(B→A)①-④C?P第五十一頁(yè)，共六十頁(yè)，2022年，8月28日4.4證明的方法例5證明（（p→q）∧p）→q是重言式證明：①（p→q）∧p②p→q①∧-③p①Com,∧-

④q②③MP⑤（（p→q）∧p）→q①-④C?P用間接證明方法證明重言式則是將所證公式的否定引入作為假設(shè)前提，然后推出矛盾。否定一個(gè)公式將導(dǎo)致邏輯矛盾，那么這個(gè)公式一定是重言式。

第五十二頁(yè)，共六十頁(yè)，2022年，8月28日4.4證明的方法例6證明A→（A∨B）是重言式證明：①（A→（A∨B））②（A∨（A∨B））①Impl③A∧（A∨B）②DeM④A∧（A∧B）③DeM⑤（A∧A）∧B④Ass⑥A∧A⑤∧-第五十三頁(yè)，共六十頁(yè)，2022年，8月28日4.4證明的方法二無(wú)效推理的證明(一)用真值表證明推理的無(wú)效性一個(gè)推理是有效的，我們可以為其建立一個(gè)形式證明。形式證明運(yùn)用推理規(guī)則說(shuō)明，結(jié)論是從前提推演出來(lái)的，因此前提真時(shí)結(jié)論不可能假，推理當(dāng)然就是有效的。如果推理是無(wú)效的，那么運(yùn)用推理規(guī)則不可能從前提推演出結(jié)論。所謂不可能是指：無(wú)論怎樣推演都推不出結(jié)論形式的命題公式。形式證明并沒有規(guī)定推演到多少步就必須中止。因此，對(duì)于無(wú)效推理我們面臨的是一個(gè)無(wú)法窮盡的推演過程。這意味著形式證明方法不能證明推理是無(wú)效的。第五十四頁(yè)，共六十頁(yè)，2022年，8月28日4.4證明的方法我們的命題邏輯系統(tǒng)不僅要能證明有效推理，而且還應(yīng)該證明推理的無(wú)效性。因此，必須給出證明無(wú)效推理的方法。真值表是判定推理是否有效的可靠方法。一個(gè)推理是有效的，那么前提真時(shí)結(jié)論必真。在真值表上表現(xiàn)為無(wú)論變?cè)毁x予什么樣的值，作為前提的命題公式真時(shí)，作為結(jié)論的命題公式一定是真的。如果一個(gè)推理是無(wú)效的，其前提真時(shí)結(jié)論可真可假。因此只要在真值表上找到一組變?cè)馁x值使得前提真而結(jié)論假，那么推理就是無(wú)效的。第五十五頁(yè)，共六十頁(yè)，2022年，8月28日4.4證明的方法例7用真值表判定下列推理是否有效。C→（A∧B），A∨C/∴B→C證明：給出相應(yīng)的真值表：ABCA∧BC→（A∧B）A∨CB→CTTTTTTT

*TTFTTTFTFTFFTTTFFFT