自然演繹邏輯導(dǎo)論

1、自然演繹邏輯導(dǎo)論第八章命題邏輯第八章命題邏輯的元理論的元理論第一節(jié)對象語言與元語言、常項變項與變項變項 l8 11 對象語言與元語言對象語言與元語言l對象語言是被討論的語言，元語言是用于討論對象語言的語言。 l對象語言不含元語言的成分，但元語言可以包含對象語言的成分。 l對象語言的某一個成分通過加引號的方法成為元語言成分，這個元語言成分是相應(yīng)的對象語言成分的專名專名。除此之外，對象語言的一類一類成分可以由元語言的一個變項來表示，這個變項被稱為元變項元變項（metavariable），它是相應(yīng)的那一類對象語言成分的通名通名。元變項的值域是對象語言中與之相對應(yīng)的那類成分，但元變項本身不屬對象語言，

2、而屬于元語言。 8 12 常項變項與變項變項l被放在引號中的符號是這個符號在元語言中的專名即元專名元專名，亦即元常項元常項。與之不同，元變元變項項不是表示對象語言的某一個一個符號，而是表示對象語言的某一類一類符號。相應(yīng)地，元變項不是被放在引號中，而是用與對象語言某類符號相應(yīng)的黑體字（或用其他什么方式）來體現(xiàn)。元變項也就是元通名元通名。 第二節(jié)SL的語法l8 21 SL的基本語法的基本語法l關(guān)于一個邏輯系統(tǒng)的整體性質(zhì)的理論叫做這個邏輯系統(tǒng)的元理論。l語法只涉及符號語言的純粹形式，而不涉及它的內(nèi)容；語義則在一定程度上涉及符號語言的內(nèi)容。 l一、初始符號一、初始符號：l命題常項：從A到Z的大寫字母（

3、帶或不帶正整數(shù)下標）。l聯(lián)結(jié)詞：，。l輔助符號：（，）。l二、形成規(guī)則二、形成規(guī)則：l1、每一個命題常項是一個命題。l2、如果P是一個命題，那么P是一個命題。l3、如果P和Q是命題，那么（PQ）是一個命題。l4、如果P和Q是命題，那么（PQ）是一個命題。l5、如果P和Q是命題，那么（PQ）是一個命題。l6、如果P和Q是命題，那么（PQ）是一個命題。l7、只有通過應(yīng)用或重復(fù)應(yīng)用以上項目的一條或多條而形成的符號式是命題。（習慣上，由此構(gòu)成的公式的最外邊一對括號可以省去。）l三、推演規(guī)則三、推演規(guī)則（變形規(guī)則）：l包括八條整推規(guī)則、十條置換規(guī)則、條件證明規(guī)則和間接證明規(guī)則。 8 22 一些語法元定理

4、及其證明l元定理元定理8.2.1：在SC中，如果 P，那么對于的每一個母集而言， P。 l元定理元定理8.2.2：如果SL的一個命題集是SC不一致的，那么，SL的任一命題Q在SC中是從可推演的。 l元定理元定理8.2.3：對于任何命題集和任何命題P，在SC中 P，當且僅當，P是SC不一致的。 l元定理元定理8:2.4: 如果命題集是SC不一致的，那么，的每一個母集是SC不一致的。 l元定理元定理8.2.5：如果命題集是SC不一致的，那么，至少有一的有限子集是SC不一致的。 l元定理元定理8:2.6: 如果至少有一的有限子集是SC不一致的，那么，是SC不一致的。l元定理元定理8.2.7： 一個命

5、題集是SC一致的，當且僅當，的每一有限子集是SC一致的。 第三節(jié)SL的語義l8 31 SL的基本語義l五個真值函項聯(lián)結(jié)詞的特征真值表就是SL的最基本的語義。 l定義：定義：SL的一個命題集是真值函項地一致的，當且僅當，至少有一真值指派使得的每一成員是真的。SL的一個命題集是真值函項地不一致的，當且僅當，不是真值函項地一致的。 l定義：定義：SL的一個命題集重言蘊涵一個命題P，當且僅當，沒有一個真值指派使得，的每一成員為真而P為假。 l重言有效也叫做“真值函項地有效”。 8 32 一些語義元定理及其證明l元定理元定理8.3.1：SL的一個命題P是矛盾式，當且僅當，P是真值函項地不一致的。l元定理

6、元定理8.3.2：SL的一個命題P是重言式，當且僅當，P是真值函項地不一致的。 l元定理元定理8.3.3：SL的一個命題P是偶然式，當且僅當，P和P都是真值函項地一致的。 l元定理元定理8.3.4：SL的命題P和Q是重言等值的，當且僅當，(PQ)是真值函項地不一致的。 l元定理元定理8.3.5：對于SL的一個命題集和一個命題P，如果 P，那么P 是真值函項地不一致的。 l元定理元定理8.3.6：對于SL的一個命題集和一個命題P，如果P 是真值函項地不一致的，那么 P。 l元定理元定理8.3.7：SL的一個命題P是重言式，當且僅當， P。 第四節(jié)數(shù)學(xué)歸納法l8 41 什么是數(shù)學(xué)歸納法l數(shù)學(xué)歸納法

7、的基本原理是：為證明某一定理對于某一領(lǐng)域的所有對象都成立，把該類對象以某種方式進行排序，然后分兩步進行證明：一、證明定理對該序列的第一項成立；二、證明如果定理對第K項成立，那么它對K1項也成立。l前者證明的是奠基命題奠基命題（basis clause），即“定理對該序列的第一項成立”；后者證明的是歸納步驟歸納步驟（inductive step），歸納步驟的前件即“定理對第K項成立”叫做歸納假設(shè)歸納假設(shè)（inductive hypothesis）。這兩個步驟一旦完成，該定理便被證明對該領(lǐng)域的所有對象成立。 8 42 數(shù)學(xué)歸納法的例示數(shù)學(xué)歸納法的例示1l求證元命題：SL的每一命題的左括號和右括號的

8、數(shù)目是相等的。l奠基命題奠基命題：lSL的每一個只含聯(lián)結(jié)詞的0個出現(xiàn)的命題滿足元命題。l歸納步驟歸納步驟：l如果SL中含有聯(lián)結(jié)詞的K或少于K個出現(xiàn)的每一命題P滿足元命題，那么SL中含有聯(lián)結(jié)詞的K1個出現(xiàn)的每一命題P也滿足元命題。（K是一個變項，其變域為非負整數(shù)，即0加上正整數(shù)。）l證明證明奠基命題：SL的每一個只含聯(lián)結(jié)詞的0個出現(xiàn)的命題只有命題常項，而命題常項的左括號和右括號的數(shù)目都為0，故滿足元命題。 l證明證明歸納步驟：既然K是非負整數(shù)，K1是正整數(shù)。SL中含有聯(lián)結(jié)詞的K1個出現(xiàn)的命題P至少含有聯(lián)結(jié)詞的一次出現(xiàn)，因而是一復(fù)合命題?，F(xiàn)將其分為兩種情況：l情況1：P具有形式Q。既然P即Q含有聯(lián)

9、結(jié)詞的K1個出現(xiàn)，那么Q含有聯(lián)結(jié)詞的K個出現(xiàn)。根據(jù)歸納假設(shè)，Q滿足元命題。Q對于Q既未增加也未減少任何括號，因此，Q也滿足元命題。l情況2：P具有如下形式之一：（QR）、（QR）、（QR）和（QR）。既然P含有聯(lián)結(jié)詞的K1個出現(xiàn)，那么Q和R分別含有聯(lián)結(jié)詞的K或少于K個出現(xiàn)。根據(jù)歸納假設(shè)，Q和R滿足元命題。P只是在公式的最外邊同時加上一個左括號和一個右括號，這使得，P的左括號和右括號的數(shù)目分別為：Q的左括號數(shù)目R的左括號數(shù)目1，Q的右括號數(shù)目R的右括號數(shù)目1，故P滿足元定理。l證畢。 8 43 數(shù)學(xué)歸納法的例示2l求證：SL的每一與或非命題P與其對偶P之間具有相反的真值（P真當且僅當P假）。 第

10、五節(jié)聯(lián)結(jié)詞的真值函項完全性l8 51 什么是真值函項完全性什么是真值函項完全性l對于每一個真值函項，對于每一個真值函項，SL中是否至少有一個中是否至少有一個命題可以表達它？命題可以表達它？這個問題就是SL的聯(lián)結(jié)詞是否具有真值函項完全性的問題，亦即形式語言SL對于真值函項是否具有表達的完全性表達的完全性的問題。 lSL的聯(lián)結(jié)詞具有真值函項完全性。 8 52 對SL的真值函項完全性的證明l元定理元定理8.5.1對于每一個包含有限多個自變項的真值函項，都有一個SL命題可以表達它，并且該命題只含有聯(lián)結(jié)詞“”“”“”。 第六節(jié)SC的可靠性l8 61 什么是什么是SC的可靠性的可靠性l對于SL的一個命題P

11、和一個命題集，如果在SC中可以從推演出P，那么重言蘊涵P。這就是說，從到P的推演是(真值函項地)有效的；亦即，當?shù)拿恳怀蓡T為真時P不可能為假。一個具有這種性質(zhì)的自然演繹系統(tǒng)，我們說它作為命題邏輯是可靠的可靠的。 l如果SL的一個命題集重言蘊涵一個命題P，那么在SC 中P可由推演出來。這也就是說，SL中的所有(真值函項地)有效的推論都可成為SC中的一個推演。一個具有這后一性質(zhì)的自然演繹系統(tǒng)，我們說它作為命題邏輯是完全的完全的。 l可靠性（soundness）和完全性（completeness）是自然演繹系統(tǒng)的兩個重要性質(zhì)。 8 62 一些元定理及其證明l元定理元定理8.6.1：在SC中，如果 P

12、, 那么 P。 l元定理元定理8.6.2: 如果 P，那么對于的每一個母集而言， P。 l元定理元定理8.6.3：如果Q R，那么 QR。 l元定理元定理8.6.4：如果 QR，那么Q R。 l元定理元定理8.6.5：如果 Q并且 Q，那么是真值函項地不一致的。 l元定理元定理8.6.6：如果Q 是真值函項地不一致的，那么 Q。 l元定理元定理8.6.7：如果Q和Q1是重言等值的，那么P和P(Q1/Q)也是重言等值的。 8 63 對SC的可靠性的證明l證明：出現(xiàn)在出現(xiàn)在SC的一個推演中的每一個命題的一個推演中的每一個命題都被它所隸屬的假設(shè)集重言蘊涵。都被它所隸屬的假設(shè)集重言蘊涵。 l對于任一參

13、與命題P所直接隸屬的假設(shè)域內(nèi)的推演的命題Q而言，Q所隸屬的命題集是P所隸屬的命題集的一個子集。 l元定理元定理8.6.8： SC的每一定理都是一個重言式。 第七節(jié)SC的完全性 l8 71 不一致性引理和最大一致性集合l元定理元定理8.7.1：如果 P，那么，在SC中 Pl元定理元定理8.7.2：對于SL的一個命題集和一個命題P， P，當且僅當，P 是真值函項地不一致的。 l元定理元定理8.2.3：對于任一命題集和任一命題P，在SC中 P，當且僅當，P 是SC不一致的。 l元定理元定理8.7.3（不一致性引理）：如果SL的一個命題集是真值函項地不一致的，那么也是SC不一致的。 l元定理元定理8.7.4（最大一致性引理）：如果是